We consider broadcast network design games in undirected networks in which every player is a node wishing to receive communication from a distinguished source node s and the cost of each communication link is equally shared among the downstream receivers according to the Shapley value. We prove that the Price of Stability of such games is constant, thus closing a long-standing open problem raised in Anshelevich et al. (2008). Our result is obtained by means of homogenization, a new technique that, in any intermediate state locally diverging from a given optimal solution T^*, is able to restore local similarity by exploiting cost differences between nearby players in T^*.

The price of stability for undirected broadcast network design with fair cost allocation is constant

FLAMMINI, MICHELE
;
2020-01-01

Abstract

We consider broadcast network design games in undirected networks in which every player is a node wishing to receive communication from a distinguished source node s and the cost of each communication link is equally shared among the downstream receivers according to the Shapley value. We prove that the Price of Stability of such games is constant, thus closing a long-standing open problem raised in Anshelevich et al. (2008). Our result is obtained by means of homogenization, a new technique that, in any intermediate state locally diverging from a given optimal solution T^*, is able to restore local similarity by exploiting cost differences between nearby players in T^*.
2020
Network design games; Price of stability; Pure Nash equilibria
File in questo prodotto:
File Dimensione Formato  
2020_GamesEconBehav_123_Bilo.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: Versione Editoriale (PDF)
Licenza: Non pubblico
Dimensione 633.95 kB
Formato Adobe PDF
633.95 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/349
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? ND
social impact