Good neighbors are hard to find: Computational complexity of network formation
From MaRDI portal
Publication:934968
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
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