Complexity Results about Nash Equilibria

1 Introduction

Noncooperative game theory provides a normative frame­ work for analyzing strategic interactions of agents. However, for the toolbox to be operational, the solutions it defines will have to be computed [22] . There has been growing interest in the computational complexity of natural questions in game theory. Starting at least as early as the 1970s, complexity the­ orists have focused on the complexity of playing particular highly structured games (usually board games, such as chess or Go [10], but also games such as Geography or QSAT [23]). These games tend to be alternating-move zero-sum games with enormous state spaces, which can nevertheless be con­ cisely represented due to the simple rules governing the tran­ sition between states. As a result, effort on finding results for general classes of games has often focused on complex languages in which such structured games can be concisely represented.

Real-world strategic settings are generally not nearly as structured, nor do they generally possess the other proper­ ties (most notably, zero-sumness) of board games and the like. Algorithms for analyzing this more general class of games strategically are a necessary component of sophisti­ cated agents that are to play such games. Additionally, they are needed by mechanism designers who have (some) con­ trol over the rules of the game and would like the outcome of the game to have certain properties, such as maximum social welfare.

*The material in this paper is based upon work supported by the National Science Foundation under CAREER Award IRI-9703122, Grant IIS-9800994, ITR IIS-0081246, and ITR IIS-0121678.

Noncooperative game theory provides languages for rep­ resenting large classes of strategic settings, as well as so­ phisticated notions of what it means to "solve" such games. The best known solution concept is that of Nash equilib­ rium [16], where the players' strategies are such that no in­ dividual player can derive any benefit from deviating from its strategy. The question of how complex it is to construct such an equilibrium has been dubbed "a most fundamental com­ putational problem whose complexity is wide open" and "to­ gether with factoring, [ ... ] the most important concrete open question on the boundary ofP today" [19] .

While this question remains open, important concrete ad­ vances have been made in determining the complexity of re­ lated questions. For example, 2-person zero-sum games can be solved using linear programming [12] in polynomial time. As another example, determining the existence of a joint strategy where each player gets expected payoff at least k is NP-complete in a concisely representable extensive form game where both players receive the same utility [2] . 1 As yet another example, in 2-player general-sum normal form games, determining the existence of Nash equilibria with cer­ tain properties is NP-hard [4]. Finally, the complexity of best-responding, of guaranteeing payoffs, and of finding an equilibrium in repeated and sequential games has been stud­ ied in [1, 7, 11, 18, 25] .

In this paper we provide new complexity results on ques­ tions related to Nash equilibria. In Section 2 we provide a single reduction which significantly improves on many of Gilboa and Zemel's results on determining the existence of Nash equilibria with certain properties. In Section 3, we use the same reduction to show that counting the number of Nash equilibria (or connected sets of Nash equilibria) is #P-hard. In Section 4 we show that determining whether a pure-strategy Bayes-Nash equilibrium exists is NP-hard. Fi­ nally, in Section 5 we show that determining whether a pure­ strategy Nash equilibrium exists in a stochastic (Markov) game is PSPAC£-hard even if the game is invisible (this remains NP-hard if the game is finite) . All of our hardness results hold even if there are only two players and the game is symmetric.

1 This game can be converted to a normal form game as well, but it will grow exponentially in size, and the hardness result does not go through.

2 Equilibria with certain properties in normal form games

When one analyzes the strategic structure of a game, espe­ cially from the viewpoint of a mechanism designer who tries to construct good rules for a game, finding a single equilib­ rium is far from satisfactory. More desirable equilibria may exist: in this case the game becomes more attractive, espe­ cially if one can coax the players into playing a desirable equilibrium. Also, less desirable equilibria may exist: in this case the game becomes less attractive. Before we can make a definite judgment about the quality of the game, we would like to know the answers to questions such as: What is the game's most desirable equilibrium? Is there a unique equilib­ rium? If not, how many equilibria are there? Algorithms that tackle these questions would be useful both to players and to the mechanism designer.

