A Polynomial Time Algorithm for Finding Nash Equilibria in Planar Win-Lose Games

DOI10.7155/JGAA.00147zbMATH Open1152.91382OpenAlexW2162603877MaRDI QIDQ5301416FDOQ5301416

Authors Louigi Addario-Berry, Neil Olver, Adrian Vetta

Publication date 19 January 2009

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL http://www.emis.de/journals/JGAA/accepted/2007/Addario-BerryOlverVetta2007.11.1.pdf

Mathematics Subject Classification ID

Applications of graph theory (05C90) Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Games involving graphs (91A43)

Recommendations

• Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games
• Some tractable win-lose games
• Enumeration of Nash equilibria for two-player games
• Nash equilibria in random games
• The complexity of computing a Nash equilibrium

Cited in

(9)

• On mutual concavity and strategically-zero-sum bimatrix games
• Some tractable win-lose games
• Well supported approximate equilibria in bimatrix games
• Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games
• The complexity of computational problems about Nash equilibria in symmetric win-lose games
• Constant rank two-player games are PPAD-hard
• An average polynomial algorithm for solving antagonistic games on graphs
• Polynomial time winning strategies for three variants of \((s,t)\)-Wythoff's game
• The complexity of uniform Nash equilibria and related regular subgraph problems

This page was built for publication: A Polynomial Time Algorithm for Finding Nash Equilibria in Planar Win-Lose Games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5301416)