We study the performances of Nash equilibria in isolation games, a class of competitive location games recently introduced in Zhao et al. (Proc. of the 19th International Symposium on Algorithms and Computation (ISAAC), pp. 148–159, 2008). For all the cases in which the existence of Nash equilibria has been shown, we give tight or asymptotically tight bounds on the prices of anarchy and stability under the two classical social functions mostly investigated in the scientific literature, namely, the minimum utility per player and the sum of the players’ utilities. Moreover, we prove that the convergence to Nash equilibria is not guaranteed in some of the not yet analyzed cases.

On the performances of Nash equilibria in isolation games

Flammini M;
2011

Abstract

We study the performances of Nash equilibria in isolation games, a class of competitive location games recently introduced in Zhao et al. (Proc. of the 19th International Symposium on Algorithms and Computation (ISAAC), pp. 148–159, 2008). For all the cases in which the existence of Nash equilibria has been shown, we give tight or asymptotically tight bounds on the prices of anarchy and stability under the two classical social functions mostly investigated in the scientific literature, namely, the minimum utility per player and the sum of the players’ utilities. Moreover, we prove that the convergence to Nash equilibria is not guaranteed in some of the not yet analyzed cases.
Nash equilibria; Price of anarchy and stability; Isolation games
File in questo prodotto:
File Dimensione Formato  
2011_JCombOptim_22_Bilo.pdf

accesso aperto

Tipologia: Versione Editoriale (PDF)
Licenza: Accesso gratuito
Dimensione 551.14 kB
Formato Adobe PDF
551.14 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

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