Simple complexity from imitation games

DOI10.1016/j.geb.2009.10.003zbMath1200.91023MaRDI QIDQ2268119

Andrew McLennan, Rabee Tourky

Publication date: 10 March 2010

Published in: Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.geb.2009.10.003

zbMATH Keywords

complexity; quadratic programming; stationary points; symmetric games; symmetric Nash equilibria; imitation games; NASH

Mathematics Subject Classification ID

91A10: Noncooperative games

90C60: Abstract computational complexity for mathematical programming problems

90C20: Quadratic programming

91A05: 2-person games

Related Items

Constant Rank Two-Player Games are PPAD-hard, Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria, On the Hardness and Existence of Quasi-Strict Equilibria, A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games, A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games, A repeated imitation model with dependence between stages: decision strategies and rewards, Computing equilibria: a computational complexity perspective, Games in oriented matroids, The complexity of equilibria: Hardness results for economies via a correspondence with games, Imitation games and computation, Complexity of rational and irrational Nash equilibria, Communication complexity of approximate Nash equilibria, Simple complexity from imitation games, Oriented Euler complexes and signed perfect matchings, The complexity of computational problems about Nash equilibria in symmetric win-lose games, Unnamed Item, Settling Some Open Problems on 2-Player Symmetric Nash Equilibria

Cites Work

• Unnamed Item
• On total functions, existence theorems and computational complexity
• New complexity results about Nash equilibria
• On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games
• Nash and correlated equilibria: Some complexity considerations
• On standard quadratic optimization problems
• On the complexity of the parity argument and other inefficient proofs of existence
• Oddness of the number of equilibrium points: a new proof
• Simple complexity from imitation games
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Computing correlated equilibria in multi-player games