Abstract:
We investigate complexity issues related to pure Nash equilibria of strategic games. We show that, even in very restrictive settings, determining whether a game has a pure Nash Equilibrium is NP-hard, while deciding whether a game has a strong Nash equilibrium is SigmaP2-complete. We then study practically relevant restrictions that lower the complexity. In particular, we are interested in quantitative and qualitative restrictions of the way each player's payoff depends on moves of other players. We say that a game has small neighborhood if the utility function for each player depends only on (the actions of) a logarithmically small number of other players. The dependency structure of a game G can be expressed by a graph DG(G) or by a hypergraph H(G). By relating Nash equilibrium problems to constraint satisfaction problems (CSPs), we show that if G has small neighborhood and if H(G) has bounded hypertree width (or if DG(G) has bounded treewidth), then finding pure Nash and Pareto equilibria is feasible in polynomial time. If the game is graphical, then these problems are LOGCFL-complete and thus in the class NC2 of highly parallelizable problems.

---

Extracted Text

 


 
gottlob05a.dvi

 
Journal of Artificial Intelligence Research 24 (2005) 357-406
Submitted 12/04; published 09/05
Pure Nash Equilibria: Hard and Easy Games
Georg Gottlob
gottlob@dbai.tuwien.ac.at
Information Systems Department,Technische Universit¨
at Wien,
A-1040 Wien, Austria
Gianluigi Greco
ggreco@mat.unical.it
Dipartimento di Matematica,Universit`
a della Calabria,
I-87030 Rende, Italy
Francesco Scarcello
scarcello@deis.unical.it
DEIS,
Universit`
a della Calabria,
I-87030 Rende, Italy
Abstract
We investigate complexity issues related to pure Nash equilibria of strategic games. We
show that, even in very restrictive settings, determining whether a game has a pure NashEquilibrium is NP-hard, while deciding whether a game has a strong Nash equilibrium isΣP
2 -complete. We then study practically relevant restrictions that lower the complexity.
In particular, we are interested in quantitative and qualitative restrictions of the way eachplayer’s payoff depends on moves of other players. We say that a game has small neighbor-hood if the utility function for each player depends only on (the actions of) a logarithmicallysmall number of other players. The dependency structure of a game G can be expressedby a graph G(G) or by a hypergraph H(G). By relating Nash equilibrium problems toconstraint satisfaction problems (CSPs), we show that if G has small neighborhood and ifH(G) has bounded hypertree width (or if G(G) has bounded treewidth), then finding pureNash and Pareto equilibria is feasible in polynomial time. If the game is graphical, thenthese problems are LOGCFL-complete and thus in the class NC2 of highly parallelizableproblems.
1. Introduction and Overview of Results
The theory of strategic games and Nash equilibria has important applications in economicsand decision making (Nash, 1951; Aumann, 1985). Determining whether Nash equilib-ria exist, and effectively computing them, are relevant problems that have attracted muchresearch in computer science (e.g. Deng, Papadimitriou, & Safra, 2002; McKelvey & McLen-nan, 1996; Koller, Megiddo, & von Stengel, 1996). Most work has been dedicated to com-plexity issues related to mixed equilibria of games with mixed strategies, where the player’schoices are not deterministic and are regulated by probability distributions. In that con-text, the existence of a Nash equilibrium is guaranteed by Nash’s famous theorem (Nash,1951), but it is currently open whether such an equilibrium can be computed in polynomialtime (cf., Papadimitriou, 2001). First results on the computational complexity for a two-person game have been presented by Gilboa and Zemel (1989), while extensions to moregeneral types of games have been provided by Megiddo and Papadimitriou (1991), and by
c 2005 AI Access Foundation. All rights reserved.

 
Gottlob, Greco, and Scarcello
Papadimitriou (1994b). A recent paper of Conitzer and Sandholm (2003b) also proved theNP-hardness of determining whether Nash equilibria with certain natural properties exist.
In the present paper, we are not dealing with mixed strategies, but rather investigate the
complexity of deciding whether there exists a Nash equilibrium in the case of pure strategies,where each player chooses to play an action in a deterministic, non-aleatory manner. Nashequilibria for pure strategies are briefly referred to as pure Nash equilibria. Note that inthe setting of pure strategies, a pure Nash equilibrium is not guaranteed to exist (see,for instance, Osborne & Rubinstein, 1994). Particular classes of games having pure Nashequilibria have been studied by Rosenthal (1973), Monderer and Shapley (1993), and byFotakis et al. (2002). Recently, Fabrikant at el. (2004) renewed the interest in the classof games defined Rosenthal (1973), called congestion games, by showing that a pure Nashequilibrium can be computed in polynomial time in the symmetric network case, while theproblem is PLS-complete (Johnson, Papadimitriou, & Yannakakis, 1998) in general.
Our goal is to study fundamental questions such as the existence of pure Nash, Pareto,
and strong Nash equilibria, the computation of such equilibria, and to find arguably realisticrestrictions under which these problems become tractable. Throughout the paper, Paretoand strong Nash equilibria are considered only in the setting of pure strategies.
While pure strategies are conceptually simpler than mixed strategies, the associated
computational problems appear to be harder. In fact, we show that even if severe restric-tions are imposed on the set of allowed strategies, determining whether a game has a pureNash or Pareto Equilibrium is NP-complete, while deciding whether a game has a strongNash equilibrium is even ΣP -complete. However, by jointly applying suitable pairs of more
2
realistic restrictions, we obtain settings of practical interest in which the complexity of theabove problems is drastically reduced. In particular, determining the existence of a pureNash equilibrium and computing such an equilibrium will be feasible in polynomial timeand we will show that, in certain cases, these problems are even complete for the very lowcomplexity class LOGCFL, which means that these problems are essentially as easy as themembership problem for context-free languages, and are thus highly parallelizable (in NC2).
In the setting of pure strategies, to which we will restrict our attention in the rest of
this paper, a finite strategic game is one in which each player has a finite set of possibleactions, from which she chooses an action once and for all, independently of the actualchoices of the other players. The choices of all players can thus be thought to be madesimultaneously. The choice of an action by a player is referred to as the player’s strategy.It is assumed that each player has perfect knowledge over all possible actions and overthe possible strategies of all players. A global strategy, also called profile in the literature,consists of a tuple containing a strategy for each player. Each player has a polynomial-timecomputable real valued utility function, which allows her to assess her subjective utility ofeach possible global strategy (global strategies with higher utility are better). A pure Nashequilibrium (Nash, 1951) is a global strategy in which no player can improve her utility bychanging her action (while the actions of all other players remain unchanged). A strongNash equilibrium (Aumann, 1959) is a pure Nash equilibrium where no change of strategiesof whatever coalition (i.e., group of players) can simultaneously increase the utility for allplayers in the coalition. A pure Nash equilibrium is Pareto optimal (e.g. Maskin, 1985) ifthe game admits no other pure Nash equilibrium for which each player has a strictly higherutility. A Pareto-optimal Nash equilibrium is also called a Pareto Nash Equilibrium.
358

 
Pure Nash Equilibria: Hard and Easy Games
Before describing our complexity results, let us discuss various parameters and features
that will lead to restricted versions of strategic games. We consider restrictions of strategicgames which impose quantitative and/or qualitative limitations on how the payoffs of anagent (and hence her decisions) may be influenced by the other agents.
The set of neighbors Neigh(p) of a player is the set of other players who potentially
matter w.r.t. p’s utility function. Thus, whenever a player q = p is not in Neigh(p) then p’sutility function does not directly depend on the actions of q. We assume that each gameis equipped with a polynomial-time computable function Neigh with the above property.1The player neighborhood relationship, typically represented as a graph (or a hypergraph),is the central notion in graphical games (Koller & Milch, 2001; Kearns, Littman, & Singh,2001b), as we will see in more detail in the next section.
A first idea towards the identification of tractable classes of games is to restrict the
cardinality of Neigh(p) for all players p. For instance, consider a set of companies in amarket. Each company has usually a limited number of other market players on which itbases its strategic decisions. These relevant players are usually known and constitute theneighbors of the company in our setting. However, note that even in this case the gameoutcome still depends on the interaction of all players, though possibly in an indirect way.Indeed, the choice of a company influences the choice of its competitors, and hence, in turn,the choice of competitors of its competitors, and so on. In this more general setting, anumber of real-world cases can be modeled in a very natural way. We can thus define thefollowing notion of limited neighborhood:
Bounded Neighborhood:
Let k > 0 be a fixed constant. A strategic game with as-
sociated neighborhood function Neigh has k-bounded neighborhood if, for each player p,|Neigh(p)| ≤ k.
While in some setting the bounded neighborhood assumption is realistic, in other set-
tings the constant bound appears to be too harsh an imposition. It is much more realisticand appealing to relax this constraint and consider a logarithmic bound rather than a con-stant bound on the number of neighbors.
Small Neighborhood:
For a game G denote by P (G) the set of its players, by Act(p)
the set of possible actions of a player p, and by ||G|| the total size of the description of agame G (i.e., the input size n). Furthermore, let maxNeigh(G) = maxp∈P
|
(G) Neigh(p)| and
maxAct (G) = maxp∈P
|
(G) Act (p)|.
A class of strategic games has small neighborhood if, for each game G in this class,
log ||G||
maxNeigh(G) = O(
)
log maxAct (G)
Note the denominator log maxAct (G) in the above bound. Intuitively, we use this term
to avoid “cheating” by trading actions for neighbors. Indeed, roughly speaking, playerinteractions may be reduced significantly by adding an exponential amount of additionalactions. For any player, these fresh actions may encode all possible action configurations of
1. Note that each game can be trivially represented in this setting, possibly setting Neigh(p) to be the
set of all players, for each player p. In most cases, however, one will be able to provide a much betterneighborhood function.
359

 
Gottlob, Greco, and Scarcello
Figure 1: Dependency hypergraph and dependency graph for the game G.
some of her neighbors, yielding an equivalent game with less interaction, and possibly withfewer players, too. The denominator takes this into account.
In other terms, a class of games has small neighborhood if there is a constant c such
that for all but finitely many pairs (G, p) of games and players, |Neigh(p)| < c ×( log ||G||
log |Act(p)| ).
The related notion i (G) of intricacy of a game is defined by:
maxNeigh(G) × log maxAct (G)
i (G) =
log ||G||
.
It is clear that a class of games has small neighborhood if and only if the intricacy of allgames in it is bounded by some constant.
Obviously, bounded neighborhood implies small neighborhood, but not vice-versa. We
believe that a very large number of important (classes of) games in economics have thesmall neighborhood property.
In addition to the quantitative aspect of the size of the neighborhood (and of the neigh-
borhood actions), we are also interested in qualitative aspects of mutual strategic influence.Following Kearns et al. (2001b), for a game G with a set P of players, we define the strate-gic dependency graph as the undirected graph G(G) having P as its set of vertices and
p, q | q ∈ P ∧ p ∈ Neigh(q) as its set of edges. Moreover, we define the strategic de-pendency hypergraph H(G), whose vertices are the players P and whose set of hyperedges is
p∪Neigh(p) | p ∈ P. For instance, consider a game G over players A, B, C, and D suchthat Neigh(A) = B, C , Neigh(B) = A, C , Neigh(C ) = A, B, and Neigh(D) = C .Figure 1 shows the dependency graph and the dependency hypergraph associated with G.
We consider the following classes of structurally restricted games:
Acyclic-Graph Games:
Games G for which G(G) is acyclic.
Acyclic-Hypergraph Games:
Games G for which H(G) is acyclic. Note that there are
several definitions of hypergraph acyclicity (Fagin, 1983). Here we refer to the broadest(i.e., the most general) one, also known as α-acyclicity (Fagin, 1983; Beeri, Fagin, Maier,& Yannakakis, 1983) (see Section 2).
Each acyclic-graph game is also an acyclic-hypergraph game, but not vice-versa. As an
extreme example, let G be a game with player set P in which the utility of each action foreach player depends on all other players. Then G(G) is a clique of size |P | while H(G) isthe trivially acyclic hypergraph having the only hyperedge P .
For strategic games, both the acyclic graph and the acyclic hypergraph assumptions are
very severe restrictions, which are rather unlikely to apply in practical contexts. However,
360

 
Pure Nash Equilibria: Hard and Easy Games
there are important generalizations that appear to be much more realistic for practicalapplications. These concepts are bounded treewidth (Robertson & Seymour, 1986) andbounded hypertree width (Gottlob, Leone, & Scarcello, 2002b) (see also Section 5), whichare suitable measures of the degree of cyclicity of a graph and of a hypergraph, respectively.In particular, each acyclic graph (hypergraph) has treewidth (hypertree width) ≤ 1. It wasargued that an impressive number of “real-life” graphs have a very low treewidth (Downey& Fellows, 1995). Hypertree width in turn was fruitfully applied in the context of databasequeries (Gottlob et al., 2002b) and constraint satisfaction problems (Gottlob, Leone, &Scarcello, 2000). Formal definitions are given in Section 5. Note that both computingthe treewidth of a graph and the hypertree width of a hypergraph are NP-hard problems.However, for each (fixed) constant k, it can be checked in polynomial time whether agraph has treewidth k (Bodlaender, 1997) and whether a hypergraph has hypertree widthk (Gottlob et al., 2002b). We have, for each constant k, the following restricted classes ofgames:
Games of treewidth bounded by k:
The games G such that the treewidth of G(G)
is ≤ k.
Games of hypertree width bounded by k:
The games G such that the hypertree
width of H(G) is ≤ k.
In the context of complexity and efficiency studies, it is very important to make clear
how an input (in our case, a multiplayer game) is represented. We say that a game isin general form if the sets of players and actions are given in extensional form and ifthe neighborhood and utility functions are polynomially computable functions.
Unless
otherwise stated, we always assume that games are given in general form. For classes ofgames having particular properties, some alternative representations have been used byvarious authors. For instance, in game theory literature, the set of utility functions is oftenrepresented through a single table (or matrix) having an entry for each combination ofplayers’ actions containing, for each player p, the evaluation of her utility function for thatparticular combination. This representation is said to be in standard normal form (SNF)(see, for instance, Osborne & Rubinstein, 1994; Owen, 1982). Note that, if there are manyplayers, this representation may be very space consuming, particularly if some players arenot interested in all other players, but only in some subset of them. Moreover, in this case,the monolithic utility table in SNF obscures much of the structure that is present in real-world games (Koller & Milch, 2001). In fact, in the context of games with restricted playersinteractions, the most used representation is the graphical normal form (GNF). In GNFgames, also known as graphical games (Kearns, Littman, & Singh, 2001a; Kearns et al.,2001b; Kearns & Mansour, 2002; Vickrey, 2002), the utility function for each player p isgiven by a table that displays p’s utility as a function of all possible combined strategies ofp and p’s neighbors, but not of other players irrelevant to p. Therefore, for large populationgames (modeling for instance agent interactions over the internet), the SNF is practicallyunfeasible, while the more succinct graphical normal form works very well, and is actuallya more natural representation.
Main results.
The main results of this paper are summarized as follows:
361

 
Gottlob, Greco, and Scarcello
• Determining whether a strategic game has a pure Nash equilibrium is NP-complete
and remains NP-complete even for following two restricted cases:
– Games in graphical normal form (GNF) having bounded neighborhood (Theo-
rem 3.1).
– Acyclic-graph games, and acyclic-hypergraph games (Theorem 3.2).
The same results hold for Pareto Nash equilibria for pure strategies.
• Determining whether a strategic game has a strong Nash equilibrium is Σp-complete
2
and thus at the second level of the Polynomial Hierarchy (Theorem 3.7 and Theo-rem 3.8). The proof of this theorem gives us a fresh game-theoretic view of the classΣP as the class of problems whose positive instances are characterized by a coalition
2
of players who cooperate to provide an equilibrium, and win against any other dis-joint coalition, which fails in trying to improve the utility for all of its players. E.g.,in the case of Σ2 quantified Boolean formulas, the former coalition consists of theexistentially quantified variables, and the latter of the universally quantified ones.
• The pure Nash, Pareto and strong equilibrium existence and computations problems
are feasible in logarithmic space for games in standard normal form (Theorem 4.1).
• The pure Nash equilibrium existence and computation problems are tractable for
games (in whatever representation) that simultaneously have small neighborhood andbounded hypertree width (Theorem 5.3). Observe that each of the two joint restric-tions, small neighborhood and bounded hypertree width, is weaker than the restric-tions of bounded neighborhood and acyclicity, respectively, of which each by itself doesnot guarantee tractability. Thus, in order to obtain tractability, instead of strength-ening a single restriction, we combined two weaker restrictions. While we think thateach of the two strong restrictions is unrealistic, we believe that for many naturalgames the combined weaker restrictions do apply. In order to prove the tractabilityresult, we establish a relationship between strategic games and the well-known finitedomain constraint satisfaction problem (CSP), much studied in the AI and OR liter-ature (e.g. Vardi, 2000; Gottlob et al., 2000). Let us point out that also Vickrey andKoller (2002) recently exploited a mapping to CSP for the different problem of findingapproximate mixed equilibria in graphical games. We show that each (general, notnecessarily GNF) strategic game G can be translated into a CSP instance having thesame hypertree width as G, and whose feasible solutions exactly correspond to theNash equilibria of the game. Then, we are able to prove that G is equivalent to anacyclic constraint satisfaction problem of size ||G||O(i(G)×hw(G)), where i(G) is the in-tricacy of G and hw(G) is the hypertree width of its strategic dependency hypergraph.Acyclic CSPs, in turn, are well-known to be solvable in polynomial time.
• Exploiting the same relationship with CSPs, we prove that the Nash-equilibrium ex-
istence and computation problems are tractable for games in graphical normal form(GNF) having bounded hypertree width (Theorem 5.3), regardless of the game intri-cacy, i.e., even for unbounded neighborhood.
362

 
Pure Nash Equilibria: Hard and Easy Games
• We show that if a strategic game has bounded treewidth, then it also has bounded
hypertree width (Theorem 5.7). Note that this is a novel result on the relationshipbetween these two measures of the degree of cyclicity, since earlier works on similarsubjects dealt with either the primal or the dual graph of a given hypergraph, ratherthan with a dependency graph, as we do in the present paper, focused on games. Com-bined with the two previous points, this entails that the Nash-equilibrium existenceand computation problems are tractable for games that simultaneously have smallneighborhood and bounded treewidth, and for GNF games having bounded treewidth(Corollary 5.9).
• In all above cases where a pure Nash Equilibrium can be computed in polynomial time,
also a Pareto Nash equilibrium can be computed in polynomial time (Theorem 4.6and Corollary 5.4).
• These tractability results partially extend to strong Nash equilibria. Indeed, the
checking problem becomes feasible in polynomial time for acyclic-hypergraph gamesin GNF. However, even in such simple cases, deciding whether a game has strongNash equilibria is NP-complete, and thus still untractable (Theorem 4.8).
• We go a bit further, by determining the precise complexity of games with acyclic
(or even bounded width) interactions among players: In case a game is given inGNF, the problem of determining a pure Nash equilibrium of a game of boundedhypertree-width (or bounded treewidth) is LOGCFL-complete and thus in the par-allel complexity class NC2 (Theorem 6.1). Membership in LOGCFL follows fromthe membership of bounded hypertree-width CSPs in LOGCFL (Gottlob, Leone, &Scarcello, 2001). Hardness for LOGCFL is shown by transforming (logspace uniformfamilies of) semi-unbounded circuits of logarithmic depth together with their inputsinto strategic games, such that the game admits a Nash equilibrium if and only if thecircuit outputs one on the given input.
Figure 2 summarizes our results on the existence of pure Nash equilibria.
While various authors have dealt with the complexity of Nash equilibria (e.g. Gilboa &Zemel, 1989; Papadimitriou, 1994b; Koller & Megiddo, 1992, 1996; Conitzer & Sandholm,2003b), most investigations were dedicated to mixed equilibria and — to the best of ourknowledge — all complexity results in the present paper are novel. We are not aware of anyother work considering the quantitative and structural restrictions on pure games studiedhere. Note that tree-structured games were first considered by Kearns et al. (2001b) inthe context of mixed equilibria. It turned out that, for such games, suitable approximationof (mixed) Nash equilibria can be computed in polynomial time. In our future work, wewould like to extend our tractability results even to this setting. We are not aware ofany work by others on the parallel complexity of equilibria problems. We believe thatour present work contributes to the understanding of pure Nash equilibria and proposesappealing and realistic restrictions under which the main computation problems associatedwith such equilibria are tractable.
The rest of the paper is organized as follows. In Section 2 we introduce the basic notions
of games and Nash equilibria that are studied in the paper, and we describe how games
363

 
Gottlob, Greco, and Scarcello
Figure 2: Complexity of deciding existence of pure Nash equilibria for games in GNF —
numbers indicate theorems where the corresponding results are proved.
may be represented. In Section 3 we thoroughly study the computational complexity ofdeciding the existence of pure Nash, Pareto and strong equilibria. In Section 4 we identifytractable classes of games, and in Section 5 we extend our tractability results to largerclass of games, where the interaction among players has a bounded degree of cyclicity. InSection 6 we improve the results on the polynomial tractability of easy games, providing theprecise computational complexity for games with acyclic (or bounded width) interactionsamong players. Finally, in Section 7, we draw our conclusions, and we discuss possiblefurther research and related works.
364

 
Pure Nash Equilibria: Hard and Easy Games
2. Games and Nash Equilibria
A game G is a tuple P, Neigh, Act, U , where P is a non-empty set of distinct players andNeigh : P −→ 2 P is a function such that for each p ∈ P , Neigh(p) ⊆ P − p containsall neighbors of p, Act : P −→ A is a function returning for each player p a set of possibleactions Act(p), and U associates a utility function up : Act(p) ×j ∈Neigh(p) Act(j ) →
to
each player p.
Note that, in general, the players interests are not symmetric. Thus, it may happen
that, for a pair of players p1, p2 ∈ P , p1 ∈ Neigh(p2 ) but p2 ∈ Neigh(p1 ).
For a player p, pa denotes her choice to play the action a ∈ Act(p). Each possible pa is
called a strategy for p, and the set of all strategies for p is denoted by St (p).2
For a non-empty set of players P ⊆ P , a combined strategy for P is a set containing
exactly one strategy for each player in P . St(P ) denotes the set of all combined strategiesfor the players in P .
A combined strategy (also, profile) x is called global if all players contribute to it, that
is, if P = P . The global strategies are the possible outcomes of the game.
A set of players K ⊆ P is often called a coalition. Let x be a global strategy, K a
coalition, and y a combined strategy for K. Then, we denote by x−K[y] the global strategywhere, for each player p ∈ K, her individual strategy pa ∈ x is replaced by her individualstrategy pb ∈ y. If K is a singleton p, we will simply write x−p[y].
Let x be a global strategy, p a player, and up the utility function of p. Then, with a
small abuse of notation, up(x) will denote the output of up on the projection of x to thedomain of up, i.e., the output of the function up applied to the actions played by p and herneighbors according to the strategy x.
In the context of complexity and efficiency studies it is very important to make clear
how an input (in our case, a multiplayer game) is represented.
General Form:
A game is in general form if the sets of players and actions are given in
extensional form, while the neighborhood and utility functions are given intentionally, e.g.,through encodings of deterministic Turing transducers. More precisely, we are interested inclasses of games such that the computation time of the neighborhood and utility functionsis globally bounded by some polynomial. Let us denote by Ck the class of all games Gin general form whose neighborhood and utility functions are computable in time O(nk),where n = |G|.
For the sake of presentation, we assume hereafter ¯
k ≥ 1 to be any such a fixed global
bound. Moreover, unless otherwise stated, when we speak of a “general game G” (or weomit any specification at all) we mean a game G ∈ C¯.
k
The following more restrictive classes of (representations of) games have been used by
many authors.
Standard Normal Form (SNF):
A game with set P of players is in standard normal
form (SNF) if its utility functions are explicitly represented by a single table or matrixhaving an entry (or cell) for each global strategy x, displaying a list containing for each player
2. Note the technical distinction between actions and strategies: an action is an element of the form a,
while a strategy is an element of the form pa , i.e., it is an action chosen by a player. This helps intechnical proofs, since a strategy singles out both a player and her choice.
365

 
Gottlob, Greco, and Scarcello
p, p’s payoff up(x) w.r.t. x. (Equivalently, we may describe the utilities by |P | such tables,where the i-th table describes just the payoff of player i.) This is a representation of utilityfunctions often assumed in the literature (see, for instance, Osborne & Rubinstein, 1994;Owen, 1982). Observe that, in the general case, even if an utility function is polynomiallycomputable, writing it down in form of a table may require exponential space.
Graphical Normal Form (GNF):
A game with a set P of players is in graphical normal
form (GNF) if the utility function for each player p is represented by a separate tablecontaining a cell for each combined strategy x ∈ St(Neigh(p) ∪ p) of the p’s set ofneighbors Neigh(p) ∪p, displaying p’s payoff up(x) w.r.t. x. A game in GNF is illustratedin Example 2.1. The GNF representation has been adopted in several recent papers thatstudy games with a large number of players, where the utility function of each player dependsdirectly only on the strategies of those (possibly few) players she is interested in (e.g. Kearnset al., 2001a, 2001b; Kearns & Mansour, 2002; Vickrey, 2002). Note that GNF may lead toan exponentially more succinct game representation than SNF. Notwithstanding, the SNFis often used in the literature, mostly because, historically, the first investigations focusedon two-player games. Moreover, games in GNF are often referred to as graphical games.We prefer to use the phrasing games in graphical normal form, because this makes clearthat we are addressing representational issues.
The following example, to which we will refer throughout the paper, should sound
familiar to everyone, as it is a generalization of the well known two-person game “battle ofsexes”.
Example 2.1 (FRIENDS) Let us consider the game FRIENDS, that is played by a groupof persons that have to plan their evening happenings. The players are George (short: G),Pauline (P ), Frank (F ), Robert (R), and Mary (M ). Each of them have to decide to goeither to see a movie (m) or to see an opera (o). However, preferences concern not only theparticular option (m or o) to be chosen, but usually also the persons to join for the evening(possibly, depending on the movie or opera choice). For instance, we assume that Frankis interested in joining Pauline and Robert. He would like to join both of them. However,Pauline is an expert of movies and Robert is an expert of operas. Thus, if it is not possibleto go out all together, he prefers to go to the cinema with Pauline and to the opera withRobert. Pauline would like to stay with Frank, and she prefers the movies. Robert doesnot like Frank because he speaks too much and, as we know, he prefers the opera. Mary,too, likes operas and would like to go to the opera with Robert. Finally, George is thematchmaker of the group: He has no personal preferences but would like that Frank andPauline stay together for the evening, best if they go to the cinema. All the utility functionsassociated with this game are shown in Figure 3, where we denote the fact that a player Xchooses an action a by Xa, e.g., Fm denotes the strategy where Frank chooses to play theaction m.
2
Let us now formally define the main concepts of equilibria to be further studied in this
paper.
Definition 2.2 Let G = P, Neigh, A, U be a game. Then,
366

 
Pure Nash Equilibria: Hard and Easy Games
F
PmRm
PmRo
PoRm
PoRo
G
PmFm
PmFo
PoFm
PoFo
m
2
2
1
0
m
2
0
0
1
o
0
2
1
2
o
2
0
0
1
R
Fm
Fo
P
Fm
Fo
M
Rm
Ro
m
0
1
m
2
0
m
1
0
o
2
0
o
0
1
o
0
2
Figure 3: Utility functions for FRIENDS in GNF
• a global strategy x is a pure Nash Equilibrium for G if, for every player p ∈ P ,
∃pa ∈ St(p) such that up(x) < up(x−p[pa]);
• a global strategy x is a pure strong Nash Equilibrium for G if, ∀K ⊆ P, ∀y ∈
St (K ), ∃p ∈ K such that up(x) ≥ up(x−K [y]) or, equivalently, if ∀K ⊆ P , ∃y ∈St (K ) such that, ∀p ∈ K, up(x) < up(x−K[y]);
• a pure Nash equilibrium x is a pure Pareto Nash Equilibrium for G if there does not
exist a pure Nash equilibrium y for G such that, ∀p ∈ P, up(x) < up(y).3
The sets of pure Nash, strong Nash, and Pareto Nash equilibria of G are denoted by
NE(G), SNE(G), and PNE(G), respectively. It is easy to see and well known that thefollowing relationships hold among these notions of Nash equilibria: SNE(G) ⊆ PNE(G) ⊆
NE(G). Moreover, the existence of a Nash equilibrium does not imply the existence of astrong Nash equilibrium. However, if there exists a Nash equilibrium, then there exists alsoa Pareto Nash equilibrium.
Example 2.3 The
strategies
Fm, Pm, Ro, Gm, Mo,
Fm, Pm, Ro, Go, Mo,
Fo, Po, Rm, Gm, Mm and Fo, Po, Rm, Go, Mm are the Nash equilibria of the FRIENDSgame. For instance, consider the latter strategy, where all players get payoff 1. In thiscase, since P plays opera and R plays movie, F cannot improve his payoff by changing fromopera to movie. The same holds for G, while R, P , and M would get the lower payoff 0, ifthey change their choices.
Moreover, note that the first two strategies above, namely Fm, Pm, Ro, Gm, Mo and
Fm, Pm, Ro, Go, Mo, are the only Pareto Nash equilibria, as well as the strong Nash equi-libria. Indeed, for these global strategies all players get their maximum payoff 2, and thusthere is no way to improve their utilities.
2
The interaction among players of G can be more generally represented by a hypergraph
H(G) whose vertices coincide with the players of G and whose set of (hyper)edges containsfor each player p a (hyper)edge H(p) = p∪ Neigh(p), referred-to as the characteristic edgeof p. Intuitively, characteristic edges correspond to utility functions.
3. Note that only pure strategies do matter in this definition, as there is no requirement with regard to
how pure candidate equilibria compare to possible mixed equilibria.
367

 
Gottlob, Greco, and Scarcello
A fundamental structural property of hypergraphs is acyclicity. Acyclic hypergraphs
have been deeply investigated and have many equivalent characterizations (e.g. Beeri et al.,1983). We recall here that a hypergraph H is acyclic if and only if there is a join tree for H,that is, there is a tree JT whose vertices are the edges of H and, whenever the same playerp occurs in two vertices v1 and v2, then v1 and v2 are connected in JT , and p occurs in eachvertex on the unique path linking v1 and v2 (see Figure 5 for a join tree of H(FRIENDS)).In other words, the set of vertices in which p occurs induces a (connected) subtree of JT .We will refer to this condition as the Connectedness Condition of join trees (also known asrunning intersection property).
Another representation of the interaction among players is through the (undirected)
dependency graph G(G) = (P, E), whose vertices coincide with the players of G, and p, q ∈E if p is a neighbor of q (or vice versa). For completeness we observe that, even if most workson graphical games use this dependency graph, another natural choice is representing thegame structure by a directed graph (also called influence graph), which takes into accountthe fact that payoffs of a player p may depend on payoffs of a player q and not vice versa, ingeneral. Following Kearns et al. (2001b), in the present paper we use the undirected versionbecause we are interested in identifying game structures that possibly allow us to computeefficiently Nash equilibria, and directed graphs do not help very much for this purpose. Letus give a hint of why this is the case, by thinking of a group of players ¯
X = X1, . . . , Xn,
each one having only one neighbor C, whose payoffs do not depend on any player in ¯
X.
Player C has one neighbor D, who has C has its only neighbor. Figure 4 shows a directedgraph representing these player interactions. It is easy to design a game with these players
Figure 4: A directed graph representation of player interactions.
such that, for some combined strategy x of the ¯
X players, there is no Nash equilibrium,
while for some other combined strategy x of these players, there is a combined strategy yof C and D such that the union of x and y is a Nash equilibrium for the game. Therefore,as far as the possibility of reaching a Nash equilibrium is concerned, the choices of playersin ¯
X depend on each other, on the way of playing of C, and transitively on player D, too.
Observe that the undirected dependency graph represents in a succinct way, i.e., throughtheir direct connections, such a mutual relationship among players. However, the directgraph does not model this kind of influence, as looking at this graph it seems that playersin ¯
X should not worry about any other player in the game. In fact, exploiting the gadgets
and the constructions described in this paper, it is easy to see that even simple games whosedirected influence graphs are quasi-acyclic (i.e., they are acyclic, but for some trivial cycleslike the one shown in Figure 4), are hard to deal with. Thus, apart from the well known
368

 
Pure Nash Equilibria: Hard and Easy Games
G
F
G
F
G
F
H (F,P,R)
F
P
R
P
R
P
R
H (P,F)
H (R,F)
P
R
M
M
M
H(FRIENDS)
(FRIENDS)
G
PG of H(FRIENDS)
H (G,F,P)
G
H (M,R)
M
Figure 5: Hypergraph, dependency graph, and primal graph of the FRIENDS game. On
the right, a join tree for H(FRIENDS).
easy acyclic cases, any reasonable generalization of the notion of direct acyclicity does notappear to be useful for identifying further tractable classes of games.
Observe that the dependency graph G(G) is different from the so called primal graph PG
of H(G), which contains an edge for all pairs of vertices that jointly occur in some hyperedgeof H(G). In general, G(G) is much simpler than PG. For instance, consider a game G witha player p that depends on all other players q1, . . . , qn, while these players are independentof each other (but possibly depend on p). Then, G(G) is a tree. However, the primal graphof H(G) is a clique with n + 1 vertices.
Example 2.4 The hypergraph H(FRIENDS), the graph G(FRIENDS) and the primalgraph of H(FRIENDS) are shown in Figure 5. Note that the dependency graph associ-ated with the FRIENDS game is not acyclic, even though the associated hypergraph isacyclic (on the right, we also report a join tree for it). Moreover, note that the dependencygraph differs from the primal graph, as player P is not a neighbor of R and viceversa.
2
3. Hard Games
In this section, we precisely characterize the complexity of deciding the existence of thedifferent kinds of pure Nash equilibria (regular, Pareto, and strong). This way, we are ableto identify the sources of complexity of such problems, in order to single out, in the followingsections, some natural and practically relevant tractable cases.
Every game considered in this section is assumed to be either in general or in graphical
normal form. Indeed, as we shall discuss in details in Section 4, for games in standardnormal form, computing pure Nash equilibria is a tractable problem, since one can easilyexplore the (big) table representing the utility functions of all players, in order to detectthe strategy of interest. Since this table is given in input, such a computation is triviallyfeasible in polynomial time.
We start by showing that deciding the existence of a pure Nash equilibrium is a difficult
problem, even in a very restricted setting.
369

 
Gottlob, Greco, and Scarcello
Figure 6: Schema of the reduction in the proof of Theorem 3.1.
Theorem 3.1 Deciding whether a game G has a pure Nash equilibrium is NP-complete.Hardness holds even if G is in GNF and has 3-bounded neighborhood, and the number ofactions is fixed.
Proof. Membership. We can decide that NE(G) = ∅ by guessing a global strategy x andverifying that x is a Nash equilibrium for G. The latter task can be done in polynomialtime. Indeed, for each player p and for each action a ∈ Act(p), we only have to check thatchoosing the strategy pa does not lead to an increment of up, and each of these tests isfeasible in polynomial time.Hardness. Recall that deciding whether a Boolean formula in conjunctive normal formΦ = c1 ∧ . . . ∧ cm over the variables X1, . . . , Xn is satisfiable, i.e., deciding whether thereexists truth assignments to the variables making each clause cj true, is the well knownNP-complete problem (CNF) SAT. Hardness holds even for its 3SAT restriction where eachclause contains at most three distinct (possibly negated) variables, and each variable occursin at most three clauses (Garey & Johnson, 1979). W.l.o.g, assume Φ contains at least oneclause and one variable.
We define a GNF game G such that: The players are partitioned into two sets Pv and Pc,
corresponding to the variables and to the clauses of Φ, respectively; for each player c ∈ Pc,Neigh(c) is the set of the players corresponding to the variables in the clause c, and foreach player v ∈ Pv, Neigh(v ) is the set of the players corresponding to the clauses in whichv occurs; t, f, u is the set of possible actions for all the players, in which t and f can beinterpreted as the truth values true and false for variables and clauses. Figure 6 shows thegraph G(G) for the game G associated with the formula (X1 ∨ X3 ∨ X4) ∧ (¬X2 ∨ X4) ∧(X4 ∨ X5 ∨ X6).
Let x be a global strategy, then the utility functions are defined as follows. For each
player c ∈ Pc, her utility function uc is such that
(i) uc(x) = 3 if c plays t, and all of her neighbors play an action in t, f  in such a way
that at least one of them makes the corresponding clause true;
(ii) uc(x) = 2 if c plays u, and all of her neighbors play an action in t, f  in such a way
that none of them makes the corresponding clause true;
(iii) uc(x) = 2 if c plays f and there exists v ∈ Neigh(c) such that v plays u;
(iv) uc(x) = 1 in all the other cases.
370

 
Pure Nash Equilibria: Hard and Easy Games
For each player v ∈ Pv, her utility function uv is such that
(v) uv(x) = 3 if v plays an action in t, f  and all of her neighbors play an action in t, f ;
(vi) uv(x) = 2 if v plays u and there exists c ∈ Neigh(v ) such that c plays u;
(vii) uv(x) = 1 in all the other cases.
We claim:
Φ is satisfiable ⇔ G admits a Nash equilibrium.
(⇒) Assume Φ is satisfiable, and take one of such satisfying truth assignments, say σ.
Consider the global strategy x for G where each player in Pv chooses the action accordingto σ, and where each player in Pc plays t. Note that, in this case, all players get payoff 3according to the rules (i) and (v) above, and since 3 is the maximum payoff, x is a Nashequilibrium for G.
(⇐) Let us show that each Nash equilibrium x for G corresponds to a satisfying truth
assignment of G. We first state the following properties of the strategies for G.
P1 : A strategy x in which a player v ∈ Pv plays u cannot be a Nash equilibrium. Indeed,
assume by contradiction that x is a Nash equilibrium. Then, all c ∈ Neigh(v ) mustplay f and have payoff 2, from rule (iii); otherwise they would get payoff 1, by rule (iv).However, in this case player v gets payoff 1 from rule (vii), and thus, from rule (v),she can easily increase her payoff to 3 by playing an action in t, f . Contradiction.
P2 : A strategy x in which a player c ∈ Pc plays u cannot be a Nash equilibrium. Indeed,
if there is such a player c that chooses u, then from rule (vi) each variable playerv ∈ Neigh(c) must play u, in order to get her maximum possible payoff 2 for the caseat hand. Therefore, x cannot be a Nash equilibrium, by property P1 above.
P3 : A strategy x in which all players play an action in t, f  and the corresponding truth
assignment makes a clause c false cannot be a Nash equilibrium. In fact, in this case,from rule (ii), c should play u in order to get its maximum possible payoff 2, andhence x is not a Nash equilibrium, by property P2.
P4 : A strategy x in which all players play an action in t, f  and there exists a player c ∈ Pc
that plays f cannot be a Nash equilibrium. Indeed, if x is a Nash equilibrium and allplayers play an action in t, f , by property P 3 the truth assignment corresponding tothis strategy satisfies each clause c. It follows that a player c that plays f contradictsthe assumption that x is a Nash equilibrium, because c could change her choice to t,improving her payoff to 3.
From these properties, it follows that every Nash equilibrium of G should be a strategy
where all players play either t or f and all players corresponding to clauses must play t andget payoff 3, as they are all made true by the truth assignment of their neighbors.
Combined with the “⇒”-part, this entails that there is a one-to-one correspondence
between satisfying truth assignments to the variables of Φ and Nash equilibria of the game G.
Finally, observe that the tables (matrices) representing the entries of the utility func-
tions (rules (i)–(vii) above) can be built in polynomial time from Φ. Moreover, from theassumptions that we made on the structure of Φ, each player depends on 3 other playersat most.
2
371

 
Gottlob, Greco, and Scarcello
It is worthwhile noting that, though quite limited, in the above proof the interaction
among players is rather complicated. In particular, it is easy to see that the dependencygraph of the game described in the hardness part of the proof is cyclic. Thus, one maywonder if the problem is any easier for games with simple structured interactions. We nextshow that, in the general setting, even if the structure of player interactions is very simple,the problem of deciding whether pure Nash equilibria exist remains hard.
Theorem 3.2 Deciding whether a game G in general form has a pure Nash equilibrium isNP-complete, even if both its dependency graph and its associated hypergraph are acyclic,and the number of actions is fixed.
Proof. Membership follows from the previous theorem. We next prove that this problem isNP-hard, via a reduction from SAT. Given a Boolean formula Φ over variables X1, ..., Xm,we define a game G with m players X1, ..., Xm corresponding to the variables of Φ, and twoadditional players T and H. Any player Xi, 1 ≤ i ≤ m, has only two available actions, t andf , corresponding to truth assignments to the corresponding variable of Φ. Moreover, theutility function of each player Xi is a constant, say 1. Hence, the choice of Xi is independentof any other player.
The actions of player T are s and u, which can be read “satisfied” and “unsatisfied,”
while the actions of player H are g and b, and can be read “good” and “bad,” respectively.The role of T is to check whether the actions chosen by X1, . . . , Xm encode a satisfying truthassignment for Φ. Indeed, their behaviors – described below – ensure that only strategieswhere T plays s may be Nash equilibria, because of her interaction with player H, whoserole is to discard bad strategies. Given a combined strategy x for the “variable players”X1, ..., Xm, we denote by Φ(x) the evaluation of Φ on the truth values determined by thestrategy x.
Player T depends on the players in X1, . . . , Xm, H, and her utility function is defined
as follows. For any combined strategy y = x1 ∪ x2 for X1, . . . , Xm, H, T , where x1 isa combined strategy for X1, ..., Xm and x2 for T and H:
• uT (y) = 1 if Φ(x1) is true and T plays s, or Φ(x1) is false and x2 = Tu, Hg, or
Φ(x1) is false and x2 = Ts, Hb;
• uT (y) = 0, otherwise.
Player H depends only on T and, for any combined strategy x for H and T , her utility
function is the following:
• uH(x) = 1 if x is either Ts, Hg or Tu, Hb;• uH(x) = 0, otherwise.
We claim there is a one-to-one correspondence between Nash equilibria of this game
and satisfying assignments for Φ. Indeed, let φ be a satisfying assignment for Φ and xφ thecombined strategy for X1, . . . , Xm where these players choose their actions according to φ.Then, xφ ∪ Ts, Hg is a Nash equilibrium for G, because all players get their maximumpayoff.
372

 
Pure Nash Equilibria: Hard and Easy Games
On the other hand, if Φ is unsatisfiable, for any combined strategy x1 for X1, . . . , Xm,
Φ(x1) is false. In this case, T and H have opposite interests and it is easy to check that, foreach combined strategy x2 ∈ St(H , T ), x1 ∪ x2 is not a Nash equilibrium for G, becauseeither H or T can improve its payoff.
Finally, observe that the dependency graph G(G) is a tree, and that the hypergraph
H(G) is acyclic.
2
As shown in Figure 2, the above NP-hardness result immediately extends to all gener-
alizations of acyclicity. The case of acyclic-hypergraph games in GNF will be dealt with inSection 4.
Let us now draw our attention to Pareto equilibria. By Definition 2.2, a Pareto Nash
equilibrium exists if and only if a Nash equilibrium exists. Therefore, from Theorems 3.1and 3.2, we get the following corollary.
Corollary 3.3 Deciding whether a game G has a Pareto Nash equilibrium is NP-complete.Hardness holds even if G has a fixed number of actions and if either G is in graphical normalform and has k-bounded neighborhood, for any fixed constant k ≥ 3, or if both G(G) andH(G) are acyclic.
However, while checking whether a global strategy x is a pure Nash equilibrium is
tractable, it turns out that checking whether x is a Pareto Nash equilibrium is a compu-tationally hard task. In fact, we next show that this problem is as difficult as checkingwhether x is a strong Nash equilibrium. However, we will see that deciding the existence ofa strong Nash equilibrium is much harder, and in fact complete for the second level of thePolynomial Hierarchy. To this end, in the following proofs, we associate quantified BooleanFormulas having two quantifier alternations (2QBFs) with games.
Quantified Boolean Formulas (QBFs) and games.
Let
Ξ
=
∃α1, . . . αn ∀β1, . . . βq
Φ
be a quantified Boolean formula in disjunctive normal form, i.e., Φ is a Boolean formula ofthe form d1 ∨. . .∨dm over the variables α1, . . . αn, β1, . . . βq, where each di is a conjunction ofliterals. Deciding the validity of such formulas is a well-known ΣP -complete problem – (e.g.
2
Stockmeyer & Meyer, 1973), and it is easy to see that hardness result holds even if eachdisjunct dj in Ξ contains three literals at most and each variable occurs in three disjunctsat most. Moreover, without loss of generality, we assume that the number m of disjuncts isa power of 2, say m = 2 , for some integer
≥ 2. Note that, if 2 −1 < m < 2 , then we can
build in polynomial time a new QBF Ξ having 2l − m more disjuncts, each one containingboth a fresh existentially quantified variable and its negation. Clearly, such disjuncts cannotbe made true by any assignment, and hence Ξ is equivalent to Ξ. Hereafter, we will considerquantified Boolean formulas of this form, that we call R2QBF. For each such formula Ξ, atruth value assignment σ to the existentially quantified variables α1, . . . , αn such that theformula ∀ β1, . . . βq
σ(Φ) is valid is called a witness of validity for Ξ.
As a running example for this section,
we consider the following QBF Ξr:
∃α1α2α3∀β1β2β3β4β5 (α1 ∧ α2) ∨ (α1 ∧ α3) ∨ (α1 ∧ ¬β1) ∨ (β1) ∨ (¬β2 ∧ ¬β3) ∨ (β1 ∧ β3) ∨(β3 ∧ β4) ∨ (β5).
373

 
Gottlob, Greco, and Scarcello
Figure 7: On the left: the dependency graph of the game GΞr. On the right: a truth-value
assignment for Ξr corresponding to a strong Nash equilibrium of GΞr.
We define a GNF game GΞ associated with a R2QBF Ξ as follows. The players of GΞ
are partitioned in five sets Pe, Pu, Pd, Pt, and the singleton C.
Players in Pe, Pu, and Pd correspond to the existential variables α1, . . . αn, to the univer-
sal variables β1, . . . βl, and to the m disjuncts of Φ, respectively. Each “variable” player v inPe ∪ Pu may play a “truth value” action in T, F  (read: true, false), and her neighborsare the (at most three) players in Pd corresponding to the disjuncts of Φ where v occurs.Each “disjunct” player p may play an action in T, F, w, and her neighbors are the (atmost three) players corresponding to her variables, plus one player belonging to the setPt, as described below. As shown in Figure 7, these disjunct players are the leaves of acomplete binary tree comprising all players in Pt as intermediate vertices, and the playerC as its root. In fact, the “tree” players Pt act as logical-or gates of a circuit. For the sakeof a simpler presentation, for each tree player p, children(p) denotes the set of two playersthat are children of p in this tree, while parent(p) denotes her parent. As for disjunct play-ers, the set of available actions for players in Pt is T, F, w. Finally, the player C, called“challenger,” may play actions in T, w. As shown in Figure 7, the neighbors of C are thetwo top level tree-players.
Let x be a global strategy. The utility functions for the players in GΞ are defined as
follows.
Existential-variables players. For each α ∈ Pe,
(E-i) uα(x) = 1, no matter of what other players do;
Universal-variables players. For each β ∈ Pu,
(U-i) uβ(x) = 2, if there exists a (disjunct) neighbor playing w;
(U-ii) uβ(x) = 1 in all other cases.
Disjuncts players. For each d ∈ Pd,
374

 
Pure Nash Equilibria: Hard and Easy Games
(D-i) ud(x) = 2 if d and her parent (i.e., a node from Pt) both play w, and the
disjunct of Φ corresponding to d is made false by the truth-value actions in x ofher variable players, i.e., by the players in Neigh(d ) ∩ (Pe ∪ Pu);
(D-ii) ud(x) = 1 if d plays T and the disjunct of Φ corresponding to d is made true
by the truth-value actions in x of her variable players;
(D-iii) ud(x) = 1 if d plays F , the disjunct of Φ corresponding to d is made false
by the truth-value actions of her variable players, and her parent node (a treeplayer) does not play w;
(D-iv) ud(x) = 0, in all other cases.
Tree players. For each p ∈ Pt,
(TREE-i) up(x) = 2 if both p and all of her neighbors play w;
(TREE-ii) up(x) = 1 if p plays T , none of her neighbors plays w, and some player
in children(p) plays T ;
(TREE-iii) up(x) = 1 if p plays F , none of her neighbors plays w, and all players in
children(p) plays F ;
(TREE-iv) up(x) = 1 if p plays an action in T, F , and some of her neighbors plays
w, but not all of them;
(TREE-v) up(x) = 0 in all other cases.
Challenger. For player C,
(CHALL-i) uC(x) = 2 if C plays w, and either both of her neighbors play F , or at
least one of them plays w;
(CHALL-ii) uC(x) = 1 if C plays T , some of her neighbors plays T , and none plays
w;
(CHALL-iii) uC(x) = 0 in all other cases.
Intuitively, universal-variable players corresponding to the variables β1, . . . βq choose
their actions trying to falsify the formula, since their maximum payoff 2 can be obtainedonly if Φ is not satisfied. The strategies of variable players are suitably “evaluated” byplayers in Pd ∪ Pt, and eventually by C.
It is worthwhile noting that GΞ can be built in polynomial time (actually, in LOGSPACE)
from Ξ, and that each player in GΞ may play at most three actions and has a boundednumber of neighbors. More precisely, for the sake of presentation, in the above constructioneach player has at most four neighbors. However, we will show later in this section how thisbound can be reduced easily to three.
Let x be a global strategy for GΞ. We denote by σ(x) the truth-value assignment for
Φ determined by the actions chosen by the variable players (i.e., those in Pe ∪ Pu) in thestrategy x. Moreover, we denote by σe(x) and σu(x) its restriction to the existential andthe universal variables, respectively.
Lemma 3.4 There is a one-to-one correspondence among the satisfying truth-value assign-ments for Φ and the Nash equilibria of GΞ where no player plays w.
375

 
Gottlob, Greco, and Scarcello
Proof. Assume Φ is satisfiable, and let σ be a satisfying truth-value assignment for it.Consider the following global strategy xσ for GΞ: each variable player in Pe ∪ Pu chooses hertruth-value action according to σ; each disjunct player in Pd plays either T or F , dependingon the logical evaluation of the disjunct associated with her; each tree player p in Pt playseither T or F , acting as an OR gate having as its input the values played by children (p);the player C plays T . Note that no player chooses w in xσ.
Figure 7 shows on the right the strategy for GΞ associated with the truth assignment
α1 = α2 = α3 = β1 = T and β2 = β3 = β4 = β5 = F .
Since σ is a satisfying assignment, at least one disjunct of Φ will be evaluated to true
and thus at least one of the tree-player neighbors of C plays T . Therefore, it is easy tocheck that, according to the utility functions of GΞ, all players get payoff 1 with respectto xσ. In particular, this follows from rule (D-ii) or (D-iii) for disjunct players, from rule(TREE-ii) or (TREE-iii) for tree players, and from rule (CHALL-ii) for the player C.
Moreover, the only rules that may increase some payoff from 1 to 2 are (TREE-i),
(CHALL-i) and (D-i). However, no single player can increase her payoff by changing heraction, because all these rules may be applied only if there is some neighbor that is playingw, which is not the case in xσ. It follows that the global strategy xσ is a Nash equilibriumfor GΞ.
We next prove the converse, that is, we show that each Nash equilibrium x for GΞ where
no player chooses w corresponds to a satisfying truth-value assignment for Φ. This proof isbased on the following properties of x:
P1 : At least one player in Neigh(C ) does not play F . Otherwise, C would play w in order
to get payoff 2, from rule (CHALL-i), contradicting the hypothesis on x.
P2 : At least one player in Pd plays T . Otherwise, since no player chooses w in x, the only
possible choice for all disjunct players would be F . However, in this case, the bestavailable choice for all tree-players depending on disjunct players in Pd is to play F ,according to (TREE-iii). It follows by induction that all players in Pt would play Fand, in particular, all neighbors of C. However, this contradicts property P1 of x.
P3 : Φ is satisfied by the truth-assignment σ(x). Let p ∈ Pd be a disjunct player that plays
T , and whose existence is guaranteed by property P2. From the hypothesis that noplayer chooses w, rule (D-i) is not applicable to p. It follows that the disjunction dof Φ corresponding to player p is true with respect to σ(x). Otherwise, x would notbe a Nash equilibrium, because p would get payoff 0 from (D-iv) and could improveit by playing the correct evaluation F , after rule (D-iii).
Therefore, in case no player chooses w, all global strategies that are Nash equilibria
correspond to satisfying assignments for Φ.
2
Lemma 3.5 A Nash equilibrium x for GΞ where no player chooses w is strong if and onlyif σe(x) is a witness of validity for Ξ.
Proof. (⇒) Assume x is a strong Nash equilibrium for GΞ where no player chooses w.Then, σ(x) satisfies Φ, from the previous lemma. Assume by contradiction that σe(x) isnot a witness of validity for Ξ. Then, there is an assignment σu for the universal variables
376

 
Pure Nash Equilibria: Hard and Easy Games
such that Φ is not satisfied with respect to σe(x) ∪ σu. Let K be the coalition comprisingall players in GΞ but the existential players in Pe, and let y be the combined strategy for Ksuch that all universal players in Pu choose their truth-value action according to σu, and allthe other players in K play w. By the choice of σu, all the disjuncts are made false via thetruth-value actions chosen by players in Pu. Then, from rule (D-i), all disjunct players getpayoff 2 according to x−K[y]. Similarly, from (Tree-i) and (Chall-i), all tree-players and theplayer C get payoff 2 in x−K[y]. However, this means that all players in the coalition areimproving their payoff, and this contradicts the fact that x is a strong Nash equilibrium.
(⇐) Assume that Ξ is valid and let σ(x) be a satisfying truth-value assignment for Φ
such that σe(x) is a witness of validity for Ξ, for some Nash equilibrium x for GΞ. Indeed,from Lemma 3.4 we know such an equilibrium (where no player plays w) exists for everysatisfying assignment, and that no player chooses w in x. Moreover, it is easy to check thatall players get payoff 1, according to this global strategy. Assume by contradiction that x isnot a strong Nash equilibrium for GΞ. Then, there is a coalition K and a combined strategyy for K such that all players in the coalition may improve their payoff in the global strategyx−K[y], and hence they get payoff 2 in this strategy. Note that no existential player maybelong to K and thus change her action, because there is no way for her to improve herpayoff. Then, from rule (Tree-i), the only way for players in Pt to improve their payoff to 2is that all of them change their actions to w, because all these rules require that, for eachplayer, all of her neighbors play w. Thus, if one of them belongs to K, then all of thembelong to this coalition, as well as player C and all the disjunct players in Pd, that are theirneighbors and should change her choices to w in order to get 2, too. On the other hand,for all disjunct players p in Pd, this improvement to 2 depends also on the variable playersoccurring in the disjunct of Φ associated with p (D-i). In particular, besides playing w, thisdisjunct should also be made false, because of some change in the choices of the universalplayers p depends on. Note that such players may in turn improve their payoff to 2, if p playsw. It follows any coalition K that shows x is not a Nash equilibrium contains a number ofuniversal players that are able to let all the disjunct players to be unsatisfied and hence tochange their actions to w, thus getting payoff 2. However, the truth-values correspondingto the actions of players in Pu ∩ K determine an assignment σu that contradicts the validityof Ξ.
2
Theorem 3.6 Given a game G and a global strategy x, deciding whether x ∈ SNE(G)(resp., x ∈ PNE(G)) is co-NP-complete. Hardness holds even if the given strategy x is apure Nash equilibrium, G is in graphical normal form and has 3-bounded neighborhood, andthe number of actions is fixed.
Proof. Membership. Deciding whether x ∈ PNE(G) is in NP: (i) check in polynomialtime whether x ∈ NE(G); (ii) if this is not the case, guess a global strategy y and checkin polynomial time whether y ∈ NE(G) and y dominates x. Similarly, deciding whetherx ∈ SNE(G) is in NP: (i) check in polynomial time whether x ∈ NE(G); (ii) if this is notthe case, guess a coalition of players K and a combined strategy y for the players in K,and check in polynomial time whether all the players in K increase their payoff by playingtheir actions according to the new strategy y.
377

 
Gottlob, Greco, and Scarcello
Figure 8: Transformation of a disjunct containing exactly three literals.
Hardness. It is well-known that checking whether a satisfiable formula Φ in 3DNF is tau-tologically valid is co-NP complete. We reduce this problem to the problem of checkingwhether a given Nash equilibrium is strong (Pareto). Let Φ be a satisfiable formula in3DNF. Find a satisfying truth value assignment σ for Φ. This is obviously possible inpolynomial time, given that Φ is satisfiable and in DNF. Define Ξ = ∀β1, . . . βq
Φ. Ξ can
be considered a (degenerate) R2QBF without existentially quantified variables. Let GΞ bethe game associated with Ξ. Obviously, GΞ can be constructed in polynomial time fromΦ. Let x be the Nash equilibrium for GΞ determined by this truth-value assignment whereno player chooses w, as described in Lemma 3.4, and note that even this equilibrium canbe computed in polynomial time from σ. Then, by Lemma 3.5, x is strong if only if Φ isvalid (i.e., the vacuous assignment σe is a witness of validity). This settles the hardness ofchecking whether a given Nash Equilibrium is strong. In addition, it is not hard to see thatin the above construction x is a Pareto equilibrium for GΞ if and only if Φ is a tautology.Indeed, note that, there is a truth-value assignment σ that falsifies Φ, if and only if thereis a global strategy y where (universal) variable players play according to σ and all otherplayers choose w, such that y dominates the Nash equilibrium x. Thus checking whether agiven Nash equilibrium is Pareto is co-NP complete, too.
We conclude the proof by observing that, in our reduction, each player in Pe ∪ Pu ∪ Pt ∪
C depends on three other players at most, but some player d in Pd may depend on fourother players, if the corresponding disjunct contains exactly three literals. In this case, wemay introduce an additional player d whose set of actions is T, F, w and whose neighborsare the first two literals plus d. Moreover, her utility function is such that d acts as anAND-gate on the inputs of the literals, preferring w if the two literals are evaluated false, orif d plays w. In this new encoding, d depends only on d and on the third literal occurringin the disjunct. As for the basic construction previously defined, her payoff is 2 if she playsw, her parent plays w, and the third literal is false, or if d plays w. Figure 8 shows thistransformation. Note that this construction preserves all the properties proved so far, andeach player depends on three other players at most.
2
Deciding whether a game has a strong Nash equilibrium turns out to be much more
difficult than deciding the existence of pure (Pareto) Nash equilibria. Indeed, this problemis located at the second level of the polynomial hierarchy.
Theorem 3.7 Given a game G, deciding whether G has a strong Nash equilibrium is ΣP -
2
complete. Hardness holds even if G is in graphical normal form and has 3-bounded neigh-borhood, and the number of actions is fixed.
378

 
Pure Nash Equilibria: Hard and Easy Games
Proof. Membership. We can decide that SNE(G) = ∅ by guessing a global strategy x andverifying that x is a strong Nash equilibrium for G. From Theorem 3.6, the latter task isfeasible in co-NP. It follows that the problem belongs to ΣP .
2
Hardness. Let Ξ = ∃α1, . . . αn∀β1, . . . βqΦ be a R2QBF. Recall that deciding the validityof such formulas is a ΣP -complete problem – see the definition of R2QBF above, in the
2
current section.
We define a game G associated with Ξ, obtained from G
Ξ
Ξ with the addition of one
more gadget. In G there is a fresh player D depending on the player C only. It is called
Ξ
“duplicator,” because D gets her maximum payoff if she plays the same action as thechallenger player C. On the other hand, also C depends on this new player D, besides herother tree-players neighbors (recall the construction shown in Figure 7). Both C and Dplay actions in T, w, u. Everything else is the same as in GΞ, but for the utility functionsof players C and D:
Challenger. For player C,
(CHALL-i) uC(x) = 2 if C and D play different actions in w, u and either all of
her tree-players neighbors (i.e., the players in Neigh(C ) − D) play F , or atleast one of them plays w;
(CHALL-ii) uC(x) = 1 if C plays T , one player in Neigh(C ) − D plays T , and
none plays w;
(CHALL-iii) uC(x) = 0 in all other cases.
Duplicator. For player D,
(DUPL-i) uD(x) = 1 if D plays the same action as C;
(DUPL-ii) uD(x) = 0 in all other cases.
Recall that, in order to maximize their payoffs, the universal-variable players try to
make Φ false, and that the strategies of variable players are suitably “evaluated” by playersin Pd ∪ Pt, acting as a Boolean circuit. Moreover, the challenger and the duplicator aredesigned in such a way that strategies where some player chooses w, which do not correspondto satisfying assignments for Φ, cannot lead to Nash equilibria. Formally, for any Nashequilibrium of G , the following properties hold.
Ξ
P1 : At least one player in Neigh(C )−D does not play F and no player in Neigh(C )−D
plays w. Otherwise, C would play an action in w, u different from the one playedby D in x, in order to get payoff 2, from rule (CHALL-i). However, such a strategycannot be an equilibrium, because D could improve her payoff by choosing the sameaction as C in x.
P2 : If a player in Pd ∪ Pt plays w then all players in Pd ∪ Pt play w. Indeed, let p be
a player in Pd ∪ Pt playing w and assume by contradiction that there is a player qin Pd ∪ Pt that does not play w. W.l.o.g., we can assume that q ∈ Neigh(p) andviceversa. Then, p gets payoff 0, but could increase her payoff by playing an action inT, F  according to (D-ii) or (D-iii) for players in Pd, and to (TREE-ii), (TREE-iii)or (TREE-iv) for players in Pt. This contradicts the fact that x is a Nash equilibrium.
379

 
Gottlob, Greco, and Scarcello
P3 : No player in Pd ∪ Pt plays w. Otherwise, from P2, all players in Pd ∪ Pt play w and,
in particular, the players in Neigh(C ) − D. However, this is not possible, afterproperty P1.
Therefore, rule (Chall-i) is not applicable for C with respect to x. However, from the
above properties at least one of her tree-players neighbors should play T and C can play Tin her turn and get payoff 1, from rule (Chall-ii). Then, D may play T and get payoff 1, aswell. Thus, it is no longer possible to have a Nash equilibrium with some player choosingthe action w. Therefore, after Lemma 3.5 (as the presence of the duplicator does not affectthat proof), we get the following fundamental result: a global strategy x is a strong Nashequilibrium for G if and only if the truth-value assignment σ
Ξ
e(x) is a witness of validity
for Ξ. In particular, SNE(G ) = ∅ if and only if Ξ is valid.
Ξ
Finally, observe that even the game G can be modified as shown in Figure 8, in order
Ξ
to get a 3-bounded neighborhood game.
2
We next show that, if the game is given in general form, the above hardness result holds
even if the structure of player interactions is very simple.
Theorem 3.8 Deciding whether a game G in general form has a strong Nash equilibriumis ΣP -complete, even if both its dependency graph and its associated hypergraph are acyclic,
2
and the number of actions is fixed.
Proof. The proof of membership in ΣP is the same as the membership proof in the previous
2
theorem. We next prove that this problem is hard for ΣP .
2
Let Ξ
=
∃α1, . . . αn∀β1, . . . βq Φ be a quantified Boolean formula in disjunctive
normal form. We define a game ¯
GΞ with m players α1, . . . αn, β1, . . . βq corresponding to
the existentially and universally quantified variables of Ξ, and two additional players T andH. The game is based on a combination of the game techniques exploited in the proofs ofTheorem 3.2 and Theorem 3.7. Any player associated with a variable has only two availableactions, t and f , which represent truth assignments to the corresponding variable of Φ; theactions of player T are s and u, which can be read “satisfied” and “unsatisfied,” while theactions of player H are g and b, and can be read “good” and “bad,” respectively.
Given a combined strategy x, we denote by Φ(x) the evaluation of Φ on the truth values
determined by the strategy x. Then, the utility functions are defined as follows. Any playerαi (1 ≤ i ≤ n) gets always payoff 1. Any player βj (1 ≤ j ≤ q) depends on T and getspayoff 1 if T plays s in x, and payoff 2 if T plays u in x. Player H depends only on T andgets payoff 1 if x contains either Ts, Hg or Tu, Hb, and 0, otherwise. Finally, player Tdepends on players in α1, . . . αn, β1, . . . βq, H, and her utility function is defined as follows:
• uT (x) = 2, if Φ(x) is false, T plays u, and H plays g;
• uT (x) = 1, if Φ(x) is true and T plays s, or if Φ(x) is false, T plays s, and H plays b;
• uT (x) = 0, otherwise.
First, observe that both the dependency graph and the dependency hypergraph of ¯
GΞ
are acyclic. Moreover, after the proof of Theorem 3.2, it is easy to see that there is a one-to-one correspondence between Nash equilibria of this game and satisfying assignments for
380

 
Pure Nash Equilibria: Hard and Easy Games
Φ. Then, for any Nash equilibrium x for ¯
GΞ, we denote by σx its corresponding truth-value
assignment, and by σx
e the restriction of this assignment to the existential variables of Ξ.
Note that, as shown in the above mentioned proof, at any Nash equilibrium, player T playss and all players in the game get payoff 1.
We next prove that any witness of validity for Ξ corresponds to a strong Nash equi-
librium for ¯
GΞ. Let x be a Nash equilibrium and consider a coalition K of players that
deviate from x, leading to a new profile x . From the definition of the game, the only wayfor the coalition to get a payoff higher than 1 is that T changes her choice to u. In thiscase, if Φ(x ) is false (and H plays g), T will get payoff 2. Since Φ is true with respect tox, it follows that some variable players have to change their choices, which means that theyshould belong to the coalition and improve their payoffs. Therefore, all variable playersin K should correspond to universally quantified variables, as only these players are ableto improve their payoffs from 1 to 2. Thus, such a coalition K exists if and only if theuniversally quantified variables can make the formula false, that is, σx
e is not a witness of
validity for Ξ. Equivalently, it follows that x is a strong Nash equilibrium if and only if Ξis valid.
2
Remark 3.9 Recall that we assumed any general game G to be taken from the class C¯.
k
It is worthwhile noting that, for games without restriction on player interactions, our
hardness results hold for games where the utility functions are computable in constant time,too. Namely, consider Theorems 3.1, 3.6, and 3.7. In these constructions, each player hasat most three neighbors and a fixed number of actions. Therefore, the utility function ofeach player is computable in constant time.
4. Easy Games
Before we deal with tractable games in graphical normal form (GNF), let us recall thatall computational problems dealt with in this paper are tractable for games in standardnormal form (SNF), even for arbitrary interactions among players. Actually, we next pointout that they can be carried out in logarithmic space and are thus in a very low complexityclass that contains highly parallelizable problems only. This is not very surprising, becausein fact the size of SNF games may be exponentially larger than the size of the same gamesencoded in GNF.
Theorem 4.1 Given a game in standard normal form, the following tasks are all feasiblein logarithmic space: Determining the existence of a pure Nash equilibrium, a pure Paretoequilibrium, or a strong Nash equilibrium, and computing all such equilibria.
Proof. Let P , as usual, denote the set of players. We assume w.l.o.g. that each player hasat least two possible actions (in fact, a player with a single action can be eliminated fromthe game by a simple logspace transformation, yielding an equivalent game). The size ofthe input matrix is thus at least 2|P |.
Given that all possible global strategies are explicitly represented, each corresponding
to a table cell (which can be indexed in logarithmic space in the size of the input, whichcorresponds to polynomial space in |P | × |A|, where P and A are the sets of players and the
381

 
Gottlob, Greco, and Scarcello
set of all possible actions, respectively), the Nash equilibria are easily identified by scanning(i.e., enumerating) all global strategies x keeping a logspace index of x on the worktape,and checking in logarithmic space (in the size of the input) whether no player can improveher utility by choosing another action. Given that all Nash Equilibria can be generated inlogarithmic space, they also can be generated in polynomial time.
The Pareto equilibria can be identified by successively enumerating all Nash equilibria
x, and by an additional loop for each x, enumerating all Nash equilibria y (indexed inlogarithmic space as above) and outputting x if there is no y such that, ∀p ∈ P , up(y) >up(x). The latter condition can be tested by means of a simple scan of the players.
Strong Nash equilibria can be identified by enumerating all Nash equilibria and by scan-
ning all possible coalitions of the players (which can be indexed in logarithmic space, astheir number is 2|P |) in order to discard those equilibria x for which there exists a coalitionK ⊆ P and a combined strategy y for K, such that for each p ∈ K, up(x) < up(x−K[y]).Finally, note that, for a fixed coalition K, the enumeration of all the combined strategies yfor K can be carried out by means of an additional nested loop, requiring logarithmic spacefor indexing each such strategy.
2
4.1 Constraint Satisfaction Problems and Games in Graphical Normal Form
Let us now consider games in GNF. We first establish an interesting connection betweenconstraint satisfaction problems and games. An instance of a constraint satisfaction problem(CSP) (also constraint network) is a triple I = (Var , U, C), where Var is a finite set of vari-ables, U is a finite domain of values, and C = C1, C2, . . . , Cq is a finite set of constraints.Each constraint Ci is a pair (Si, ri), where Si is a list of variables of length mi called theconstraint scope, and ri is an mi-ary relation over U , called the constraint relation. (Thetuples of ri indicate the allowed combinations of simultaneous values for the variables Si).A solution of a CSP instance is a substitution θ : Var −→ U , such that for each 1 ≤ i ≤ q,Siθ ∈ ri. The problem of deciding whether a CSP instance has any solution is called con-straint satisfiability (CS). Since we are interested in CSPs associated with games, wherevariables are players of games, we will use interchangeably the terms variable and player,whenever no confusion arises.
Let G = P, Neigh, A, U be a game and p ∈ P a player. Define the Nash constraint
NC (p) = (Sp, rp) as follows: The scope Sp consists of the players in p∪ Neigh(p), and therelation rp contains precisely all combined strategies x for p ∪ Neigh(p) such that thereis no yp ∈ St(p) such that up(x) < up(x−p[yp]). Thus note that, for each Nash equilibriumx of G, x ∩ St(Sp) is in rp.
The constraint satisfaction problem associated with G, denoted by CSP(G), is the triple
(Var , U, C), where Var = P , the domain U contains all the possible actions of all players,and C = NC (p) | p ∈ P, i.e., it is the set of Nash constraints for the players in G.
Example 4.2 The constraint satisfaction problem associated with FRIENDS game is(F, G, R, P, M , m, o, C), where the set of constraints contains exactly the following Nashconstraints: NC (F ) = (F , P, R, rF ), NC (G) = (G, P, F , rG ), NC (R) = (R, F , rR),NC (P ) = (P, F , rP ), and NC (M ) = (M , R, rM ), where the constraint scopes are shownin Figure 9.
2
382

 
Pure Nash Equilibria: Hard and Easy Games
G
P
F
R
F
P
F
F
P
R
m
m
m
rR :
o
m
rP :
m
m
m
m
m
o
m
m
m
o
o
o
m
m
o
m
m
o
rF :
o
m
o
rG :
o
m
o
m
o
m
m
o
m
M
R
o
o
m
o
o
m
r
o
o
o
m
o
o
M :
m
m
0
o
o
o
o
Figure 9: Constraint relations of the game FRIENDS in Example 2.1.
The structure of a constraint satisfaction problem I = (Var , U, C) is represented by the
hypergraph H(I) = (V, H), where V = Var and H = var (S) | C = (S, r) ∈ C, and var (S)denotes the set of variables in the scope S of the constraint C. Therefore, by definitionof CSP (G), the hypergraph of any game G coincides with the hypergraph of its associatedconstraint satisfaction problem, and thus they have the same structural properties.
The following theorem establishes a fundamental relationship between games and CSPs.
Theorem 4.3 A strategy x is a pure Nash equilibrium for a game G if and only if it is asolution of CSP (G).
Proof. Let x be a Nash equilibrium for G and let p be any player. Then, for each strategypa ∈ St(p), up(x) ≥ up(x−p[pa]). Since up depends only on the players in p ∪ Neigh(p),their combined strategy x ⊆ x is a tuple of NC (p), by construction. It follows that thesubstitution assigning to each player p its individual strategy pa ∈ x is a solution of CSP (G).
On the other hand, consider any solution θ of CSP (G), and let p be any player. Let
P = p ∪ Neigh(p) and x the combined strategy θ(q) | q ∈ P . Then, x is a tupleof NC (p), because θ is a solution of CSP (G). Thus, for each p, by definition of NC (p),there is no individual strategy for p that can increase her utility, given the strategies of theother players. It follows that the global strategy containing θ(p) for each player p is a Nashequilibrium for G.
2
The following theorem states the feasibility of the computation of CSP (G).
Theorem 4.4 Let G be a game having small neighborhood or in graphical normal form.Then, computing CSP (G) is feasible in polynomial time.
Proof. Let G = P, Neigh, A, U be a game having small neighborhood. We show thatNC (p) = (Sp, rp) can be computed in polynomial time. We initialize rp with all the com-bined strategies for p ∪ Neigh(p). The number of these combined strategies is boundedby
maxAct (G)|Neigh(p)| = 2 log(maxAct(G)|Neigh(p)|) ≤ 2 i(G)×log(||G||) = ||G||i(G),
where the intricacy i (G) of G is given by
maxNeigh(G) × log maxAct(G)
log ||G||
.
383

 
Gottlob, Greco, and Scarcello
Function NashEvaluation(J T : join tree of H(G)): Booleanbegin
Bottom-Up(J T );let v = (Sv, rv) be the root of JT ;if rv = ∅ then return false;else
Top-Down(J T );Select-equilibrium(J T );output J T ;return true;
end;
Procedure Bottom-Up(var T : tree)
Procedure Top-Down(var T : tree)
begin
begin
Done := the set of all the leaves of T ;
let v = (S
while ∃v ∈ T such that
v, rv) be the root of T ;
for each c = (Sc, rc) child of v do
(i) v ∈ Done, and
rc := rc
rv;
(ii) c | c is child of v ⊆ Done do
let Tc be the subtree of T rooted at c;
for each c = (Sc, rc) child of v do
Top-Down(T
r
c);
v := rv
rc;
end for
Done := Done ∪ v;
end;
end while
end;
Figure 10: Evaluation of an acyclic game.
Since G has small neighborhood, i(G) is bounded by some constant, and thus the set of allcombined strategies for p is polynomially bounded. The initialization process computes foreach p all corresponding combined strategies (via a simple enumeration), and thus takespolynomial time (in the size of G).
Now, for each tuple x in rp we have to check whether it should be kept in rp or not. Let
m = up(x). For each action a ∈ Act(p), compute in polynomial time m = up(x−p[pa]) anddelete x if m > m. It follows that CSP (G) can be computed in polynomial time from G.
A similar line of reasoning applies if G is in GNF. In this case, the utility functions are
explicitly given in input in a tabular form, and thus the computation of Nash constraintsis yet easier. In fact, this task is feasible in logspace for GNF games.
2
After Theorem 4.3, an acyclic-hypergraph game G having small neighborhood or in
graphical normal form can be solved in polynomial time. Indeed, G and CSP(G) have thesame hypergraph and, as shown by Gottlob et al. (2000), a solution of an acyclic constraintsatisfaction problem can be computed by (a slight adaptation of) the well known Yan-nakakis’s algorithm for evaluating acyclic conjunctive queries (Yannakakis, 1981), or by theLOGCFL algorithm proposed by Gottlob et al. (2000), which shows this problem is highlyparallelizable — see Section 6, for more information on the complexity class LOGCFL. Forthe sake of completeness, in Figure 10, we report an algorithm for deciding the existence ofa Nash equilibrium and for computing Nash equilibria of acyclic-hypergraph games, basedon these results. We assume the reader is familiar with typical database operations likesemi-joins (for more details, see, e.g., Maier, 1986).
The algorithm takes in input a join tree J T of H(G). With a small abuse of notation,
each vertex of J T , which is formally a hyperedge Hv associated with a player v, is alsoused to denote the player herself as well as the Nash constraint (Sv, rv) associated with v.
384

 
Pure Nash Equilibria: Hard and Easy Games
Procedure Select-equilibrium(var T : tree)begin
let v = (Sv, rv) be the root of T ;select any combined strategy tv ∈ rv s.t. ∀tv ∈ rv, uv(tv) ≤ uv(tv);
delete all tuples in rv, but tv;for each c = (Sc, rc) child of v do
rc := rc
rv;
let Tc be the subtree of T rooted at c;Select-equilibrium(Tc);
end for
end;
Figure 11: Selection of a (Pareto) Nash equilibrium of an acyclic game.
The algorithm consists of two phases. In the first bottom-up phase, the constraint relationrv of each node v = (Sv, rv) of JT is filtered by means of a semijoin with the constraintrelation rc (denoted by rv
rc) of each of her children c in JT . This semijoin eliminates
all tuples from rv corresponding to combined strategies of the players in P = (Neigh(c) ∪
c) ∩ (Neigh(v) ∪ v)) that are not available (or no longer available) in rc.
This way, all tuples corresponding to strategies that do not match and hence cannot lead
to Nash equilibria are deleted, starting from the leaves. Finally, either the root is empty andhence G does not have equilibria, or the tuples remaining in the root p encode the strategiesthat p may choose in Nash equilibria of the game. In the top-down phase, this propertyof the root is propagated down the tree by taking the semi-join of every vertex with all itschildren. At the end, we get a tree such that all tuples encode strategies belonging to Nashequilibria and, vice versa, all Nash equilibria are made from strategies in the relations storedin J T . Then, by standard techniques developed for acyclic database queries and CSPs, wecan compute from J T all Nash equilibria of G in a backtrack-free way, and thus in timepolynomial in the combined size of the input game and of the equilibria in output. Notethat this is the best we can do, as a game may have an exponential number of equilibria.
For completeness, Figure 11 shows Procedure Select-equilibrium, that selects from J T
one Nash equilibrium. It is very similar to Procedure Top-Down, but for the selection stepbefore semi-joins: for any vertex, Select-equilibrium first picks a combined strategy tv ∈ rv,deletes all other tuples in rv, and then performs the semi-joins with its children and callsitself recursively, to propagate the choice of tv towards the leaves of the tree. Note that theselection of tv may be arbitrary, after the previous bottom-up and top-down steps. However,in Figure 11 we select strategies giving the best payoffs, in order to get a Nash equilibriumthat cannot be dominated by any other Nash equilibrium.
Theorem 4.5 Deciding the existence of pure Nash equilibria, as well as computing a Nashequilibrium is feasible in polynomial time for all classes C of acyclic-hypergraph games suchthat every game G ∈ C has small neighborhood or is in graphical normal form.
From the above discussion, it immediately follows that this tractability result can be
extended to the problem of computing a Pareto Nash equilibrium.
Theorem 4.6 Deciding the existence of Pareto Nash equilibria, as well as computing aPareto Nash equilibrium for pure strategies is feasible in polynomial time for all classes C
385

 
Gottlob, Greco, and Scarcello
Function InCoalitionx,JT (Hp : vertex, st: combined strategy): booleanbegin
let (Sp, rp) be the constraint associated with player p and N+ = p ∪ Neigh(p);guess a tuple st ∈ rp such that st matches st on the players they have in common;if p’s strategy in st is different from her strategy in x and up(x−N+ [st ]) ≤ up(x) then
return false;
else
let Kp be the set of children of Hp in the join tree JT ;if Kp = ∅ then
return true;
else
return
H
InCoalitionx,JT (H
p ∈Kp
p ,st );
end if
end.
Figure 12: Algorithm for deciding the existence of a coalition improving x.
of acyclic-hypergraph games such that every game G ∈ C has small neighborhood or is ingraphical normal form.
Proof. Recall that Procedure Select-equilibrium in Figure 11, at each vertex v encounteredduring the visit of J T , select a combined strategy that guarantees to the player correspond-ing to v the maximum payoff over the available choices (that, at this point, are all andonly those strategies that may lead to Nash equilibria). In particular, the payoff of the firstplayer to be evaluated, say the root p, cannot be worse than the payoff of p in any otheravailable strategy. Thus, the tuples left in J T after this procedure encode a Pareto Nashequilibrium of G, as it cannot be strictly dominated by any other Nash equilibrium.
For the sake of completeness, we point out that, differently from the previous case of
plain Nash equilibria, from J T we cannot compute easily all Pareto Nash equilibria of thegame in input-output polynomial time.
2
One may thus wonder whether the above result holds for strong Nash equilibria, too.
Unfortunately, we next show that computing a Strong Nash equilibrium is a difficult problemeven in the case of acyclic interactions among players. However, the complexity is reducedby one level with respect to the arbitrary interaction case, because checking whether a givenequilibrium is strong is feasible in polynomial time in the acyclic case.
Lemma 4.7 Let G be an acyclic-hypergraph game that has small neighborhood or is ingraphical normal form, and let x be a global strategy. Then, deciding whether x ∈ SNE(G)is feasible in polynomial time.
Proof.
Since G has small neighborhood or is in graphical normal form, from Theorem
4.4 we can build in polynomial time the constraints associated with each player. Moreover,its hypergraph H(G) is acyclic and thus it has a join tree. Let JT be a join tree of H(G).We show how to use J T for deciding in polynomial time whether the strategy x is not inSNE(G), i.e., that there exists a coalition C of players getting an incentive to deviate alltogether from x. Then, the result follows because PTIME is closed under complementation.Specifically, we next show an implementation of this task by an alternating Turing machineM with a logarithmic-space working tape. Therefore, the problem is in ALOGSPACE,which is equal to PTIME (Chandra, Kozen, & Stockmeyer, 1981).
386

 
Pure Nash Equilibria: Hard and Easy Games
The machine M for deciding whether x is not a strong Nash equilibrium works as follows:
• guess a player q;
• guess a strategy stq for q that is different from her choice in x;
• root the tree JT at the vertex corresponding to the characteristic edge Hq of player q;
• check that InCoalitionx,JT (Hq, stq) returns true, where InCoalitionx,JT is the Boolean
function shown in Figure 12.
Intuitively, the non-deterministic Turing machine first chooses a player q belonging to
a possible coalition C disproving x. Thus, q should improve her payoff, and in general –unless x is not a strong Nash equilibrium, getting this improvement may require that someof her neighbors Kq deviate from x and hence belong to C. However, in this case, all playersin Kq should be able to improve their payoffs. Again, to do that, they can involve otherplayers in the coalition, and so on.
Whether or not this process is successful is checked by the recursive Boolean function
InCoalitionx,JT , which takes in input a vertex Hp of the join tree JT and a combinedstrategy st. Recall that each vertex of the join tree is an (hyper)edge of the hypergraph,corresponding to a player of G. In particular, Hp is the characteristic edge of player p.InCoalitionx,JT has to check whether all players deviating from the given global strategy xare able to improve their payoffs. At the first call of this function, the first parameter Hqis the root of J T and identifies the first player q chosen for the coalition C. The secondparameter st is the strategy chosen by q, which is different from q’s corresponding choicein x. At a generic recursive call, the first parameter Hp identifies a player p to be checked,and the second parameter st encodes a combined strategy for the player w associated withthe parent Hw of Hp in JT and for w’s neighbors. Now, the function has to check thateither p does not change her choice with respect to x, or she changes and improves herpayoff. To this end, the function guesses a tuple st ∈ rp, where rp is the constraint relationassociated with p. Then, st encodes a combined strategy for p and her neighbors. Thisstrategy has to match the parameter st on the players they have in common, because stcontains the actions already chosen by the algorithm when the parent Hw of Hp has beenevaluated. Then, if p’s choice in st is different from p’s choice in x, it means that p has beennon-deterministically chosen as a member of the coalition C. Thus, p should improve herpayoff, or she immediately causes the fail of this computation branch of the nondeterministicTuring machine. Otherwise, that is, if p plays the same action as in x, then she does notbelong to C and the function has to check, recursively, that in the rest of the join tree alldeviating players improve their payoffs. This is done by propagating the current combinedstrategy st to the children of Hp in JT . Observe that this propagation is necessary even ifp does not belong to C, because connected coalitions do not necessarily induce connectedsubtrees in J T . Indeed, it may happen that some player z belonging to the coalition is aneighbor of both p and w, but her characteristic edge Hz occurs far from Hw in the jointree, possibly in the subtree of J T rooted at p. (For the sake of completeness, note that inthis case z should be a neighbor of all players occurring in the path from Hz to Hw in JT ,from the connectedness property of join trees.)
387

 
Gottlob, Greco, and Scarcello
Figure 13: On the left: the dependency graph of the game G(Φs). On the right: a coalition
witnessing that c5 and c7 are playing in a conflicting way.
Finally, let us consider briefly the low-level implementation of the alternating Turing
machine M . Existential states correspond to guesses, while universal states correspond tothe recursive calls to InCoalitionx,JT , plus some further machinery for auxiliary computa-tions. At each step, we have to encode on the worktape the two parameters p and st and thelocal variables, while x, J T , the game G and the pre-computed constraint relations are onthe input tape. Note that p may be encoded by the logspace pointer to her position in theinput tape, as well as any combined strategy stw may be encoded by a logspace pointer toits corresponding entry in the constraint relation associated with w. Similar considerationsapply to the other local variables, e.g., the guessed combined strategy st . Moreover, it iseasy to check that all the computations performed by the function are feasible in logspace.Therefore M is a logspace ATM, and the overall computation is in PTIME. (For a detaileddescription of such logspace ATM computations, we refer the interested reader to Gottlobet al., 2001; Gottlob, Leone, & Scarcello, 2002a).
2
Theorem 4.8 Let G be an acyclic-hypergraph game that has small neighborhood or is ingraphical normal form. Then, deciding whether G has strong Nash equilibria, i.e., SNE(G) =
∅ is NP-complete. Hardness holds even if G is in graphical normal form and has 3-boundedneighborhood.
Proof.
Membership. Given the game G, we can guess a global strategy x and verify in
polynomial time, by Lemma 4.7, that x is in fact a strong Nash equilibrium.
Hardness. The reduction is from SAT. Consider a Boolean formula in conjunctive normal
form Φ = c1 ∧ . . . ∧ cm over variables X1, . . . , Xn and assume, w.l.o.g, that m = 2 , for some
> 0. As a running example, consider the formula Φs = (X1 ∨ X2) ∧ (X1 ∨ X3) ∧ (X1 ∨
¬X4 ∨ X8) ∧ (X4) ∧ (¬X5 ∨ ¬X6) ∧ (X1 ∨ X4 ∨ X6) ∧ (X6 ∨ X7) ∧ (X8).
From Φ, we build the following GNF game G(Φ). The players are partitioned in two
sets Pc and Pt. The set Pc contains exactly one player for each clause of Φ, while playersin Pt are such that G(G) is a complete binary tree, whose leaves are the players in Pc, asshown in Figure 13 for Φs.
388

 
Pure Nash Equilibria: Hard and Easy Games
Players in G(Φ) play actions corresponding to variables in Φ plus some further special
actions.
Intuitively, each player c ∈ Pc may play a literal occurring in the clause she
represents, while players in Pt have to check that no pair of players ci, cj ∈ Pc plays ina conflicting way, that is, plays complementary literals. To this end, the game rules aredesigned in such a way that players in Pt may improve their payoffs if they are able toform a coalition proving that some pair of players are playing complementary literals. It isworthwhile noting that, in general, this situation cannot be detected by any single player,since the conflicting clauses may be very far from each other. For instance, in Figure 13, c5and c7 play ¯
x6 and x6, respectively, which is detected by a coalition involving their lowest
common ancestor, say p, and the players of Pt occurring in the two paths from c5 and c7 top. We show that a global strategy is a strong Nash equilibrium of this game if and only ifthere is no such a disproving coalition. Indeed, in this case, there are no conflicting clausesand thus the formula Φ is satisfiable by setting to true all literals played by the clauseplayers.
Formally, each player c ∈ Pc may play either a special action B (read: bad) or an action
xi (resp. ¯
xi) called literal action, provided that Xi is a variable occurring positively (resp.
negatively) in the corresponding clause of Φ. Each player t ∈ Pt may play an action in
vi, wi, ¯
wi | Xi is a variable in Φ ∪ T , where T can be read as “okay with me!”
We next describe the utility functions, given any global strategy x.A player c ∈ Pc gets payoff 1 if she plays a literal action and her unique neighbor (i.e.,
her parent) plays T , or if she plays B and her neighbor does not play T (C-i); otherwise,she gets payoff 0 (C-ii).
For a player t ∈ Pt, the utility function ut is such that:
(T-i) ut(x) = 2 if t plays wi, her parent (if any) plays wi or vi, none of her children plays
B, and one of her children plays either wi or xi (depending on whether she is a leafor not);
(T-ii) ut(x) = 2 if t plays ¯
wi, her parent (if any) plays ¯
wi or vi, none of her children plays
B, and one of her children plays either ¯
wi or ¯
xi;
(T-iii) ut(x) = 2 if t plays vi, her parent (if any) plays T , and her children play either xi
and ¯
xi or wi and ¯
wi;
(T-iv) ut(x) = 1 if t plays T ;
(T-v) ut(x) = 0 in all the other cases.
Then, G(Φ) has the following properties.
P1 : Let x be a global strategy for G(Φ). Then, x is a Nash equilibrium if and only if all
players in Pt play T in x and there is no player in Pc playing B.
If players in Pt play T and players in Pc do not play B, then they get payoff 1 dueto rules (T-iv) and (C-i). In this case, no player has an incentive to deviate, since bychanging strategy she would get payoff 0 due to rules (T-v) and (C-ii).
For the other direction of the proof, let x be a Nash equilibrium and assume, bycontradiction, that there is a player c ∈ Pc choosing B. From (C-i) and (C-ii), it
389

 
Gottlob, Greco, and Scarcello
follows that some neighbor of c, say t, does not play T . However, this is impossible,because t would get payoff 0 (from T-v) and could improve her payoff by playing T ,contradicting the fact that x is a Nash equilibrium. Next, assume there exists a playerin Pt that does not play T , and let t ∈ Pt be a player at the lowest possible level ofthe tree satisfying this assumption. It follows that the children of t are clause players,for otherwise, by the choice of t, both of them should play T , and thus t would getpayoff 0 (T-V) and could improve to 1 by playing T . Therefore, Neigh(t ) ∩ Pc = ∅.Then, the only way for t to get payoff greater than 0 comes from rule (T-iii), whichmeans that her clause children play in a conflicting way, say xi and ¯
xi. However, since
t does not play T , they both get payoff 0 and thus could deviate from x by playing Band getting payoff 1. Contradiction.
P2 : Let x be a Nash equilibrium for G(Φ). Then, a coalition of players getting an incentive
to deviate from x exists if and only if there are two clauses playing in x in a conflictingway.
(If part.) Since x is a Nash equilibrium, from Property P1, all players in Pt play T andget payoff 1. If there are two clauses, say c1 and c2, playing xi and ¯
xi, respectively,
we may identify an improving coalition as follows: let t be first common ancestor ofc1 and c2, and let P1 and P2 be the sets of vertices (players) occurring in the pathsfrom t to c1 and c2, respectively. Then, let t change to vi, and all the players in P1(resp. P2) change to wi (resp. ¯
wi) in x – see Figure 13. Then, from the game rules
above, all players in the coalition K = P1 ∪ P2 ∪ t get payoff 2, improving the payoff1 that they get in x.
(Only-if part.) Let K be a coalition of players improving the Nash equilibrium x.From property P1, all players in Pt ∩ K should get payoff 2, as they get 1 in x. Lett ∈ K by the player in Pt at the highest (close to the root) level in the tree, i.e., suchthat parent(t), if any, does not belong to K. From (T-iii), the children of t must playeither xi and ¯
xi or wi and ¯
wi, depending on whether they are or are not leaves of
the tree. In the former case, we have identified two conflicting players and thus theproperty is immediately proved. Hence, let us investigate the latter one. Let t and tbe the children of t playing wi and ¯
wi, respectively. Since they do not play T , both t
and t belong to K and have to improve their payoff to 2. Therefore, a child of t mustplay wi and a child of t must play ¯
wi, according to (T-i) and (T-ii). Therefore, these
players belong to K, too, and the same happen for some of their children. Eventually,a leaf descendant of t plays xi and a leaf descendant of t plays ¯
xi, qed.
The NP hardness of deciding the existence of a SNE follows from the following claim:
Φ
is satisfiable ⇔ G(Φ) admits a strong Nash equilibrium.
(⇒) Assume Φ is satisfiable and take a satisfying assignment σ. Let xσ be a global
strategy such that: each player c ∈ Pc plays any literal occurring in the clause c that is truewith respect to σ; and each player t ∈ Pt plays T . From P1, xσ is a Nash equilibrium for
G(Φ). Moreover, by construction no pair of players choose conflicting actions in xσ. Hence,due to P2, there exists no coalition of players getting an incentive by deviating from xσ,and thus xσ is strong. (⇐) Let x be a strong Nash equilibrium for G(Φ). Then, there isno coalition of players getting an incentive to deviate from x. Due to P1, no player in Pc
390

 
Pure Nash Equilibria: Hard and Easy Games
plays B, and due to P2 no pair of players play in a conflicting way. Hence, σx witnessesthat Φ is satisfiable. More precisely, it encodes an implicant of Φ, that can be extended toa satisfying assignment choosing any truth value for all Boolean variables occurring in Φnot chosen by any player in x.
2
5. Further Structurally Tractable Classes of Games
For strategic games, both the acyclic graph and the acyclic hypergraph assumptions arevery severe restrictions, which are rather unlikely to apply in practical contexts. In thissection, we prove that even more general and structurally complicated classes of gamescan be dealt with in an efficient way. We consider the notions of treewidth (Robertson &Seymour, 1986) and hypertree width (Gottlob et al., 2002b), which are the broadest knowngeneralizations of graph and hypergraph acyclicity, respectively (Gottlob et al., 2000). Weshow that tractability results for acyclic games hold for these generalizations, too, and studythe relationship between the two notions.
5.1 Hypertree Decompositions of Games
Let H = (V, E) be a hypergraph. Denote by vert (H) and edges(H) the sets V and E,respectively. Moreover, for any set of edges E ⊆ edges(H), let vert(E ) =
h.
h∈E
A hypertree for a hypergraph H is a triple T, χ, λ , where T = (N, E) is a rooted
tree, and χ and λ are labeling functions which associate with each vertex p ∈ N twosets χ(p) ⊆ vert(H) and λ(p) ⊆ edges(H). If T = (N , E ) is a subtree of T , we defineχ(T ) =
χ(v). We denote the root of T by root(T ). Moreover, for any p ∈ N , T
v∈N
p
denotes the subtree of T rooted at p.
Definition 5.1 (Gottlob et al., 2002b) A hypertree decomposition of a hypergraph His a hypertree HD = T, χ, λ for H, where T = (N, E), which satisfies all the followingconditions:
1. for each edge h ∈ edges(H), there exists p ∈ N such that vert(h) ⊆ χ(p) (we say that
p covers h);
2. for each vertex Y ∈ vert(H), the set p ∈ N | Y ∈ χ(p) induces a (connected) subtree
of T ;
3. for each p ∈ N , χ(p) ⊆ vert(λ(p));
4. for each p ∈ N , vert(λ(p)) ∩ χ(Tp) ⊆ χ(p).
An edge h ∈ edges(H) is strongly covered in HD if there exists p ∈ N such that vert(h) ⊆χ(p) and h ∈ λ(p). In this case, we say that p strongly covers h. A hypertree decompositionHD of hypergraph H is a complete decomposition of H if every edge of H is strongly coveredin HD. The width of a hypertree decomposition T, χ, λ is maxp∈vertices(T)|λ(p)|. Thehypertree width hw(H) of H is the minimum width over all its hypertree decompositions.
Note that for any constant k checking whether a hypergraph has hypertree-width at
most k is feasible in polynomial time (Gottlob et al., 2002b).
391

 
Gottlob, Greco, and Scarcello
F,L,G,M,P,R HF, HL
G
F
P
R
F,G,P H
F,M,P,R HM, HR
G
L
L
M
F,P H 
P
Figure 14: H(FRIENDS’) and a hypertree decomposition for it.
Let k > 0 be a fixed constant. Then, we say that a game G has k-bounded hypertree
width if the hypertree width of its associated hypergraph H(G) is at most k. A hypertreedecomposition of width at most k (if any) can be computed in polynomial time.
Recall that the notion of bounded hypertree-width generalizes the notion of (hyper-
graph) acyclicity. In particular, the class of acyclic-hypergraph games is precisely the classof games G whose hypergraph H(G) has hypertree width 1.
Example 5.2 Consider again the game FRIENDS in Example 2.1. Figure 5 shows on theleft its associated hypergraph, and on the right a join tree for it. In fact, this join tree is ahypertree decomposition of width 1 for the hypergraph, where, for each vertex p, λ(p) is theset of hyperedges reported in p and χ(p) is the set of players occurring in these hyperedges.
For a more involved example, consider the extension FRIENDS of FRIENDS where a
new player Laura (short: L) joins the group. Laura would like to go with George to thecinema, and with Pauline and Mary to the opera. Figure 14 shows on the left the hyper-graph H(FRIENDS’). This hypergraph is not acyclic, but with a low degree of cyclicity.Indeed, its hypertree width is 2, as witnessed by the hypertree decomposition of width 2shown on the right, in Figure 14. Here, for each vertex p of the decomposition tree, the twosets denote its labels χ(p) and λ(p), respectively.
2
A class of games C is said to have bounded hypertree-width if there is a finite k such
that, for each game G ∈ C, G has k-bounded hypertree width. We next show that all thetractability results that hold for acyclic-hypergraph games holds for bounded hypertree-width games, as well.
Theorem 5.3 Deciding the existence of pure Nash equilibria, as well as computing a Nashequilibrium is feasible in polynomial time for all classes C of games having bounded hypertree-width and such that every game G ∈ C has small neighborhood or is in graphical normalform.
Proof. Let C be a class of games such that each game G ∈ C has hypertree-width at mostk, for some k > 0, and has small neighborhood or is in graphical normal form. Then, wecan build the constraint satisfaction problem CSP (G) in polynomial time, by Theorem 4.4.
392

 
Pure Nash Equilibria: Hard and Easy Games
Moreover, the hypertree width of G is at most k, and its hypergraph H(G) is the same asthe hypergraph H associated with CSP (G). From results by Gottlob et al. (2001), it followsthat CSP (G) can be solved in polynomial time, which is equivalent to deciding the existenceof Nash equilibria in polynomial time, by Theorem 4.3.
Constructively, we can compute in polynomial time a hypertree decomposition of H hav-
ing width at most k, exploit this decomposition for building an equivalent acyclic problem(by putting together the constraints of players occurring in the same vertex of the decom-position tree), and finally solve this problem by using the algorithm shown in Figure 10. 2
As for acyclic-hypergraph games, this result can be immediately extended to the problem
of computing a Pareto Nash equilibrium.
Corollary 5.4 Deciding the existence of Pareto Nash equilibria, as well as computing aPareto Nash equilibrium for pure strategies is feasible in polynomial time for all classesC of games having bounded hypertree-width and such that every game G ∈ C has smallneighborhood or is in graphical normal form.
5.2 Treewidth and Hypertree Width of Games
We next consider the treewidth of game structures. Recall that any game may be repre-sented either by the primal graph or by the dual graph, as shown in Figure 5 for the gameFRIENDS. Therefore, a first question is which graph is better as far as the identification oftractable classes of games is concerned. From the results by Gottlob et al. (2000), we knowthat the notion of bounded treewidth for the primal graph is generalized by the notion ofbounded hypertree width, that is, looking at the hypertree width of the game hypergraphwe may identify wider classes of tractable games. Moreover, from the results by Greco andScarcello (2003), it follows that looking at the treewidth of the dependency graph is betterthan looking at the treewidth of the primal graph.4
We thus know that bounded treewidth for the primal graph is sufficient for ensuring
game tractability. However, two questions are still to be answered, and will be the subjectof this section:
1. Do tractability results for bounded treewidth for the primal graph extend to the wider
class of games having bounded treewidth for the dependency graph?
2. What is the relationship between bounded treewidth for the dependency graph and
bounded hypertree width of the game hypergraph?
Definition 5.5 (Robertson & Seymour, 1986) A tree decomposition of a graph G =(V, E) is a pair T, χ , where T = (N, F ) is a tree, and χ is a labeling function assigningto each vertex p ∈ N a set of vertices χ(p) ⊆ V , such that the following conditions aresatisfied:
(1) for each vertex b of G, there exists p ∈ N such that b ∈ χ(p);
4. In fact, this result is on relationship between primal graph and incidence graph. However, it is easy to
see that, for games, the treewidth of the incidence graph is the same as the treewidth of the dependencygraph.
393

 
Gottlob, Greco, and Scarcello
G
F
F,L,P,R
P
R
L,P,R,M
F,G,L,P
L
M
Figure 15: G(FRIENDS’) and a tree decomposition for it.
(2) for each edge b, d ∈ E, there exists p ∈ N such that b, d ⊆ χ(p);
(3) for each vertex b of G, the set p ∈ N | b ∈ χ(p) induces a connected subtree of T .
Note that Condition 1 is subsumed by Condition 2 for graphs without isolated vertices.
The width of the tree decomposition T, χ is maxp∈N |χ(p) − 1|. The treewidth of G is theminimum width over all its tree decompositions. This notion generalizes graph acyclicity,as the acyclic graphs are precisely those graphs having treewidth 1. 5
Example 5.6 Consider again the game FRIENDS introduced in the Example 5.2. Fig-ure 15 shows on the left the cyclic dependency graph G(FRIENDS’), and on the right atree decomposition of width 3 of this graph.
2
Let k > 0 be a fixed integer, and let G be a game. We say that a game G has k-bounded
treewidth if the treewidth of its dependency graph G(G) is at most k. Recall that, givena graph G, computing a tree-decomposition of width at most k of G (if any) is feasible inpolynomial (actually, linear) time (Bodlaender, 1997).
We next prove an interesting graph-theoretic result to shed some light on the different
possible representations of game structures: every class of games having bounded treewidthhas bounded hypertree width, too. We remark that the previous results on the relationshipbetween treewidth and hypertree width described in the literature (e.g. Gottlob et al.,2000) cannot be used here. Indeed, they deal with the primal graph and the dual graphrepresentations, while we are now interested in the dependency graph, which is more effectivethan the primal graph, and somehow incomparable with the (optimal) dual graph.
A
detailed comparison of these two latter notions is reported by Greco and Scarcello (2003).
Theorem 5.7 For each game G, hypertreewidth (H(G)) ≤ treewidth(G(G)) + 1.
Proof.
Let TD be a tree decomposition of G(G) and let k − 1 be its width, that is,
the largest label of the vertices of TD contains k players. Then, we show that there is ahypertree decomposition of H(G) having width k. Recall that H(G) contains, for each player
5. Observe that the “−1” in the definition of treewidth has been introduced in order to get this correspon-
dence with acyclic graphs, as 2 is the minimum cardinality for the largest label in any tree decomposition.
394

 
Pure Nash Equilibria: Hard and Easy Games
p, the characteristic edge H(p) = p ∪ Neigh(p). Let HD = T, χ, λ be a hypertree suchthat:
• the tree T has the same form as the decomposition tree TD, i.e., there is a tree
isomorphism δ : vert(T ) −→ vert(T D) between T and TD;
• for each vertex v ∈ T , λ(v) = H(p) | p ∈ δ(v), i.e., λ(v) contains the characteristic
edge of each player occurring in the vertex of the tree decomposition correspondingto v;
• χ(v) is the set of all vertices occurring in the edges in λ(v), i.e., contains all players
in δ(v) and their neighbors.
Note that the width of HD is k, as it is determined by the largest λ label, which contains
the same number of elements as the largest label in TD.
We claim that HD is a hypertree decomposition of H(G). Consider the four conditions
in Definition 5.1: Conditions 3 and 4 are trivially satisfied because, for each vertex v,χ(v) = vert(λ(v)), by construction. Condition 1 is guaranteed by the fact that TD satisfiesits corresponding Conditions 1 and 2. We next show that Condition 2, i.e., the connectednesscondition, holds, too.
Let v1 and v2 be two vertices of T such that there exists p ∈ χ(v1)∩χ(v2). Let v = δ(v
1
1)
and v = δ(v
2
2) be the sets of vertices in the tree decomposition TD corresponding to v1 and
v2, respectively. Since p ∈ χ(v1) and p ∈ χ(v2), there are two players p1 and p2 such that (i)H(p1) ∈ λ(v1) and p ∈ H(p1), and (ii) H(p2) ∈ λ(v2) and p ∈ H(p2). Then, by construction,p1 ∈ v and p
(see Figure 16).
1
2 ∈ v2
We claim that, for each vertex v in the unique path connecting v1 and v2 in T (denoted
by v1
v2), λ(v) contains a player from the set p1, p2, p, which entails that p ∈ χ(v)
and hence that Condition 2 is satisfied by HD. This is equivalent to claim, on the treedecomposition TD, that each vertex v in the path v
v contains a player in p
1
2
1, p2, p.
If both v and v contain p, then the claim trivially holds because all the vertices in the
1
2
path v
v must contain p, from Condition 3 of tree decompositions (the connectedness
1
2
condition).
Hence, let us assume that v does not contain p. Since p ∈ H(p
1
1), this means that p is
a neighbor of p1 and thus there exists a vertex of TD, say v = v , whose labeling contains
3
1
both p and p1. Assume now that v contains p. Figure 16.1 shows the path comprising
2
vertices v , v , and v — notice that v cannot be in the path v
v , otherwise it should
1
3
2
1
3
2
contain p as well. The result follows by observing that, again from Condition 3 of treedecompositions, all vertices in the path v
v must contain p
1
3
1, and all vertices in the
path v
v must contain p. Similarly, assume that v does not contain p. In this case,
3
2
2
since p is a neighbor of p2 (recall the above discussion for p1), there is a vertex v in TD
4
whose labeling contains both p2 and p. Figure 16.2 shows how these vertices should looklike in the tree decomposition TD. Then, the result follows by observing that all vertices inthe path v
v contains p
v contains p, and all vertices
1
3
1, all vertices in the path v3
4
in the path v
v contains p
4
2
2.
2
We next show that the converse does not hold, that is, there are classes of games having
bounded hypertree width, but unbounded treewidth. That is, the technique based on the
395

 
Gottlob, Greco, and Scarcello
Figure 16: Schema of the reduction in the proof of Theorem 5.7.
hypertree width of the game hypergraph is more effective than the corresponding techniquebased on the treewidth of the dependency graph, because it allows us to identify strictlybroader classes of tractable games.
Theorem 5.8 There are classes C of games having hypertree width 1 but unboundedtreewidth, i.e., such that, for any finite k > 0, there is a game G ∈ C such that the treewidthof G is not bounded by k.
Proof. Take the class of all games where every player depends on all other players. Forevery such game G, H(G) is acyclic and thus its hypertree width is 1, while G(G) is a cliquecontaining all players and its treewidth is the number of players minus 1.
2
396

 
Pure Nash Equilibria: Hard and Easy Games
From Theorem 5.3, Corollary 5.4, and Theorem 5.7, we immediately get the following
tractability results for bounded treewidth games.
Corollary 5.9 Deciding the existence of pure (Pareto) Nash equilibria, as well as com-puting a pure (Pareto) Nash equilibrium is feasible in polynomial time for all classes C ofgames having bounded treewidth and such that every game G ∈ C has small neighborhood oris in graphical normal form. Moreover, all Nash equilibria of such games can be computedin time polynomial in the combined size of input and output.
6. Parallel Complexity of Easy Games
In this section, we show that dealing with Nash equilibria for games with good structuralproperties is not only tractable but also parallelizable. More precisely, we show that decidingthe existence of Nash equilibria for graphical games where the player interactions has a lowdegree of cyclicity is complete for the class LOGCFL. Also, we show that computing suchan equilibrium belongs to the functional version of LOGCFL.
The complexity class LOGCFL consists of all decision problems that are logspace re-
ducible to a context-free language. In order to prove the following theorem, we exploit acharacterization of LOGCFL in terms of circuits.
We recall that a Boolean circuit Gn with n inputs is a finite directed acyclic graph whose
nodes are called gates and are labeled as follows. Gates of fan-in (indegree) zero are calledcircuit input gates and are labeled from the set false, true, z1, z2, . . . , zn, ¬z1, ¬z2, . . . , ¬zn.All other gates are labeled either AND, OR, or NOT. The fan-in of gates labeled NOT mustbe one. The unique node with fan-out (outdegree) zero is called output gate. The evaluationof Gn on input string w of length n is defined in the standard way. In particular, any inputgate g labeled by zi (resp. ¬zi) gets value true (resp. false) if the ith bit of w is 1 (resp. 0);otherwise, g gets value false (resp. true).
A Boolean circuit is thus given as a triple (N, A, label), where N is the set of nodes
(gates), A is the set of arcs, and label is the labeling of the nodes as described.
The depth of a Boolean circuit G is the length of a longest path in G from a circuit
input gate to the output gate of G. The size S(G) of G is the number of gates (includinginput-gates) in G.
A family G of Boolean circuits is a sequence (G0, G1, G2, . . .), where the nth circuit Gn
has n inputs. Such a family is logspace-uniform if there exists a logspace Turing machinewhich, on the input string containing n bits 1, outputs the circuit Gn. Note that the sizeof the nth circuit Gn of a logspace-uniform family G is polynomial in n. Intuitively, thisuniformity condition is crucial in characterizations of low parallel complexity classes in termsof circuits, because hidden inherent sequentialities in the circuit construction process mustbe avoided. In fact, the cicuits which serve as parallel devices for evaluating input strings oflength n, and which must be constructed for each n separately, should be constructible inparallel themselves. This is assured by requiring logspace uniformity, because LOGSPACEis a highly parallelizable complexity class contained in LOGCFL.
The language L accepted by a family G of circuits is defined as follows: L =
L
n≥0
n,
where Ln is the set of input strings accepted by the nth member Gn of the family. An inputstring w of length n is accepted by the circuit Gn if Gn evaluates to true on input w.
397

 
Gottlob, Greco, and Scarcello
A family G of Boolean circuits has bounded fan-in if there exists a constant c such that
each gate of each member Gn of G has its fan-in bounded by c.
A family G of Boolean circuits is semi-unbounded if the following two conditions are met:
• All circuits of G involve as non-leaves only AND and OR gates, but no NOT gates
(negation may thus only occur at the circuit input gates); and
• there is a constant c such that each AND gate of any member Gn of G has its fan-in
bounded by c (the OR gates may have unbounded fan-in).
For i ≥ 1, ACi denotes the class of all languages recognized by logspace-uniform families
of Boolean circuits of depth O(logi n).
For i ≥ 1, NCi denotes the class of all languages recognized by logspace-uniform families
of Boolean circuits of depth O(logi n) having bounded fan-in.
For i ≥ 1, SACi denotes the class of all languages recognized by semi-unbounded
logspace-uniform families of Boolean circuits of depth O(logi n).
Venkateswaran (1991) proved the following important relationship between LOGCFL
and the semi-unbounded circuits:
LOGCFL = SAC1.
Since LOGCFL = SAC1 ⊆ AC1 ⊆ NC2, the problems in LOGCFL are all highly
parallelizable.
In fact, each problem in LOGCFL is solvable in logarithmic time by a
concurrent-read concurrent-write parallel random access machine (CRCW PRAM) witha polynomial number of processors, or in log2-time by an exclusive-read exclusive-writePRAM (EREW PRAM) with a polynomial number of processors (Johnson, 1990).
We next show that the evaluation problem of SAC1 circuits can be transformed in
logspace into the considered Nash equilibrium existence problems.
g19
AND g19
g
OR g
g
17
OR 18
16
g17
AND g
g
g
g
13
AND 14 AND 15 AND 16
g
g
13
16
OR g
g
g
g
g
8
OR 9 OR 10 OR 11 OR 12
g
g
8
g
g
9
11
12
g
x
x
x
2 g
x4
5
7
qx1
qx2
qx6
g
g
g
g
2
g
g
g
g
g
1
3
4
5
6
7
1
3
6
6
A)
B)
C)
Figure 17: (A) A normalized circuit, (B)its skeleton tree, (C) a labeling corresponding to a
proof tree.
Theorem 6.1 The existence problem for pure Nash equilibria is LOGCFL-complete for thefollowing classes of strategic games in graphical normal form: acyclic-graph games, acyclic-hypergraph games, games of bounded treewidth, and games of bounded hypertree-width.
398

 
Pure Nash Equilibria: Hard and Easy Games
Proof. It is sufficient to show membership for bounded hypertree width (the largest of the4 classes) and hardness for acyclic-graph games (the smallest one).
Membership. The Nash equilibrium existence problem for NF games of bounded hyper-
tree width is in LOGCFL because, as shown in Section 4, this problem can be transformedin logspace into a CSP of bounded hypertree width, and, as shown by Gottlob et al. (2001),checking satisfiability of the latter is in LOGCFL. (Recall that LOGCFL is closed underlogspace reductions.)
Hardness. We assume that a logspace-uniform family C = G1, G2, . . . of SAC1 circuits
is given, and we prove that the problem of checking whether a binary string w is acceptedby C can be translated in logspace to an acyclic Nash equilibrium problem in NF.
On input w, compute in logspace the appropriate circuit C = G|w|. As shown by Gottlob
et al. (2001), this circuit can be transformed in logspace into an equivalent normalized circuitC which is stratified and strictly alternating (see Figure 17 (A)), and a tree-shaped proofskeleton SKEL (see Figure 17 (B)) which encompasses the common structure of all possibleproof trees for (C , w). A proof tree is a subtree of C of gates having value 1 witnessingthat C accepts w. Each proof tree corresponds to an appropriate labeling of SKEL withgates from C (for example, the labeling shown in Figure 17 (C)). A labeling is correct ifthe root of SKEL is labeled with the output gate of C , each AND gate labeled g has twochildren that are labeled with the input gates to g, each OR node of SKEL labeled g hasone child labeled with some input gate to g, and each leaf of T is labeled with an input gateto C whose output to the next higher level is 1. C accepts w if and only if there exists aproof tree for (C , w), and thus if there exists a correct labeling of SKEL.
Build a strategic game G from (C , w) and SKEL as follows. The set of players consists
of all vertices V of SKEL plus two special players α and β. The possible actions for theplayers in V are pairs (g, t), where g is a gate and t is a truth value in true, false. Theutilities for players in V are given as follows.
1. The utility of each leaf u of SKEL only depends on its action and is 1 if it plays an
input gate g of C and if g is associated with the constant true, or g is a ¬ gate andcorresponds to an input bit 0 of the string w, or g is not a ¬ gate and corresponds toan input bit 1 of w. Otherwise, the utility of u is 0.
2. Each non leaf vertex p ∈ V gets payoff 1, if it plays an action (g, true), and if either
p is an OR vertex and the unique child of p in SKEL takes action (g , true), and gis a child of the gate g in C , or p is an AND vertex and the unique children of pin SKEL take actions (g , true), and (g , true), respectively, where g and g are thechildren of the gate g in C .
3. Each non leaf vertex p ∈ V gets payoff 1, if it plays an action an action (g, false), and
if either p is an OR vertex and the unique child of p in SKEL takes action (g , false),and g is a child of g in C , or p is an AND vertex and the unique children of p inSKEL take actions (g , t ), and (g , t ), respectively, where g and g are the childrenof g in C and t ∧ t = false.
4. In all other cases, all actions of a non leaf vertex p ∈ V have utility −1.
According to what we have defined so far, it is easy to see that every Nash equilibrium
of the game corresponds to a labeling of SKEL by assigning each player of V the gate g
399

 
Gottlob, Greco, and Scarcello
of its respective action (g, t). In particular, the root node r is forced to be labeled with theoutput gate g∗ of C , and the action played by r is (g∗, true) if and only if the particularlabeling is a proof tree and (g∗, false) otherwise.
It remains to define the actions and utilities for the special players α and β. Their
intuitive role is to “kill” all those equilibria which do not correspond to a proof three i.e.,those where the root vertex plays (g∗, false)). The possible actions are ok, head, tail forα, and head, tail for β. The strategies where α plays ok have utility 1 for α if the rootvertex r of SKEL plays (g∗, true)) and utility 0 otherwise. Strategies where α plays head(resp., tail) have utility 1 for α if r plays (g∗, false) and if β plays tail (resp., head), and0 otherwise. Thus, in case r plays (g∗, false), player α tries to play the opposite of playerβ. The strategies where β plays head (resp., tail) have utility 1 for player β if α plays thesame action, and 0 otherwise.
Therefore, in case C outputs 0 on input w, r plays (g∗, false), and thus α tries to play
opposite to β while β tries to mimic α. This is a classical non-equilibrium situation. Insummary, each Nash equilibrium of G corresponds to a proof tree for (C , w). Note alsothat G(G) is acyclic, and that the construction of G from (C , w) can be done in logspace. 2
Note that, by Definition 2.2, a Pareto Nash equilibrium exists if and only if a Nash
equilibrium exists.
Corollary 6.2 The existence problem for pure Pareto Nash equilibria is LOGCFL-completefor the following classes of strategic games in graphical normal form: acyclic-graph games,acyclic-hypergraph games, games of bounded treewidth, and games of bounded hypertree-width.
Finally, as far as computation of Nash equilibria is concerned, the following corollary
follows from the above result and from a result by Gottlob at al. (2002a), stating thatwitnesses (i.e., proof trees) of LOGCFL decision problems can be computed in functionalLOGCFL (i.e., in logspace with an oracle in LOGCFL, or, equivalently, by using SAC1circuits.
Corollary 6.3 For the classes of games mentioned in Theorem 6.1, the computation ofa single pure Nash equilibria can be done in functional LOGCFL, and is therefore in theparallel complexity class N C2.
7. Conclusion
In this paper we have determined the precise complexity of pure Nash equilibria in strategicgames. As depicted in Figure 2, our study proceeded along three directions: representa-tion issues, structural properties of player interactions, and different notions of equilibria.Indeed, besides “plain” Nash equilibria, we considered Pareto and Strong Nash equilibria,where we look for Nash equilibria that are not dominated by any other Nash equilibrium, orfor profiles where no possible coalition of players may improve the payoffs of all its members,respectively.
It turns out that, apart from the simple case of standard normal form, deciding the
existence of Nash equilibria is an intractable problem (unless PTIME = NP), if there is no
400

 
Pure Nash Equilibria: Hard and Easy Games
restriction on the relationships among players. Interestingly, for Strong Nash Equilibria,this problem is located at the second level of the polynomial hierarchy, and gives us a freshgame-theoretic view of the class ΣP , as the class of problems whose positive instances are
2
characterized by a coalition of players who cooperate to provide an equilibrium, and winagainst any other disjoint coalition, which fails in trying to improve the utility for all of itsplayers.
However, this paper is not just a collection of bad news. Rather, a central goal was
to single out large classes of strategic games where detecting Nash equilibria is a tractableproblem. In particular, while early studies in game theory mainly focused on games witha small number of players (e.g., the traditional two-player framework), we are interestedhere in large population games, too. In such cases, adopting the standard normal form isclearly impractical as, for each player, one should specify her payoffs for any combinationof choices of all players in the game. We thus considered a different representation for thesegames, known in literature as graphical games (Kearns et al., 2001b), where the payoffsof each player p are functions of p’s neighbors only, that is, p’s utility function dependsonly on those players p is directly interested in. These relationships among players maybe represented as a graph or, more faithfully, as a hypergraph. We showed that, if utilityfunctions are represented as tables (graphical normal form) and the game structure is acyclicor has a low degree of cyclicity (i.e., it has bounded hypertree width), then deciding theexistence of a Nash equilibrium and possibly computing it is feasible in polynomial time.These results complement those obtained for graphical games in the mixed Nash equilibriaframework (e.g. Kearns et al., 2001b; Kearns & Mansour, 2002). Moreover, in the case ofquasi-acyclic structures, we were also able to extend tractability to classes of games whereutility functions are given implicitly (as in the general form), provided that each player hasa small number of neighbors with not too many available actions.
This paper sheds light on the sources of complexity of finding pure Nash equilibria
in strategic games, and, in particular, on the roles played by game representations andgame structures. It is worthwhile noting that these aspects of game theory have receiveda renewed deal of attention recently. For instance, see Papadimitriou (2004) for a recentwork on the complexity of pure Nash equilibria in some particular classes of games, andthe various contributions on different kinds of concise game representations (e.g. Koller &Milch, 2001; Vickrey, 2002; Kearns et al., 2001b; Leyton-Brown & Tennenholtz, 2003; Gal& Pfeffer, 2004; Kearns & Mansour, 2002).
We recall that a preliminary version of the present work has been presented at the
9th ACM Conference on Theoretical Aspects of Rationality and Knowledge (TARK’03).Since then, our results have been extended along different directions. In particular, Alvarezet al. (2005) considered a further version of general form games, called games in implicitform, where also payoff values are given in a succinct way. They showed that, for suchgames, the complexity of deciding the existence of pure Nash equilibria increases from thefirst level to the second level of the polynomial hierarchy. We point out that our generalform is slightly different from the general form adopted in the above mentioned paper, andsome confusion may arise by reading their citation of the results presented in our TARK’03paper (whose full version is the present paper). In their terminology, our Turing-machineencoding of payoff functions in general form games should be classified as non-uniform,with a uniform time-bound. However, apart from such subtle technical issues, some of their
401

 
Gottlob, Greco, and Scarcello
results on general form games with non implicit actions are very similar to ours, but theircontributions focus on games with a large number of actions, while our hardness results holdeven for games with a fixed number of actions and payoff levels. Moreover, while we showthat hardness holds even for acyclic games, they did not consider any restriction on playerinteractions. Observe that their results may be immediately strengthened, given that fromour proofs about GNF games with arbitrary player interactions it follows that NP-hardnessholds even for constant-time utility functions (as discussed in Remark 3.9).
Another line of research studies games where the computation of any Nash equilibrium
is not satisfactory, and one is rather interested in equilibria that satisfy some additional re-quirements (e.g., the best social welfare). Greco and Scarcello (2004) proved that decidingthe existence of such pure Nash equilibria, called constrained Nash equilibria, is intractableeven for very simple requirements. However, they were also able to identify some restrictions(for player interactions and requirements) making both the existence and the computationproblems easy. Recent contributions on this subject (on both pure and mixed Nash equi-libria) have been done by Schoenebeck at al. (2005) and Greco and Scarcello (2005).
Finally, we observe that there is an interesting connection among strong Nash equilibria
and some equilibria studied in cooperative/coalitional game theory (e.g. Mas-Colell, Whin-ston, & Green, 1995). In this framework, for each subset K of the players, we are giventhe utility that players in K may get, if they cooperate together. The core of a game isthe set of profiles x such that there is no subset of players that may improve their util-ities by forming their own coalition, deviating from x (Gillies, 1953). Recently, Conitzerand Sandholm (2003a) proposed a concise representation for coalition utilities, and showedthat determining whether the core of such a game is nonempty is NP-hard. An interestingfuture work may concern a detailed study of the complexity of these coalitional games, pos-sibly exploiting suitable notions of quasi-acyclic structures for identifying relevant tractableclasses.
Acknowledgments
Part of this work has been published in preliminary form in the Proceedings of the 9thACM Conference on Theoretical Aspects of Rationality and Knowledge (TARK’03).
Georg Gottlob’s work was supported by the Austrian Science Fund (FWF) under
project Nr. P17222-N04 Complementary Approaches to Constraint Satisfaction, and bythe GAMES Network of Excellence of the EU.
We thank the anonymous referees and Tuomas Sandholm for their very useful comments.
References
Alvarez, C., Gabarro, J., & Serna, M. (2005).
Pure Nash equilibria in games with a
large number of actions. Electronic Colloquium on Computational Complexity, Re-port TR05-031.
Aumann, R. (1959). Accetable points in general cooperative n-person games. Contribution
to the Theory of Games, IV.
402

 
Pure Nash Equilibria: Hard and Easy Games
Aumann, R. (1985). What is game theory trying to accomplish?. Frontiers of Economics,
28–76.
Beeri, C., Fagin, R., Maier, D., & Yannakakis, M. (1983). On the desirability of acyclic
database schemes. Journal of the ACM, 30(3), 479–513.
Bodlaender, H. (1997). Treewidth: Algorithmic techniques and results. In Proc. of the
22nd International Symposium on Mathematical Foundations of Computer Science(MFCS’97), pp. 19–36, Bratislava, Slovakia.
Chandra, A., Kozen, D., & Stockmeyer, L. (1981). Alternation. Journal of the ACM, 28(1),
114–133.
Conitzer, V., & Sandholm, T. (2003a). Complexity of determining nonemptiness of the
core. In Proc. of the 18th International Joint Conference on Artificial Intelligence(IJCAI’03), pp. 613–618, Acapulco, Mexico.
Conitzer, V., & Sandholm, T. (2003b). Complexity results about nash equilibria. In Proc.
of the 18th International Joint Conference on Artificial Intelligence (IJCAI’03), pp.765–771, Acapulco, Mexico.
Deng, X., Papadimitriou, C., & Safra, S. (2002). On the complexity of equilibria. In Proc.
of the 34th Annual ACM Symposium on Theory of Computing (STOC’02), pp. 67–71,Montreal, Canada.
Downey, R., & Fellows, M. (1995). Fixed-parameter tractability and completeness i: Basic
results. SIAM Journal on Computing, 24(4), 873–921.
Fabrikant, A., Papadimitriou, C., & Talwar, K. (2004).
The complexity of pure nash
equilibria. In Proc. of the 36th Annual ACM Symposium on Theory of Computing(STOC’04), pp. 604–612, Chicago, IL, USA.
Fagin, R. (1983). Degrees of acyclicity for hypergraphs and relational database schemes.
Journal of the ACM, 30(3), 514–550.
Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., & Spirakis, P. (2002).
The structure and complexity of nash equilibria for a selfish routing game. In Proc.of the 29th International Colloquium on Automata, Languages and Programming(ICALP’02), pp. 123–134, Malaga, Spain.
Gal, Y., & Pfeffer, A. (2004). Reasoning about rationality and beliefs. In Proc. of the
3rd International Joint Conference on Autonomous Agents and Multiagent Systems(AAMAS’04), pp. 774–781, New York, NY, USA.
Garey, M., & Johnson, D. (1979). Computers and Intractability. A Guide to the Theory of
NP-completeness. Freeman and Comp., NY, USA.
Gilboa, I., & Zemel, E. (1989). Nash and correlated equilibria: Some complexity consider-
ations. Games and Economic Behaviour, 1, 80–93.
403

 
Gottlob, Greco, and Scarcello
Gillies, D. (1953). Some theorems on n-person games. PhD thesis, Princeton, Dept. of
Mathematics.
Gottlob, G., Leone, N., & Scarcello, S. (2000). A comparison of structural csp decomposition
methods. Artificial Intelligence, 124(2), 243–282.
Gottlob, G., Leone, N., & Scarcello, S. (2001). The complexity of acyclic conjunctive queries.
Journal of the ACM, 48(3), 431–498.
Gottlob, G., Leone, N., & Scarcello, S. (2002a). Computing logcfl certificates. Theoretical
Computer Science, 270(1-2), 761–777.
Gottlob, G., Leone, N., & Scarcello, S. (2002b). Hypertree decompositions and tractable
queries. Journal of Computer and System Sciences, 63(3), 579–627.
Greco, G., & Scarcello, S. (2003). Non-binary constraints and optimal dual-graph represen-
tations. In Proc. of the 18th International Joint Conference on Artificial Intelligence(IJCAI’03), pp. 227–232, Acapulco, Mexico.
Greco, G., & Scarcello, S. (2004). Constrained Pure Nash Equilibria in Graphical Games.
In Proc. of the 16th Eureopean Conference on Artificial Intelligence (ECAI’04), pp.181–185, Valencia, Spain.
Greco, G., & Scarcello, S. (2005). Bounding the Uncertainty of Graphical Games: The
Complexity of Simple Requirements, Pareto and Strong Nash Equilibria. to appearIn Proc. of the 21st Conference in Uncertainty in Artificial Intelligence (UAI’05),Edinburgh, Scotland.
Johnson, D. (1990). A catalog of complexity classes. Handbook of Theoretical Computer
Science, Volume A: Algorithms and Complexity, 67–161.
Johnson, D., Papadimitriou, C., & Yannakakis, M. (1998).
How easy is local search?.
Journal of Computer and System Sciences, 37, 79–100.
Kearns, M., Littman, M., & Singh, S. (2001a). An efficient exact algorithm for singly con-
nected graphical games. In Proc. of the 14th International Conference on Neural In-formation Processing Systems (NIPS’01), pp. 817–823, Vancouver, British Columbia,Canada.
Kearns, M., Littman, M., & Singh, S. (2001b). Graphical models for game theory. In Proc.
of the 17th International Conference on Uncertainty in AI (UAI’01), pp. 253–260,Seattle, Washington, USA.
Kearns, M., & Mansour, Y. (2002). Efficient nash computation in large population games
with bounded influence. In Proc. of the 18th International Conference on Uncertaintyin AI (UAI’02), pp. 259–266, Edmonton, Alberta, Canada.
Koller, D., & Megiddo, N. (1992). The complexity of two-person zero-sum games in extensive
form. Games and Economic Behavior, 2, 528–552.
404

 
Pure Nash Equilibria: Hard and Easy Games
Koller, D., & Megiddo, N. (1996). Finding mixed strategies with small supports in extensive
form games. International Journal of Game Theory, 14, 73–92.
Koller, D., Megiddo, N., & von Stengel, B. (1996). Efficient computation of equilibria for
extensive two-person games. Games and Economic Behavior, 14, 220–246.
Koller, D., & Milch, B. (2001). Multi-agent influence diagrams for representing and solving
games. In Proc. of the 7th International Joint Conference on Artificial Intelligence(IJCAI’01), pp. 1027–1034, Seattle, Washington, USA.
Leyton-Brown, K., & Tennenholtz, M. (2003). Local-effect games. In Proc. of the 18th
International Joint Conference on Artificial Intelligence (IJCAI’03), pp. 772–780,Acapulco, Mexico.
Maier, D. (1986). The Theory of Relational Databases, Rochville, Md, Computer Science
Press.
Mas-Colell, A., Whinston, M., & Green, J. (1995). Microeconomic Theor. Oxford University
Press.
Maskin, E. (1985). The theory of implementation in nash equilibrium. Social Goals and
Organization: Essays in memory of Elisha Pazner, 173–204.
McKelvey, R., & McLennan, A. (1996). Computation of equilibria in finite games. Handbook
of Computational Economics, 87–142.
Megiddo, N., & Papadimitriou, C. (1991). On total functions, existence theorems, and
computational complexity. Theoretical Computer Science, 81(2), 317–324.
Monderer, D., & Shapley, L. (1993). Potential games. Games and Economic Behavior.
Nash, J. (1951). Non-cooperative games. Annals of Mathematics, 54(2), 286–295.
Osborne, M., & Rubinstein, A. (1994). A Course in Game Theory. MIT Press.
Owen, G. (1982). Game Theory. Academic Press, New York.
Papadimitriou, C. (1994a). Computational Complexity. AAddison-Wesley, Reading, Mass.
Papadimitriou, C. (1994b). On the complexity of the parity argument and other inefficient
proofs of existence. Journal of Computer and System Sciences, 48(3), 498–532.
Papadimitriou, C. (2001).
Algorithms, games, and the internet.
In Proc. of the 28th
International Colloqium on Automata, Languages and Programming (ICALP’01), pp.1–3, Crete, Greece.
Robertson, N., & Seymour, P. (1986). Graph minors ii. algorithmic aspects of tree width.
Journal of Algorithms, 7, 309–322.
Rosenthal, R. (1973). A class of games possessing pure-strategy nash equilibria. Interna-
tional Journal of Game Theory, 2, 65–67.
405

 
Gottlob, Greco, and Scarcello
Schoenebeck, G.R., & Vadhan, S.P. (2005). The Computational Complexity of Nash Equilib-
ria in Concisely Represented Games. Electronic Colloquium on Computational Com-plexity, Report TR05-052.
Stockmeyer, L., & Meyer, A. (1973). Word problems requiring exponential time: Prelim-
inary report. In Proc. of the 5th Annual ACM Symposium on Theory of Computing(STOC’73), pp. 1–9.
Vardi, M. (2000). Constraint satisfaction and database theory: a tutorial. In Proc. of
the 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of DatabaseSystems, pp. 76–85, Dallas, Texas, USA.
Venkateswaran, H. (1991). Properties that characterize logcfl. Journal of Computer and
System Sciences, 43(2), 380–404.
Vickrey, D. amd Koller, D. (2002). Multi-agent algortihms for solving graphical games. In
Proc. of the 18th National Conference on Artificial Intelligence (AAAI’02), p. 345251Edmonton, Alberta, Canada.
Yannakakis, M. (1981). Algorithms for acyclic database schemes. In Proc. of the 7th Inter-
national Conference on Very Large Data Bases (VLDB81), p. 8294 Cannes, France.
406