IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v123y2020icp359-376.html
   My bibliography  Save this article

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

Author

Listed:
  • Bilò, Vittorio
  • Flammini, Michele
  • Moscardelli, Luca

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⁎.

Suggested Citation

  • Bilò, Vittorio & Flammini, Michele & Moscardelli, Luca, 2020. "The price of stability for undirected broadcast network design with fair cost allocation is constant," Games and Economic Behavior, Elsevier, vol. 123(C), pages 359-376.
    • Handle: RePEc:eee:gamebe:v:123:y:2020:i:c:p:359-376
    DOI: 10.1016/j.geb.2014.09.010
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S089982561400150X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.geb.2014.09.010?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Epstein, Amir & Feldman, Michal & Mansour, Yishay, 2009. "Strong equilibrium in cost sharing connection games," Games and Economic Behavior, Elsevier, vol. 67(1), pages 51-68, September.
    2. Roughgarden, Tim & Tardos, Eva, 2004. "Bounding the inefficiency of equilibria in nonatomic congestion games," Games and Economic Behavior, Elsevier, vol. 47(2), pages 389-403, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Tami Tamir, 2023. "Cost-sharing games in real-time scheduling systems," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(1), pages 273-301, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Gaëtan Fournier & Marco Scarsini, 2014. "Hotelling Games on Networks: Efficiency of Equilibria," Documents de travail du Centre d'Economie de la Sorbonne 14033, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    2. Balmaceda, Felipe & Balseiro, Santiago R. & Correa, José R. & Stier-Moses, Nicolás E., 2016. "Bounds on the welfare loss from moral hazard with limited liability," Games and Economic Behavior, Elsevier, vol. 95(C), pages 137-155.
    3. José R. Correa & Nicolás Figueroa & Nicolás E. Stier-Moses, 2008. "Pricing with markups in industries with increasing marginal costs," Documentos de Trabajo 256, Centro de Economía Aplicada, Universidad de Chile.
    4. Ruben Juarez & Rajnish Kumar, 2013. "Implementing efficient graphs in connection networks," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 54(2), pages 359-403, October.
    5. Roberto Cominetti & José R. Correa & Nicolás E. Stier-Moses, 2009. "The Impact of Oligopolistic Competition in Networks," Operations Research, INFORMS, vol. 57(6), pages 1421-1437, December.
    6. Marco Scarsini & Tristan Tomala, 2012. "Repeated congestion games with bounded rationality," International Journal of Game Theory, Springer;Game Theory Society, vol. 41(3), pages 651-669, August.
    7. Le Breton, Michel & Shapoval, Alexander & Weber, Shlomo, 2021. "A game-theoretical model of the landscape theory," Journal of Mathematical Economics, Elsevier, vol. 92(C), pages 41-46.
    8. Kukushkin, Nikolai, 2019. "Quasiseparable aggregation in games with common local utilities," MPRA Paper 93588, University Library of Munich, Germany.
    9. Epstein, Amir & Feldman, Michal & Mansour, Yishay, 2009. "Efficient graph topologies in network routing games," Games and Economic Behavior, Elsevier, vol. 66(1), pages 115-125, May.
    10. Naimzada, A.K. & Raimondo, Roberto, 2018. "Heterogeneity and chaos in congestion games," Applied Mathematics and Computation, Elsevier, vol. 335(C), pages 278-291.
    11. Knight, Vincent A. & Harper, Paul R., 2013. "Selfish routing in public services," European Journal of Operational Research, Elsevier, vol. 230(1), pages 122-132.
    12. Zijun Wu & Rolf H. Moehring & Chunying Ren & Dachuan Xu, 2020. "A convergence analysis of the price of anarchy in atomic congestion games," Papers 2007.14769, arXiv.org, revised Dec 2021.
    13. György Dósa & Leah Epstein, 2019. "Quality of strong equilibria for selfish bin packing with uniform cost sharing," Journal of Scheduling, Springer, vol. 22(4), pages 473-485, August.
    14. Chenlan Wang & Xuan Vinh Doan & Bo Chen, 2022. "Atomic congestion games with random players: network equilibrium and the price of anarchy," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 2123-2142, October.
    15. Tamer Başar & Quanyan Zhu, 2011. "Prices of Anarchy, Information, and Cooperation in Differential Games," Dynamic Games and Applications, Springer, vol. 1(1), pages 50-73, March.
    16. moldovanu, benny & Hoppe-Wewetzer, Heidrun C. & Ozdenoren, Emre, 2007. "Coarse Matching and Price Discrimination," CEPR Discussion Papers 6041, C.E.P.R. Discussion Papers.
    17. Samitha Samaranayake & Walid Krichene & Jack Reilly & Maria Laura Delle Monache & Paola Goatin & Alexandre Bayen, 2018. "Discrete-Time System Optimal Dynamic Traffic Assignment (SO-DTA) with Partial Control for Physical Queuing Networks," Transportation Science, INFORMS, vol. 52(4), pages 982-1001, August.
    18. Carmona, Guilherme & Podczeck, Konrad, 2014. "Existence of Nash equilibrium in games with a measure space of players and discontinuous payoff functions," Journal of Economic Theory, Elsevier, vol. 152(C), pages 130-178.
    19. Hota, Ashish R. & Garg, Siddharth & Sundaram, Shreyas, 2016. "Fragility of the commons under prospect-theoretic risk attitudes," Games and Economic Behavior, Elsevier, vol. 98(C), pages 135-164.
    20. Sandholm, William H., 2015. "Population Games and Deterministic Evolutionary Dynamics," Handbook of Game Theory with Economic Applications,, Elsevier.

    More about this item

    Keywords

    Network design games; Price of stability; Pure Nash equilibria;
    All these keywords.

    JEL classification:

    • C62 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Existence and Stability Conditions of Equilibrium
    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
    • D85 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Network Formation

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:gamebe:v:123:y:2020:i:c:p:359-376. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.