Warning: pg_query(): Query failed: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 in /dati/webiit-old/includes/database.pgsql.inc on line 138 Warning: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 query: SELECT data, created, headers, expire, serialized FROM cache_page WHERE cid = 'https://www-old.iit.cnr.it/node/642' in /dati/webiit-old/includes/database.pgsql.inc on line 159 Warning: pg_query(): Query failed: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 in /dati/webiit-old/includes/database.pgsql.inc on line 138 Warning: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 query: SELECT data, created, headers, expire, serialized FROM cache_page WHERE cid = 'https://www-old.iit.cnr.it/node/642' in /dati/webiit-old/includes/database.pgsql.inc on line 159 Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games | IIT - CNR - Istituto di Informatica e Telematica
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.


LECTURE NOTES IN COMPUTER SCIENCE (00538S0), 2006

Autori: B. Codenotti, M. Leoncini, G. Resta
Autori IIT:

Tipo: Articoli su riviste ISI
Area di disciplina: Computer Science and Engineering
In Proceedings of ESA 2006 Da pagina 232 a pagina 243

Attività: Economia computazionale