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 EconWPA

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)
Date: 2000-11-22
Note: Type of Document - PDF; prepared on Unix; pages: 7; figures: included
View citations in EconPapers

Downloads: (external link)
http://129.3.20.41/eps/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: http://EconPapers.repec.org/RePEc:wpa:wuwpga:0004011

Access Statistics for this paper

More papers in Game Theory and Information from EconWPA
Series data maintained by EconWPA ().