The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation Is Constant

Torna indietro

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 cite{ADKTWR08}. 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^*$.

Autore Pugliese

Tutti gli autori

  • V. Bilò , M. Flammini , L. Moscardelli

Titolo volume/Rivista

Non Disponibile

Anno di pubblicazione

2013

ISSN

Non Disponibile

ISBN

Non Disponibile

Numero di citazioni Wos

Nessuna citazione

Ultimo Aggiornamento Citazioni

Non Disponibile

Numero di citazioni Scopus

13

Ultimo Aggiornamento Citazioni

26/04/2018

Settori ERC

Non Disponibile

Codici ASJC

Non Disponibile