IDEAS home Printed from https://ideas.repec.org/p/hal/journl/hal-00268851.html
   My bibliography  Save this paper

Good neighbors are hard to find: computational complexity of network formation

Author

Listed:
  • Richard Baron

    (CREUSET - Centre de Recherche Economique de l'Université de Saint-Etienne - UJM - Université Jean Monnet - Saint-Étienne)

  • Jacques Durieu

    (CREUSET - Centre de Recherche Economique de l'Université de Saint-Etienne - UJM - Université Jean Monnet - Saint-Étienne)

  • Hans Haller

    (Department of economics - Virginia Polytechnic Institute and State University [Blacksburg])

  • Philippe Solal

    (CREUSET - Centre de Recherche Economique de l'Université de Saint-Etienne - UJM - Université Jean Monnet - Saint-Étienne)

  • Savani Rahul

    (Department of Computer Science [Warwick] - University of Warwick [Coventry])

Abstract

We investigate the computational complexity of several decision problems in a simple strategic game of network formation.We find that deciding if a player has a strategy that guarantees him a certain payoff against a given strategy profile of the other players is an NP-complete problem. Deciding if there exists a strategy profile that guarantees a certain aggregate payoff is also NP-complete. Deciding if there is a Nash equilibrium in pure strategies which guarantees a certain payoff to each player is NP-hard. The problem of deciding if a given strategy profile is a Nash equilibrium is investigated as well.

Suggested Citation

  • Richard Baron & Jacques Durieu & Hans Haller & Philippe Solal & Savani Rahul, 2008. "Good neighbors are hard to find: computational complexity of network formation," Post-Print hal-00268851, HAL.
    • Handle: RePEc:hal:journl:hal-00268851
    DOI: 10.1007/s10058-008-0043-x
    as

    Download full text from publisher

    To our knowledge, this item is not available for download. To find whether it is available, there are three options:
    1. Check below whether another version of this item is available online.
    2. Check on the provider's web page whether it is in fact available.
    3. Perform a search for a similarly titled item that would be available.

    Other versions of this item:

    References listed on IDEAS

    as
    1. Koller, Daphne & Megiddo, Nimrod & von Stengel, Bernhard, 1996. "Efficient Computation of Equilibria for Extensive Two-Person Games," Games and Economic Behavior, Elsevier, vol. 14(2), pages 247-259, June.
    2. Markus Mobius & Raphael Schoenle, 2006. "The Evolution of Work," NBER Working Papers 12694, National Bureau of Economic Research, Inc.
    3. T. Badics & E. Boros, 1998. "Minimization of Half-Products," Mathematics of Operations Research, INFORMS, vol. 23(3), pages 649-660, August.
    4. Haller, Hans & Sarangi, Sudipta, 2005. "Nash networks with heterogeneous links," Mathematical Social Sciences, Elsevier, vol. 50(2), pages 181-201, September.
    5. Berninghaus, Siegfried K. & Schwalbe, Ulrich, 1996. "Evolution, interaction, and Nash equilibria," Journal of Economic Behavior & Organization, Elsevier, vol. 29(1), pages 57-85, January.
    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. Demuynck, Thomas, 2011. "The computational complexity of rationalizing boundedly rational choice behavior," Journal of Mathematical Economics, Elsevier, vol. 47(4-5), pages 425-433.
    2. Gilles, Robert P. & Chakrabarti, Subhadip & Sarangi, Sudipta, 2012. "Nash equilibria of network formation games under consent," Mathematical Social Sciences, Elsevier, vol. 64(2), pages 159-165.
    3. Thomas Demuynck, 2014. "The computational complexity of rationalizing Pareto optimal choice behavior," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 42(3), pages 529-549, March.
    4. Sung, Shao-Chin & Dimitrov, Dinko, 2010. "Computational complexity in additive hedonic games," European Journal of Operational Research, Elsevier, vol. 203(3), pages 635-639, June.
    5. Rahmi İlkılıç & Hüseyin İkizler, 2019. "Equilibrium refinements for the network formation game," Review of Economic Design, Springer;Society for Economic Design, vol. 23(1), pages 13-25, June.
    6. Fabrice Talla Nobibon & Laurens Cherchye & Yves Crama & Thomas Demuynck & Bram De Rock & Frits C. R. Spieksma, 2016. "Revealed Preference Tests of Collectively Rational Consumption Behavior: Formulations and Algorithms," Operations Research, INFORMS, vol. 64(6), pages 1197-1216, December.

    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. Jacques Durieu & Hans Haller & Philippe Solal, 2011. "Nonspecific Networking," Games, MDPI, vol. 2(1), pages 1-27, February.
    2. repec:osf:socarx:h63mz_v1 is not listed on IDEAS
    3. Fernando A. Lozano & Mary J. Lopez, 2013. "Border Enforcement and Selection of Mexican Immigrants in the United States," Feminist Economics, Taylor & Francis Journals, vol. 19(1), pages 76-110, January.
    4. Sung, Shao-Chin & Dimitrov, Dinko, 2010. "Computational complexity in additive hedonic games," European Journal of Operational Research, Elsevier, vol. 203(3), pages 635-639, June.
    5. Pascal Billand & Christophe Bravard & Sudipta Sarangi, 2011. "Resources Flows Asymmetries in Strict Nash Networks with Partner Heterogeneity," Working Papers 1108, Groupe d'Analyse et de Théorie Economique Lyon St-Étienne (GATE Lyon St-Étienne), Université de Lyon.
    6. Bernhard von Stengel & Antoon van den Elzen & Dolf Talman, 2002. "Computing Normal Form Perfect Equilibria for Extensive Two-Person Games," Econometrica, Econometric Society, vol. 70(2), pages 693-715, March.
    7. Bravard, Christophe & Charroin, Liza & Touati, Corinne, 2017. "Optimal design and defense of networks under link attacks," Journal of Mathematical Economics, Elsevier, vol. 68(C), pages 62-79.
    8. Haller, Hans & Hoyer, Britta, 2019. "The common enemy effect under strategic network formation and disruption," Journal of Economic Behavior & Organization, Elsevier, vol. 162(C), pages 146-163.
    9. Michael D König & Stefano Battiston & Mauro Napoletano & Frank Schweitzer, 2008. "The Efficiency and Evolution of R&D Networks," Working Papers hal-00973077, HAL.
    10. Emek Basker & Timothy Simcoe, 2021. "Upstream, Downstream: Diffusion and Impacts of the Universal Product Code," Journal of Political Economy, University of Chicago Press, vol. 129(4), pages 1252-1286.
    11. Goeree, Jacob K. & Riedl, Arno & Ule, Aljaz, 2009. "In search of stars: Network formation among heterogeneous agents," Games and Economic Behavior, Elsevier, vol. 67(2), pages 445-466, November.
    12. Filippo Vergara Caffarelli, 2017. "One-Way Flow Networks with Decreasing Returns to Linking," Dynamic Games and Applications, Springer, vol. 7(2), pages 323-345, June.
    13. K. de Jaegher & J.J.A. Kamphorst, 2008. "Network formation with decreasing marginal benefits of information," Working Papers 08-16, Utrecht School of Economics.
    14. Andrea Galeotti, 2006. "One-way flow networks: the role of heterogeneity," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 29(1), pages 163-179, September.
    15. repec:spo:wpmain:info:hdl:2441/9933 is not listed on IDEAS
    16. Pascal Billand & Christophe Bravard & Sudipta Sarangi, 2011. "Strict Nash networks and partner heterogeneity," International Journal of Game Theory, Springer;Game Theory Society, vol. 40(3), pages 515-525, August.
    17. Thomas J. Holmes & Matthew F. Mitchell, 2008. "A theory of factor allocation and plant size," RAND Journal of Economics, RAND Corporation, vol. 39(2), pages 329-351, June.
    18. Gao Hongwei & Qiao Han & Sedakov Artem & Wang Lei, 2015. "A Dynamic Formation Procedure of Information Flow Networks," Journal of Systems Science and Information, De Gruyter, vol. 3(2), pages 97-110, April.
    19. repec:hal:wpspec:info:hdl:2441/9935 is not listed on IDEAS
    20. repec:spo:wpecon:info:hdl:2441/9935 is not listed on IDEAS
    21. Haller, Hans, 2012. "Network extension," Mathematical Social Sciences, Elsevier, vol. 64(2), pages 166-172.
    22. Pascal Billand & Christophe Bravard & Sudipta Sarangi & J. Kamphorst, 2011. "Confirming information flows in networks," Post-Print halshs-00672351, HAL.
    23. Billand, Pascal & Bravard, Christophe & Sarangi, Sudipta, 2012. "Existence of Nash networks and partner heterogeneity," Mathematical Social Sciences, Elsevier, vol. 64(2), pages 152-158.
    24. Matthew F. Mitchell, 2005. "Specialization And The Skill Premium In The 20th Century," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 46(3), pages 935-955, August.

    More about this item

    Keywords

    Strategic games · Network formation · Computational complexity;

    JEL classification:

    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
    • D02 - Microeconomics - - General - - - Institutions: Design, Formation, Operations, and Impact
    • 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:hal:journl:hal-00268851. 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: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    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.