IIT Home Page CNR Home Page

Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix 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 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.


Authors: B. Codenotti, M. Leoncini, G. Resta
IIT authors:

Type: Article in ISI Journal
Field of reference: Computer Science and Engineering
In Proceedings of ESA 2006 Da pagina 232 a pagina 243

Activity: Economia computazionale