Furthermore, algorithms that answer certain existence questions may pave the way to designing algorithms that con­ struct a Nash equilibrium. For example, if we had an algo­ rithm that told us whether there exists any equilibrium where a certain player plays a certain strategy, this could be useful in eliminating possibilities in the search for a Nash equilibrium.

However, all the existence questions that we have investi­ gated tum out to be NP-hard. These are not the first results of this nature; most notably, Gilboa and Zemel provide some NP-hardness results in the same spirit [4]. We provide a sin­ gle reduction which in demonstrates (sometimes stronger ver­ sions of) most of their hardness results, and interesting new results. Additionally, as we show in Section 3, the reduction shows #P-hardness of counting the number of equilibria.

We first need some standard definitions from game theory.

Definition 1 In a normal form game, we are given a set of agents A, and for each agent i, a strategy set :Ei and a utility function ui : :E1 x :E2 x ... x :EIAI ____. R

Definition 2 A mixed strategy a dor player i is a probability distribution over :Ei. A special case of a mixed strategy is a pure strategy, where all of the probability mass is on one element of:Ei.

Definition 3 (Nash [16]) Given a normal form game, a Nash equilibrium (NE) is vector of mixed strategies, one for each agent i, such that no agent has an incentive to deviate from its mixed strategy given that the others do not deviate. That is, for any i and any alternative mixed strategy a~, we have E[ui(s1 , s2, . . . , Si, ... , siAl)] ::=: E[ui(sl, s2, ... , s~, ... , siAl)], where each Si is drawn from ai, and s~from a~.

Now we are ready to present our reduction.

Definition 4 Let ¢ be a Boolean formula in conjunctive nor­ mal form. Let V be its set of variables (with lVI = n ), L the set of corresponding literals (a positive and a negative one for each variableP, and C its set of clauses. The func­ tion v : L ---. V gives the variable corresponding to a lit­ eral, e.g. v(xr) = v( -xr) = x1. We define G(¢) to be the following symmetric 2-player game in normal form. Let :E = :E1 = :E2 = L U V U C U {!}. Let the utility functions be

• u1~l 1 ,L2) = u2(l 2 ,l 1 ) = 1foralll 1 ,l 2 E L with l 1 # -l ;
• u1(l, -l) = u2( -l, l) = -2for alll E L;
• u1(l, x) = u2(x, l) = -2for alll E L, x E :E- L;
• u1(v,l) = u2(l,v) = 2forallv E V, l E Lwith v(l) ::/= v;
• u1(v, l) = u2(l, v) = 2- nfor all v E V, l E L with v(l) = v;
• u1(v,x) = u2(x,v) = -2forallv E V, x E :E- L;
• u1(c,l) = u2(l,c) = 2forall c E C, l E L with l tj. c;
• u1(c,l) = u2(l,c) = 2- nforall c E C, l E L with l E c;
• u1(c, x) = u2(x, c) = -2for all c E C, x E :E- L;
• u1 (!,f) = u2(f, f) = 0;
• u1(f,x) = u2(x,f) = 1forallx E :E- {!}.

Theorem 1 If (h, l2 , ... , ln) (where v(li) = Xi) satisfies ¢, then there is a Nash equilibrium ofG(¢) where both players play li with probability ~' with expected utility 1 for each player. The only other Nash equilibrium is the one where both players play f, and receive expected utility 0 each.

Proof: We first demonstrate that these combinations of mixed strategies indeed do constitute Nash equilibria. If (l1, l2, ... , ln) (where v(li) = Xi) satisfies ¢and the other player plays li with probability ~, playing one of these li as well gives utility I . On the other hand, playing the negation of one of these li gives utility ~( -2) + n~l (1). < 1. Play­ ing some variable v gives utility ~(2 - n) + n~l (2) = 1 (since one of the li that the other player sometimes plays has v(li) = v). Playing some clause c gives utility at most ~(2- n) + n~l (2) = 1 (since one of the li that the other player sometimes plays occurs in clause c, since the li satisfy ¢ ). Finally, playing f gives utility I. It follows that playing any one of the li that the other player sometimes plays is an optimal response, and hence that both players playing each of these li with probability ~ is a Nash equilibrium. Clearly, both players playing f is also a Nash equilibrium since play­ ing anything else when the other plays f gives utility -2.

