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

    for a different version of it.

    References listed on IDEAS

    as
    1. Jackson, Matthew O. & van den Nouweland, Anne, 2005. "Strongly stable networks," Games and Economic Behavior, Elsevier, vol. 51(2), pages 420-444, May.
    2. Goyal, Sanjeev & Joshi, Sumit, 2004. "Erratum to "Networks of collaboration in oligopoly": [Games Econ. Behav. 43 (1) (2003) 57-85]," Games and Economic Behavior, Elsevier, vol. 46(1), pages 219-219, January.
    3. Roger B. Myerson, 1977. "Graphs and Cooperation in Games," Mathematics of Operations Research, INFORMS, vol. 2(3), pages 225-229, August.
    4. Venkatesh Bala & Sanjeev Goyal, 2000. "A Noncooperative Model of Network Formation," Econometrica, Econometric Society, vol. 68(5), pages 1181-1230, September.
    5. 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.
    6. 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.
    7. Matthew O. Jackson, 2003. "A Survey of Models of Network Formation: Stability and Efficiency," Game Theory and Information 0303011, University Library of Munich, Germany.
    8. 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. 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.
    2. 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.
    3. 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.
    4. Sofia Priazhkina & Samuel Palmer & Pablo Martín-Ramiro & Román Orús & Samuel Mugel & Vladimir Skavysh, 2024. "Digital Payments in Firm Networks: Theory of Adoption and Quantum Algorithm," Staff Working Papers 24-17, Bank of Canada.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Michael Kosfeld, "undated". "Network Experiments," IEW - Working Papers 152, Institute for Empirical Research in Economics - University of Zurich.
    10. Bougheas, Spiros, 2022. "Contagion in networks: Stability and efficiency," Mathematical Social Sciences, Elsevier, vol. 115(C), pages 64-77.
    11. 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.
    12. repec:ehu:ikerla:19437 is not listed on IDEAS
    13. Bloch, Francis & Jackson, Matthew O., 2007. "The formation of networks with transfers among players," Journal of Economic Theory, Elsevier, vol. 133(1), pages 83-110, March.
    14. Roldan, Flavia, 2011. "Covert networks and antitrust policy," IESE Research Papers D/932, IESE Business School.
    15. Roldan, Flavia, 2010. "Collusive networks in market-sharing agreements under the presence of an antitrust authority," IESE Research Papers D/854, IESE Business School.
    16. 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.
    17. 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.
    18. Carlos Ponce & Flavia Roldán, 2016. "Antitrust policies in network environments," Documentos de Investigación 112, Universidad ORT Uruguay. Facultad de Administración y Ciencias Sociales.
    19. Alexander Elbittar & Rodrigo Harrison & Roberto Muñoz, 2007. "Network Structure in a Link-formation Game: An Experimental Study," Working Papers DTE 405, CIDE, División de Economía.
    20. Bayer, Péter & Guerdjikova, Ani, 2024. "Optimism leads to optimality: Ambiguity in network formation," Journal of Economic Dynamics and Control, Elsevier, vol. 168(C).
    21. Subhadip Chakrabarti & Supanit Tangsangasaksri, 2014. "Network Topology, Higher Orders Of Stability And Efficiency," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 16(04), pages 1-21.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

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