ECCC-Report TR06-012https://eccc.weizmann.ac.il/report/2006/012Comments and Revisions published for TR06-012en-usTue, 24 Jan 2006 01:40:34 +0200
Paper TR06-012
| Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Games |
Bruno Codenotti,
Mauro Leoncini,
Giovanni Resta
https://eccc.weizmann.ac.il/report/2006/012It is known that finding a Nash equilibrium for win-lose bimatrix
games, i.e., two-player games where the players' payoffs are zero
and one, is complete for the class PPAD.
We describe a linear time algorithm which computes a Nash
equilibrium for win-lose bimatrix games where the number of winning
positions per strategy of each of the players is at most two.
The algorithm acts on the directed graph that represents the
zero-one pattern of the payoff matrices describing the game. It is
based upon the efficient detection of certain subgraphs which enable
us to determine the support of a Nash equilibrium.
Tue, 24 Jan 2006 01:40:34 +0200https://eccc.weizmann.ac.il/report/2006/012