Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > COMPUTATIONAL GAME THEORY:
Reports tagged with computational game theory:
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