Ara Hayrapetyan
Éva Tardos
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.
- 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.Google Scholar
- E. Anshelevich, A. Dasgupta, J. Kleinberg, É. Tardos, T. Wexler, and T. Roughgarden. The Price of Stability for Network Design with Fair Cost Allocation. IEEE Symposium on Foundations of Computer Science, 295--304, 2004. Google ScholarDigital Library
- R. Aumann. Acceptable Points in General Cooperative n-Person Games. Contributions to the Theory of Games IV Princeton University Press, 1959.Google Scholar
- B. Awerbuch, Y. Azar, and A. Epstein. The Price of Routing Unsplittable Flow. ACM Symposium on Theory of Computing, 57--66, 2005. Google ScholarDigital Library
- M. Beckmann, C. B. McGuire, and C. B. Winsten. Studies in the Economics of Transportation. Yale University Press, 1956.Google Scholar
- S. Catoni and S. Pallottino. Traffic Equilibrium Paradoxes. Transportation Science, 240--244, 1991.Google Scholar
- G. Christodoulou and E. Koutsoupias. The Price of Anarchy of Finite Congestion Games. ACM Symposium on Theory of Computing, 67--73, 2005. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- R. Cominetti, J. R. Correa, and N. E. Stier-Moses. Network Games with Atomic Players. Columbia Working Paper # DRO-2006-03, 2006.Google Scholar
- 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. Google ScholarDigital Library
- A. Fabrikant, C. H. Papadimitriou, and K. Talwar. The Complexity of Pure Nash Equilibria. ACM Symposium on Theory of Computing, 604--612, 2004. Google ScholarDigital Library
- A. V. Goldberg and J. D. Hartline. Collusion-Resistant Mechanisms for Single-Parameter Agents. ACM-SIAM Symposium on Discrete Algorithms, 620--629, 2005. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- E. Koutsoupias and C. H. Papadimitriou. Worst-Case Equilibria. International Symposium on Theoretical Aspects of Computer Science, 404--413, 1999. Google ScholarDigital Library
- I. Milchtaich. Congestion Games with Player-Specific Payoff Functions. Games and Economic Behavior, 111--124, 1996.Google Scholar
- D. Monderer and L. S. Shapley. Potential Games. Games and Economic Behavior, 124--143, 1996.Google Scholar
- D. Moreno and J. Wooders. Coalition-Proof Equilibrium. Games and Economic Behavior, 80--112, 1996.Google Scholar
- H. Moulin and S. Shenker. Strategyproof Sharing of Submodular Costs: Budget Balance Versus Efficiency. Economic Theory, 511--533, 2001.Google Scholar
- A. Orda, R. Rom, and N. Shimkin. Competitive Routing in Multiuser Communication Networks. IEEE/ACM Transactions on Networking, 510--521, 1993. Google ScholarDigital Library
- C. H. Papadimitriou. Algorithms, Games and the Internet. ACM Symposium on Theory of Computing, 749--753, 2001. Google ScholarDigital Library
- J. B. Rosen. Existence and Uniqueness of Equilibrium Points for Concave N-Person Games. Econometrica, 520--534, 1965.Google Scholar
- R. W. Rosenthal. A Class of Games Possessing Pure-Strategy Nash Equilibria. International Journal of Game Theory, 65--67, 1973.Google Scholar
- T. Roughgarden. The Price of Anarchy is Independent of the Network Topology. ACM Symposium on Theory of Computing, 428--437, 2002. Google ScholarDigital Library
- T. Roughgarden. Selfish Routing with Atomic Players. ACM-SIAM Symposium on Discrete Algorithms, 1184--1185, 2005. Google ScholarDigital Library
- T. Roughgarden and É. Tardos. How Bad Is Selfish Routing? Journal of the ACM, 236--259, 2002. Google ScholarDigital Library
- S. Suri, C. D. Toth, and Y. Zhou. Selfish Load Balancing and Atomic Congestion Games. ACM Symposium on Parallel Algorithms and Architectures, 188--195, 2004. Google ScholarDigital Library
Index Terms
- The effect of collusion in congestion games
Recommendations
The price of anarchy of finite congestion games
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computingWe consider the price of anarchy of pure Nash equilibria in congestion games with linear latency functions. For asymmetric games, the price of anarchy of maximum social cost is Θ(√N), where N is the number of players. For all other cases of symmetric or ...
Congestion games with failures
We introduce a new class of games, congestion games with failures (CGFs), which allows for resource failures in congestion games. In a CGF, players share a common set of resources (service providers), where each service provider (SP) may fail with some ...
Selfishness, collusion and power of local search for the ADMs minimization problem
WINE'07: Proceedings of the 3rd international conference on Internet and network economicsWe consider non cooperative games in all-optical networks where users share the cost of the used ADM switches for realizing given communication patterns. We show that the two fundamental cost sharing methods, Shapley and Egalitarian, induce polynomial ...
Comments