Welfare maximization in congestion games

ABSTRACT

Congestion games are non-cooperative games where the utility of a player from using a certain resource depends on the total number of players that are using the same resource. While most work so far took a game-theoretic approach to this problem, we study centralized solutions for congestion games from a computational point of view. We analyze the computational complexity of the welfare-maximization problem, and provide both approximation algorithms and lower bounds. Throughout the paper, different kinds of congestion effects (externalities) among the players are considered: positive, negative, and unrestricted. Our main algorithmic result is a constant approximation algorithm for congestion games with unrestricted externalities. We describe an important and useful connection between congestion games and combinatorial auctions. This connection allows us to use insights and methods from the combinatorial-auction literature for solving congestion games. Finally, we initiate the study of strategic centralized mechanisms in congestion-game environments.

REFERENCES

• 1: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 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: B. Awerbuch , Y. Azar , E. F. Grove , Ming-Yang Kao , P. Krishnan , J. S. Vitter, Load balancing in the L/sub p/ norm, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.383, October 23-25, 1995
• 4: Liad Blumrosen , Noam Nisan, On the computational power of iterative auctions, Proceedings of the 6th ACM conference on Electronic commerce, p.29-43, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064013]
• 5: Deeparnab Chakrabarty , Aranyak Mehta , Viswanath Nagarajan, Fairness and optimality in congestion games, Proceedings of the 6th ACM conference on Electronic commerce, p.52-57, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064015]
• 6: 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]
• 7: V. Conitzer and T. Sandholm. Expressive negotiation in settings with externalities. In AAAI 05, 2005.
• 8: Vincent Conitzer , Tuomas Sandholm, Expressive negotiation over donations to charities, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988781]
• 9: Peter Cramton , Yoav Shoham , Richard Steinberg, Combinatorial Auctions, The MIT Press, 2006
• 10: Shahar Dobzinski , Noam Nisan , Michael Schapira, Approximation algorithms for combinatorial auctions with complement-free bidders, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060681]
• 11: Shahar Dobzinski , Noam Nisan , Michael Schapira, Truthful randomized mechanisms for combinatorial auctions, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132607]
• 12: Shahar Dobzinski , Michael Schapira, An improved approximation algorithm for combinatorial auctions with submodular bidders, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1064-1073, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109675]
• 13: S. Dobzinski and M. Schapira. Optimal upper and lower approximation bounds for k-duplicates combinatorial auctions. Working paper, the Hebrew University.
• 14: B. Ellickson, B. Grodal, S. Scotchmer, and W. R. Zame. Clubs and the market. Econometrica, 67(5):1185--1219, 1999.
• 15: Eyal Even-Dar , Yishay Mansour, Fast convergence of selfish rerouting, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 16: A. Fabrikant, C. Papadimitriou, and K. Talwar. The complexity of pure nash equilibria. In FOCS 04, pages 604--612, 2004.
• 17: Uriel Feige, On maximizing welfare when utility functions are subadditive, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132523]
• 18: Joan Feigenbaum , Christos Papadimitriou , Scott Shenker, Sharing the cost of muliticast transmissions (preliminary version), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.218-227, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335332]
• 19: M. Hajiaghayi, M. Mahdian, and V. Mirrokni. Facility location problem with general cost functions. Networks, 42(1):42--47, 2003.
• 20: E. Hazan, S. Safra, and O. Schwartz. On the complexity of approximating k-dimensional matching. In RANDOM-APPROX, 2003.
• 21: D. S. Hochbaum. Heuristics for the fixed cost median problem. Mathematical programming, 22(2):148--162, 1982.
• 22: L. Katz and C. Shapiro. Network externalities, competition, and compatibility. American Economic Review, 75(3):424--440, 1985.
• 23: H. Konishi, M. L. Breton, and S. Weber. Pure strategy nash equilibrium in a group formation game with positive externalities. Games and Economic Behavior, 21(1-2):161--182, 1997.
• 24: E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, pages 404--413, 1999.
• 25: Benny Lehmann , Daniel Lehmann , Noam Nisan, Combinatorial auctions with decreasing marginal utilities, Proceedings of the 3rd ACM conference on Electronic Commerce, p.18-28, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501161]
• 26: I. Milchtaich. Congestion games with player-specific payoff functions. Games and Economic Behavior, 13:111--124, 1996.
• 27: D. Monderer. Generalized congestion games. Seminar Presentation, Dagstuhl, Germany, January 2005.
• 28: D. Monderer and L. S. Shapley. Potential games. Games and Economic Behavior, 14:124--143, 1996.
• 29: N. Nisan and A. Ronen. Algorithmic mechanism design. Games and Economic Behaviour, 35:166--196, 2001. A preliminary version appeared in STOC 1999.
• 30: N. Nisan and I. Segal. The communication requirements of efficient allocations and supporting prices, 2003. Forthcoming in the Journal of Economic Theory.
• 31: R. W. Rosenthal. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2:65--67, 1973.
• 32: Tim Roughgarden, Selfish Routing and the Price of Anarchy, The MIT Press, 2005
• 33: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

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

General Terms:
Algorithms, Economics, Theory

Keywords:
approximation algorithms, combinatorial auctions, congestion games, welfare maximization