ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > POLYNOMIAL TIME ALGORITHM:
Reports tagged with polynomial time algorithm:
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