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. 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.
    3. Di Feng & Bettina Klaus, 2022. "Preference revelation games and strict cores of multiple‐type housing market problems," International Journal of Economic Theory, The International Society for Economic Theory, vol. 18(1), pages 61-76, March.
    4. Raimondo, Roberto, 2020. "Pathwise smooth splittable congestion games and inefficiency," Journal of Mathematical Economics, Elsevier, vol. 86(C), pages 15-23.
    5. Alexandre Belloni & Changrong Deng & Saša Pekeč, 2017. "Mechanism and Network Design with Private Negative Externalities," Operations Research, INFORMS, vol. 65(3), pages 577-594, June.
    6. Moulin, Hervé, 2014. "Pricing traffic in a spanning network," Games and Economic Behavior, Elsevier, vol. 86(C), pages 475-490.
    7. 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.
    8. 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.
    9. 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.
    10. Chen, Enxian & Qiao, Lei & Sun, Xiang & Sun, Yeneng, 2022. "Robust perfect equilibrium in large games," Journal of Economic Theory, Elsevier, vol. 201(C).
    11. Correa, José R. & Schulz, Andreas S. & Stier-Moses, Nicolás E., 2008. "A geometric approach to the price of anarchy in nonatomic congestion games," Games and Economic Behavior, Elsevier, vol. 64(2), pages 457-469, November.
    12. Gusev, Vasily V., 2021. "Nash-stable coalition partition and potential functions in games with coalition structure," European Journal of Operational Research, Elsevier, vol. 295(3), pages 1180-1188.
    13. Deshi Ye & Lin Chen & Guochuan Zhang, 0. "On the price of anarchy of two-stage machine scheduling games," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-20.
    14. 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.
    15. 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.
    16. György Dósa & Leah Epstein, 2019. "Pareto optimal equilibria for selfish bin packing with uniform cost sharing," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 827-847, April.
    17. 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.
    18. José R. Correa & Andreas S. Schulz & Nicolás E. Stier-Moses, 2004. "Selfish Routing in Capacitated Networks," Mathematics of Operations Research, INFORMS, vol. 29(4), pages 961-976, November.
    19. 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.
    20. Jonathan Kluberg & Georgia Perakis, 2012. "Generalized Quantity Competition for Multiple Products and Loss of Efficiency," Operations Research, INFORMS, vol. 60(2), pages 335-350, April.

    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.