Fiche du document
11 mars 2008
- handle: 10670/1.gegb4o
- hal: hal-00268851
- doi: 10.1007/s10058-008-0043-x
Ce document est lié à :
info:eu-repo/semantics/altIdentifier/doi/10.1007/s10058-008-0043-x
Sujets proches
Military strategy Decision (Psychology) Decision processes Making decisions Decision analysis Management--Decision making Deciding Management decisionsCiter ce document
Richard Baron et al., « Good neighbors are hard to find: computational complexity of network formation », HAL-SHS : économie et finance, ID : 10.1007/s10058-008-0043-x
Métriques
Partage / Export
Résumé
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.