Efficient computation of Nash equilibria for very sparse win-lose bimatrix games

It is known that finding a Nash equilibrium for win-lose bimatrixgames, i.e., two-player garnes where the players' payoffs are zero andone, is complete for the class PPAD. We describe a linear timealgorithm which computes a Nash equilibrium for win-lose bimatrixgarnes where the number of winning positions per strategy of each ofthe players is at most two. The algorithm acts on the directed graphthat represents the zero-one pattern of the payoff matrices describingthe game. It is based upon the efficient detection of certain subgraphswhich enable us to determine the support of a Nash equilibrium.