On the NP-completeness of Finding an Optimal Strategy in Games with Common Payoffs

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
To appear, International Journal of Game Theory

Keywords

Computer Science and Game Theory, Computational Complexity, Distributed, Parallel, and Cluster Computing, D.1.3

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/30572

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0103019
 http://arxiv.org/abs/cs/0103019

Collections

arXiv