Simple complexity from imitation games

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

Rabee Tourky, Andrew McLennan

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

On the Hardness and Existence of Quasi-Strict Equilibria, 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, Simple complexity from imitation games, Oriented Euler complexes and signed perfect matchings, 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