On the NP-completeness of Finding an Optimal Strategy in Games with Common Payoffs
<|reference_start|>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.<|reference_end|>
@article{chu2001on,
    title={On the NP-completeness of Finding an Optimal Strategy in Games with
  Common Payoffs},
    author={Francis Chu and Joseph Y. Halpern},
    journal={arXiv preprint arXiv:cs/0103019},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0103019},
    primaryClass={cs.GT cs.CC cs.DC}
}