On the NP-completeness of Finding an Optimal Strategy in Games with Common Payoffs
Chu, Francis · Halpern, Joseph Y.
Computer Science and Game Theory
Computational Complexity
Distributed, Parallel, and Cluster Computing
D.1.3
Original · EN
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.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.