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.

MoreLess

Year of publication:	2001-10-10
Authors:	Chu, Francis ; Halpern, Joseph
Published in:	International Journal of Game Theory. - Springer. - Vol. 30.2001, 1, p. 99-106
Publisher:	Springer

More details

Extent:	application/pdf
Type of publication:	Article
Notes:	Received January 2001/Final version May 1, 2001
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10005375638