On the NP-Completeness of Finding an Optimal Strategy in Games with Common Payoffs

Francis C. Chu and Joseph Halpern ()
Additional contact information
Francis C. Chu: Cornell University

Game Theory and Information from University Library of Munich, Germany

Abstract: Given 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.

Keywords: common payoff games; NP-completeness (search for similar items in EconPapers)
JEL-codes: C70 C80 (search for similar items in EconPapers)
Pages: 7 pages
Date: 2000-11-22
Note: Type of Document - PDF; prepared on Unix; pages: 7; figures: included
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://econwpa.ub.uni-muenchen.de/econ-wp/game/papers/0004/0004011.pdf (application/pdf)

Related works:
Journal Article: On the NP-completeness of finding an optimal strategy in games with common payoffs (2001)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wpa:wuwpga:0004011

Access Statistics for this paper

More papers in Game Theory and Information from University Library of Munich, Germany
Bibliographic data for series maintained by EconWPA ( this e-mail address is bad, please contact ).