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

Richard Baron, Jacques Durieu (), Hans Haller, Philippe Solal and Savani Rahul
Additional contact information
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]
Savani Rahul: Department of Computer Science [Warwick] - University of Warwick [Coventry]

Post-Print from HAL

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.

Keywords: Strategic; games; ·; Network; formation; ·; Computational; complexity (search for similar items in EconPapers)
Date: 2008-03-11
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Published in Review of Economic Design, 2008, 12 (1), pp.1-19. ⟨10.1007/s10058-008-0043-x⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
Journal Article: Good neighbors are hard to find: computational complexity of network formation (2008)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-00268851

DOI: 10.1007/s10058-008-0043-x

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().