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.
['Louigi Addario-Berry', 'Neil Olver', 'Adrian Vetta']
A Polynomial Time Algorithm for finding Nash Equilibria in Planar Win-Lose Games