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

Details 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

2001-03-27

arxiv.org/abs/cs/0103019v1

Computer Science

Computer Science and Game Theory

To appear, International Journal of Game Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the NP-completeness of Finding an Optimal Strategy in Games with Common Payoffs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the NP-completeness of Finding an Optimal Strategy in Games with Common Payoffs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the NP-completeness of Finding an Optimal Strategy in Games with Common Payoffs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-28212