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

Simple item page
dc.creatorChu, Francis
dc.creatorHalpern, Joseph Y.
dc.date2001-03-27
dc.date.accessioned2026-07-07T03:17:01Z
dc.date.available2026-07-07T03:17:01Z
dc.descriptionConsider 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.
dc.descriptionTo appear, International Journal of Game Theory
dc.identifierhttps://arxiv.org/abs/cs/0103019
dc.identifierhttp://arxiv.org/abs/cs/0103019
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30572
dc.subjectComputer Science and Game Theory
dc.subjectComputational Complexity
dc.subjectDistributed, Parallel, and Cluster Computing
dc.subjectD.1.3
dc.titleOn the NP-completeness of Finding an Optimal Strategy in Games with Common Payoffs
dc.typetext

Files

Collections

arXiv