Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00147
A Polynomial Time Algorithm for Finding Nash Equilibria in Planar Win-Lose Games
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.
Submitted: January 2007.
Revised: August 2007.
Communicated by Giuseppe Liotta
article (PDF)
BibTeX