On the impact of combinatorial structure on congestion games

ABSTRACT

We study the impact of combinatorial structure in congestion games on the complexity of computing pure Nash equilibria and the convergence time of best response sequences. In particular, we investigate which properties of the strategy spaces of individual players ensure a polynomial convergence time. We show that if the strategy space of each player consists of the bases of a matroid over the set of resources, then the lengths of all best response sequences are polynomially bounded in the number of players and resources. We also prove that this result is tight, that is, the matroid property is a necessary and sufficient condition on the players' strategy spaces for guaranteeing polynomial-time convergence to a Nash equilibrium.

In addition, we present an approach that enables us to devise hardness proofs for various kinds of combinatorial games, including first results about the hardness of market sharing games and congestion games for overlay network design. Our approach also yields a short proof for the PLS-completeness of network congestion games. In particular, we show that network congestion games are PLS-complete for directed and undirected networks even in case of linear latency functions.

REFERENCES

• 1: Ackermann, H., Röglin, H., and Vöcking, B. 2006. Pure Nash equilibria in player-specific and weighted congestion games. In Proceedings of the 2nd International Workshop on Internet and Network Economics (WINE). Lecture Notes in Computer Science, vol. 4286. Springer-Verlag, New York, 50--61.
• 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: 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]
• 5: 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]
• 6: Floren, P., and Orponen, P. 1994. Complexity issues in discrete Hopfield networks. Department of Computer Science, University of Helsinki, Helsinki, Finland, Tech. Rep. A-1994-4.
• 7: Michel Goemans , Li Erran Li , Vahab S. Mirrokni , Marina Thottan, Market sharing games applied to content distribution in ad-hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989467]
• 8: Ieong, S., McGrew, R., Nudelman, E., Shoham, Y., and Sun, Q. 2005. Fast and compact: A simple class of congestion games. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI). AAAI Press, Menlo Park, CA, 489--494.
• 9: David S. Johnson , Christos H. Papadimtriou , Mihalis Yannakakis, How easy is local search?, Journal of Computer and System Sciences, v.37 n.1, p.79-100, August 1988 [doi>10.1016/0022-0000(88)90046-3]
• 10: Vahab S. Mirrokni , Michel X. Goemans, Approximation algorithms for distributed and selfish agents, Massachusetts Institute of Technology, Cambridge, MA, 2005
• 11: Pekka Orponen, Computing with truly asynchronous threshold logic networks, Theoretical Computer Science, v.174 n.1-2, p.123-136, March 1997 [doi>10.1016/S0304-3975(96)00017-5]
• 12: Svatopluk Poljak, Integer Linear Programs and Local Search for Max-Cut, SIAM Journal on Computing, v.24 n.4, p.822-839, Aug. 1995 [doi>10.1137/S0097539793245350]
• 13: Rosenthal, R. W. 1973. A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65--67.
• 14: Alejandro A. Schäffer , Mihalis Yannakakis, Simple local search problems that are hard to solve, SIAM Journal on Computing, v.20 n.1, p.56-87, Feb. 1991 [doi>10.1137/0220004]
• 15: Schrijver, A. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer. Volume B, Matroids, Trees, Stable Sets, Chapters 39--69.
• 16: Ion Stoica , Daniel Adkins , Shelley Zhuang , Scott Shenker , Sonesh Surana, Internet indirection infrastructure, IEEE/ACM Transactions on Networking (TON), v.12 n.2, p.205-218, April 2004 [doi>10.1109/TNET.2004.826279]
• 17: Renato Werneck , João Setubal , Arlindo da Conceicão, Finding minimum congestion spanning trees, Journal of Experimental Algorithmics (JEA), 5, p.11-es, 2000 [doi>10.1145/351827.384253]

INDEX TERMS

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

General Terms:
Algorithms, Economics, Theory

Keywords:
Congestion games, Nash equilibria, convergence, local search