Now we demonstrate that there are no other Nash equilib­ ria. If the other player always plays f, the unique best re­ sponse is to also play f since playing anything else will give utility -2. Otherwise, given a mixed strategy for the other player, consider a player's expected utility given that the other player does not play f. (That is, the probability distribution over the other player's strategies is proportional to the proba­ bility distribution constituted by that player's mixed strategy, except f occurs with probability 0). If this expected utility is less than 1, the player is strictly better off playing f (which gives utility 1 when the other player does not play f, and also performs better than the original strategy when the other player does play f). So this cannot occur in equilibrium.

2 Thus, if XI is a variable, XI and -XI are literals. We make a distinction between the variable XI and the literal XI.

There are no Nash equilibria where one player always plays f but the other does not, so suppose both players play f with probability less than one. Consider the expected social welfare (E[u1 + u2]), given that neither player plays f. It is easily verified that there is no outcome with social welfare greater than 2. Also, any outcome in which one player plays an element of V or C has social welfare strictly below 2. It follows that if either player ever plays an element of V or C, the expected social welfare given that neither player plays f is strictly below 2. By linearity of expectation it follows that the expected utility of at least one player is strictly below 1 given that neither player plays f, and by the above reasoning, this player would be strictly better off playing f instead of its randomization over strategies other than f. It follows that no element of V or Cis ever played in a Nash equilibrium.

So, we can assume both players only put positive probabil­ ity on strategies in L U {!}. Then, if the other player puts pos­ itive probability on f, playing f is a strictly better response than any element of L (since both give utility 1 if the other player plays an element of L, but f does better if the other player plays f). It follows that the only equilibrium where f is ever played is the one where both players always play f .

Now we can assume that both players only put positive probability on elements of L. Suppose that for some l E L, the probability that a given player plays either l or -l is Jess than ~. Then the expected utility for the other player of play­ ing v(l) is strictly greater than ~(2- n) + n~l (2) = 1, and hence this cannot be a Nash equilibrium. So we can assume that for any l E L , the probability that a given player plays either lor-lis precisely ~·

If there is an element of L such that player 1 puts posi­ tive probability on it and player 2 on its negation, both play­ ers have expected utility less than 1 and would be better off switching to f . So, in a Nash equilibrium, if player 1 plays l with some probability, player 2 must play l with probability ~, and thus player 1 must play l with probability ~· Thus we can assume that for each variable, exactly one of its cor­ responding literals is played with probability ~ by both play­ ers. It follows that in any Nash equilibrium (besides the one where both players play f), literals that are sometimes played indeed correspond to an assignment to the variables.

All that is left to show is that if this assignment does not satisfy ¢ , it does not correspond to a Nash equilibrium. Let c E C be a clause that is not satisfied by the assignment, that is, none of its literals are ever played. Then playing c would give utility 2, and both players would be better off playing this. ·

Hence, there exists a Nash equilibrium in G( ¢) where each player gets utility 1 if and only if ¢ is satisfiable; otherwise, the only equilibrium is the one where both players play f and each of them gets 0. Since any sensible definition of welfare optimization would prefer the first kind of equilibrium, it fol­ lows that determining whether a "good" equilibrium exists is hard for any such definition. Additionally, the first kind of equilibrium is, in various senses, an optimal outcome for the game, even if the players were to cooperate, so even finding out whether such an optimal equilibrium exists is hard. The following corollaries illustrate these points (each corollary is immediate from Theorem 1).

