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

DOI10.7155/JGAA.00147MaRDI QIDQ5301416zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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)

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

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)