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

Authors

  • Louigi Addario-Berry
  • Neil Olver
  • Adrian Vetta

DOI:

https://doi.org/10.7155/jgaa.00147

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.

Downloads

Download data is not yet available.

Downloads

Published

2007-01-01

How to Cite

Addario-Berry, L., Olver, N., & Vetta, A. (2007). A Polynomial Time Algorithm for Finding Nash Equilibria in Planar Win-Lose Games. Journal of Graph Algorithms and Applications, 11(1), 309–319. https://doi.org/10.7155/jgaa.00147

Issue

Vol. 11 No. 1 (2007)

Section

Articles

Categories

License

Copyright (c) 2007 Louigi Addario-Berry, Neil Olver, Adrian Vetta

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.