Corollary 1 Even in symmetric 2-player games, it is NP­ hard to determine whether there exists a NE with expected (standard) social welfare ( E[ I: ui]J at least k, even l $i$IAI

when k is the maximum social welfare that could be obtained in the game.

Corollary 2 Even in symmetric 2-player games, it is NP­ hard to determine whether there exists a NE where all players have expected utility at least k, even when k is the largest number such that there exists a distribution over outcomes of the game such that all players have expected utility at least k.

Corollary 3 Even in symmetric 2-player games, it is NP­ hard to determine whether there exists a Pareto-optimal NE. (A distribution over outcomes is Pareto-optimal if there is no other distribution over outcomes such that every player has at least equal expected utility, and at least one player has strictly greater expected utility).

Corollary 4 Even in symmetric 2-player games, it is NP­ hard to determine whether there exists a NE where player 1 has expected utility at least k.

Some additional interesting corollaries are:

Corollary 5 Even in symmetric 2-player games, it is NP­ hard to determine whether there is more than one Nash equi­ librium.

Corollary 6 Even in symmetric 2-player games, it is NP­ hard to determine whether there is an equilibrium where player 1 sometimes plays x E 'E1.

Corollary 7 Even in symmetric 2-player games, it is NP­ hard to determine whether there is an equilibrium where player 1 never plays x E 'E1.

All of these results indicate that it is hard to obtain sum­ mary information about a game's Nash equilibria. (Corol­ lary 5 and weaker 3 versions of Corollaries 2, 6 and 7 were first proven by Gilboa and Zemel [4] .)

3 Counting the number of equilibria in normal form games

Existence questions do not tell the whole story. In general, we are interested in characterizing all the equilibria of a game. One rather weak such characterization is the number of equi­ libria4. We can use Theorem 1 to show that even determining this number in a given normal form game is hard.

Corollary 8 Even in symmetric 2-player games, counting the number of Nash equilibria is #P-hard.

3 0ur results prove hardness in a slightly more restricted setting.

4 The number of equilibria in normal form games has been stud­ ied both in the worst case [15] and in the average case [14].

Proof: The number of Nash equilibria in our game G(¢) is the number of satisfying assignments to the variables of ¢, plus one. Counting the number of satisfying assignments to a CNF formula is #P-hard [24]. ·

It is easy to construct games where there is a continuum of Nash equilibria. In such games, it is more meaningful to ask how many distinct continuums of equilibria there are. More formally, one can ask how many maximal connected sets of equilibria a game has (a maximal connected set is a connected set which is not a proper subset of a connected set).

Corollary 9 Even in symmetric 2-player games, counting the number of maximal connected sets of Nash equilibria is # P­ hard.

Proof: Every Nash equilibrium in G(¢) constitutes a maxi­ mal connected set by itself, so the number of maximal con­ nected sets is the number of satisfying assignments to the variables of¢, plus one. ·

The most interesting #?-hardness results are the ones where the corresponding existence and search questions are easy, such as counting the number of perfect bipartite matchings. In the case of Nash equilibria, the existence question is trivial: it has been analytically shown (by Kakutani's fixed point the­ orem) that a Nash equilibrium always exists [16]. The com­ plexity of the search question remains open.

4 Pure-strategy Bayes-Nash equilibria

Equilibria in pure strategies are particularly desirable because they avoid the uncomfortable requirement that players ran­ domize over strategies among which they are indifferent [3]. In normal form games with small numbers of players, it is easy to determine the existence of pure-strategy equilibria: one can simply check, for each combination of pure strate­ gies, whether it constitutes a Nash equilibrium. However, this is not feasible in Bayesian games, where the players have private information about their own preferences (represented by types). Here, players may condition their actions on their types, so the strategy space of each player is exponential in the number of types.

In this section, we show that the question of whether a pure-strategy Bayes-Nash equilibrium exists is in fact NP­ hard even in symmetric two-player games. First, we need the standard definition of a Bayesian game and Bayes-Nash equi­ librium from game theory.

Definition 5 In a Bayesian game, we are given a set of agents A; for each agent i, a set of types 8;; a commonly known prior distribution cp over 81 X 82 X ... X 8IAI; for each agent i, a set of strategies ~;; and for each agent i, a utility function U; : 8; X ~1 X ~2 X ··. X ~IAI ---t ~.

Definition 6 (Harsanyi [5]) Given a Bayesian game, a Bayes-Nash equilibrium (BNE) is a vector of mixed strate­ gies, one for each pair i, B; E 8;, such that no agent has an incentive to deviate, for any of its types, given that the others do not deviate. That is, for any i, B; E 8;, and any alternative mixed strategy u~,6, , we have

We can now define the computational problem.

Definition 7 (PURE-STRATEGY-BNE) We are given a Bayesian game. We are asked whether there exists a BNE where all the strategies 0"; ,6, are pure.

To show our NP-hardness result, we will reduce from the SET-COVER problem.

Definition 8 (SET-COVER) We are given a set s {81, ... '8n}, subsets s1, s2, ... 'Sm of s with U1<i<m S; = S, and an integer k. We are asked whether the~e exist Sct , Sc 2 , · ·· , SCk such that U 1 $i$ k Sc, = S.

Theorem 2 PURE-STRATEGY-ENE is NP-hard, even in symmetric 2-player games where¢ is uniform.

Proof: We reduce an arbitrary SET-COVER instance to the following PURE-STRATEGY-ENE instance. Let there be two players, with 8 = 8 1 = 8 2 = { Bl, ... , ()k}. ¢ is uniform. Furthermore, ~ ~1 ~2 {S1, S2, ... , Sm, 81, 82, ... , 8n}· The utility functions we choose in fact do not depend on the types, so we omit the type argument in their definitions. They are as follows:

• u1(S;, Sj) = u2(Sj, S;) = 1 for all S; and Sj;
• u1(S;, 8j) = u2(8j, S;) = 1 for all S; and 8j ~ Si;
• u1(S;, 8j) = u2(8j, S;) = 2 for all S; and 8j E S;;
• u1(8;,8j) =u2(8j,8i) = -3kforall8;and8j;
• u1 (8j, S;) = u2(S;, 8j) = 3 for all S; and 8j ~ S;;
• u1 (8j, Si) = u2(S;, 8j) = -3k for all S; and 8j E S; .

We now show the two instances are equivalent. First suppose there exist Sc 1 , Sc 2 , ··· , Sck such that U1 <i<k Sc, = S. Suppose both players play as follows: when their type is B;, they play Sc,. We claim that this is a BNE. For suppose the other player employs this strategy. Then, because for any Sj, there is at least one Sc, such that 8 j E Sc,, we have that the expected utility of playing 8j is at most fc( -3k) + kk" 1 3 < 0. It follows that playing any of the sj (which gives utility 1) is optimal. So there is a pure-strategy BNE.

On the other hand, suppose that there is a pure-strategy BNE. We first observe that in no pure-strategy BNE, both players play some element of S for some type: for if the other player sometimes plays some 8j, the utility of playing some 8; is at most fc ( -3k) + kk 1 3 < 0, whereas playing someS; instead guarantees a utility of at least 1. So there is at least one player who never plays any element of S. Now suppose the other player sometimes plays some 8j. We know there is some S; such that 8j E S;. If the former player plays this S;, this will give it a utility of at least fc2 + kk" 1 1 = 1 + fc· Since it must do at least this well in the equilibrium, and it never plays elements of S, it must sometimes receive utility 2. It follows that there exist Sa and 8b E Sa such that the former player sometimes plays Sa and the latter sometimes plays 8b. But then, pla~inf 8b gives the latter player a utility of at most fc( -3k) + --i-3 < 0, and it would be better off playing some S; instead. (Contradiction.) It follows that in no pure-strategy BNE, any element of S is ever played.

Now, in our given pure-strategy equilibrium, consider the set of all the Si that are played by player 1 for some type. Clearly there can be at most k such sets. We claim they cover S. For if they do not cover some element Sj, the expected utility of playing Sj for player 2 is 3 (because player 1 never plays any element of S). But this means that player 2 (who never plays any element of S either) is not playing optimally. (Contradiction.) Hence, there exists a set cover. ·

If one allows for general mixed strategies, a Bayes-Nash equilibrium always exists [3]. However, the question of how efficiently one can be constructed remains open.

5 Pure-strategy Nash equilibria in stochastic (Markov) games

We now shift our attention from single-shot games to games with multiple stages. In each stage, the players get to act and obtain payoffs. There has already been some research into the complexity of playing repeated and sequential games. For ex­ ample, determining whether a particular automaton is a best response is NP-complete [1]; it is NP-complete to compute a best-response automaton when the automata under consid­ eration are bounded [18]; the question of whether a given player with imperfect recall can guarantee itself a given pay­ off using pure strategies is NP-complete [7]; and in general, best-responding to an arbitrary strategy can even be noncom­ putable [25]. In this section, we present, to our knowledge, the first PSPAC£-hardness result on the existence of a pure­ strategy equilibrium.

A multi-stage game is typically represented as a stochastic (Markov) game, where there is an underlying set of states, and the game shifts between these states from stage to stage [3, 20, 21). At every stage, each player's payoff depends not only on the players' actions, but also on the state. Furthermore, the probability of transitioning to a given state is determined by the current state and the players' current actions. Hardness results for such games cannot be obtained simply by formu­ lating a known hard game such as generalized Go [10] or QSAT [23] as a Markov game, because such a formulation would have to specify an exponential number of states. Even if the number of states is polynomial, one might suspect hard­ ness because the strategy spaces are extremely rich. However, in this section we show PSPAC£-hardness even in a variant where the strategy spaces are simple (in the sense that the players cannot condition their actions on events in the game).

Definition 9 A stochastic (Markov) game consists of

• A set of players A;
• A set of states S, among which the game transits;
• For each player i, a set of actions L:i that can be played in any state;
• A transition probability function p : S x I::1 x ... x I::IAI x S--> [0,1], where p(sl,al, ... ,aiAI,s2) gives the probability of the game being in state s2 in the next stage given that the current state of the game is s1 and the players play actions a1, ... , alAI;
• For each player i, a payoff function ui : S x I::1 x ... I::IAI --> ~. where ui(s, a1, ... , alAI) gives the pay-
• off to player i in state s where the players play actions al, ... , alAI;
• A discount factor J such that the total utility of agent 00 . . "\' s:k ( k k k ) h k . h z IS L.. u ui s , a1, ... , alAI , w ere s 1s t e state k=O of the game at stage k and the players play actions k k . k a1 , ... ,a A mstage.

1 1

In general, a player need not always be aware of the cur­ rent state of the game, the actions the others played in pre­ vious stages, or the payoffs that the player has accumulated. In the extreme case, players never find out any of these and are hence playing blindly. We call such a Markov game in­ visible. It is relatively easy to specify a pure strategy in an invisible Markov game, because there is nothing to condition on. Hence, such a strategy is "simply" an infinite sequence of actions (for player i, a sequence { a7}, where it plays action a~ in stage k, regardless). 5 In spite of this apparent simplicity of the game, we show that determining whether pure-strategy equilibria exist is extremely hard.

Definition 10 (PURE-STRATEGY-INVISIBLE­

MARKOV-NE) We are given an invisible Markov game. We are asked whether there exists a Nash equilibrium where all the strategies are pure.

We show that this problem is PSPAC£-hard, by reducing from PERIODIC-SAT, which is PSPAC£-complete [17].

Definition 11 (PERIODIC-SAT) We are given a CNF for­ mula ¢(0) over the variables {x~ ... x~} U {xt .. . x~}. Let ¢(k) be the same formula, except that all the superscripts are incremented by k. We are asked whether there exists a Boolean assignment to the variables uk=O,l , ... {X~ ... x~} such that ¢( k) is satisfied for every k = 0, 1, ... .

Theorem 3 PURE-STRATEGY-INVISIBLE-MARKOV-NE is PSPAC£-hard, even when the game is symmetric, 2-player, and the transition process is deterministic.

Proof: We reduce an arbitrary PERIODIC-SAT instance to the following symmetric 2-player PURE-STRATEGY­ INVISIBLE-MARKOV-NE instance. The state space is S = { si}1:5i:5n U { t},ch<i:::;2n;cEC U { tr,ch<i:52n;cEC U { r }, where C is the set of clauses in ¢(0). Furthermore, I: = I::1 = I::2 = {t,!} U C. The transition probabilities are

• p( Si, xl, x 2 , si+l(modn)) = 1 for 1 < i :::; n and all x 1 ,x 2 E I:;
• p(s1, b 1 , b 2 , s2) = 1 for all b 1 , b 2 E {t, !};
• p(s1, c, b, tL) = 1 for all bE {t,!} and c E C;
• p(s1, b, c, t~ c)= 1 for all bE {t,!} and c E C;
• p(s1,c 1 ,c 2 ,r) = 1 for all c 1 ,c 2 E C;
• p(t{c,x 1 ,x 2 ,t{+l,c) = 1 forall1 < i < 2n,j E {1,2}, c E C, and x 1 , x 2 E I:;
• p(t~nc,xl,x 2 ,r) = 1 for all j E {1,2}, c E C, and x 1 x2 E I:· , ,

5 We do not need to worry about issues of credible threats and subgame perfection in this setting, so we can simply use Nash equi­ librium as our solution concept [13] .

• p(r,x 1 ,x 2 ,r) = 1 forallx 1 ,x 2 E I; .

Some of the utilities obtained in a given stage are as follows (we do not specify utilities irrelevant to our analysis):

• u 1(si,x 1 ,x 2 ) = u2(si,x 2 ,x 1 ) = 0 for 1 < i::; nand allx 1 ,x 2 EI;;
• u 1(s1,b 1 , b 2 ) = u2(s1,b 2 ,b 1 ) = 0 for all bl,b 2 E {t, !};
• u1(s1,c,b) = u2(s1,b,c) = 1 for all bE {t,f} and c E C, when setting variable x? to b does not satisfy c;
• u1(s1,c,b) = u2(s1,b,c) = -1 for all bE {t,f} and c E C, when setting variable x? to b does satisfy c;
• u1(s1,c 1 , c 2 ) = u2(s1, c 2 , c 1 ) = -1 for all c 1 , c 2 E C;
• U1 (tkn+i ,c' x, b) = u2(t~n+i,c · b, x) = 0 fork E {0, 1}, 1 ::; i ::; n, all c E C and b E { t,!} such that setting variable x~ to b does not satisfy c, and all x E I;;
• ul(tkn+i,c,x,b) = u2(t~n+i,c,b,x) = -4fork E {0, 1}, 1 ::; i ::; n, all c E C and b E {t,!} such that setting variable x~ to b does satisfy c, and all x E I;;
• ul(tkn+i,c'x,c') = u2(t~n+i,c,c',x) = 0 fork E {0, 1}, 1 ::; i::; n, all c, c' E C, and all x E I;.

Additionally, the game played in stater is some symmet­ ric zero-sum game without a pure-strategy equilibrium (for example, a generalization of rock-paper-scissors) with very small payoffs. Finally, the discount factor is o = ( ~) 2n 1 +t (so that o 2 n > ~).

We start our analysis with a few observations. First, there can be no pure-strategy equilibrium in which state r is reached at some point, because (since r is an absorbing state) this would require that some pure-strategy equilibrium of the game in state r were played whenever state r occurred. (Oth­ erwise a player who is not best-responding in one of these stages could simply switch to a best response in this stage, and because the game is invisible, the rest of the game would remain unaffected, so this would give higher utility.) But such an equilibrium does not exist. Second, if we ever reach one of the t{ c states, we will inevitably reach state r at some point after 'this. It follows that all pure-strategy Nash equilibria never leave the si states.

Now suppose an assignment satisfying the periodic SAT formula exists. Let both players play as follows: in stage kn + i (with 1 ::; i ::; n), b E { t,!} is played, where b is the value that the variable x~ is set to. Clearly, both players receive utility 0 with these strategies. Does either player have an incentive to deviate? The only deviation of any signifi­ cance is to play some c E C when the current state is s1. So, without loss of generality (because of the symmetry of the game), say player 2 deviates to playing c E C in stage kn + 1 (when the state is s1). We know that in the satisfying assign­ ment, some variable x~ among x~, .. . , x~, x~+l, ... , x~+ 1 is set to some b such that setting x~-k to b satisfies c. If it is x~, which is set to b, then in stage kn + 1 player 1 plays b, and player 2 gets payoff -1 in this stage since we are in state s1 and setting x? to b satisfies c. Otherwise, if it is x~ with l = k + 1 or i ;:j:. 1, which is set to b, then player 2 will get payoff 1 in stage kn + 1, but in stage ln + i player 1 plays b, and player 2 gets payoff -4 in this stage since we are in state t~l-k)n+i,c and setting x~-k to b satisfies c. The discount­ ing is insignificant enough that this more than cancels out the 1 earned in stage kn + 1. Player 2 will get (at most) 0 in the other stages up to the first stage in stater, and given that we made the payoffs in the game in state r sufficiently small relative to o, player 2 will not earn enough in the remaining stages to cancel out its losses so far. So there is no incentive to deviate. Thus, a pure-strategy NE exists.

On the other hand, suppose that no assignment satisfying the periodic SAT formula exists. Let us investigate whether a Nash equilibrium could exist. We know that in such a Nash equilibrium we never leave the si, so both players receive utility 0, and no c is ever played in a stage with state s1. Since playing a c in one of the other stages can have no deterrent value, we may suppose that only elements of { t , !} are played. Now consider the following assignment to the x~: if player 1 plays bin stage kn + i, x~ is set to b. Since no assignment satisfying the periodic SAT formula exists, we know there is some clause c and some k such that no . bl l k k k+l k+l . varia e xi among x1, .. . , xn, x1 , ... , xn 1s set to some b such that setting x~-k to b satisfies c. But then, if player 2 deviates to play this c in stage kn + 1, it will receive payoff 1 in this stage, and payoff 0 in all the remaining stages up to the first stage in stater. Furthermore, player 2 can guarantee itself at least payoff 0 in each stage in state r, as this state corresponds to a zero-sum symmetric game. It follows that this deviation gives player 2 positive utility and is hence beneficial. Thus, no pure-strategy NE exists. ·

A simpler version of the same argument shows a weaker form of hardness for the case where the game is restricted to have only finitely many stages (we omit the proof due to limited space):

Theorem 4 PURE-STRATEGY-INVISIBLE-MARKOV-NE is NP-hard, even when the game is symmetric, 2-player, the transition process is deterministic, and the number of stages in the game is finite.

6 Conclusions and future research

Noncooperative game theory provides a normative frame­ work for analyzing strategic interactions. However, for the toolbox to be operational, the solutions it defines will have to be computed. In this paper, we provided a single reduction that 1) demonstrates NP-hardness of determining whether Nash equilibria with certain natural properties exist, and 2) demonstrates the #P-hardness of counting Nash equilibria (or connected sets of Nash equilibria). We also showed that 3) determining whether a pure-strategy Bayes-Nash equilibrium exists is NP-hard, and that 4) determining whether a pure­ strategy Nash equilibrium exists in a stochastic (Markov) game is PSPAC£-hard even in invisible games (and NP­ hard if the game is finite). All of our hardness results hold even if there are only two players and the game is symmetric.

There are numerous open research questions in computing solutions to noncooperative games. Some recent work has fo­ cused on novel knowledge representations which, in certain settings, can drastically speed up equilibrium finding (e.g. [6, 8, 9]). One avenue of future work includes identifying restricted classes of games for which equilibria (or equilibria with certain properties) can be found fast. Another avenue involves studying the complexity of characterizing (some of) the equilibria of a game partially. Yet another avenue in­ cludes analyzing the computational complexity of other solu­ tion concepts from noncooperative game theory.