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

Strong price of anarchy

Author

Listed:
  • Andelman, Nir
  • Feldman, Michal
  • Mansour, Yishay

Abstract

A strong equilibrium is a pure Nash equilibrium which is resilient to deviations by coalitions. We define the strong price of anarchy (SPoA) to be the ratio of the worst strong equilibrium to the social optimum. Differently from the Price of Anarchy (defined as the ratio of the worst Nash Equilibrium to the social optimum), it quantifies the loss incurred from the lack of a central designer in settings that allow for coordination. We study the SPoA in two settings, namely job scheduling and network creation. In the job scheduling game we show that for unrelated machines the SPoA can be bounded as a function of the number of machines and the size of the coalition. For the network creation game we show that the SPoA is at most 2. In both cases we show that a strong equilibrium always exists, except for a well defined subset of network creation games.

Suggested Citation

  • Andelman, Nir & Feldman, Michal & Mansour, Yishay, 2009. "Strong price of anarchy," Games and Economic Behavior, Elsevier, vol. 65(2), pages 289-317, March.
    • Handle: RePEc:eee:gamebe:v:65:y:2009:i:2:p:289-317
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899-8256(08)00068-7
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Hervé Moulin & Scott Shenker, 2001. "Strategyproof sharing of submodular costs:budget balance versus efficiency," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 18(3), pages 511-533.
    2. Dutta, Bhaskar & Mutuswami, Suresh, 1997. "Stable Networks," Journal of Economic Theory, Elsevier, vol. 76(2), pages 322-344, October.
      • Dutta, Bhaskar & Mutuswami, Suresh, 1996. "Stable Networks," Working Papers 971, California Institute of Technology, Division of the Humanities and Social Sciences.
    3. Holzman, Ron & Law-Yone, Nissan, 1997. "Strong Equilibrium in Congestion Games," Games and Economic Behavior, Elsevier, vol. 21(1-2), pages 85-101, October.
    4. Holzman, Ron & Law-yone (Lev-tov), Nissan, 2003. "Network structure and strong equilibrium in route selection games," Mathematical Social Sciences, Elsevier, vol. 46(2), pages 193-205, October.
    5. Igal Milchtaich, 1998. "Crowding games are sequentially solvable," International Journal of Game Theory, Springer;Game Theory Society, vol. 27(4), pages 501-509.
    6. Rachel E. Kranton & Deborah F. Minehart, 2001. "A Theory of Buyer-Seller Networks," American Economic Review, American Economic Association, vol. 91(3), pages 485-508, June.
    7. Bernheim, B. Douglas & Peleg, Bezalel & Whinston, Michael D., 1987. "Coalition-Proof Nash Equilibria I. Concepts," Journal of Economic Theory, Elsevier, vol. 42(1), pages 1-12, June.
    8. Monderer, Dov & Shapley, Lloyd S., 1996. "Potential Games," Games and Economic Behavior, Elsevier, vol. 14(1), pages 124-143, 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. Krzysztof R. Apt & Bart Keijzer & Mona Rahn & Guido Schäfer & Sunil Simon, 2017. "Coordination games on graphs," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(3), pages 851-877, August.
    2. Rosner, Shaul & Tamir, Tami, 2023. "Scheduling games with rank-based utilities," Games and Economic Behavior, Elsevier, vol. 140(C), pages 229-252.
    3. Cong Chen & Yinfeng Xu, 0. "Coordination mechanisms for scheduling selfish jobs with favorite machines," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-33.
    4. Jasper Jong & Marc Uetz, 2020. "The quality of equilibria for set packing and throughput scheduling games," International Journal of Game Theory, Springer;Game Theory Society, vol. 49(1), pages 321-344, March.
    5. Martin Hoefer, 2013. "Strategic cooperation in cost sharing games," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(1), pages 29-53, February.
    6. 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.
    7. Harks, Tobias & Klimm, Max, 2015. "Equilibria in a class of aggregative location games," Journal of Mathematical Economics, Elsevier, vol. 61(C), pages 211-220.
    8. Cong Chen & Yinfeng Xu, 2020. "Coordination mechanisms for scheduling selfish jobs with favorite machines," Journal of Combinatorial Optimization, Springer, vol. 40(2), pages 333-365, August.
    9. 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.
    10. 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.
    11. Tobias Harks & Max Klimm & Rolf Möhring, 2013. "Strong equilibria in games with the lexicographical improvement property," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(2), pages 461-482, May.
    12. Tobias Harks & Martin Hoefer & Anja Schedel & Manuel Surek, 2021. "Efficient Black-Box Reductions for Separable Cost Sharing," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 134-158, February.
    13. 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.
    14. 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.
    15. Michal Feldman & Tami Tamir, 2012. "Conflicting Congestion Effects in Resource Allocation Games," Operations Research, INFORMS, vol. 60(3), pages 529-540, June.
    16. Eleonora Braggion & Nicola Gatti & Roberto Lucchetti & Tuomas Sandholm & Bernhard von Stengel, 2020. "Strong Nash equilibria and mixed strategies," International Journal of Game Theory, Springer;Game Theory Society, vol. 49(3), pages 699-710, September.
    17. Tobias Harks & Max Klimm, 2012. "On the Existence of Pure Nash Equilibria in Weighted Congestion Games," Mathematics of Operations Research, INFORMS, vol. 37(3), pages 419-436, August.
    18. Leah Epstein & Sven O. Krumke & Asaf Levin & Heike Sperber, 2011. "Selfish bin coloring," Journal of Combinatorial Optimization, Springer, vol. 22(4), pages 531-548, November.

    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. 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. Milchtaich, Igal & Winter, Eyal, 2002. "Stability and Segregation in Group Formation," Games and Economic Behavior, Elsevier, vol. 38(2), pages 318-346, February.
    3. Jackson, Matthew O. & Zenou, Yves, 2015. "Games on Networks," Handbook of Game Theory with Economic Applications,, Elsevier.
    4. Page Jr., Frank H. & Wooders, Myrna, 2009. "Strategic basins of attraction, the path dominance core, and network formation games," Games and Economic Behavior, Elsevier, vol. 66(1), pages 462-487, May.
    5. Hellmann, Tim & Staudigl, Mathias, 2014. "Evolution of social networks," European Journal of Operational Research, Elsevier, vol. 234(3), pages 583-596.
    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. Igal Milchtaich, 2015. "Network topology and equilibrium existence in weighted network congestion games," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(3), pages 515-541, August.
    8. Yannai A. Gonczarowski & Moshe Tennenholtz, 2014. "Noncooperative Market Allocation and the Formation of Downtown," Discussion Paper Series dp663, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    9. Tobias Harks & Max Klimm & Rolf Möhring, 2013. "Strong equilibria in games with the lexicographical improvement property," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(2), pages 461-482, May.
    10. Kukushkin, Nikolai S., 2017. "Strong Nash equilibrium in games with common and complementary local utilities," Journal of Mathematical Economics, Elsevier, vol. 68(C), pages 1-12.
    11. Yannai A. Gonczarowski & Moshe Tennenholtz, 2014. "Cascading to Equilibrium: Hydraulic Computation of Equilibria in Resource Selection Games," Discussion Paper Series dp673, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    12. Ron Holzman & Dov Monderer, 2015. "Strong equilibrium in network congestion games: increasing versus decreasing costs," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(3), pages 647-666, August.
    13. Rodrigo J. Harrison & Roberto Munoz, 2003. "Stability and Equilibrium Selection in a Link Formation Game," Game Theory and Information 0306004, University Library of Munich, Germany.
    14. Sergio Currarini & Carmen Marchiori & Alessandro Tavoni, 2016. "Network Economics and the Environment: Insights and Perspectives," Environmental & Resource Economics, Springer;European Association of Environmental and Resource Economists, vol. 65(1), pages 159-189, September.
    15. Slikker, M. & Gilles, R.P. & Norde, H.W. & Tijs, S.H., 2000. "Directed Communication Networks," Discussion Paper 2000-84, Tilburg University, Center for Economic Research.
    16. Jean-François Caulier & Ana Mauleon & Vincent Vannetelbosch, 2013. "Contractually stable networks," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(2), pages 483-499, May.
    17. Roland Pongou & Roberto Serrano, 2009. "A dynamic theory of fidelity networks with an application to the spread of HIV/AIDS," Working Papers 2009-03, Instituto Madrileño de Estudios Avanzados (IMDEA) Ciencias Sociales.
    18. Mark Voorneveld & Peter Borm & Freek Van Megen & Stef Tijs & Giovanni Facchini, 1999. "Congestion Games And Potentials Reconsidered," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 1(03n04), pages 283-299.
    19. Gilles, R.P. & Sarangi, S., 2003. "The Role of Trust in Costly Network Formation," Discussion Paper 2003-53, Tilburg University, Center for Economic Research.
    20. Xujin Chen & Zhuo Diao & Xiaodong Hu, 2022. "On weak Pareto optimality of nonatomic routing networks," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 1705-1723, October.

    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:65:y:2009:i:2:p:289-317. 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.