Simple complexity from imitation games
From MaRDI portal
Publication:2268119
DOI10.1016/j.geb.2009.10.003zbMath1200.91023MaRDI QIDQ2268119
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
complexity; quadratic programming; stationary points; symmetric games; symmetric Nash equilibria; imitation games; NASH
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