Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with win-lose game:
TR06-012 | 17th January 2006
Bruno Codenotti, Mauro Leoncini, Giovanni Resta

Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Games

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

ISSN 1433-8092 | Imprint