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

DOI10.1007/s10058-008-0043-xzbMath1140.91325OpenAlexW2040737867MaRDI QIDQ934968

Philippe Solal, Jacques Durieu, Rahul Savani, Richard Baron, Hans H. Haller

Publication date: 31 July 2008

Published in: Review of Economic Design (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10058-008-0043-x

zbMATH Keywords

computational complexitynetwork formationstrategic games

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decision theory for games (91A35)

Related Items

Revealed Preference Tests of Collectively Rational Consumption Behavior: Formulations and Algorithms, The computational complexity of rationalizing boundedly rational choice behavior, Nash equilibria of network formation games under consent, Equilibrium refinements for the network formation game, Computational complexity in additive hedonic games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• (Non-)existence and scope of Nash networks
• New complexity results about Nash equilibria
• Collusive behavior in noncooperative epsilon-equilibria of oligopolies with long but finite lives
• Nash and correlated equilibria: Some complexity considerations
• The complexity of two-person zero-sum games in extensive form
• On the complexity of the parity argument and other inefficient proofs of existence
• Efficient computation of equilibria for extensive two-person games
• The statistical mechanics of best-response strategy revision
• Network potentials
• Network formation with heterogeneous players
• Complexity and stochastic evolution of dyadic networks
• Nash networks with heterogeneous links
• Minimization of Half-Products
• On a network creation game
• The Price of Stability for Network Design with Fair Cost Allocation
• Near-optimal network design with selfish agents
• Monitoring Cooperative Agreements in a Repeated Principal-Agent Relationship
• A Noncooperative Model of Network Formation
• A deductive approach to friendship networks
• Computing correlated equilibria in multi-player games