2012 · 31 citations · 25 references
Social SciencesMathematicsGame TheoryMathematical EconomicsOptimizationAlgorithmic Game TheoryApproximation AlgorithmsCongestion ControlNash EquilibriumNetwork GamesNoncooperative Game TheoryApproximate Nash EquilibriumApproximation Algorithms For EquilibriaComputational Game TheoryGame-theoretic OptimizationLower BoundsPotential FunctionsQuadratic Cost FunctionsUpper Bounds
We consider structural and algorithmic questions related to the Nash dynamics of weighted congestion games. In weighted congestion games with linear latency functions, the existence of pure Nash equilibria is guaranteed by potential function arguments. Unfortunately, this proof of existence is inefficient and computing pure Nash equilibria in such games is a PLS-hard problem even when all players have unit weights. The situation gets worse when superlinear (e.g., quadratic) latency functions come into play; in this case, the Nash dynamics of the game may contain cycles and pure Nash equilibria may not even exist. Given these obstacles, we consider approximate pure Nash equilibria as alternative solution concepts. Do such equilibria exist? And if so, can we compute them efficiently?
25
The complexity of pure Nash equilibria
Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar · 2004 · 662 citations
Sink Equilibria and Convergence
M. X. Goemans, Vahab Mirrokni, Adrian Vetta · 2005 · 229 citations
Dimitris Fotakis, Spyros Kontogiannis, Paul G. Spirakis · Theoretical Computer Science · 2005 · 211 citations · Full text