On the NP-completeness of finding an optimal strategy in games with common payoffs
AbstractConsider a very simple class of (finite) games: after an initial move by nature, each player makes one move. Moreover, the players have common interests: at each node, all the players get the same payoff. We show that the problem of determining whether there exists a joint strategy where each player has an expected payoff of at least r is NP-complete as a function of the number of nodes in the extensive-form representation of the game.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
Bibliographic InfoArticle provided by Springer in its journal International Journal of Game Theory.
Volume (Year): 30 (2001)
Issue (Month): 1 ()
Note: Received January 2001/Final version May 1, 2001
Contact details of provider:
Web page: http://link.springer.de/link/service/journals/00182/index.htm
Other versions of this item:
- Francis C. Chu & Joseph Y. Halpern, 2000. "On the NP-Completeness of Finding an Optimal Strategy in Games with Common Payoffs," Game Theory and Information 0004011, EconWPA.
- C70 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - General
- C80 - Mathematical and Quantitative Methods - - Data Collection and Data Estimation Methodology; Computer Programs - - - General
You can help add them by filling out this form.
CitEc Project, subscribe to its RSS feed for this item.
- Tim Roughgarden, 2010. "Computing equilibria: a computational complexity perspective," Economic Theory, Springer, vol. 42(1), pages 193-236, January.
- Demuynck, Thomas, 2011. "The computational complexity of rationalizing boundedly rational choice behavior," Journal of Mathematical Economics, Elsevier, vol. 47(4-5), pages 425-433.
- F. Forges & B. von Stengel, 2002. "Computionally Efficient Coordination in Games Trees," THEMA Working Papers 2002-05, THEMA (THéorie Economique, Modélisation et Applications), Université de Cergy-Pontoise.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Guenther Eichhorn) or (Christopher F Baum).
If references are entirely missing, you can add them using this form.