Simple complexity from imitation games

DOI10.1016/j.geb.2009.10.003zbMath1200.91023OpenAlexW2091731906MaRDI 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

complexityquadratic programmingstationary pointssymmetric gamessymmetric Nash equilibriaimitation gamesNASH

Mathematics Subject Classification ID

Noncooperative games (91A10) Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20) 2-person games (91A05)

Related Items (18)

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

This page was built for publication: Simple complexity from imitation games