Strong equilibrium in cost sharing connection games

ABSTRACT

In this work we study cost sharing connection games, where each player has a source and sink he would like to connect, and the cost of the edges is either shared equally (fair connection games) or in an arbitrary way (general connection games).We study the graph topologies that guarantee the existence of a strong equilibrium (where no coalition can improve the cost of eachof its members) regardless of the specific costs on the edges.

Our main existence results are the following: (1) For a single source and sink we show that there is always a strong equilibrium (both for fair and general connection games). (2) For a single source multiple sinks we show that for a series parallel graph a strong equilibrium always exists (both for fair and general connection games). (3) For multi source and sink we show that an extension parallel graph always admits a strong equilibrium in fair connection games.

As for the quality of the strong equilibrium we show that in any fair connection games the cost of a strong equilibrium is Θ(log n) from the optimal solution, where n is the number of players. (This should be contrasted with the Ω(n) price of anarchy for the same setting.) For single source general connection games and single source single sink fair connection games, we show that a strong equilibrium is always an optimal solution.

REFERENCES

• 1: N. Andelman, M. Feldman, and Y. Mansour. Strong Price of Anarchy. In SODA'07, 2007.
• 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 (FOCS'04), 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. Aumann. Acceptable Points in General Cooperative n-Person Games. In Contributions to the Theory of Games, volume 4, 1959.
• 5: Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
• 6: 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]
• 7: R. Holzman and N. Law-Yone. Strong equilibrium in congestion games. Games and Economic Behavior, 21:85--101, 1997.
• 8: R. Holzman and N. L.-Y. (Lev-tov). Network structure and strong equilibrium in route selection games. Mathematical Social Sciences, 46:193--205, 2003.
• 9: E. Koutsoupias and C. H. Papadimitriou. Worst-case equilibria. In STACS, pages 404--413, 1999.
• 10: Igal Milchtaich, Topological Conditions for Uniqueness of Equilibrium in Networks, Mathematics of Operations Research, v.30 n.1, p.225-244, February 2005 [doi>10.1287/moor.1040.0122]
• 11: I. Milchtaich. Network topology and the efficiency of equilibrium. Games and Economic Behavior, 57:321--346, 2006.
• 12: I. Milchtaich. The equilibrium existence problem in finite network congestion games. Forthcoming in Lecture Notes in Computer Science, 2007.
• 13: D. Monderer and L. S. Shapley. Potential Games. Games and Economic Behavior, 14:124--143, 1996.
• 14: H. Moulin and S. Shenker. Strategyproof sharing of submodular costs: Budget balance versus efficiency. Economic Theory, 18(3):511--533, 2001.
• 15: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 16: R. W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65--67, 1973.
• 17: Tim Roughgarden, The price of anarchy is independent of the network topology, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509971]
• 18: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 19: O. Rozenfeld and M. Tennenholtz. Strong and correlated strong equilibria in monotone congestion games. In Workshop on Internet and Network Economics, 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Payment schemes

General Terms:
Algorithms, Economics, Theory

Keywords:
Nash equilibrium, coalitions, cost sharing games, game theory, network design, price of anarchy, strong equilibrium, strong price of anarchy