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

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

Mathematics Subject Classification ID

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

Cited In (9)

• 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
• Well supported approximate equilibria in bimatrix games
• Constant Rank Two-Player Games are PPAD-hard
• Parameterized two-player Nash equilibrium
• The complexity of computational problems about Nash equilibria in symmetric win-lose 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)