Good neighbors are hard to find: computational complexity of network formation
Author
Abstract
(This abstract was borrowed from another version of this item.)
Suggested Citation
DOI: 10.1007/s10058-008-0043-x
Download full text from publisher
As the access to this document is restricted, you may want to look for a different version below or search for a different version of it.
Other versions of this item:
- 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.
References listed on IDEAS
- 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.
- Markus Mobius & Raphael Schoenle, 2006.
"The Evolution of Work,"
NBER Working Papers
12694, National Bureau of Economic Research, Inc.
- Markus Mobius & Raphael Schoenle, 2006. "The Evolution of Work," Working Papers 25, Brandeis University, Department of Economics and International Business School.
- T. Badics & E. Boros, 1998. "Minimization of Half-Products," Mathematics of Operations Research, INFORMS, vol. 23(3), pages 649-660, August.
- Haller, Hans & Sarangi, Sudipta, 2005. "Nash networks with heterogeneous links," Mathematical Social Sciences, Elsevier, vol. 50(2), pages 181-201, September.
- Berninghaus, Siegfried K. & Schwalbe, Ulrich, 1996. "Evolution, interaction, and Nash equilibria," Journal of Economic Behavior & Organization, Elsevier, vol. 29(1), pages 57-85, January.
Citations
Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
Cited by:
- 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.
- Thomas DEMUYNCK, 2011. "The computational complexity of rationalizing Pareto optimal choice behavior," Working Papers of Department of Economics, Leuven ces11.13, KU Leuven, Faculty of Economics and Business (FEB), Department of Economics, Leuven.
- Thomas Demuynck, 2014. "The computational complexity of rationalizing Pareto optimal choice behavior," ULB Institutional Repository 2013/251999, ULB -- Universite Libre de Bruxelles.
- 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.
- Sung, Shao-Chin & Dimitrov, Dinko, 2008. "Computational Complexity in Additive Hedonic Games," Discussion Papers in Economics 6430, University of Munich, Department of Economics.
- Sung, Shao Chin & Dimitrov, Dinko, 2008. "Computational Complexity in Additive Hedonic Games," Coalition Theory Network Working Papers 46655, Fondazione Eni Enrico Mattei (FEEM).
- Dinko Dimitrov & Shao-Chin Sung, 2008. "Computational Complexity in Additive Hedonic Games," Working Papers 2008.98, Fondazione Eni Enrico Mattei.
- 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.
- 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.
- Demuynck, Thomas, 2011.
"The computational complexity of rationalizing boundedly rational choice behavior,"
Journal of Mathematical Economics, Elsevier, vol. 47(4-5), pages 425-433.
- Thomas Demuynck, 2011. "The computational complexity of rationalizing boundedly rational choice behavior," ULB Institutional Repository 2013/252242, ULB -- Universite Libre de Bruxelles.
- 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.
- Robert P. Gilles & Subhadip Chakrabarti & Sudipta Sarangi, 2011. "Nash Equilibria of Network Formation Games under Consent," Economics Working Papers 11-03, Queen's Management School, Queen's University Belfast.
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.- Jacques Durieu & Hans Haller & Philippe Solal, 2011.
"Nonspecific Networking,"
Games, MDPI, vol. 2(1), pages 1-27, February.
- Jacques Durieu & Hans Haller & Philippe Solal, 2004. "Nonspecific Networking," Game Theory and Information 0403005, University Library of Munich, Germany.
- Jacques Durieu & Hans Haller & Philippe Solal, 2011. "Nonspecific networking," Post-Print halshs-00667662, HAL.
- Billand, Pascal & Bravard, Christophe & Sarangi, Sudipta, 2012.
"Existence of Nash networks and partner heterogeneity,"
Mathematical Social Sciences, Elsevier, vol. 64(2), pages 152-158.
- Pascal Billand & Christophe Bravard & Sudipta Sarangi, 2011. "Existence of Nash Networks and Partner Heterogeneity," Post-Print halshs-00574277, HAL.
- Pascal Billand & Christophe Bravard & Sudipta Sarangi, 2011. "Existence of Nash Networks and Partner Heterogeneity," Working Papers 1111, Groupe d'Analyse et de Théorie Economique Lyon St-Étienne (GATE Lyon St-Étienne), Université de Lyon.
- Pascal Billand & Christophe Bravard & Sudipta Sarangi, 2012. "Existence of Nash Networks and Partner Heterogeneity," Post-Print halshs-00728035, HAL.
- Pascal Billand & Christophe Bravard & Sudipta Sarangi, 2011. "Existence of Nash Networks and Partner Heterogeneity," Post-Print halshs-00590315, HAL.
- Billand, Pascal & Bravard, Christophe & Iyengar, Sitharama S. & Kumar, Rajnish & Sarangi, Sudipta, 2016.
"Network connectivity under node failure,"
Economics Letters, Elsevier, vol. 149(C), pages 164-167.
- Pascal Billand & Christophe Bravard & Sitharama S. Iyengar & Rajnish Kumar & Sudipta Sarangi, 2016. "Network connectivity under node failure," Post-Print hal-01404559, HAL.
- 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.
- J. Vandenbossche & T. Demuynck & -, 2010. "Network formation with heterogeneous agents and absolute friction," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 10/642, Ghent University, Faculty of Economics and Business Administration.
- Thomas Demuynck & Joost Vandenbossche, 2013. "Network formation with heterogeneous agents and absolute friction," ULB Institutional Repository 2013/252237, ULB -- Universite Libre de Bruxelles.
- 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.
- Lozano, Fernando A. & Lopez, Mary J., 2010. "Border Enforcement and Selection of Mexican Immigrants in the United States," IZA Discussion Papers 4898, Institute of Labor Economics (IZA).
- 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.
- Sung, Shao-Chin & Dimitrov, Dinko, 2008. "Computational Complexity in Additive Hedonic Games," Discussion Papers in Economics 6430, University of Munich, Department of Economics.
- Dinko Dimitrov & Shao-Chin Sung, 2008. "Computational Complexity in Additive Hedonic Games," Working Papers 2008.98, Fondazione Eni Enrico Mattei.
- Sung, Shao Chin & Dimitrov, Dinko, 2008. "Computational Complexity in Additive Hedonic Games," Coalition Theory Network Working Papers 46655, Fondazione Eni Enrico Mattei (FEEM).
- 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.
- Pascal Billand & Christophe Bravard & Sudipta Sarangi, 2011. "Resources Flows Asymmetries in Strict Nash Networks with Partner Heterogeneity," Post-Print halshs-00574256, HAL.
- Bernhard Kittel & Wolfgang Luhan, 2013. "Decision making in networks: an experiment on structure effects in a group dictator game," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 40(1), pages 141-154, January.
- 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.
- von Stengel, B. & van den Elzen, A.H. & Talman, A.J.J., 1997. "Computing normal form perfect equilibria for extensive two-person games," Other publications TiSEM 4487e2bf-5bc1-47d3-819f-2, Tilburg University, School of Economics and Management.
- von Stengel, B. & van den Elzen, A.H. & Talman, A.J.J., 2002. "Computing normal form perfect equilibria for extensive two-person games," Other publications TiSEM 9f112346-b587-47f3-ad2e-6, Tilburg University, School of Economics and Management.
- von Stengel, B. & van den Elzen, A.H. & Talman, A.J.J., 1997. "Computing normal form perfect equilibria for extensive two-person games," Research Memorandum 752, Tilburg University, School of Economics and Management.
- 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.
- Christophe Bravard & Liza Charroin & Corinne Touati, 2015. "Optimal design and defense of networks under link attacks," Working Papers 1519, Groupe d'Analyse et de Théorie Economique Lyon St-Étienne (GATE Lyon St-Étienne), Université de Lyon.
- Christophe Bravard & Liza Charroin & Corinne Touati, 2017. "Optimal Design and Defense of Networks Under Link Attacks," Post-Print hal-01384998, HAL.
- Christophe Bravard & Liza Charroin & Corinne Touati, 2016. "Optimal design and defense of networks under link attacks," Post-Print halshs-01411520, HAL.
- Christophe Bravard & Liza Charroin & Corinne Touati, 2015. "Optimal design and defense of networks under link attacks," Working Papers halshs-01176928, HAL.
- Pascal Billand & Christophe Bravard & Sudipta Sarangi & J. Kamphorst, 2011.
"Confirming information flows in networks,"
Post-Print
halshs-00672351, HAL.
- Pascal Billand & Christophe Bravard & J. Kamphorst & Sudipta Sarangi, 2013. "Confirming Information flows in Networks," Post-Print halshs-00878931, HAL.
- Billand, Pascal & Bravard, Christophe & Kamphorst, Jurjen J.A. & Sarangi, Sudipta, 2013. "Confirming Information Flows in Networks," MPRA Paper 45835, University Library of Munich, Germany.
- Sudipta Sarangi & Pascal Billand & Christophe Bravard & Jurjen Kamphorst, 2012. "Confirming Information Flows in Networks," Departmental Working Papers 2012-02, Department of Economics, Louisiana State University.
- Pascal Billand & Christophe Bravard & Jurjen Kamphorst & Sudipta Sarangi, 2012. "Confirming Information Flows in Networks," Tinbergen Institute Discussion Papers 12-019/1, Tinbergen Institute.
- Billand, P. & Bravard, C. & Kamphorst, J. & Sarangi, S., 2013. "Confirming information flows in networks," Working Papers 2013-06, Grenoble Applied Economics Laboratory (GAEL).
- 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.
- Frey Vincenz & Corten Rense & Buskens Vincent, 2012. "Equilibrium Selection in Network Coordination Games: An Experimental Study," Review of Network Economics, De Gruyter, vol. 11(3), pages 1-28, September.
- Michael D König & Stefano Battiston & Mauro Napoletano & Frank Schweitzer, 2008.
"The Efficiency and Evolution of R&D Networks,"
Working Papers
hal-00973077, HAL.
- Michael D. König & tefano Battiston & Mauro Napoletano & Frank Schweitzer, 2008. "The efficiency and evolution of R&D Networks," Documents de Travail de l'OFCE 2008-31, Observatoire Francais des Conjonctures Economiques (OFCE).
- Mauro Napoletano & Stefano Battiston & Michael König & Frank Schweitzer, 2008. "The Efficiency and Evolution of R&D Networks," Sciences Po publications 08/95, Sciences Po.
- Michael D. König & S. Battiston & M. Napoletano & F. Schweitzer, 2008. "The Efficiency and Evolution of R&D Networks," CER-ETH Economics working paper series 08/95, CER-ETH - Center of Economic Research (CER-ETH) at ETH Zurich.
- Mauro Napoletano & Stefano Battiston & Michael D König & Frank Schweitzer, 2008. "The efficiency and evolution of R&D Networks," Working Papers hal-01066189, HAL.
- Michael D König & Stefano Battiston & Mauro Napoletano & Frank Schweitzer, 2008. "The efficiency and evolution of R&D Networks," Post-Print hal-01053618, HAL.
- Mauro Napoletano & Stefano Battiston & Michael König & Frank Schweitzer, 2008. "The efficiency and evolution of R&D Networks," Sciences Po publications 2008-31, Sciences Po.
- Michael D König & Stefano Battiston & Mauro Napoletano & Frank Schweitzer, 2008. "The Efficiency and Evolution of R&D Networks," SciencePo Working papers Main hal-00973077, HAL.
- Michael D König & Stefano Battiston & Mauro Napoletano & Frank Schweitzer, 2008. "The efficiency and evolution of R&D Networks," SciencePo Working papers Main hal-01053618, HAL.
- Mauro Napoletano & Stefano Battiston & Michael D König & Frank Schweitzer, 2008. "The efficiency and evolution of R&D Networks," SciencePo Working papers Main hal-01066189, HAL.
- Michael König & Stefano Battiston & Mauro Napoletano & Frank Schweitzer, 2008. "The efficiency and evolution of R&D Networks," Sciences Po publications info:hdl:2441/9933, Sciences Po.
- 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.
- Emek Basker & Timothy Simcoe, 2017. "Upstream, Downstream: Diffusion and Impacts of the Universal Product Code," NBER Working Papers 24040, National Bureau of Economic Research, Inc.
- Emek Basker & Timothy Simcoe, 2017. "Upstream, Downstream: Diffusion and Impacts of the Universal Product Code," Working Papers 17-66, Center for Economic Studies, U.S. Census Bureau.
- Lasse Kliemann, 2011. "The Price of Anarchy for Network Formation in an Adversary Model," Games, MDPI, vol. 2(3), pages 1-31, August.
- 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.
- Goeree, J.K. & Riedl, A.M. & Ule, A., 2005. "In search of stars: network formation among heterogeneous agents," Research Memorandum 033, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
- Aljaž Ule & Jacob K. Goeree & Arno Riedl, 2007. "In Search of Stars: Network Formation among Heterogeneous Agents," Working Papers 2007.65, Fondazione Eni Enrico Mattei.
- Ule, Aljaz & Goeree, Jacob K. & Riedl, Arno, 2007. "In Search of Stars: Network Formation among Heterogeneous Agents," Coalition Theory Network Working Papers 9099, Fondazione Eni Enrico Mattei (FEEM).
- Goeree, Jacob K. & Riedl, Arno & Ule, Aljaz, 2005. "In Search of Stars: Network Formation among Heterogeneous Agents," IZA Discussion Papers 1754, Institute of Labor Economics (IZA).
- Gerard van der Laan & A.F. Tieman, 1996. "Evolutionary Game Theory and the Modelling of Economic Behavior," Tinbergen Institute Discussion Papers 96-172/8, Tinbergen Institute.
- Ping Sun & Elena Parilina, 2022. "Impact of Utilities on the Structures of Stable Networks with Ordered Group Partitioning," Dynamic Games and Applications, Springer, vol. 12(4), pages 1131-1162, December.
- Corine M. Laan & Ana Isabel Barros & Richard J. Boucherie & Herman Monsuur & Judith Timmer, 2019. "Solving partially observable agent‐intruder games with an application to border security problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(2), pages 174-190, March.
More about this item
Keywords
Strategic games; Network formation; Computational complexity; C72; D02; D85;All these keywords.
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 statisticsCorrections
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:spr:reecde:v:12:y:2008:i:1:p:1-19. 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.