Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00147 A Polynomial Time Algorithm for Finding Nash Equilibria in Planar Win-Lose Games Louigi Addario-Berry , Neil Olver , and Adrian Vetta Vol. 11, no. 1, pp. 309-319, 2007. Regular paper Abstract Two-player win-lose games have a simple directed graph representation. Exploiting this, we develop graph theoretic techniques for finding Nash equilibria in such games. In particular, we give a polynomial time algorithm for finding a Nash equilibrium in a two-player win-lose game whose graph representation is planar.
|
Revised: August 2007. Submitted: January 2007. Communicated by Giuseppe Liotta |
| Journal of Graph Algorithms and Applications |