TR06-012 Authors: Bruno Codenotti, Mauro Leoncini, Giovanni Resta

Publication: 24th January 2006 01:40

Downloads: 1897

Keywords:

It 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.