The effect of collusion in congestion games

ABSTRACT

In this paper we initiate the study of how collusion alters the quality of solutions obtained in competitive games. The price of anarchy aims to measure the cost of the lack of coordination by comparing the quality of a Nash equilibrium to that of a centrally designed optimal solution. This notion assumes that players act not only selfishly, but also independently. We propose a framework for modeling groups of colluding players, in which members of a coalition cooperate so as to selfishly maximize their collective welfare. Clearly, such coalitions can improve the social welfare of the participants, but they can also harm the welfare of those outside the coalition. One might hope that the improvement for the coalition participants outweighs the negative effects on the others. This would imply that increased cooperation can only improved the overall solution quality of stable outcomes. However, increases in coordination can actually lead to significant decreases in total social welfare. In light of this, we propose the price of collusion as a measure of the possible negative effect of collusion, specifying the factor by which solution quality can deteriorate in the presence of coalitions. We give examples to show that the price of collusion can be arbitrarily high even in convex games. Our main results show that in the context of load-balancing games, the price of collusion depends upon the disparity in market power among the game participants. We show that in some symmetric nonatomic games (where all users have access to the same set of strategies) increased cooperation always improves the solution quality, and in the discrete analogs of such games, the price of collusion is bounded by two.

REFERENCES

• 1: E. Altman, T. Basar, T. Jiménez, and N. Shimkin. Competitive Routing in Networks with Polynomial Costs. IEEE Transactions on Automatic Control, 92--96, 2002.
• 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: R. Aumann. Acceptable Points in General Cooperative n-Person Games. Contributions to the Theory of Games IV Princeton University Press, 1959.
• 4: Baruch Awerbuch , Yossi Azar , Amir Epstein, Large the price of routing unsplittable flow, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060599]
• 5: M. Beckmann, C. B. McGuire, and C. B. Winsten. Studies in the Economics of Transportation. Yale University Press, 1956.
• 6: S. Catoni and S. Pallottino. Traffic Equilibrium Paradoxes. Transportation Science, 240--244, 1991.
• 7: George Christodoulou , Elias Koutsoupias, The price of anarchy of finite congestion games, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060600]
• 8: G. Christodoulou and E. Koutsoupias. On The Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games. European Symposium on Algorithms, 59--70, 2005.
• 9: R. Cominetti, J. R. Correa, and N. E. Stier-Moses. Network Games with Atomic Players. Columbia Working Paper # DRO-2006-03, 2006.
• 10: J. R. Correa, A. S. Schulz, and N. E. Stier-Moses. On The Inefficiency of Equilibria in Congestion Games. Conference on Integer Programming and Combinatorial Optimization, 167--181, 2005.
• 11: Alex Fabrikant , Christos Papadimitriou , Kunal Talwar, The complexity of pure Nash equilibria, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007445]
• 12: Andrew V. Goldberg , Jason D. Hartline, Collusion-resistant mechanisms for single-parameter agents, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 13: A. Kothari, S. Suri, C. D. Tóth, and Y. Zhou. Congestion Games, Load Balancing, and Price of Anarchy. Workshop on Combinatorial and Algorithmic Aspects of Networking, 2004.
• 14: E. Koutsoupias and C. H. Papadimitriou. Worst-Case Equilibria. International Symposium on Theoretical Aspects of Computer Science, 404--413, 1999.
• 15: I. Milchtaich. Congestion Games with Player-Specific Payoff Functions. Games and Economic Behavior, 111--124, 1996.
• 16: D. Monderer and L. S. Shapley. Potential Games. Games and Economic Behavior, 124--143, 1996.
• 17: D. Moreno and J. Wooders. Coalition-Proof Equilibrium. Games and Economic Behavior, 80--112, 1996.
• 18: H. Moulin and S. Shenker. Strategyproof Sharing of Submodular Costs: Budget Balance Versus Efficiency. Economic Theory, 511--533, 2001.
• 19: Ariel Orda , Raphael Rom , Nahum Shimkin, Competitive routing in multiuser communication networks, IEEE/ACM Transactions on Networking (TON), v.1 n.5, p.510-521, Oct. 1993 [doi>10.1109/90.251910]
• 20: 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]
• 21: J. B. Rosen. Existence and Uniqueness of Equilibrium Points for Concave N-Person Games. Econometrica, 520--534, 1965.
• 22: R. W. Rosenthal. A Class of Games Possessing Pure-Strategy Nash Equilibria. International Journal of Game Theory, 65--67, 1973.
• 23: 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]
• 24: Tim Roughgarden, Selfish routing with atomic players, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 25: 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]
• 26: Subhash Suri , Csaba D. Tóth , Yunhong Zhou, Selfish load balancing and atomic congestion games, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007941]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Economics, Theory

Keywords:
coalitions, congestion games, game theory, games, load-balancing, price of anarchy, price of collusion