On the NP-completeness of finding an optimal strategy in games with common payoffs

On the NP-completeness of finding an optimal strategy in games with common payoffs

0.00 Avg rating0 Votes
Article ID: iaor2003657
Country: Germany
Volume: 30
Issue: 1
Start Page Number: 99
End Page Number: 106
Publication Date: Jan 2001
Journal: International Journal of Game Theory
Authors: ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.