On the NP-Completeness of Finding an Optimal Strategy in Games with Common Payoffs
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.
|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://econwpa.repec.org|
When requesting a correction, please mention this item's handle: RePEc:wpa:wuwpga:0004011. See general information about how to correct material in RePEc.
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.