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 . 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 diffrences between nearby players in T*.
File in questo prodotto:
Non ci sono file associati a questo prodotto.