It is known that finding a Nash equilibrium for win-lose bimatrixgames, i.e., two-player garnes where the players' payoffs are zero andone, is complete for the class PPAD. We describe a linear timealgorithm which computes a Nash equilibrium for win-lose bimatrixgarnes where the number of winning positions per strategy of each ofthe players is at most two. The algorithm acts on the directed graphthat represents the zero-one pattern of the payoff matrices describingthe game. It is based upon the efficient detection of certain subgraphswhich enable us to determine the support of a Nash equilibrium.

Efficient computation of Nash equilibria for very sparse win-lose bimatrix games / B., Codenotti; Leoncini, Mauro; G., Resta. - STAMPA. - 4168:(2006), pp. 232-243. (Intervento presentato al convegno 14th Annual European Symposium on Algorithms, ESA 2006 tenutosi a Zurich, che nel September 11-15, 2006) [10.1007/11841036_23].

Efficient computation of Nash equilibria for very sparse win-lose bimatrix games

LEONCINI, Mauro;
2006

Abstract

It is known that finding a Nash equilibrium for win-lose bimatrixgames, i.e., two-player garnes where the players' payoffs are zero andone, is complete for the class PPAD. We describe a linear timealgorithm which computes a Nash equilibrium for win-lose bimatrixgarnes where the number of winning positions per strategy of each ofthe players is at most two. The algorithm acts on the directed graphthat represents the zero-one pattern of the payoff matrices describingthe game. It is based upon the efficient detection of certain subgraphswhich enable us to determine the support of a Nash equilibrium.
2006
14th Annual European Symposium on Algorithms, ESA 2006
Zurich, che
September 11-15, 2006
4168
232
243
B., Codenotti; Leoncini, Mauro; G., Resta
Efficient computation of Nash equilibria for very sparse win-lose bimatrix games / B., Codenotti; Leoncini, Mauro; G., Resta. - STAMPA. - 4168:(2006), pp. 232-243. (Intervento presentato al convegno 14th Annual European Symposium on Algorithms, ESA 2006 tenutosi a Zurich, che nel September 11-15, 2006) [10.1007/11841036_23].
File in questo prodotto:
File Dimensione Formato  
lncs4168pp232-243.pdf

Accesso riservato

Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 448.12 kB
Formato Adobe PDF
448.12 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/641688
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 19
  • ???jsp.display-item.citation.isi??? 14
social impact