On the value of coordination in network design

ABSTRACT

We study network design games where n self-interested agents have to form a network by purchasing links from a given set of edges. We consider Shapley cost sharing mechanisms that split the cost of an edge in a fair manner among the agents using the edge. It is well known that the price of anarchy of these games is as high as n. Therefore, recent research has focused on evaluating the price of stability, i.e. the cost of the best Nash equilibrium relative to the social optimum.

In this paper we investigate to which extent coordination among agents can improve the quality of solutions. We resort to the concept of strong Nash equilibria, which were introduced by Aumann and are resilient to deviations by coalitions of agents. We analyze the price of anarchy of strong Nash equilibria and develop lower and upper bounds for unweighted and weighted games in both directed and undirected graphs. These bounds are tight or nearly tight for many scenarios. It shows that using coordination, the price of anarchy drops from linear to logarithmic bounds.

We complement these results by also proving the first super-constant lower bound on the price of stability of standard equilibria (without coordination) in undirected graphs. More specifically, we show a lower bound of Ω(log W/ log log W) for weighted games, where W is the total weight of all the agents. This almost matches the known upper bound of O(log W). Our results imply that, for most settings, the worst-case performance ratios of strong coordinated equilibria are essentially always as good as the performance ratios of the best equilibria achievable without coordination. These settings include unweighted games in directed graphs as well as weighted games in both directed and undirected graphs.

REFERENCES

• 1: Nir Andelman , Michal Feldman , Yishay Mansour, Strong price of anarchy, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.189-198, January 07-09, 2007, New Orleans, Louisiana
• 2: Elliot Anshelevich , Anirban Dasgupta , Jon Kleinberg , Eva Tardos , Tom Wexler , Tim Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.295-304, October 17-19, 2004 [doi>10.1109/FOCS.2004.68]
• 3: Elliot Anshelevich , Anirban Dasgupta , Eva Tardos , Tom Wexler, Near-optimal network design with selfish agents, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780617]
• 4: R.J Aumann. Acceptable points in general cooperative n-person games. In A. W. Tucker and R. D. Luce (eds.), Contributions to the Theory of Games, Vol. IV, Annals of Mathematics Studies, 40:287--324, 1959.
• 5: V. Bala and S. Goyal. A non-cooperative model of network formation. Econometrica, 68:1181--1229, 2000.
• 6: Chandra Chekuri , Julia Chuzhoy , Liane Lewin-Eytan , Joseph (Seffi) Naor , Ariel Orda, Non-cooperative multicast and facility location games, Proceedings of the 7th ACM conference on Electronic commerce, p.72-81, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134716]
• 7: Ho-Lin Chen , Tim Roughgarden, Network design with weighted players, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148114]
• 8: Jacomo Corbo , David Parkes, The price of selfish behavior in bilateral network formation, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073833]
• 9: Nikhil R. Devanur , Milena Mihail , Vijay V. Vazirani, Strategyproof cost-sharing mechanisms for set cover and facility location games, Decision Support Systems, v.39 n.1, p.11-22, March 2005 [doi>10.1016/j.dss.2004.08.004]
• 10: Amir Epstein , Michal Feldman , Yishay Mansour, Strong equilibrium in cost sharing connection games, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250924]
• 11: Alex Fabrikant , Ankur Luthra , Elitza Maneva , Christos H. Papadimitriou , Scott Shenker, On a network creation game, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.347-351, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872088]
• 12: Joan Feigenbaum , Christos H. Papadimitriou , Scott Shenker, Sharing the cost of multicast transmissions, Journal of Computer and System Sciences, v.63 n.1, p.21-41, August 2001 [doi>10.1006/jcss.2001.1754]
• 13: A. Fiat, H. Kaplan, M. Levy, S. Olonetsky and R. Shabo. On the price of stability for designing undirected networks with fair cost allocations. Proc. 33rd International Colloquium on Automata, Languages and Programming (ICALP), Springer LNCS 4051, 608--618, 2006.
• 14: H. Haller and S. Sarangi. Nash networks with heterogeneous agents. Working paper, Department of Economics, Louisiana State University, no. 2003--06, 2003.
• 15: Shai Herzog , Scott Shenker , Deborah Estrin, Sharing the “cost” of multicast trees: an axiomatic analysis, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.847-860, Dec. 1997 [doi>10.1109/90.650144]
• 16: M. Hoefer. Non-cooperative tree creation. Proc. 31st International Symposium on Mathematical Foundations of Computer Science (MFCS), Springer LNCS 4162, 517--527, 2006.
• 17: M. Jackson and A. van den Nouweland. Strongly stable networks. Games and Economic Behavior, 51:420--444, 2005.
• 18: Kamal Jain , Vijay Vazirani, Applications of approximation algorithms to cooperative games, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.364-372, July 2001, Hersonissos, Greece [doi>10.1145/380752.380825]
• 19: E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. Proc. 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS), Springer LNCS 1564, 404--413, 1999.
• 20: D. Monderer and L. Shapley. Potential games. Games and Economic Behavior, 14:124--143, 1996.
• 21: A. van den Nouweland. Models of network formation in cooperative games. In Group Formation in Economics; Networks, Clubs, and Coalitions, G. Demange and M. Wooders (eds), Cambridge University Press, 58--88, 2005.
• 22: Martin Pál , Éva Tardo, Group Strategyproof Mechanisms via Primal-Dual Algorithms, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.584, October 11-14, 2003
• 23: Adrian Vetta, Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.416, November 16-19, 2002

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Theory