On the impact of combinatorial structure on congestion games
- 17 December 2008
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 55 (6), 1-22
- https://doi.org/10.1145/1455248.1455249
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.Keywords
Funding Information
- eu (1907)
- Deutsche Forschungsgemeinschaft (Vo889/2-1)
This publication has 13 references indexed in Scilit:
- Pure Nash Equilibria in Player-Specific and Weighted Congestion GamesLecture Notes in Computer Science, 2006
- Fairness and optimality in congestion gamesPublished by Association for Computing Machinery (ACM) ,2005
- The Price of Stability for Network Design with Fair Cost AllocationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- The complexity of pure Nash equilibriaPublished by Association for Computing Machinery (ACM) ,2004
- Market sharing games applied to content distribution in ad-hoc networksPublished by Association for Computing Machinery (ACM) ,2004
- Near-optimal network design with selfish agentsPublished by Association for Computing Machinery (ACM) ,2003
- Computing with truly asynchronous threshold logic networksTheoretical Computer Science, 1997
- Integer Linear Programs and Local Search for Max-CutSIAM Journal on Computing, 1995
- How easy is local search?Journal of Computer and System Sciences, 1988
- A class of games possessing pure-strategy Nash equilibriaInternational Journal of Game Theory, 1973