Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games (Articolo in rivista)

Type

• Prodotto della ricerca (Classe)
• Articolo in rivista (Classe)

Label

• Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games (Articolo in rivista) (literal)

Anno

• 2006-01-01T00:00:00+01:00 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi

• 10.1007/11841036_23 (literal)

Alternative label

• [1] Codenotti B., [1] Resta G., [1] Leoncini M. (2006)
  Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games
  in Lecture notes in computer science
  (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

• [1] Codenotti B., [1] Resta G., [1] Leoncini M. (literal)

Pagina inizio

• 232 (literal)

Pagina fine

• 243 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#altreInformazioni

• Codice Puma: cnr.iit/2006-A2-010 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume

• 4168 (literal)

Rivista

• Lecture notes in computer science (Rivista)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note

• In Proceedings of ESA 2006 (literal)

Note

• ISI Web of Science (WOS) (literal)
• Scopu (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni

• [1] CNR-IIT, Pisa, Italy (literal)

Titolo

• Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games (literal)

Abstract

• 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. (literal)

Prodotto di

• Analisi e sviluppo di metodi e algoritmi efficienti per il calcolo ad alte prestazioni (ICT.P09.003.001) (Modulo)
• Istituto di informatica e telematica (IIT) (Istituto)
• Metodi e algoritmi efficienti per la risoluzione di problemi complessi (ICT.P11.011.001) (Modulo)

Autore CNR

• GIOVANNI RESTA (Unità di personale interno)
• BRUNO CODENOTTI (Persona)
• MAURO LEONCINI (Unità di personale esterno)

Insieme di parole chiave

• Parole chiave di "Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games" (Insieme di parole chiave)

Incoming links:

Prodotto

• Istituto di informatica e telematica (IIT) (Istituto)
• Metodi e algoritmi efficienti per la risoluzione di problemi complessi (ICT.P11.011.001) (Modulo)
• Analisi e sviluppo di metodi e algoritmi efficienti per il calcolo ad alte prestazioni (ICT.P09.003.001) (Modulo)

Autore CNR di

• GIOVANNI RESTA (Unità di personale interno)
• BRUNO CODENOTTI (Persona)
• MAURO LEONCINI (Unità di personale esterno)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi

• Lecture notes in computer science (Rivista)

Insieme di parole chiave di

• Parole chiave di "Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games" (Insieme di parole chiave)