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 European Symposium on Algorithms tenutosi a Zurich, Switzerland nel September 11-15, 2006.

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.
14th European Symposium on Algorithms
Zurich, Switzerland
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 European Symposium on Algorithms tenutosi a Zurich, Switzerland nel September 11-15, 2006.
File in questo prodotto:
File Dimensione Formato  
lncs4168pp232-243.pdf

non disponibili

Tipologia: Post-print dell'autore (bozza post referaggio)
Dimensione 448.12 kB
Formato Adobe PDF
448.12 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento 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