On the NP-Completeness of Finding an Optimal Strategy in Games with Common Payoffs
AbstractGiven a finite game with common payoffs (i.e. the players have completely common interests), we show that the problem of determining whether there exists a joint strategy where each player nets at least k is NP-complete.
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.
Bibliographic InfoPaper provided by EconWPA in its series Game Theory and Information with number 0004011.
Length: 7 pages
Date of creation: 22 Nov 2000
Date of revision:
Note: Type of Document - PDF; prepared on Unix; pages: 7; figures: included
Contact details of provider:
Web page: http://126.96.36.199
common payoff games; NP-completeness;
Other versions of this item:
- Francis Chu & Joseph Halpern, 2001. "On the NP-completeness of finding an optimal strategy in games with common payoffs," International Journal of Game Theory, Springer, vol. 30(1), pages 99-106.
- 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
This paper has been announced in the following NEP Reports:
- NEP-ALL-2001-02-14 (All new papers)
You can help add them by filling out this form.
CitEc Project, subscribe to its RSS feed for this item.
- 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.
- Demuynck, Thomas, 2011. "The computational complexity of rationalizing boundedly rational choice behavior," Journal of Mathematical Economics, Elsevier, vol. 47(4-5), pages 425-433.
- Tim Roughgarden, 2010. "Computing equilibria: a computational complexity perspective," Economic Theory, Springer, vol. 42(1), pages 193-236, January.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (EconWPA).
If references are entirely missing, you can add them using this form.