IDEAS home Printed from https://ideas.repec.org/a/kap/netspa/v23y2023i3d10.1007_s11067-023-09588-x.html
   My bibliography  Save this article

The Calculation and Simulation of the Price of Anarchy for Network Formation Games

Author

Listed:
  • Shaun Lichter

    (Morgan Stanley)

  • Christopher Griffin

    (Penn State University)

  • Terry Friesz

    (Penn State University)

Abstract

We model the formation of networks as the result of a game where by players act selfishly to get the portfolio of links they desire most. The integration of player strategies into the network formation model is appropriate for organizational networks because in these smaller networks, dynamics are not random, but the result of intentional actions carried through by players maximizing their own objectives. This model is a better framework for the analysis of influences upon a network because it integrates the strategies of the players involved. We present an Integer Program that calculates the price of anarchy of this game by finding the worst stable graph and the best coordinated graph for this game. We simulate the formation of the network and calculated the simulated price of anarchy, which we find tends to be rather low.

Suggested Citation

  • Shaun Lichter & Christopher Griffin & Terry Friesz, 2023. "The Calculation and Simulation of the Price of Anarchy for Network Formation Games," Networks and Spatial Economics, Springer, vol. 23(3), pages 581-610, September.
    • Handle: RePEc:kap:netspa:v:23:y:2023:i:3:d:10.1007_s11067-023-09588-x
    DOI: 10.1007/s11067-023-09588-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11067-023-09588-x
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s11067-023-09588-x?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. Goyal, Sanjeev & Joshi, Sumit, 2003. "Networks of collaboration in oligopoly," Games and Economic Behavior, Elsevier, vol. 43(1), pages 57-85, April.
    2. Roger B. Myerson, 1977. "Graphs and Cooperation in Games," Mathematics of Operations Research, INFORMS, vol. 2(3), pages 225-229, August.
    3. Venkatesh Bala & Sanjeev Goyal, 2000. "A Noncooperative Model of Network Formation," Econometrica, Econometric Society, vol. 68(5), pages 1181-1230, September.
    4. Paul Belleflamme & Francis Bloch, 2004. "Market sharing agreements and collusive networks," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 45(2), pages 387-411, May.
    5. Charo I Del Genio & Hyunju Kim & Zoltán Toroczkai & Kevin E Bassler, 2010. "Efficient and Exact Sampling of Simple Graphs with Given Arbitrary Degree Sequence," PLOS ONE, Public Library of Science, vol. 5(4), pages 1-7, April.
    6. Matthew O. Jackson, 2003. "A Survey of Models of Network Formation: Stability and Efficiency," Game Theory and Information 0303011, University Library of Munich, Germany.
    7. Emily M. Jin & Michelle Girvan & M. E. J. Newman, 2001. "The Structure of Growing Social Networks," Working Papers 01-06-032, Santa Fe Institute.
    Full references (including those not matched with items on IDEAS)

    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. Alessio D'Ignazio & Emanuele Giovannetti, 2006. "From Exogenous To Endogenous Economic Networks: Internet Applications," Journal of Economic Surveys, Wiley Blackwell, vol. 20(5), pages 757-796, December.
    2. Norma Olaizola & Federico Valenciano, 2016. "From bilateral two-way to unilateral one-way flow link-formation," SERIEs: Journal of the Spanish Economic Association, Springer;Spanish Economic Association, vol. 7(2), pages 257-278, June.
    3. Pramod C. Mane & Kapil Ahuja & Nagarajan Krishnamurthy, 2020. "Stability, efficiency, and contentedness of social storage networks," Annals of Operations Research, Springer, vol. 287(2), pages 811-842, April.
    4. Olaizola Ortega, María Norma & Valenciano Llovera, Federico, 2016. "A Marginalist Model of Network Formation," IKERLANAK info:eu-repo/grantAgreeme, Universidad del País Vasco - Departamento de Fundamentos del Análisis Económico I.
    5. Michael Kosfeld, "undated". "Network Experiments," IEW - Working Papers 152, Institute for Empirical Research in Economics - University of Zurich.
    6. Marco Marini, 2007. "An Overview of Coalition & Network Formation Models for Economic Applications," Working Papers 0712, University of Urbino Carlo Bo, Department of Economics, Society & Politics - Scientific Committee - L. Stefanini & G. Travaglini, revised 2007.
    7. Joost Vandenbossche & Thomas Demuynck, 2013. "Network Formation with Heterogeneous Agents and Absolute Friction," Computational Economics, Springer;Society for Computational Economics, vol. 42(1), pages 23-45, June.
    8. 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.
    9. Navarro, Noemi, 2007. "Fair allocation in networks with externalities," Games and Economic Behavior, Elsevier, vol. 58(2), pages 354-364, February.
    10. Britta Hoyer & Kris De Jaegher, 2023. "Network disruption and the common-enemy effect," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(1), pages 117-155, March.
    11. Takács, Károly & Janky, Béla, 2007. "Smiling contributions: Social control in a public goods game with network decline," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 378(1), pages 76-82.
    12. Jackson, Matthew O. & Zenou, Yves, 2015. "Games on Networks," Handbook of Game Theory with Economic Applications,, Elsevier.
    13. Timo Hiller & Timo Hiller, 2013. "Peer Effects in Endogenous Networks," STICERD - Theoretical Economics Paper Series 564, Suntory and Toyota International Centres for Economics and Related Disciplines, LSE.
    14. repec:cep:stitep:/2013/564 is not listed on IDEAS
    15. Yannis M. Ioannides & Linda Datcher Loury, 2004. "Job Information Networks, Neighborhood Effects, and Inequality," Journal of Economic Literature, American Economic Association, vol. 42(4), pages 1056-1093, December.
    16. Marco A. Marini, 2007. "An Overview of Coalitions and Networks Formation Models for Economic Applications," Working Papers 0707, CREI Università degli Studi Roma Tre, revised 2007.
    17. Sumit Joshi & Poorvi Vora, 2013. "Weak and strong multimarket bidding rings," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 53(3), pages 657-696, August.
    18. Spagnolo, Giancarlo & Lippert, Steffen, 2004. "Networks of Relations," SSE/EFI Working Paper Series in Economics and Finance 570, Stockholm School of Economics, revised 04 Jun 2010.
    19. Shaun Lichter & Terry Friesz & Christopher Griffin & Amir Bagherzadeh, 2022. "Collaborative Network Topologies in Spatial Economies," Networks and Spatial Economics, Springer, vol. 22(3), pages 439-459, September.
    20. Filippo Vergara Caffarelli, 2009. "Networks with decreasing returns to linking," Temi di discussione (Economic working papers) 734, Bank of Italy, Economic Research and International Relations Area.
    21. Matthew O. Jackson, 2003. "A Survey of Models of Network Formation: Stability and Efficiency," Game Theory and Information 0303011, University Library of Munich, Germany.

    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:kap:netspa:v:23:y:2023:i:3:d:10.1007_s11067-023-09588-x. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.