On the NP-completeness of finding an optimal strategy in games with common payoffs
Consider 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.
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|
|Order Information:||Web: http://link.springer.de/orders.htm|
When requesting a correction, please mention this item's handle: RePEc:spr:jogath:v:30:y:2001:i:1:p:99-106. 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: (Sonal Shukla)or (Christopher F Baum)
If references are entirely missing, you can add them using this form.