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

• 成果类型: Article
• 署名作者: Bilo, Vittorio; Flammini, Michele; Moscardelli, Luca
• 署名单位: University of Salento; University of L'Aquila; Gran Sasso Science Institute (GSSI); G d'Annunzio University of Chieti-Pescara
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2014.09.010
• 发表日期: 2020
• 页码: 359-376
• 关键词: Network design games; Price of stability; Pure Nash equilibria

摘要

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 sand 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 etal. (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*. (C) 2014 Elsevier Inc. All rights reserved.