%%% Versione del 23/05/05
%%% Con correzioni %francescoPost: correzioni per la versione degli spagnoli
%%%                %gianluigi: il numero 1. 2. o 3. indica il testo del revisore corrispondente
%%%                            il commento aggiuntivo spiega come abbiamo reagito
%%%                            (nessun commento nessuna reazione)
%%%                %francescofinal: correzioni francesco
%%%                %ggc  Parti che Giorgio dovrebbe controllare.
%%%                %gggg  revisioni di Giorgio
%%%                %gianluigiFinal ultime modifiche dopo Giorgio

\documentstyle[jair,twoside,11pt,theapa,graphicx,amsfonts,amssymb]{article}
\input epsf %% at top of file

%\usepackage{theapa}
%\usepackage{jair}
%\usepackage{amsfonts}
%\usepackage[english]{babel}
%\selectlanguage{english}
%\usepackage{amssymb}
%\usepackage{graphicx}

\jairheading{24}{2005}{357-406}{12/04}{09/05}

\ShortHeadings{Pure Nash Equilibria: Hard and Easy Games} {Gottlob, Greco, and Scarcello}

\firstpageno{357}

% THEOREMS -------------------------------------------------------

\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{exmp}[thm]{Example}
\newtheorem{rem}[thm]{Remark}

\newcommand{\qed}{\hfill $\Box$\\ }

%%%%%%%% Kaz %%%%%%%%%%%%%%%

\newcommand{\proof}{\noindent {\bf Proof}.\ }

% complexity -----------------------------------------------------------

\newcommand{\pn}[1]{{\small#1}} % problem name
\newcommand{\Pol}{\mbox{\rm PTIME}}
\newcommand{\NP}{\mbox{\rm NP}}
\newcommand{\WP}{\downarrow^W}
\newcommand{\IP}{\downarrow^I}
\newcommand{\logspace}{{\rm LOGSPACE}}
\newcommand{\LOGSPACE}{{\rm LOGSPACE}}
\newcommand{\DL}{{\rm LOGSPACE}}
\newcommand{\LLOG}{{{\rm L}^{\rm LOGCFL}}}
\newcommand{\LLOGLOG}{{\rm L}^{\rm LOGCFL}(\rm LOGCFL)}
\newcommand{\AC}[1]{{\rm AC}_{#1}}
\newcommand{\NC}[1]{{\rm NC}_{#1}}
\newcommand{\SAC}{{\rm SAC}^1}
\newcommand{\logcfl}{{\rm LOGCFL}}
\newcommand{\LOGCFL}{{\rm LOGCFL}}
\newcommand{\LCFL}{\mbox{\rm LOGCFL}}
\newcommand{\coLCFL}{\mbox{\rm co-LOGCFL}}
\newcommand{\FCFL}{\rm L^{LOGCFL}}
\newcommand{\np}{\mbox{\rm NP}}
%\newcommand{\sl}{\mbox{\rm SL}}
\newcommand{\SL}{\mbox{\rm SL}}
\newcommand{\NL}{\mbox{\rm NL}}
\newcommand{\CONP}{\mbox{\rm co-}\NP }
\newcommand{\coNP}{\mbox{\rm co-}\NP }
\newcommand{\CONL}{\mbox{\rm co-}\NL }
\newcommand{\SigmaP}[1]{{\Sigma}_{#1}^{P}}
\newcommand{\PiP}[1]{{\Pi}_{#1}^{P}}
\newcommand{\B}[1]{{\rm B}_{#1}}
\newcommand{\Bc}[1]{{\rm B}^c_{#1}}
\newcommand{\DeltaP}[1]{{\Delta}_{#1}^{P} }
\newcommand{\DeltalogP}[1]{{\Delta}_{#1}^{P [O(\log n)]} }
% ----------------------------------------------------------------

\newcommand{\nop}[1]{}
\newcommand{\shortv}[1]{#1}
\newcommand{\longv}[1]{#1}


\def\x{{\bf x}}
\def\y{{\bf y}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\St}{\mathit{St}}
\newcommand{\Act}{\mathit{Act}}
\newcommand{\maxAct}{\mathit{maxAct}}
\newcommand{\SRP}{\mathit{SRP}}
\newcommand{\N}{\mathit{Neigh}}
\newcommand{\maxN}{\mathit{maxNeigh}}
\newcommand{\G}{{\mathcal{G}}}
\newcommand{\C}{{\mathcal{C}}}
\newcommand{\GX}{\G_{\Xi}}
\newcommand{\GXr}{\G_{\Xi_r}}

\newcommand{\DG}{{\rm G}}
%\renewcommand{\H}{\mathcal{H}}
\renewcommand{\H}{{\rm H}}
\newcommand{\JT}{J\!T}
\newcommand{\HG}{{\rm H}}
\newcommand{\component}[1]{\mbox{\rm[$#1$]-}component}
\newcommand{\connected}[1]{\mbox{\rm[$#1$]-}connected}
\newcommand{\HD}{H\!D}
\newcommand{\TD}{T\!D}
\newcommand{\CSP}{\mathit{CSP}}
\newcommand{\nc}{\mathit{NC}}
\newcommand{\true}{\mathit{true}}
\newcommand{\false}{\mathit{false}}
\newcommand{\intr}{\mathit{i}}

\newcommand{\NE}{\mbox{${\mathcal N\!E}$}}
\newcommand{\LNE}{\mbox{${\mathcal L\!N\!E}$}}
\newcommand{\SNE}{\mbox{${\mathcal S\!N\!E}$}}
\newcommand{\PNE}{\mbox{${\mathcal P\!N\!E}$}}

\newcommand{\tuple}[1]{\langle#1\rangle}

\newcommand{\semijoin}{\ltimes}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
% ----------------------------------------------------------------
\vfuzz2pt % Don't report over-full v-boxes if over-edge is small
\hfuzz2pt % Don't report over-full h-boxes if over-edge is small

\sloppy

\def\bvs{\vspace{-0mm}}



\begin{document}

\title{Pure Nash Equilibria: Hard and Easy Games}


\author{\name Georg Gottlob \email gottlob@dbai.tuwien.ac.at\\
        \addr Information Systems Department,\\
              Technische Universit\"{a}t Wien,\\
              A-1040 Wien, Austria
        \AND
        \name Gianluigi Greco \email ggreco@mat.unical.it \\
        \addr Dipartimento di Matematica,\\
              Universit\`a della Calabria,\\
              I-87030 Rende, Italy
        \AND
        \name Francesco Scarcello \email scarcello@deis.unical.it \\
        \addr DEIS, \\
              Universit\`a della Calabria, \\
              I-87030 Rende, Italy}


\maketitle

\begin{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
$\SigmaP{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 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 $\mathcal
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
$\NC{2}$ of highly parallelizable problems.
\end{abstract}

%\begin{keyword}
%Game Theory, Graphical Games, Pure Nash Equilibria, Computational Complexity,
%Treewidth, Hypertree Width,
%Constraint Satisfaction.
%\end{keyword}


\section{Introduction and Overview of Results}\label{sec:intro}

The theory of strategic games and Nash equilibria has important applications in economics and decision making
\cite{N51,A85}. Determining whether Nash equilibria exist, and effectively computing them, are relevant problems
that have attracted much research in computer science \cite<e.g.>{DPS02,MM96,KMS96}. Most work has been
dedicated to complexity issues related to {\em mixed equilibria} of games with {\em mixed strategies}, where the
player's choices are not deterministic and are regulated by probability distributions. In that context, the
existence of a Nash equilibrium is guaranteed by Nash's famous theorem \cite{N51}, but it is currently open
whether such an equilibrium can be computed in polynomial time \cite<cf.,>{P01}. First results on the
computational complexity for a two-person game have been presented by Gilboa and Zemel \citeyear{GZ89}, while
extensions to more general types of games have been provided by Megiddo and Papadimitriou \citeyear{MP91}, and
by Papadimitriou~ \citeyear{P94}. A recent paper of Conitzer and Sandholm \citeyear{conitzer} also proved the
\NP-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 {\em pure strategies}, where each player chooses
to play an action in a deterministic, non-aleatory manner. Nash equilibria for pure strategies are briefly
referred to as {\em pure Nash equilibria}. Note that in the setting of pure strategies, a pure Nash equilibrium
is not guaranteed to exist \cite<see, for instance,>{OR94}. Particular classes of games having pure Nash
equilibria have been studied by Rosenthal \citeyear{R73}, Monderer and Shapley \citeyear{MS93}, and by Fotakis
et al. \citeyear{FKKMS02}.  Recently, Fabrikant at el. \citeyear{P04} renewed the interest in the class of games
defined Rosenthal \citeyear{R73}, called \emph{congestion games}, by showing that a pure Nash equilibrium can be
computed in polynomial time in the symmetric network case, while the problem is PLS-complete \cite{JP88} in
general.

Our goal is to study fundamental questions such as the {\em existence} of pure Nash, Pareto, and strong Nash
equilibria, the {\em computation} of such equilibria, and to find arguably realistic restrictions under which
these problems become tractable. Throughout the paper, Pareto and 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 restrictions are imposed on the set of allowed
strategies, determining whether a game has a pure Nash or Pareto Equilibrium is NP-complete, while deciding
whether a game has a strong Nash equilibrium is even $\SigmaP{2}$-complete. However, by jointly applying
suitable pairs of more  realistic restrictions, we obtain settings of practical interest in which the complexity
of the above problems is drastically reduced. In particular, determining the existence of a pure Nash
equilibrium and computing such an equilibrium will be feasible in polynomial time and we will show that, in
certain cases, these problems are even complete for the very low complexity class LOGCFL, which means that these
problems are essentially as easy as the membership problem for context-free languages, and are thus highly
parallelizable (in NC$_2$).

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 possible actions, from which she chooses an
action once and for all, independently of the actual choices of the other players. The choices of all players
can thus be thought to be made simultaneously. The choice of an action by a player is referred to as the
player's {\em strategy}. It is assumed that each player has perfect knowledge over all possible actions and over
the possible strategies of all players. A {\em global strategy}, also called {\em profile} in the literature,
consists of a tuple containing a strategy for each player. Each player has a polynomial-time computable real
valued {\em utility function}, which allows her to assess her subjective utility of each possible global
strategy (global strategies with higher utility are better). A pure {\em Nash equilibrium} \cite{N51} is a
global strategy in which no player can improve her utility by changing her action (while the actions of all
other players remain unchanged). A {\em strong Nash equilibrium} \cite{A59} is a pure Nash equilibrium where no
change of strategies of whatever coalition (i.e., group of players) can simultaneously increase the utility for
all players in the coalition. A pure Nash equilibrium is {\em Pareto optimal} \cite<e.g.>{M85} if the game
admits no other pure Nash equilibrium for which each player has a strictly higher utility.
%\footnote{A Nash
%equilibrium is said to be {\em strongly Pareto optimal} if the
%game admits  no other Nash equilibrium for which no player has a
%lower utility but at least one player has a higher utility. In
%this paper, we will not deal with strongly Pareto optimal
%equilibria.
% It is easy to see that, complexity-wise,
% Pareto optimality and strong Pareto optimality are equivalent;
% we will therefore disregard strong Pareto optimality in the sequel.
%}
A Pareto-optimal Nash equilibrium is also called a Pareto Nash Equilibrium.


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
strategic games which impose quantitative and/or qualitative limitations on how the payoffs
of an agent (and hence her decisions) may be influenced by the other agents.
%francescofinal: Seguendo le indicazioni di Giorgio, evitiamo di complicarci la vita. Ho commentato
%   la frase incriminata e le osservazioni di Gianluigi (da recuperare eventualmente altrove).
%%This is one way of capturing the
%%idea of bounded rationality in strategic games. For a different
%%view of bounded rationality, see also Papadimitriou and Yannakakis
%%\cite{PY94}.
%%gianluigi: ho tolto il discorso su bounded rationality ed aggiunto una frase
%%1. claim is made that restricting ways in which
%%agents decisions may influence other agents is a way of capturing bounded
%%rationality. This is certainly a possible interpretation, but not at all
%%convincing one, especially in the light of results of this paper that state
%%that such restrictions don't necessarily make the problem easier. I think
%%the real and perfectly valid reason for considering such representations is
%%that they allow one to capture independence properties inherent in many
%%interactions, and thus allow for a much more compact way to represent
%%things - a trend common in a lot of AI. I would probably drop the mention of
%%bounded rationality, as it might just spark unnecessary reaction, and is not
%%at all related to the rest of the paper.
%%2. The bounded rationality connection is completely unclear.
%These restrictions will generally allow for a succinct representation of games, and are therefore particulary
%suited for modeling large networks where games are being played by a large number of players.
%%gianluigi: citati vari lavori su giochi succinti
%%francescofinal(commentati qui e ripresi nelle conclusioni)
%%2. Moreover, graphical games/the assumption of few players affecting others' utilities is by no means the only way
%%of coming up with a concise representation for games. For example, the authors briefly mention congestion games.
%%(Kevin Leyton-Brown has some variants of these as well, called local effect games/action graph games.) Many
%%games that cannot be concisely modeled as graphical games can nevertheless be modeled concisely by these game
%%representations. For example, if I drive a sports utility vehicle, that affects everybody else through global
%%warming, but it can still be concisely modeled. It really needs to be made clear that this paper is about one
%%particular concise representation rather than games in general.
%And, in fact, several examples of games with succinct representation have been recently proposed in the
%literature \cite<e.g.>{KM01,koller,KLS01b,LT03,GP04,KM02}. Among these approaches, throughout the paper we shall
%focus on restrictions on the interactions among players, whose study was firstly proposed by \cite{KM01} and
%\cite{KLS01b}.

The {\em set of neighbors $\N(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\neq p$ is not in $\N(p)$ then $p$'s
utility function does not directly depend on the actions of $q$. We assume that each game is
equipped with a polynomial-time computable function $\N$ with the above property.\footnote{Note
that each game can be trivially represented in this setting, possibly setting $\N(p)$ to be the set
of all players, for each player $p$. In most cases, however, one will be able to provide a much
better neighborhood function.}
 The player neighborhood relationship, typically represented as a graph (or a hypergraph),
 is the central notion in {\em graphical games} \cite{KM01,KLS01b}, 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 $\N(p)$ for all players $p$. For instance, consider a set of companies in a market.
Each company has usually a limited number of other market players on which it bases its strategic
decisions. These relevant players are usually known and constitute the neighbors of the company in
our setting. However, note that even in this case the game outcome 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, a number of real-world cases can be modeled in a very natural way.
%francescofinal: ho inserito il riferimento ai graphical games nel precedente paragrafo.
%%1. where the neighbor relations are introduced, a much better job could be done for introducing GNF. I
%%think it's much more natural to introduce this relation in terms of graphs, rather than the other way around, in
%%particular because after parsing this it looks very similar to graphical games. Also, this is the place where
%%the relationship to graphical games should be discussed. (You do it much later, in section 2). I suspect that
%%most of the audience for this paper will be pretty familiar with them - that representation and name is becoming
%%well-known and standard. It was extremely confusing to read this description without any reference to graphical
%%games. In fact, although I like the term GNF quite a bit, the term "graphical game" is so standard by now, that
%%it might be worthwhile to just use it throughout, or really stress that they're the same.
%Notice that, this more general setting is well suited for modeling in a natural way a number of real-world
%cases, and in fact it has been already exploited by \cite{KM01,KLS01b} to define the class of \emph{graphical
%games}, where the utility function for each player may depend (directly) only on strategies of a small number of
%other players.
%
We can thus define the following notion of limited neighborhood:

%gianluigi: direi di non tenerne conto. non ci dice come...
%2. The definitions of bounded/small neighborhood should be reorganized.

\paragraph*{\bf Bounded Neighborhood:}
Let $k>0$ be a fixed constant. A strategic game with associated neighborhood function $\N$ has {\em $k$-bounded
neighborhood} if, for each player $p$, $|\N(p)|\leq k$.

While in some setting the bounded neighborhood assumption is realistic, in other settings the constant bound
appears to be too harsh an imposition. It is much more realistic and appealing to relax this constraint and
consider a {\em logarithmic} bound rather than a constant bound on the number of neighbors.

\paragraph*{\bf 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 a game $\G$ (i.e., the input size $n$). Furthermore,
let $\maxN(\G)=max_{p\in P(\G)}|\N(p)|$ and $\maxAct(\G)=max_{p\in P(\G)}|\Act(p)|$.

%ggc:  Qui non abbiamo modificato, anche se molte cose dovrebbero essere più chiare dopo la versione pro-spagnoli.
%gianluigi
%1. The problem I have here is with the
%introduction of "classes of games". I believe this to be a non-trivial question. For it to make sense, first a
%definition needs to be made of what is a game. This is tricky, since there are many different possible syntactic
%representations, and no universally accepted semantics. Thus, even if definition is connected explicitly to some
%representation, a notion of equivalence between games needs to be made. Although all of this often is
%intuitively clear, game theorists have been arguing about these issues for many years. So a more explicit
%definition, that is sufficient for this paper, is in order. Probably just syntactic equivalence is all you need.
%
%As an aside: I wonder if it's possible to somehow phrase the definition of small neighborhood for a single game,
%without reference to a class (i.e. get rid of big-O, somehow)?
A class of strategic games has {\em small neighborhood} if, for each game $\G$ in this class,
$$\maxN(\G) = O(\frac{\log||\G||}{ \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.
%ggc
%francescofinal: Ho cercato di chiarire meglio il concetto.
%3. p.3. When justifying the denominator log maxAct(G), the sentence
%beginning "Roughly speaking", could you provide more explanation? Perhaps an example?
Indeed, roughly speaking, player interactions may be reduced significantly
 by adding an exponential amount of additional actions. For any
player, these fresh actions may encode all possible action configurations of some of her
neighbors, yielding an equivalent game with
%gggg  VEDI http://andromeda.rutgers.edu/~jlynch/Writing/l.html per la
%  prossima riga
less interaction, and possibly with fewer
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, $|\N(p)| < c\times(\frac{\log||\G||}{ \log |\Act(p)|}).$

The related notion $\intr(\G)$ of {\em intricacy} of a game is defined by:
$$\intr(\G) = \frac{\maxN(\G)\times \log \maxAct(\G)}{\log ||\G||}.$$
%$$\intr(\G) = \max_{p\in P(\G)} \frac{|\N(p)|\times \log |Act(p)|}{\log ||\G||}.$$
It is clear that a class of games has small neighborhood if and only if the intricacy of all games in it is
bounded by some constant.

\nop{Clearly, every game having a bounded neighborhood function also has a bounded action-neighborhood function,
but not vice-versa. Intuitively, this may be illustrated by the following example. Players: a large number of
people in various cities, some of which are friends. Actions: holiday travels to some other city, or staying at
home. Utility: 2 if I travel to city A and at least two friends (not coming from my own city) will be there; 1
if I travel to a city A and only one such friend will be there; 1 if I stay at home and at least one friend from
another city visits here; 0 otherwise. (The same utility function applies to all players). If we assume that
many people have friends in many cities, but everybody has only a limited number of friends in every foreign
city, say at most $k$, then the action-neighborhood is significantly smaller than the general neighborhood, in
fact, the action-neighborhood is bounded by $k$. }
%
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 the small neighborhood property.

%francescofinal: Ho aggiunto una citazione per far capire che nel contesto di graphical games
%                viene usato il grafo non diretto.
In addition to the quantitative aspect of the size of the neighborhood (and of the neighborhood actions), we are
also interested in qualitative aspects of mutual strategic influence. Following Kearns et al.~\citeyear{KLS01b},
for a game $\G$ with a set $P$ of players, we define the {\em strategic dependency graph} as the undirected
graph $\DG(\G)$ having $P$ as its set of vertices and $\{\{p,q\} \mid q\in P\wedge p\in \N(q)\}$ as its set of
edges. Moreover, we define the {\em strategic dependency hypergraph} $\H(\G)$, whose vertices are the players
$P$ and whose set of hyperedges is $\{\{p\}\cup\N(p) \mid p\in P\}$.
%gianluigi: ho aggiunto un esempietto giocattolo
%1. This really begs for an illustration, and going
%forward to the full-blown example 2.1 is very inconvenient. A nice picture here would help. Also, as I mentioned
%before, it might be easier for many people to actually start with Neigh(p) being represented by a digraph, and
%take definitions from there.
For instance, consider a game $\overline{\G}$ over players $A,B,C$, and $D$ such that $\N(A)=\{B,C\}$,
$\N(B)=\{A,C\}$, $\N(C)=\{A,B\}$, and $\N(D)=\{C\}$. Figure~\ref{fig:esempioGrafo} shows the dependency
graph and the dependency hypergraph associated with $\overline{\G}$.
% (these notions are further illustrated in Example \ref{esempio} below).

\begin{figure}[t]
\centering
    \includegraphics[width=0.4\textwidth]{EsempioGrafo.eps}
\caption{Dependency hypergraph and dependency graph for the game $\overline{\G}$.}\label{fig:esempioGrafo}
\end{figure}

We consider the following classes of structurally restricted games:

\paragraph*{Acyclic-Graph Games:} Games $\G$ for which $\DG(\G)$ is acyclic.

\paragraph*{Acyclic-Hypergraph Games:} Games $\G$ for which $\H(\G)$
is acyclic. Note that there are several definitions of hypergraph acyclicity \cite{fagi-83}. Here we refer to
the broadest (i.e., the most general) one, also known as $\alpha$-acyclicity \cite{fagi-83,beer-etal-83} (see
Section~\ref{sec:prelim}).

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 for each player depends on all other players.
Then $\DG(\G)$ is a clique of size $|P|$ while $\H(\G)$ is the 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, there are important generalizations that
appear to be much more realistic for practical applications. These concepts are bounded treewidth
\cite{robe-seym-86} and bounded hypertree width \cite{gott-etal-02} (see also Section~\ref{sec:hypertree}),
which are 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)  $\leq 1$. It was argued that an
impressive number of ``real-life'' graphs have a very low treewidth \cite{downey}. Hypertree width in turn was
fruitfully applied  in the context of database queries \cite{gott-etal-02} and constraint satisfaction problems
\cite{GLS99b}. Formal definitions are given in Section~\ref{sec:hypertree}.
%gianluigi: ho cercato di chiarigli
%3. Is it really true that it can be checked in polynomial time whether a graph has treewidth k. I thought that
%problem was NP-complete. Is there a subtle distinction being made here or am I completely wrong?
Note that both computing the 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 a graph has treewidth $k$~\cite{bodl-97} and whether a hypergraph has hypertree width
$k$~\cite{gott-etal-02}.
%
We have, for each constant $k$, the following restricted classes of games:

\paragraph*{Games of treewidth  bounded by $k$:} The games $\G$ such that the
treewidth of $\DG(\G)$ is~$\leq k$.

\paragraph*{Games of hypertree width bounded by $k$:} The games $\G$ such that
the hypertree width of $\H(\G)$ is $\leq 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 is in {\em general form} if the sets of players and
actions are given in extensional form and if the neighborhood and utility functions are polynomially computable
functions. Unless otherwise stated, we always assume that games are given in general form. For classes of games
having particular properties, some alternative representations have been used by various authors. For instance,
in game theory literature, the set of utility functions is often represented through a single table (or matrix)
having an entry for {\em each} combination of players' actions containing, for each player $p$, the evaluation
of her utility function for that particular combination. This representation is said to be in \emph{standard
normal form (SNF)} \cite<see, for instance,>{OR94,O82}. Note that, if there are many players, this
representation may be very space consuming, particularly if some players are not 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 \cite{KM01}. In fact, in the context of games with
restricted players interactions, the most used representation is the {\em graphical normal form (GNF)}. In GNF
games, also known as {\em graphical games}~\cite{KLS01,KLS01b,KM02,koller}, the utility function for each player
$p$ is given by a table that displays $p$'s utility as a function of all possible combined strategies of $p$ and
$p$'s neighbors, but not of other players irrelevant to $p$. Therefore, for large population games (modeling for
instance agent interactions over the internet), the SNF is practically unfeasible, while the more succinct
graphical normal form works very well, and is actually a more natural representation.

\paragraph*{Main results.}

The main results of this paper are summarized as follows:

\begin{itemize}
\item Determining whether a strategic game has a pure Nash equilibrium is NP-complete and remains NP-complete
even for following two restricted cases:
\begin{itemize}
\item Games in graphical normal form (GNF) having bounded neighborhood (Theorem~\ref{thmNP}).

\item Acyclic-graph  games, and acyclic-hypergraph games (Theorem~\ref{theo:acyc-hard}).
\end{itemize}
The same results hold for Pareto Nash equilibria for pure strategies. \item Determining whether a strategic game
has a strong Nash equilibrium is $\Sigma^p_2$-complete and thus at the second level of the Polynomial Hierarchy
(Theorem~\ref{theo:sigmaP2} and Theorem~\ref{theo:acyc-sigmap2-hard}). The proof of this theorem gives us a
fresh  game-theoretic view of the class $\SigmaP{2}$ as the class of  problems whose positive instances are
characterized by a coalition of players who cooperate to provide an equilibrium, and win against any other
disjoint coalition, which fails in trying to improve the utility for all of its players. E.g., in the case of
$\Sigma_2$ quantified Boolean formulas, the former coalition consists of the existentially quantified variables,
and the latter of the universally quantified ones.

\item The pure Nash, Pareto and strong equilibrium existence and computations problems are feasible in
logarithmic space for games in standard normal form
%gianluigi: lasciamo com'è.
%1. These results seem pretty obvious even
%without reading the proof. They should definitely be included for
%completeness, but maybe that should be mentioned.
(Theorem~\ref{thm:easySNF}).

\item The pure Nash equilibrium existence and computation problems are tractable for games (in whatever
representation) that simultaneously have small neighborhood and bounded hypertree width
(Theorem~\ref{theo:small-neighbors}). Observe that each of the two joint restrictions, small neighborhood and
bounded hypertree width, is weaker than the restrictions of bounded neighborhood and acyclicity, respectively,
of which each by itself does not guarantee tractability. Thus, in order to obtain tractability, instead of
strengthening a single restriction, we combined two weaker restrictions. While we think that each of the two
strong restrictions is unrealistic, we believe that for many natural games the combined weaker restrictions do
apply. In order to prove the tractability  result, we establish a relationship between strategic games and the
well-known finite domain constraint satisfaction problem (CSP), much studied in the AI and OR literature
\cite<e.g.>{vardi,GLS99b}. Let us  point out that also Vickrey and Koller \citeyear{koller} recently exploited a
mapping to CSP for the different problem of finding approximate mixed equilibria in graphical games. We show
that each (general, not necessarily GNF) strategic game $\G$ can be translated into a CSP instance having the
same hypertree width as $\G$, and whose feasible solutions exactly correspond to the Nash equilibria of the
game. Then, we are able to prove that $\G$ is equivalent to an \textit{acyclic} constraint satisfaction problem
of size $||{\G}||^{O(i({\G})\times hw({\G}))}$, where $i({\G})$ is the intricacy 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.

\item Exploiting the same relationship with CSPs, we prove that the Nash-equilibrium existence and computation
problems are tractable for games in graphical normal form (GNF) having bounded hypertree width
(Theorem~\ref{theo:small-neighbors}), regardless of the game intricacy, i.e., even for unbounded neighborhood.

\item We show that if a strategic game has bounded treewidth, then it also has bounded hypertree width
(Theorem~\ref{theo:twVShw}). Note that this is a novel result on the relationship between these two measures of
the degree of cyclicity, since earlier works on similar subjects dealt with either the primal or the dual graph
of a given hypergraph, rather than with a dependency graph, as we do in the present paper, focused on games.
Combined with the two previous points, this entails that the Nash-equilibrium existence and computation problems
are tractable for games that simultaneously have small neighborhood  and bounded treewidth, and for GNF games
having bounded treewidth (Corollary~\ref{cor:treewidth}).

\nop{ \vspace{-.3cm} \item The Nash equilibrium existence and computation problems are tractable for games that
are given in graphical normal form (GNF) and at the same time  have bounded hypertree width
(Theorem~\ref{theo:pareto}). Again our proof uses a relationship between strategic games and CSPs, but this time
we may exploit known results on the ``classical'' CSPs rather than resorting to a new generalization of CSP.
Again, since bounded treewidth implies bounded hypertree width, we get analogous results for strategic games
with bounded treewidth (Corollary~\ref{cor:treewidth}). }

\item 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~\ref{theo:pareto-acyclic} and
Corollary~\ref{cor:pareto}).

\item These tractability results partially extend to strong Nash equilibria. Indeed, the checking problem
becomes feasible in polynomial time for acyclic-hypergraph games in GNF. However, even in such simple cases,
deciding whether a game has strong Nash equilibria is $\NP$-complete, and thus still untractable
(Theorem~\ref{thmStrongNP}).

\item 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 in GNF, the problem of determining a pure Nash equilibrium
of a game of bounded hypertree-width (or bounded treewidth) is LOGCFL-complete and thus in the parallel
complexity class NC$_2$ (Theorem~\ref{theo:logcfl}). Membership in LOGCFL follows from the membership of bounded
hypertree-width CSPs in LOGCFL \cite{gott-etal-01}. Hardness for LOGCFL is shown by transforming (logspace
uniform families of) semi-unbounded circuits of logarithmic depth together with their inputs into strategic
games, such that the game admits a Nash equilibrium if and only if the circuit outputs one on the given input.
\end{itemize}

Figure \ref{fig:results} summarizes our results on the existence of pure Nash equilibria.

\begin{figure}[t]
\centering
    \includegraphics[width=0.95\textwidth]{summary-jair.eps}
\vspace{-3mm}\caption{Complexity of deciding existence of pure Nash equilibria for games in GNF --- numbers
indicate theorems where the corresponding results are proved.}\label{fig:results}\vspace{-3mm}
\end{figure}

%\vspace{-4mm}\begin{small}
%\begin{center}
%\begin{figure}[t]
%\centering \scriptsize
%\begin{tabular}{|l||c|c|c|}\hline
%
%  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%                                  & \begin{tabular}{c} \scriptsize
%                        General \\ \scriptsize Players Interaction
%                        \end{tabular}
%                        & \begin{tabular}{c}\scriptsize
%                                           Bounded \\ \scriptsize Tree width
%                                        \end{tabular}
%                        & \begin{tabular}{c}
%                        \scriptsize Bounded \\ \scriptsize Hypertree Width
%                        \end{tabular}\\ \hline \hline
% \vspace{-2mm}\scriptsize General Form         & \scriptsize $\NP$-complete & \scriptsize $\NP$-complete &  \scriptsize $\NP$-complete \\
% \vspace{-2mm}\scriptsize Bounded Neighborhood & \scriptsize $\NP$-complete & {\rm \scriptsize PTIME} & {\rm \scriptsize PTIME} \\
% \vspace{-2mm} \scriptsize Small Neighborhood   & \scriptsize $\NP$-complete & {\rm \scriptsize PTIME} & {\rm \scriptsize PTIME} \\
% %\vspace{-2mm}
% \scriptsize Graphical Normal Form& \scriptsize $\NP$-complete & \scriptsize $\LCFL$-complete & \scriptsize $\LCFL$-complete \\
% \hline
%\end{tabular}
%\caption{Complexity of deciding existence of pure Nash equilibria
%for games in GNF}\label{fig:results}
%\end{figure}
%\end{center}
%\end{small}

\noindent While various authors have dealt with the complexity of Nash equilibria
\cite<e.g.>{GZ89,P94,KM92,KM96,conitzer}, most investigations were dedicated to mixed equilibria and
--- to the best of our knowledge --- all complexity results in the
present paper are novel. We are not aware of any other work considering the quantitative and structural
restrictions on pure games studied here. Note that tree-structured games were first considered by Kearns et
al.~\citeyear{KLS01b} in the context of mixed equilibria. It turned out that, for such games, suitable
approximation of (mixed) Nash equilibria can be computed in polynomial time. In our future work, we would like
to extend our tractability results even to this setting. We are not aware of any work by others on the parallel
complexity of equilibria problems. We believe that our present work contributes to the understanding of pure
Nash equilibria and proposes appealing and realistic restrictions under which the main computation problems
associated with such equilibria are tractable.

The rest of the paper is organized as follows. In Section~\ref{sec:prelim} we introduce the basic
notions of games and Nash equilibria that are studied in the paper, and we describe how games may
be represented. In Section~\ref{sec:hard} we thoroughly study the computational complexity of
deciding the existence of pure Nash, Pareto and strong equilibria. In Section~\ref{sec:easy} we
identify tractable classes of games, and in Section~\ref{sec:hypertree} we extend our tractability
results to larger class of games, where the interaction among players has a bounded degree of
cyclicity. In Section~\ref{sec:parallel} we improve the results on the polynomial tractability of
easy games, providing the precise computational complexity for games with acyclic (or bounded
width) interactions among players. Finally, in Section~\ref{sec:conclusion}, we draw our
conclusions, and we discuss possible further research and related works.

\section{Games and Nash Equilibria}\label{sec:prelim}

A {\em game} $\G$ is a tuple $\tuple{P,\N,\Act,U}$, where $P$ is a non-empty set of distinct players and $\N:
P\longrightarrow 2^P$ is a function such that for each $p\in P$, $\N(p)\subseteq P-\{p\}$ contains all neighbors
of $p$, $\Act:P\longrightarrow A$ is a function returning for each player $p$ a set of possible actions
$\Act(p)$, and $U$ associates a utility function $u_p : \Act(p)\times_{j\in \N(p)} \Act(j)\rightarrow \Re$ to
each player $p$.

Note that, in general, the players interests are not symmetric. Thus, it may happen that, for a pair of players
$p_1,p_2\in P$, $p_1\in \N(p_2)$ but $p_2\not\in \N(p_1)$.

For a player $p$, $p_a$ denotes her  choice to play the action $a\in\Act(p)$. Each possible $p_a$ is called a
{\em strategy} for $p$, and the set of all strategies for $p$ is denoted by $\St(p)$.\footnote{Note the
technical distinction between actions and strategies: an action is an element of the form \textit{a}, while a
strategy is an element of the form $\mathit{p_a}$, i.e., it is an action chosen by a player. This helps in
technical proofs, since a strategy singles out both a player and her choice.}

For a non-empty set of players $P'\subseteq P$, a {\em combined strategy} for $P'$ is a set containing exactly
one strategy for each player in $P'$. $\St(P')$ denotes the set of all combined strategies for the players in
$P'$.

A combined strategy (also, {\em profile}) $\x$ is called {\em 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\subseteq P$ is often called a {\em 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 strategy where, for each player $p\in K$, her individual strategy $p_a\in \x$ is
replaced by her individual strategy $p_b \in \y$. If $K$ is a singleton $\{p\}$, we will simply write
$\x_{-p}[\y]$.

Let $\x$ be a global strategy, $p$ a player, and $u_p$ the utility function of $p$. Then, with a small abuse of
notation, $u_p(\x)$ will denote the output of $u_p$ on the projection of $\x$ to the domain of $u_p$, i.e., the
output of the function $u_p$ applied to the actions played by $p$ and her neighbors 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.

%ggc
%gianluigi: secondo noi la versione corrente (post-spagnoli) va già bene.
%1. definition of general form. This should be made crisper, and more explicit, especially since this is
%not meant for theory community. I think "extensional form" is too obscure - it should be defined, or even
%rephrased as something like "listed explicitly". (There is another place earlier in the introduction where
%extensional form gets used as well). When you mention that Neigh and U are polynomially computable functions, it
%is best to be explicit that they're poly (|P|, |A|). The biggest confusion with this definition is its input
%size. Again, you should state precisely what that is. It is not immediately clear just how neighborhood and
%utility functions are given. You could assume that those are oracles that don't contribute to input size.
%However, as stated in your footnote, those could be descriptions of Turing machines, in which case their
%encoding size might matter.
%2. I believe the "general" form of games assumes some oracle giving the utilities, this should be discussed more
%thoroughly rather than just in a footnote.
%3. Your use of the terminology "general form" is surprising. Standard normal form is the most general form
%possible for games. Not all games can be represented in general form, with a polynomially computable utility
%function.
%francescoPost: nuova definizione
\paragraph*{General Form:} A game is in {\em 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 in classes of games such that the computation time of the neighborhood and utility
functions is globally bounded by some polynomial. Let us denote by $\C_{k}$ the class of all games
$\G$ in general form whose neighborhood and utility functions are computable in time $O(n^k)$,
where $n = |\G|$.

For the sake of presentation, we assume hereafter $\bar k\geq 1$ to be any such a fixed global bound. Moreover,
unless otherwise stated, when we speak of a ``general game $\G$'' (or we omit any specification at all) we mean
a game $\G\in \C_{\bar k}$.

The following more restrictive classes of (representations of) games have been used by many authors.

\paragraph*{Standard Normal Form (SNF):} A game with set $P$ of players is in
{\em standard normal form (SNF)} if its utility functions are explicitly represented by a single table or matrix
having an entry (or cell) for {\em each} global strategy $\bf x$, displaying a list containing for each player
$p$, $p$'s payoff $u_p({\bf x})$ w.r.t. $\bf 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 utility
functions often assumed in the literature \cite<see, for instance,>{OR94,O82}. Observe that, in the general
case, even if an utility function is polynomially computable, writing it down in form of a table may require
exponential space.

\paragraph*{Graphical Normal Form (GNF):}
A game with a set $P$ of players is in {\em graphical  normal form (GNF)}  if the utility function for each
player $p$ is represented by a separate table containing a cell for each combined strategy ${\bf x}\in
St(\N(p)\cup \{p\})$ of the $p$'s set of neighbors $\N(p)\cup\{p\}$, displaying $p$'s payoff $u_p({\bf x})$
w.r.t. {\bf x}.
 A game in GNF is illustrated in Example~\ref{esempio}.
The GNF representation has been adopted in several recent papers that study games with a
large number of players, where the utility function of each player depends directly only on
the strategies of those (possibly few) players she is interested
in~\cite<e.g.>{KLS01,KLS01b,KM02,koller}. Note that GNF may lead to an exponentially more
succinct game representation than SNF. Notwithstanding, the SNF is often used in the
literature, mostly because, historically, the first investigations focused on two-player
games. Moreover, games in GNF are often referred to as {\em graphical games}. We prefer to
use the phrasing {\em games in graphical normal form}, because this makes clear that 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 of sexes".

\begin{exmp}{\bf (FRIENDS) }\label{esempio}\em
Let us consider the game FRIENDS, that is played by a group of persons that have to plan their
evening happenings. The players are \emph{George} (short: $G$), \emph{Pauline} ($P$), \emph{Frank}
($F$), \emph{Robert} ($R$), and \emph{Mary} ($M$). Each of them have to decide to go either to see
a \emph{movie} ($m$) or to see an \emph{opera} ($o$). However, preferences concern not only the
particular 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 Frank is
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 possible to go out all
together, he prefers to go to the cinema with Pauline and to the opera with Robert. Pauline would
like to stay with Frank, and she prefers the movies. Robert does not 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 the matchmaker of the group: He has no personal preferences
but would like that Frank and Pauline stay together for the evening, best if they go to the cinema.
All the utility functions associated with this game are shown in Figure \ref{fig:util-friends},
where we denote the fact that a player $X$ chooses an action $a$ by $X_a$, e.g., $F_m$ denotes the
strategy where Frank chooses to play the action $m$. \qed

%gianluigi: ho modficato la figura introducendo un grafo diretto. Il revisore 1. e' stato molto insistente su questo
%punto (ha fatto altri commenti in merito).
%francescofinal: Per non confondere le idee, abbiamo poi deciso di evitare di introdurre il grafo diretto.
%                Più avanti chiariamo con un commento come mai si preferisce l'indiretto.
%1. It would be extremely helpful in Figure 2,
%besides showing utility functions also to show the directed influence graph
%(i.e. visualize Neigh(p)).
%The interactions in the FRIENDS game are summarized by means of an intuitive graphical notation on the right of
%the same figure: Each player is in one-to-one correspondence with a node of the graph, and a directed edge from
%a player $p$ to a player $q$ means that the choice of $q$ is directly affected by the strategy played by $p$.
%Notice that $F$ and $P$ are directly interacting since their strategies are mutually dependent. Moreover, while
%even though $O$ is directly interested only in $F$, her strategy is transitively affected by $R$ as well. \qed

\begin{figure}\centering \small
\begin{tabular}{c||cccc}
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  $F$ & $P_mR_m$ & $P_mR_o$ & $P_oR_m$ & $P_oR_o$\\ \hline \hline
  $m$ &  2 &  2&  1 &  0  \\ \hline
  $o$ &  0 &  2&  1 &  2 \\ \hline
\end{tabular}
\ \ \ \ \begin{tabular}{c||cccc}
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  $G$ & $P_mF_m$ & $P_mF_o$ & $P_oF_m$ & $P_oF_o$\\ \hline \hline
  $m$ &  2 &  0 &  0 &  1 \\ \hline
  $o$ &  2 &  0 &  0 &  1 \\ \hline
\end{tabular} \\ \ \\
\vspace{0.5cm}
\begin{tabular}{c||cc}
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  $R$ & $F_m$ & $F_o$\\ \hline \hline
  $m$ &  0 &  1  \\ \hline
  $o$ &  2 &  0 \\ \hline
\end{tabular}
\ \ \ \ \begin{tabular}{c||cc}
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  $P$ & $F_m$ & $F_o$\\ \hline \hline
  $m$ &  2 &  0  \\ \hline
  $o$ &  0 &  1 \\ \hline
\end{tabular}
\ \ \ \ \begin{tabular}{c||cc}
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  $M$ & $R_m$ & $R_o$\\ \hline \hline
  $m$ &  1 &  0  \\ \hline
  $o$ &  0 &  2 \\ \hline
\end{tabular}\\
\caption{Utility functions for FRIENDS in GNF}\label{fig:util-friends}
\end{figure}
\end{exmp}

%\begin{figure}\centering \small
%\begin{tabular}{cc}
%\begin{tabular}{c}
%\begin{tabular}{c||cccc}
%  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%  $F$ & $P_mR_m$ & $P_mR_o$ & $P_oR_m$ & $P_oR_o$\\ \hline \hline
%  $m$ &  2 &  2&  1 &  0  \\ \hline
%  $o$ &  0 &  2&  1 &  2 \\ \hline
%\end{tabular}\\ \ \\
%\begin{tabular}{c||cccc}
%  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%  $G$ & $P_mF_m$ & $P_mF_o$ & $P_oF_m$ & $P_oF_o$\\ \hline \hline
%  $m$ &  2 &  0 &  0 &  1 \\ \hline
%  $o$ &  2 &  0 &  0 &  1 \\ \hline
%\end{tabular}\\ \ \\
%\begin{tabular}{c||cc}
%  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%  $R$ & $F_m$ & $F_o$\\ \hline \hline
%  $m$ &  0 &  1  \\ \hline
%  $o$ &  2 &  0 \\ \hline
%\end{tabular}\ \ \ \ \
%\begin{tabular}{c||cc}
%  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%  $P$ & $F_m$ & $F_o$\\ \hline \hline
%  $m$ &  2 &  0  \\ \hline
%  $o$ &  0 &  1 \\ \hline
%\end{tabular}\ \ \ \ \
%\begin{tabular}{c||cc}
%  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%  $M$ & $R_m$ & $R_o$\\ \hline \hline
%  $m$ &  1 &  0  \\ \hline
%  $o$ &  0 &  2 \\ \hline
%\end{tabular}
%\end{tabular} &
%\begin{tabular}{c}
%\includegraphics[width=0.21\textwidth]{FriendsHGPdiretto.eps}\\
%\end{tabular}
%\end{tabular}
%\caption{Utility functions for FRIENDS in GNF. On the right, a graphical representation of the friends'
%interactions.}\label{fig:util-friends}
%\end{figure}
%\end{exmp}

Let us now formally define the main concepts of equilibria to be further studied in this paper.

%gianluigi: aggiunto footnote
%2. In the definitions of Pareto and strong Nash, emphasize that this is
%*pure* Pareto and *pure* Nash equilibrium as well. Also emphasize that in this definition of Pareto optimal
%Nash, there is no requirement with regard to how the (pure) equilibrium compares to mixed equilibria.
\begin{defn}\label{defn:NE}\em
Let $\G=\tuple{P,\N,A,U}$ be a game. Then,
\vspace{-4mm}\begin{itemize}
\item a global strategy $\x$ is a pure Nash Equilibrium for $\G$ if,
 for every player $p\in P$, $\not\exists p_a \in \St(p)$ such that
$u_p(\x)<u_p(\x_{-p}[p_a])$;

\item a global strategy $\x$ is a pure strong Nash Equilibrium for $\G$ if, $ \forall K\subseteq P, \ \forall y \in \St(K), \
\exists p \in K \mbox{ such that } u_p(\x)\geq u_p(\x_{-K}[y]) $ or, equivalently, if
 $\forall K\subseteq P$, $\not\exists y \in \St(K)$ such that, $\forall p \in K$,
$u_p(\x)< u_p(\x_{-K}[y])$;

\item 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, $ \forall p \in P, \ u_p(\x)< u_p(\y).$\footnote{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.}
\end{itemize}
\end{defn}

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 the following relationships hold among these
notions of Nash equilibria: $ \SNE(\G) \subseteq \PNE(\G) \subseteq \NE(\G).$
%
Moreover, the existence of a Nash equilibrium does not imply the existence of a strong Nash equilibrium.
However, if there exists a Nash equilibrium, then there exists also a Pareto Nash equilibrium.

\begin{exmp}\label{ex:prelim} \em
The strategies $\{F_m,P_m,R_o,G_m,M_o\}$, $\{F_m,P_m,R_o,G_o,M_o\}$, $\{F_o,P_o,R_m,G_m,M_m\}$ and
$\{F_o,P_o,R_m,G_o,M_m\}$ are the Nash equilibria of the FRIENDS game. For instance, consider the latter
strategy, where all players get payoff 1. In this case, since $P$ plays opera and $R$ plays movie, $F$ cannot
improve his payoff by changing from opera to movie. The same holds for $G$, while $R$, $P$, and $M$ would get
the lower payoff 0, if they change their choices.

Moreover, note that the first two strategies above, namely $\{F_m,P_m,R_o,G_m,M_o\}$ and
$\{F_m,P_m,R_o,G_o,M_o\}$, are the only Pareto Nash equilibria, as well as the strong Nash equilibria. Indeed,
for these global strategies all players get their maximum payoff 2, and thus there is no way to improve their
utilities. \qed
\end{exmp}


%\nop{ !!! ATTENZIONE, AGGIORNARE LE NOTAZIONI !!! Observe that, in many games, a player may be interested in
%different groups of neighbors, possibly overlapping, depending on her strategy.
%
%For instance, referring to our running example, a person may consider a group of friends, if her choice is the
%movie, and another group if her choice is the opera. Therefore, an interesting issue is to study if the problem
%of computing  Nash equilibria becomes easier if, for each player, the maximum number of relevant players with
%respect to any of her strategies is small, e.g., bounded by some fixed constant.
%
%
%Formally, let $p$ be a player, $P'=\N(p)$  the set of her neighbors, and $p_a\in\St(p)$ a strategy. We say that
%a set of players $K$ is {\em relevant} for $p$ with respect to $p_a$ if there is a pair of combined strategies
%$y_1,y_2\in \St(K)$, and a combined strategy $y_o\in \St(P'-K)$ for the other neighbors, such that
%$u_p(\{p_a\}\cup y_o\cup y_1) \neq u_p(\{p_a\}\cup y_o\cup y_2)$. That is, when $p$ plays $a$, her utility
%function does actually depend on the choices of players in $K$.
%
%\begin{defn}\label{sec:defn-ARP}\em
%Let $t>0$ be a fixed constant. We say that $\G$ has the {\it $t$-bounded strategy-relevant players (SRP)
%property} if
%\begin{myitemize}
%\item[$\bullet$] we are additionally given a function $\SRP$ that, given any strategy $p_a$, returns a set
%$X\subseteq \N(p)$ of relevant players for $p$ with respect to strategy $p_a$; and
%
%\tnbls
%
%\item[$\bullet$] for each player $p$ and each strategy $p_a\in\St(p)$,
%       $|\SRP(p_a)|\leq t$.
%\end{myitemize}
%Moreover, $\G$ has the {\it total $t$-bounded SRP property} if, additionally, for each player $p$ and each
%strategy $p_a\in \St(p)$, $\SRP(p_a)=\N(p)$, i.e., if each player has at most $t$ neighbors.
%\end{defn}
%}

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  contains for each
player $p$ a (hyper)edge $\H(p)= \{p\}\cup \N(p)$, referred-to as the {\em characteristic edge of
$p$}. Intuitively, characteristic edges correspond to utility functions.

A fundamental structural property of hypergraphs is \emph{acyclicity}. Acyclic hypergraphs have
been deeply investigated and have many equivalent characterizations \cite<e.g.>{beer-etal-83}. We
recall here that a hypergraph $\H$ is acyclic if and only if there is a \emph{join tree} for $\H$,
that is, there is a tree $\JT$ whose vertices are the edges of $\H$ and, whenever the same player
$p$ occurs in two vertices $v_1$ and $v_2$, then $v_1$ and $v_2$ are connected in $\JT$, and $p$
occurs in each vertex on the unique path linking $v_1$ and $v_2$ (see
Figure~\ref{fig:friends-hyper} for a join tree of $\H(\makebox{\rm FRIENDS})$). In other words, the
set of vertices in which $p$ occurs induces a (connected) subtree of $\JT$.
%gianluigi: lo inserisco come aggiunta.
%1. I believe in AI "running intersection
%property" is a more common term for this. It's good to at least mention it
%in this definition.
We will refer to this condition as the {\em Connectedness Condition} of join trees (also known as
{\em running intersection property}).

Another representation of the interaction among players is through the (undirected) dependency
graph
 $\DG(\G)=(P,E)$, whose vertices coincide with the players of $\G$, and $\{p,q\}\in E$
if $p$ is a neighbor of $q$ (or vice versa).
%ggc
%francescofinal: chiacchiere sulla questione directed
%1. GNF vs. graphical games. One thing that might be worth mentioning,
%is that most (though not all) of the literature on GNF assumes directed
%graphs, whereas in this paper that is not assumed. The difference is
%probably minor, though.
%1. It is
%mentioned that a natural representation of Neigh() is the undirected
%dependency graph. It seems that a directed one would be even more natural
%(though probably not more useful), since symmetry is not assumed. All other
%graphs/hypergraphs can be constructed from the directed version. It might
%help to include it in Figure 3 alongside the other graphs.
%3. Why is the strategic dependency graph undirected? A directed graph would seem more natural. I understand
%that this fits your acyclic-graph and bounded-treewidth definitions, but a comment would be useful when the
%graph is defined.
For completeness we observe that, even if most works on graphical games use this dependency graph,
another natural choice is representing the game structure by a directed graph (also called
influence graph), which takes into account the fact that payoffs of a player $p$ may depend on
payoffs of a player $q$ and not vice versa, in general.
   Following Kearns et al.~\citeyear{KLS01b}, in the present paper we use the undirected version
 because we are interested in identifying game structures that possibly allow us to compute efficiently
 Nash equilibria, and directed graphs do not help very much for this purpose.
Let us give a hint of why this is the case, by thinking of a group of players $\bar X=
\{X_1,\ldots,X_n\}$,
    each one having only one neighbor $C$, whose payoffs do not depend on any player in $\bar X$.
    Player $C$ has one neighbor $D$, who has $C$ has its only neighbor.
    Figure~\ref{fig:esempioSpiegazioneDiretto} shows a directed graph representing these player
    interactions.
\begin{figure}[ht]
\centering
    \includegraphics[width=0.3\textwidth]{esempioSpiegazioneDiretto.eps}
\caption{A directed graph representation of player
interactions.}\label{fig:esempioSpiegazioneDiretto}
\end{figure}
 It is easy to design a game with these players such that,
 for some combined strategy $\x$ of the $\bar X$ players, there is no Nash equilibrium, while for some
 other combined strategy $\x'$ of these players, there is a combined strategy $\y$ of $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 players in $\bar 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., through their
   direct connections, such a mutual relationship among players.
   However, the direct graph does not model this kind of influence, as looking at this
   graph it seems that players in $\bar 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 whose directed influence graphs are quasi-acyclic (i.e., they are acyclic, but
  for some trivial cycles like the one shown in Figure~\ref{fig:esempioSpiegazioneDiretto}),
   are hard to deal with.
  Thus, apart from the well known easy acyclic cases, any reasonable generalization of
  the notion of direct acyclicity
does not appear to be useful for identifying further tractable classes of
  games.


%gggg IO TOGLIEREI IL HINT E SCRIVEREI
% In fact, the structural restrictions on the player interaction we
% study in this paper, tree-width and hypertree-width are defined for
%    undirected graphs. The notion of treewidth can be generalized to
%    directed graphs, but it is not clear whether bounded directed
%    treewidth  can be checked
%    in polynomial time. The notion of hypertree width has no
%    directed counterpart at all. Note that all our hardness results
%    for undirected interaction graphs trivially carry over to the
%    directed case (by simulating an undirected edge through two
%    directed edges).


Observe that the dependency graph $\DG(\G)$ is different from  the so called {\em primal graph}
{\it PG} of $\H(\G)$, which contains an edge for all pairs of vertices that jointly occur in some
hyperedge of $\H(G)$. In general, $\DG(\G)$ is much simpler than {\it PG}. For instance, consider a
game $\G$ with a player $p$ that depends on all other players $q_1,\ldots,q_n$, while these players
are independent of each other (but possibly depend on $p$). Then, $\DG(\G)$ is a tree. However, the
primal graph of $\H(\G)$ is a clique with $n+1$ vertices.

\begin{figure}[t]
    \centering
    \begin{tabular}{ccc}
        \includegraphics[width=0.6\textwidth]{FriendsHGP.eps} & \hspace{0.5cm} & \includegraphics[width=0.3\textwidth]{JTH.eps} \\
    \end{tabular}
    \caption{Hypergraph, dependency graph, and primal graph of the FRIENDS game. On the right, a join tree for $\H(\mbox{\rm FRIENDS})$.}\label{fig:friends-hyper}
\end{figure}

\begin{exmp}\em
The hypergraph $\H(\makebox{\rm FRIENDS})$, the graph $\DG(\makebox{\rm FRIENDS})$ and the primal
graph of $\H(\makebox{\rm FRIENDS})$ are shown in Figure \ref{fig:friends-hyper}.
 Note that the
dependency graph associated with the FRIENDS game is not acyclic, even though the associated
hypergraph is acyclic (on the right, we also report a join tree for it). Moreover, note that the
dependency graph differs from the primal graph, as player $P$ is not a neighbor of $R$ and
viceversa. \qed
\end{exmp}
%gianluigi
%One thing that is a little confusing throughout the paper is the example of a hypergraph with a single edge when
%all players influence each other. Surely this is not a very useful thing for tractability (unless tractability
%is measured in terms of the input size, maybe). In any case some explanation would be helpful.

\section{Hard Games}\label{sec:hard}

In this section, we precisely characterize the complexity of deciding the existence of the different kinds of
pure Nash equilibria (regular, Pareto, and strong). This way, we are able to identify the sources of complexity
of such problems, in order to single out, in the following sections, 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~\ref{sec:easy}, for games in standard normal form, computing pure Nash
equilibria is a tractable problem, since one can easily explore the (big) table representing the utility
functions of all players, in order to detect the strategy of interest. Since this table is given in input, such
a computation is trivially feasible 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.

\begin{thm}\label{thmNP} 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 of
actions is fixed.
% and where, moreover, each player is allowed to
%play at most three actions.
% for any fixed
%constant $k\geq 3$, that is, if each player depends on $k$ players
%at most.
\end{thm}

\proof \emph{Membership.} We can decide that $\NE(\G)\neq\emptyset$ by guessing a global strategy $\x$ and
verifying that $\x$ is a Nash equilibrium for $\G$. The latter task can be done in polynomial time. Indeed, for
each player $p$ and for each action $a\in\Act(p)$, we only have to check that choosing the strategy $p_a$ does
not lead to an increment of $u_p$, and each of these tests is feasible in polynomial time.

%gianluigi: ho inserito i nomi
%1. This is non-essential, of course, but SAT
%and 3SAT are both standard names for this problem. It would help to use
%them, for clarity.
\noindent\emph{Hardness.} Recall that deciding whether a Boolean formula in conjunctive normal form
$\Phi=c_1\wedge \ldots \wedge c_m$ over the variables $X_1,\ldots,X_n$ is satisfiable, i.e., deciding
whether there exists truth assignments to the variables making each clause $c_j$ true, is the well known
$\NP$-complete problem (CNF) SAT. Hardness holds even for its 3SAT restriction where each clause
contains at most three distinct (possibly negated) variables, and each variable occurs in at most three
clauses \cite{gare-john-90}. W.l.o.g, assume $\Phi$ contains at least one clause and one variable.

We define a GNF game $\G$ such that: The players are partitioned into two sets $P_v$ and $P_c$, corresponding to
the variables and to the clauses of $\Phi$, respectively; for each player $c \in P_c$, $\N(c)$ is the set of the
players corresponding to the variables in the clause $c$, and for each player $v \in P_v$, $\N(v)$ is the set of
the players corresponding to the clauses in which $v$ occurs; $\{t,f,u\}$ is the set of possible actions for all
the players, in which $t$ and $f$ can be interpreted as the truth values {\em true} and {\em false} for
variables and clauses. Figure \ref{fig:RiduzioneNP} shows the graph $\DG(\G)$ for the game $\G$ associated with
the formula $(X_1\vee X_3 \vee X_4)\wedge (\neg X_2 \vee X_4)\wedge (X_4 \vee X_5 \vee X_6)$.

%gianluigi: un revisore non ved gli indici nella figura: ho rigenerato la figura e la ho ingrandita
\begin{figure}[t]
    \centering
    \includegraphics[width=0.6\textwidth]{NPRid.eps}
    \caption{Schema of the reduction in the proof of Theorem \ref{thmNP}.}\label{fig:RiduzioneNP}
\end{figure}


Let $\x$ be a global strategy, then the utility functions are defined as follows. For each player $c\in P_c$,
her utility function $u_c$ is such that
\begin{description}
%gianluigi: riscritto (i) e (ii)
%2. "all neighbors play an action making..." I suppose this should be read as "the neighbors play a
%joint action profile making" rather than "each neighbor's action by itself is sufficient to make". Little
%confusing.
%3. Condition (i) is ambiguous --- you mean that one of the neighbors makes the clause true, not that all of
%them have to, right?

\bvs\item[(i)] $u_{c}(\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;

\bvs\item[(ii)] $u_{c}(\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;

\bvs\item[(iii)] $u_{c}(\x)=2$ if $c$ plays $f$ and there exists $v \in \N(c)$ such that $v$ plays $u$;

\bvs\item[(iv)] $u_{c}(\x)=1$ in all the other cases.
\end{description}

\noindent For each player $v\in P_v$, her utility function $u_v$ is such that
\begin{description}
\bvs\item[(v)] $u_{v}(\x)=3$ if $v$ plays an action in $\{t,f\}$ and all of her neighbors play an action in
$\{t,f\}$;

\bvs\item[(vi)] $u_{v}(\x)=2$ if $v$ plays $u$ and there exists $c \in \N(v)$ such that $c$ plays $u$;

\bvs\item[(vii)] $u_{v}(\x)=1$ in all the other cases.
\end{description}

\noindent We claim: \ \  $\Phi$ is satisfiable \,$\Leftrightarrow$\, $\G$ admits a Nash equilibrium.

($\Rightarrow$) Assume $\Phi$ is satisfiable, and take one of such satisfying truth assignments, say $\sigma$.
Consider the global strategy $\x$ for $\G$ where each player in $P_v$ chooses the action according to $\sigma$,
and where each player in $P_c$ plays $t$. Note that, in this case, all players get payoff $3$ according to the
rules (i) and (v) above, and since 3 is the maximum payoff, $\x$ is a Nash equilibrium for $\G$.

($\Leftarrow$) 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$.

\vspace{-2mm}\begin{description} \item[$P_1:$] {\em A  strategy $\x$ in which a player $v \in P_v$ plays $u$
cannot be a Nash equilibrium.}
 Indeed, assume by contradiction that $\x$ is a Nash equilibrium.
 Then, all $c \in \N(v)$ must play $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.

\vspace{-2mm}\item[$P_2:$] {\em A strategy $\x$ in which a player $c \in P_c$ plays $u$ cannot be a Nash
equilibrium}. Indeed, if there is such a player $c$ that chooses $u$, then from rule (vi) each variable player
$v \in \N(c)$ must play $u$, in order to get her maximum possible payoff 2 for the case at hand. Therefore, $\x$
cannot be a Nash equilibrium, by property $P_1$ above.

\vspace{-2mm}\item[$P_3:$] {\em 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, and hence $\x$ is not a Nash
equilibrium, by property $P_2$.

\vspace{-2mm}\item[$P_4:$] {\em A strategy $\x$ in which all players play an action in $\{t,f\}$ and there
exists a player $c \in P_c$ that plays $f$ cannot be a Nash equilibrium}. Indeed, if $\x$ is a Nash equilibrium
and all players play an action in $\{t,f\}$, by property $P3$ the truth assignment corresponding to this
strategy satisfies each clause $c$. It follows that a player $c$ that plays $f$ contradicts the assumption that
$\x$ is a Nash equilibrium, because $c$ could change her choice to $t$, improving her payoff to 3.
\end{description}

    \vspace{-2mm}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$ and get
payoff 3, as they are all made true by the truth assignment of their neighbors.

Combined with the ``$\Rightarrow$''-part, this entails that there is a one-to-one correspondence between
satisfying truth assignments to the variables of $\Phi$ and Nash equilibria of the game~$\G$.

Finally, observe that the tables (matrices) representing the entries of the utility functions (rules (i)--(vii)
above) can be built in polynomial time from  $\Phi$. Moreover, from the assumptions that we made on the
structure of $\Phi$, each player depends on $3$ other players at~most. \qed

%ggc
%gianluigi: per accontentarlo, elimino "even" riferito alla questione "sparse"
%- Page 14, after the end of the proof, where it says "even if the players'
%interaction is very sparse." This doesn't seem to be the right implication.
%Sparse interaction also implies smaller input size, so it's not surprising
%that this is the hard case. Using the word "even" seems to imply that this
%case a priori should be easier than allowing full interactions.
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 dependency graph of the game described in the hardness
part of the proof is cyclic. Thus, one may wonder if the problem is any easier for games with simple structured
interactions. We next show 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.

\begin{thm}\label{theo:acyc-hard}
Deciding whether a game $\G$ in general form has a pure Nash equilibrium is $\NP$-complete, even if both its
dependency graph and its associated hypergraph are acyclic, and the number of actions is fixed.
\end{thm}
\proof Membership follows from the previous theorem. We next prove that this problem is $\NP$-hard, via a
reduction from SAT. Given a Boolean formula $\Phi$ over variables $X_1,...,X_m$, we define a game $\G$ with $m$
players $X_1,...,X_m$ corresponding to the variables of $\Phi$, and two additional players $T$ and $H$. Any
player $X_i$, $1\leq i\leq m$, has only two available actions, $t$ and $f$, corresponding to truth assignments
to the corresponding variable of $\Phi$. Moreover, the utility function of each player $X_i$ is a constant, say
1. Hence, the choice of $X_i$ is independent of 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 $X_1,\ldots,X_m$ encode a satisfying truth assignment for $\Phi$. Indeed,
their behaviors -- described below -- ensure that only strategies where $T$ plays $s$ may be Nash equilibria,
because of her interaction with player $H$, whose role is to discard bad strategies. Given a combined strategy
$\x$ for the ``variable players" $X_1,...,X_m$, we denote by $\Phi(\x)$ the evaluation of $\Phi$ on the truth
values determined by the strategy $\x$.
\begin{description}
\item[Player $T$] depends on the players in $\{X_1,\ldots,X_m,H\}$, and her utility function is defined as
follows. For any combined strategy $\y=\x_1\cup \x_2$ for $X_1,\ldots,X_m,H,T$, where $\x_1$ is a combined
strategy for $X_1,...,X_m$ and $\x_2$ for $T$ and $H$:
\begin{itemize}
\item $u_T(\y)=1$ if $\Phi(\x_1)$ is true and $T$ plays $s$, or $\Phi(\x_1)$ is false and $\x_2= \{T_u,H_g\}$,
or $\Phi(\x_1)$ is false and $\x_2= \{T_s,H_b\}$;

\item $u_T(\y)=0$, otherwise.
\end{itemize}
\item[Player $H$] depends only on $T$ and, for any combined strategy $\x$ for $H$ and $T$, her utility function
is the following:
\begin{itemize}
\item $u_H(\x)=1$ if $\x$ is either $\{T_s,H_g\}$ or $\{T_u,H_b\}$;

\item $u_H(\x)=0$, otherwise.
\end{itemize}
\end{description}

We claim there is a one-to-one correspondence between Nash equilibria of this game and satisfying assignments
for $\Phi$. Indeed, let $\phi$ be a satisfying assignment for $\Phi$ and $\x_\phi$ the combined strategy for
$X_1,\ldots,X_m$ where these players choose their actions according  to $\phi$. Then, $x_\phi \cup \{T_s, H_g
\}$ is a Nash equilibrium for $\G$, because all players get their maximum payoff.

On the other hand, if $\Phi$ is unsatisfiable, for any combined strategy $\x_1$ for $X_1,\ldots,X_m$,
$\Phi(\x_1)$ is false. In this case, $T$ and $H$ have opposite interests and it is easy to check that, for each
combined strategy $\x_2\in \St(\{H,T\})$,  $\x_1\cup\x_2$ is not a Nash equilibrium for $\G$, because either $H$
or $T$ can improve its payoff.

Finally, observe that the dependency graph $\DG(\G)$ is a tree, and that the hypergraph $\H(\G)$ is acyclic.
\qed


As shown in Figure \ref{fig:results}, the above $\NP$-hardness result immediately extends to all generalizations
of acyclicity. The case of acyclic-hypergraph games in GNF will be dealt with in Section~\ref{sec:easy}.

Let us now draw our attention to Pareto equilibria. By Definition~\ref{defn:NE}, a Pareto Nash equilibrium
exists if and only if a Nash equilibrium exists. Therefore, from Theorems~\ref{thmNP} and~\ref{theo:acyc-hard},
we get the following corollary.

\begin{cor} 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 normal form and has $k$-bounded neighborhood, for any fixed constant $k\geq 3$, or if both
$\DG(\G)$ and $\H(\G)$ are acyclic.
\end{cor}
%\proof %(Sketch.)
%The problem is equivalent to deciding whether $\G$ has Nash
%equilibria. Indeed, any Pareto equilibrium is a pure Nash
%equilibrium, by definition. Moreover, observe that if there exists
%$\x\in \NE(\G)$ then, either $\x\in \PNE(\G)$, or $\x$ is
%dominated by some other equilibrium $\y\in \NE(G)$ and hence
%by a Pareto equilibrium $\z\in \PNE(G)$.

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 computationally hard task. In fact, we next show
that this problem is as difficult as checking whether $\x$ is a strong Nash equilibrium. However, we will see
that deciding the existence of a strong Nash equilibrium is much harder, and in  fact complete for the second
level of the Polynomial Hierarchy. To this end, in the following proofs, we associate quantified Boolean
Formulas having two quantifier alternations (2QBFs) with games.

%%%%%%%% Definizione del gioco associato ad una QBF %%%%%%%%%%%%
\paragraph*{Quantified Boolean Formulas (QBFs) and games.}
Let $$\Xi \quad = \quad \exists \alpha_1,\ldots\alpha_n \quad \forall \beta_1,\ldots\beta_q
\quad\quad \Phi$$ be a quantified Boolean formula in disjunctive normal form, i.e., $\Phi$ is a
Boolean formula of the form $d_1\vee \ldots \vee d_m$ over the variables $\alpha_1,\ldots\alpha_n,
\beta_1,\ldots\beta_q$, where each $d_i$ is a conjunction of literals. Deciding the validity of
such formulas is a well-known $\Sigma^P_2$-complete problem -- \cite<e.g.>{SM73},
 and it is easy to see that hardness result holds even if each
disjunct $d_j$ in $\Xi$ contains three literals at most and each variable occurs in three
disjuncts at most. Moreover, without loss of generality, we assume that the number $m$ of
disjuncts is a power of $2$, say $m=2^\ell$, for some integer $\ell\geq 2$. Note that, if
$2^{\ell-1}<m<2^\ell$, then we can build in polynomial time a new QBF $\Xi'$ having $2^l-m$ more
disjuncts, each one containing both a fresh existentially quantified variable and its negation.
Clearly, such disjuncts cannot be made true by any assignment, and hence $\Xi'$ is equivalent to
$\Xi$. Hereafter, we will consider quantified Boolean formulas of this form, that we call R2QBF.
%gianluigi: Non abbiamo cambiato.
%1. definition of R2QBF. I've also seen this problem referred to as QSAT_2, which I think might be more
%standard.
For each such formula $\Xi$, a truth value assignment $\sigma$ to the existentially quantified variables
$\alpha_1,\ldots,\alpha_n$ such that the formula $\forall \quad \beta_1,\ldots\beta_q \quad\ \sigma(\Phi)$ is
valid is called a {\em witness of validity} for $\Xi$.

As a running example for this section, we consider the following QBF $\Xi_r$: $\exists \alpha_1\alpha_2\alpha_3
\forall \beta_1\beta_2\beta_3\beta_4\beta_5 \ (\alpha_1\wedge \alpha_2)\vee (\alpha_1\wedge \alpha_3)\vee
(\alpha_1\wedge \neg \beta_1)\vee (\beta_1)\vee (\neg \beta_2 \wedge \neg \beta_3)\vee (\beta_1 \wedge
\beta_3)\vee (\beta_3 \wedge \beta_4)\vee (\beta_5)$.

We define a GNF game $\GX$ associated with a R2QBF $\Xi$ as follows. The players of $\GX$ are partitioned in
five sets $P_e$, $P_u$, $P_d$, $P_t$, and the singleton $\{C\}$.

Players in $P_e$, $P_u$, and $P_d$ correspond to the existential variables $\alpha_1,\ldots\alpha_n$, to the
universal variables $\beta_1,\ldots\beta_l$, and to the $m$ disjuncts of $\Phi$, respectively. Each ``variable"
player $v$ in $P_e \cup P_u$ may play a ``truth value" action in $\{T,F\}$ (read: $\{{\it true}, {\it
false}\}$), and her neighbors are the (at most three) players in $P_d$ corresponding to the disjuncts of $\Phi$
where $v$ occurs. Each ``disjunct" player $p$ may play an action in $\{T,F,w\}$, and her neighbors are the (at
most three) players corresponding to her variables, plus one player belonging to the set $P_t$, as described
below. As shown in Figure \ref{fig:RiduzioneSigmaP2}, these disjunct players are the leaves of a complete binary
tree comprising all players in $P_t$ as intermediate vertices, and the player $C$ as its root. In fact, the
``tree"  players $P_t$ act as logical-or gates of a circuit. For the sake of a simpler presentation, for each
tree player $p$, $children(p)$ denotes the set of two players that are children of $p$ in this tree, while
$parent(p)$ denotes her parent. As for disjunct players, the set of available actions for players in $P_t$ is
$\{T,F,w\}$. Finally, the player $C$, called ``challenger," may play actions in $\{T,w\}$. As shown in Figure
\ref{fig:RiduzioneSigmaP2}, the neighbors of $C$ are the two top level tree-players.

\begin{figure}[t]
    \centering
    \includegraphics[width=0.98\textwidth]{SigmaP2Rid.eps}
    \caption{On the left: the dependency graph of the game $\GXr$. On the right:
    a truth-value assignment for $\Xi_r$ corresponding to a strong Nash equilibrium
    of $\GXr$.}\label{fig:RiduzioneSigmaP2}
\end{figure}


Let $\x$ be a global strategy. The {\em utility functions} for the players in $\GX$ are defined as follows.
\begin{description}
\item[Existential-variables players.] For each $\alpha\in P_e$,
\begin{description}
\bvs\item[(E-i)] $u_\alpha(\x)=1$, no matter of what other players do;
\end{description}
%\ \\
\item[Universal-variables players.] For each $\beta \in P_u$,
\begin{description}
\bvs\item[(U-i)] $u_\beta(\x)=2$, if there exists a (disjunct) neighbor playing $w$;
 \bvs\item[(U-ii)] $u_\beta(\x)=1$ in all other cases.
\end{description}
%\ \\
\item[Disjuncts players.] For each $d\in P_d$,
\begin{description}
 \bvs\item[(D-i)] $u_d(\x)=2$
if $d$ and her parent (i.e., a node from $P_t$) both play $w$, and the disjunct of $\Phi$ corresponding to $d$
 is made false by the truth-value actions in $\x$ of her
variable players, i.e., by
 the players in $\N(d) \cap (P_e \cup P_u)$;
 \bvs\item[(D-ii)] $u_d(\x)=1$ if $d$ plays $T$
and the disjunct of $\Phi$ corresponding to $d$
 is made true by the truth-value actions in $\x$ of her variable players;
 \bvs\item[(D-iii)] $u_d(\x)=1$ if $d$ plays $F$,
 the disjunct of $\Phi$ corresponding to $d$
 is made false by the truth-value actions of her variable players,
 and her parent node (a tree player) does not play $w$;
\bvs\item[(D-iv)] $u_d(\x)=0$, in all other cases.
\end{description}
%\ \\
\item[Tree players.] For each $p\in P_t$,
\begin{description}
 \bvs\item[(TREE-i)] $u_p(\x)=2$ if both $p$ and all of her neighbors
 play $w$;
 \bvs\item[(TREE-ii)]
$u_p(\x)=1$ if $p$ plays $T$, none of her neighbors plays $w$, and some player in $children(p)$ plays $T$;
 \bvs\item[(TREE-iii)] $u_p(\x)=1$ if $p$
plays $F$, none of her neighbors plays $w$, and all players in $children(p)$ plays $F$;
 \bvs\item[(TREE-iv)] $u_p(\x)=1$ if $p$ plays an action in $\{T,F\}$, and
 some of her neighbors plays $w$, but not all of them;
 \bvs\item[(TREE-v)] $u_p(\x)=0$ in all other cases.
\end{description}
%\ \\
\item[Challenger.] For player $C$,
\begin{description}
\bvs\item[(CHALL-i)] $u_C(\x)=2$ if $C$ plays $w$, and either both of her neighbors play $F$, or at least one of
them plays $w$;
 \bvs\item[(CHALL-ii)] $u_C(\x)=1$ if $C$ plays $T$,
some of her neighbors plays $T$, and none plays $w$;
 \bvs\item[(CHALL-iii)]
$u_C(\x)=0$ in all other cases.
\end{description}
\end{description}

Intuitively, universal-variable players corresponding to the variables $\beta_1,\ldots\beta_q$ choose their
actions trying to falsify the formula, since their maximum payoff $2$ can be obtained only if $\Phi$ is not
satisfied.
 The strategies of variable players are suitably
 ``evaluated" by players in $P_d\cup P_t$, and eventually by $C$.

It is worthwhile noting that $\GX$ can be built in polynomial time (actually, in $\LOGSPACE$) from $\Xi$, and
that each player in $\GX$ may play at most three actions and has a bounded number of neighbors. More precisely,
for the sake of presentation, in the above construction each player has at most four neighbors. However, we will
show later in this section how this bound can be reduced easily to three.

Let $\x$ be a global strategy for $\GX$. We denote by
 $\sigma(\x)$ the truth-value assignment for $\Phi$ determined by
 the actions chosen by the variable players
 (i.e., those in $P_e\cup P_u$) in the strategy $\x$.
Moreover, we denote by $\sigma_e(\x)$ and $\sigma_u(\x)$ its restriction to the existential and the universal
variables, respectively.


\begin{lem}\label{lem:qbf}
There is a one-to-one correspondence among the satisfying truth-value assignments for $\Phi$ and the Nash
equilibria of $\GX$
 where no player plays $w$.
\end{lem}
\noindent\textbf{Proof.} Assume $\Phi$ is satisfiable, and let $\sigma$ be a satisfying truth-value assignment
for it. Consider the following global strategy $\x_\sigma$ for $\GX$: each variable player in $P_e \cup P_u$
chooses her truth-value action according to $\sigma$; each disjunct player in $P_d$ plays either $T$ or $F$,
depending on the logical evaluation of the disjunct associated with her; each tree player $p$ in $P_t$ plays
either $T$ or $F$, acting as an OR gate having as its input the values played by $\mathit{children}(p)$; the
player $C$ plays $T$.
%; and the player $D$ plays $T$.
%gianluigi: ho commentato, sembra avere ragione.
%3. "and the player D plays T" - there is no player D
Note that no player chooses $w$ in $\x_\sigma$.

Figure \ref{fig:RiduzioneSigmaP2} shows on the right the strategy for $\GX$ associated with the truth assignment
$\alpha_1=\alpha_2=\alpha_3=\beta_1=T$ and $\beta_2=\beta_3=\beta_4=\beta_5=F$.

Since $\sigma$ is a satisfying assignment, at least one disjunct of $\Phi$ will be evaluated to {\em true} and
thus at least one of the tree-player neighbors of $C$ plays $T$. Therefore, it is easy to check that, according
to the utility functions of $\GX$, all players get payoff $1$ with respect to $\x_\sigma$. 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$.
% and from rule (DUPL-i) for $D$.

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 her action, because all these rules may be applied only if
there is some neighbor that is playing $w$, which is not the case in $\x_\sigma$. It follows that the global
strategy $\x_\sigma$ is a Nash equilibrium for $\GX$.

We next prove the converse, that is, we show that each Nash equilibrium $\x$ for $\GX$ where no player chooses
$w$ corresponds to a satisfying truth-value assignment for $\Phi$.
 This proof is based on the following properties of $\x$:

\begin{description}
\item[$P_1:$] {\em At least one player in $\N(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$.

%\item[$P_2:$] {\em If a player in $P_d \cup P_t$ plays $w$ then all
%players in $P_d \cup P_t$ play $w$.} Indeed, let $p$ be a player in
%$P_d \cup P_t$ playing $w$ and assume by contradiction that there is
%a player $q$ in $P_d\cup P_t$ that does not play $w$. W.l.o.g., we
%can assume that $q \in \N(p)$ and viceversa. Then, $p$ gets payoff
%0, but could increase her payoff by playing an action in $\{T,F\}$
%according to (D-ii) or (D-iii) for players in $P_d$, and to
%(TREE-ii), (TREE-iii) or (TREE-iv) for players in $P_t$. This
%contradicts the fact that $\x$ is a Nash equilibrium.

%\item[$P_3:$]
%{\em No player in $P_d \cup P_t$ plays $w$.} Otherwise, from $P_2$,
%all players in $P_d \cup P_t$ play $w$ and, in particular, the
%players in $\N(C)-\{D\}$. However, this is not possible, after
%property $P_1$.

\item[$P_2:$] {\em At least one player in $P_d$ 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 best available choice for all
 tree-players depending on disjunct players in $P_d$ is to play $F$,
 according to (TREE-iii).
 It follows by induction that all players in $P_t$ would play $F$
 and, in particular, all neighbors of $C$.
 However, this contradicts property $P_1$ of $\x$.

\item[$P_3:$] {\em $\Phi$ is satisfied by the truth-assignment $\sigma(\x)$.}
 Let $p\in P_d$ be a disjunct player that plays $T$, and whose
 existence is guaranteed by property $P_2$. From the hypothesis that no
 player chooses $w$,
 rule (D-i) is not applicable to $p$.
 It follows that the disjunction $d$ of $\Phi$ corresponding to player
 $p$ is true with respect to $\sigma(\x)$.
 Otherwise, $\x$ would not be a Nash equilibrium,
 because $p$ would get payoff 0 from (D-iv)
 and could improve it by playing the correct evaluation $F$, after
 rule (D-iii).
\end{description}

Therefore, in case no player chooses $w$, all global strategies that are Nash equilibria correspond to
satisfying assignments for $\Phi$. \qed

\vspace{-6mm}
\begin{lem}\label{lem:qbf2}
 A Nash equilibrium $\x$ for $\GX$ where no player chooses $w$
 is strong if and only
 if $\sigma_e(\x)$ is a witness of validity for $\Xi$.
\end{lem}
\noindent\textbf{Proof.}
 $(\Rightarrow)$ Assume $\x$ is a strong Nash
equilibrium for $\GX$ where no player chooses $w$. Then, $\sigma(\x)$ satisfies $\Phi$, from the previous lemma.
Assume by contradiction that $\sigma_e(\x)$ is not a witness of validity for $\Xi$. Then, there is an assignment
$\sigma_u'$ for the universal variables such that $\Phi$ is not satisfied with respect to $\sigma_e(\x)\cup
\sigma_u'$. Let $K$ be the coalition comprising all players in $\GX$ but the existential players in $P_e$, and
let $\y$ be the combined strategy for $K$ such that all universal players in $P_u$ choose their truth-value
action according to $\sigma_u'$, and all the other players in $K$ play $w$. By the choice of $\sigma_u'$, all
the disjuncts are made false via the truth-value actions chosen by players in $P_u$. Then, from rule (D-i), all
disjunct players get payoff 2 according to $\x_{-K}[\y]$. Similarly, from (Tree-i) and (Chall-i), all
tree-players and the player $C$ get payoff 2 in $\x_{-K}[\y]$. However, this means that all players in the
coalition are improving their payoff, and this contradicts the fact that $\x$ is a strong Nash equilibrium.

$(\Leftarrow)$ Assume that $\Xi$ is valid and let $\sigma(\x)$ be a satisfying truth-value assignment for $\Phi$
such that $\sigma_e(\x)$ is a witness of validity for $\Xi$, for some Nash equilibrium $\x$ for $\GX$. Indeed,
from Lemma \ref{lem:qbf} we know such an equilibrium (where no player plays $w$) exists for every satisfying
assignment, and that no player chooses $w$ in $\x$. Moreover, it is easy to check that all players get payoff 1,
according to this global strategy. Assume by contradiction that $\x$ is not a strong Nash equilibrium for $\GX$.
Then, there is a coalition $K$ and a combined strategy $\y$ for $K$ such that all players in the coalition may
improve their payoff in the global strategy $\x_{-K}[\y]$, and hence they get payoff $2$ in this strategy. Note
that no existential player may belong to $K$ and thus change her action, because there is no way for her to
improve her payoff.
%Then, from rules (D-i), (Tree-i), and (Chall-i), the only way for players in $P_d$, $P_t$, and $C$ to improve
%their payoff to 2 is that all of them change their actions to $w$, because all these rules require that, for
%each player, all of her neighbors play $w$. Thus, if one of them belongs to $K$, then all of them belong to this
%coalition, too.
%gianluigi: il revisore ha ragione, ed ho modificato di conseguenza
%3. These rules require that for each player all of her neighbors play w. This is not exactly true for C and P_d.
Then, from rule (Tree-i), the only way for players in $P_t$ to improve their payoff to 2 is that all of
them change their actions to $w$, because all these rules require that, for each player, all of her
neighbors play $w$. Thus, if one of them belongs to $K$, then all of them belong to this coalition, as
well as player $C$ and all the disjunct players in $P_d$, that are their neighbors and should change her
choices to $w$ in order to get 2, too. On the other hand, for all disjunct players $p$ in $P_d$, this
improvement to $2$ depends also on the variable players occurring in the disjunct of $\Phi$ associated
with $p$ (D-i). In particular, besides playing $w$, this disjunct should also be made false, because of
some change in the choices of the universal players $p$ depends on. Note that such players may in turn
improve their payoff to 2, if $p$ plays $w$. It follows any coalition $K$ that shows $\x$ is not a Nash
equilibrium contains a number of universal players that are able to let all the disjunct players to be
unsatisfied and hence to change their actions to $w$, thus getting payoff 2. However, the truth-values
corresponding to the actions of players in $P_u\cap K$ determine an assignment $\sigma_u'$ that
contradicts the validity of $\Xi$. \qed


\begin{thm}\label{thmCONP}Given a game $\G$
and a global strategy $\x$, deciding whether $\x\in \SNE(\G)$ (resp., $\x\in \PNE(\G)$) is \CONP-complete.
Hardness holds even if the given strategy $\x$ is a pure Nash equilibrium, $\G$ is in graphical normal form and
has $3$-bounded neighborhood, and the number of actions is fixed.
\end{thm}

\noindent\textbf{Proof.} {\em Membership.} Deciding whether $\x\not\in\PNE(\G)$ is in $\NP$: (i) check in
polynomial time whether $\x\not\in\NE(\G)$; (ii) if this is not the case, guess a global strategy $\y$ and check
in polynomial time whether $\y\in\NE(\G)$ and $\y$ dominates $\x$. Similarly, deciding whether
$\x\not\in\SNE(\G)$ is in $\NP$: (i) check in polynomial time whether $\x\not\in\NE(\G)$; (ii) if this is not
the 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 playing their actions according to the
new strategy $\y$.


\noindent\emph{Hardness.} It is well-known that checking whether a satisfiable formula $\Phi$ in 3DNF is {\em
tautologically valid} is co-NP complete. We reduce this problem to the problem of checking whether a given Nash
equilibrium is strong (Pareto). Let $\Phi$ be a satisfiable formula in 3DNF. Find a satisfying truth value
assignment $\sigma$ for $\Phi$. This is obviously possible in polynomial time, given that $\Phi$ is satisfiable
and in DNF. Define $\Xi = \forall \beta_1,\ldots\beta_q \quad \Phi$. $\Xi$ can be considered a (degenerate)
R2QBF without existentially quantified variables. Let $\GX$ be the game associated with $\Xi$. Obviously, $\GX$
can be constructed in polynomial time from $\Phi$. Let $\x$ be the Nash equilibrium for $\GX$ determined by this
truth-value assignment where no player chooses $w$, as described in Lemma \ref{lem:qbf}, and note that even this
equilibrium can be
 computed in polynomial time from $\sigma$. Then, by
 Lemma \ref{lem:qbf2}, $\x$ is strong if only if  $\Phi$ is valid
(i.e., the vacuous assignment $\sigma_e$ is a witness of validity). This settles the hardness of checking
whether a given Nash Equilibrium is strong.  In addition, it is not hard to see that in the above construction
$\x$ is a Pareto equilibrium for $\GX$ if and only if $\Phi$ is a tautology. Indeed, note that, there is a
truth-value assignment $\sigma'$ that falsifies $\Phi$, if and only if there is a global strategy $\y$ where
(universal) variable players play according to $\sigma'$ and all other players choose $w$, such that $\y$
dominates the Nash equilibrium $\x$. Thus checking whether a given Nash equilibrium is Pareto is co-NP complete,
too.
%***********************************************************************
% VECCHIO PARAGRAFO 1
%\noindent Let $\Xi = \exists
%\alpha_1,\ldots\alpha_n \forall \beta_1,\ldots\beta_q \quad \Phi$ be a R2QBF
%and $\GX$ the game associated with this formula. Moreover, let $\sigma_e$ be
%a truth-value assignment to the existential variables
%$\alpha_1,\ldots\alpha_n$ and assume that $\sigma_e$ can be extended to a
%truth-value assignment $\sigma$ to all variables occurring in $\Xi$ such that
%$\Phi$ is satisfied by $\sigma$. Note that
%% this
%an extension $\sigma$ of $\sigma_e$ satisfying $\Phi$ can be computed in
%polynomial time because $\Phi$ is in 3DNF.
% Recall that deciding whether such an assignment $\sigma_e$ is a
%witness of the validity of $\Xi$ is a $\coNP$-complete problem.
% Let $\x$ be the Nash equilibrium for $\GX$ determined by this
%truth-value assignment where no player chooses $w$,
% as described in Lemma \ref{lem:qbf}, and note that even this equilibrium can be
% computed in polynomial time from $\sigma$. Indeed, we can choose for
% variable players the actions corresponding to the truth-values in $\sigma$,
% and for the other players the actions derived from the evaluation of the
% Boolean circuit they represent, if all of them choose actions corresponding
% to Boolean values.
%  Then, from Lemma \ref{lem:qbf2}, $\x$ is a strong Nash equilibrium for $\x$
%  if and only if  $\sigma_e$ is a witness of validity for $\Xi$.
%**************************************************************************
% Secondo paragrafo vecchio:
%As far as Pareto equilibria are concerned, assume,
%
%again, that $\Xi$ has no existential players (and is thus of the same
%form as above).
% that we are given a formula
%$\Xi$ without existential variables. In this case, given a satisfying
%assignment $\sigma$ for $\Phi$, deciding whether this 3DNF formula is a
%tautology, i.e., is satisfiable by any truth-value assignment, is a $\coNP$
%problem. Since there are no existential players in $\GX$, it is easy to see
%that, from the same line of reasoning as above,
%
%$\x$ is a Pareto equilibrium
%for $\GX$ if and only if $\Phi$ is a tautology. Indeed, note that, if there
%is a truth-value assignment $\sigma'$ that falsifies $\Phi$, then there is a
%global strategy $\y$ where (universal) variable players play according to
%$\sigma'$ and all other players chooses $w$, such that $\y$ dominates the
%Nash equilibrium $\x$.
%**************************************************************************

We conclude the proof by observing that, in our reduction, each player in $P_e \cup P_u \cup P_t \cup \{C\}$
depends on three other players at most, but some player $d$ in $P_d$ may depend on four other players, if the
corresponding disjunct contains exactly three literals. In this case, we may introduce an additional player $d'$
whose set of actions is $\{T,F,w\}$ and whose neighbors are the first two literals plus $d$. Moreover, her
utility function is such that $d'$ acts as an AND-gate on the inputs of the literals, preferring $w$ if the two
literals are evaluated false, or if $d$ plays $w$.
%ggc
%gianluigi: non ho modificato per non complicare troppo la dimostrazione (la cosa richiede un bel po' di sforzo).
%3. Be precise (show numbers) in describing the utility function of d'
In this new encoding, $d$ depends only on $d'$ and on the third literal occurring in the disjunct. As for the
basic construction previously defined, her payoff is 2 if she plays $w$, her parent plays $w$, and the third
literal is false, or if $d'$ plays $w$. Figure \ref{fig:RiduzioneSigmaP23} shows this transformation. Note that
this construction preserves all the properties proved so far, and each player depends on three other players at
most. \qed

\begin{figure}[t]
    \centering
    \includegraphics[width=0.4\textwidth]{SigmaP2Rid3.eps}
    \caption{Transformation of a disjunct
    containing exactly three literals.}\label{fig:RiduzioneSigmaP23}
\end{figure}

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 problem is located at the second level of the
polynomial hierarchy.

\begin{thm}\label{theo:sigmaP2} Given a game $\G$,
deciding whether $\G$ has a strong Nash equilibrium is $\Sigma^P_2$-complete. Hardness holds even if $\G$ is in
graphical normal form and has $3$-bounded neighborhood, and the number of actions is fixed.
\end{thm}

\proof {\em Membership.} We can decide that $\SNE(\G)\neq\emptyset$ by guessing a global strategy $\x$ and
verifying that $\x$ is a strong Nash equilibrium for $\G$. From Theorem \ref{thmCONP}, the latter task is
feasible in $\CONP$. It follows that the problem belongs to $\Sigma^P_2$.

\noindent\emph{Hardness.} Let $\Xi= \exists \alpha_1,\ldots\alpha_n \forall \beta_1,\ldots\beta_q \Phi$ be a
R2QBF. Recall that deciding the validity of such formulas is a $\Sigma^P_2$-complete problem -- see the
definition of R2QBF above, in the current section.

We define a game $\GX'$ associated with $\Xi$, obtained from $\GX$ with the addition of one more gadget. In
$\GX'$ 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 the challenger player $C$. On the other hand, also $C$
depends on this new player $D$, besides her other tree-players neighbors (recall the construction shown in
Figure \ref{fig:RiduzioneSigmaP2}). Both $C$ and $D$ play actions in $\{T,w,u\}$.
 Everything else is
the same as in $\GX$, but for the utility functions of players $C$ and $D$:
\begin{description}
\item[Challenger.] For player $C$,
\begin{description}
\bvs\item[(CHALL-i)] $u_C(\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 $\N(C)-\{D\}$) play $F$, or at least one of them plays $w$;
 \bvs\item[(CHALL-ii)] $u_C(\x)=1$ if $C$ plays $T$,
one player in $\N(C)-\{D\}$ plays $T$, and none plays $w$; \bvs\item[(CHALL-iii)] $u_C(\x)=0$ in all other
cases.
\end{description}
%\ \\
\item[Duplicator.] For player $D$,
\begin{description}
\bvs\item[(DUPL-i)] $u_D(\x)=1$ if $D$ plays the same action as $C$; \bvs\item[(DUPL-ii)] $u_D(\x)=0$ in all
other cases.
\end{description}
\end{description}

Recall that, in order to maximize their payoffs, the universal-variable players try to make $\Phi$ false, and
that
 the strategies of variable players are suitably
 ``evaluated" by players in $P_d\cup P_t$, acting as a Boolean circuit.
 Moreover, the challenger and the duplicator are designed in such a way that
 strategies where some player chooses $w$,
 which do not correspond to satisfying assignments for $\Phi$,
 cannot lead to Nash equilibria.
 Formally, for any Nash equilibrium of $\GX'$, the following properties hold.
\begin{description}
\item[$P_1:$] {\em At least one player in $\N(C)-\{D\}$ does not play $F$ and no player in $\N(C)-\{D\}$ plays
$w$.} Otherwise, $C$ would play an action in $\{w,u\}$ different from the one played by $D$ in $\x$, in order to
get payoff 2, from rule (CHALL-i). However, such a strategy cannot be an equilibrium, because $D$ could improve
her payoff by choosing the same action as $C$ in $\x$.

\item[$P_2:$] {\em If a player in $P_d \cup P_t$ plays $w$ then all players in $P_d \cup P_t$ play $w$.} Indeed,
let $p$ be a player in $P_d \cup P_t$ playing $w$ and assume by contradiction that there is a player $q$ in
$P_d\cup P_t$ that does not play $w$. W.l.o.g., we can assume that $q \in \N(p)$ and viceversa. Then, $p$ gets
payoff 0, but could increase her payoff by playing an action in $\{T,F\}$ according to (D-ii) or (D-iii) for
players in $P_d$, and to (TREE-ii), (TREE-iii) or (TREE-iv) for players in $P_t$. This contradicts the fact that
$\x$ is a Nash equilibrium.

\item[$P_3:$] {\em No player in $P_d \cup P_t$ plays $w$.} Otherwise, from $P_2$, all players in $P_d \cup P_t$
play $w$ and, in particular, the players in $\N(C)-\{D\}$. However, this is not possible, after property $P_1$.
 \end{description}

 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 $T$ in her turn and get payoff 1, from rule
 (Chall-ii). Then, $D$ may play $T$ and get payoff $1$, as well.
 Thus, it is no longer possible to have a Nash equilibrium with some
 player choosing the action $w$.
 Therefore, after Lemma \ref{lem:qbf2} (as the presence of the duplicator does not affect
 that proof), we get the following fundamental result:
a global strategy $\x$ is a strong Nash equilibrium for $\GX'$ if and only if the truth-value assignment
$\sigma_e(\x)$ is a witness of validity for $\Xi$. In particular, $\SNE(\GX')\neq\emptyset$ if and only if $\Xi$
is valid.

Finally, observe that even the game $\GX'$ can be modified as shown in
 Figure \ref{fig:RiduzioneSigmaP23}, in order to get a 3-bounded neighborhood
 game.
\qed

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.

\begin{thm}\label{theo:acyc-sigmap2-hard}
Deciding whether a game $\G$ in general form has a strong Nash equilibrium is $\Sigma^P_2$-complete, even if
both its dependency graph and its associated hypergraph are acyclic, and the number of actions is fixed.
\end{thm}
\begin{proof}
The proof of membership in $\Sigma^P_2$ is the same as the membership proof in the previous theorem. We next
prove that this problem is hard for $\Sigma^P_2$.

 Let  $\Xi \; = \;  \exists \alpha_1,\ldots\alpha_n \forall
\beta_1,\ldots\beta_q \; \Phi\;$
 be a quantified Boolean formula in disjunctive normal form.
 We define a game $\bar{\G_\Xi}$
with $m$ players $\alpha_1,\ldots\alpha_n, \beta_1,\ldots\beta_q$ corresponding to the existentially and
universally quantified variables of $\Xi$, and two additional players $T$ and $H$. The game is based on a
combination of the game techniques exploited in the proofs of Theorem \ref{theo:acyc-hard} and Theorem
\ref{theo:sigmaP2}.
 Any player associated with a variable has only two
available actions, $t$ and $f$, which represent truth assignments to the corresponding variable of $\Phi$; 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.

Given a combined strategy $\x$, we denote by $\Phi(\x)$ the evaluation of $\Phi$ on the truth values determined
by the strategy $\x$. Then, the utility functions are defined as follows. Any player $\alpha_i$ ($1\leq i\leq
n$) gets always payoff 1. Any player $\beta_j$ ($1\leq j\leq q$) depends on $T$ and gets payoff 1 if $T$ plays
$s$ in $\x$, and payoff 2 if $T$ plays $u$ in $\x$. Player $H$ depends only on $T$ and  gets payoff 1 if $\x$
contains either $\{T_s,H_g\}$ or $\{T_u,H_b\}$, and $0$, otherwise. Finally, player $T$ depends on players in
$\{\alpha_1,\ldots\alpha_n, \beta_1,\ldots\beta_q,H\}$, and her utility function is defined as follows:
\begin{itemize}
\item $u_T(\x)=2$, if $\Phi(\x)$ is false, $T$ plays $u$, and $H$ plays $g$; \item $u_T(\x)=1$, if $\Phi(\x)$ is
true and $T$ plays $s$, or if $\Phi(\x)$ is false, $T$ plays $s$, and $H$ plays $b$; \item $u_T(\x)=0$,
otherwise.
\end{itemize}

First, observe that both the dependency graph and the dependency hypergraph of $\bar{\G_\Xi}$ are acyclic.
Moreover, after the proof of Theorem \ref{theo:acyc-hard}, it is easy to see that there is a one-to-one
correspondence between Nash equilibria of this game and satisfying assignments for $\Phi$. Then, for any Nash
equilibrium $\x$ for $\bar{\G_\Xi}$, we denote by $\sigma^\x$ its corresponding truth-value assignment, and by
$\sigma_e^\x$ the restriction of this assignment to the existential variables of $\Xi$. Note that, as shown in
the above mentioned proof, at any Nash equilibrium, player $T$ plays $s$ and all players in the game get payoff
1.

We next prove that any witness of validity for $\Xi$ corresponds to a strong Nash equilibrium for
$\bar{\G_\Xi}$. 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 way for the coalition to get a payoff
higher than 1 is that $T$ changes her choice to $u$. In this case, if $\Phi(\x')$ is false (and $H$ plays $g$),
$T$ will get payoff 2. Since $\Phi$ is true with respect to $\x$, it follows that some variable players have to
change their choices, which means that they should belong to the coalition and improve their payoffs. Therefore,
all variable players in $K$ should correspond to universally quantified variables, as only these players are
able to improve their payoffs from 1 to 2. Thus, such a coalition $K$ exists if and only if the universally
quantified variables can make the formula false, that is, $\sigma_e^\x$ is not a witness of validity for $\Xi$.
Equivalently, it follows that $\x$ is a strong Nash equilibrium if and only if $\Xi$ is valid. \qed
\end{proof}

%francescoPost
\begin{rem}\label{rem:constanttime}
Recall that we assumed any general game $\G$ to be taken from the class $\C_{\bar{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
\ref{thmNP}, \ref{thmCONP}, and \ref{theo:sigmaP2}. In these constructions, each player has at most three
neighbors and a fixed number of actions. Therefore, the utility function of each player is computable in
constant time.
\end{rem}


\section{Easy Games}\label{sec:easy}

Before we deal with tractable games in graphical normal form (GNF), let us recall that all computational
problems dealt with in this paper are tractable for games in standard normal form (SNF), even for arbitrary
interactions among players. Actually, we next point out that they can be carried out in logarithmic space and
are thus in a very low complexity class that contains highly parallelizable problems only. This is not very
surprising, because in fact the size of SNF games may be exponentially larger than the size of the same games
encoded in GNF.

\begin{thm}\label{thm:easySNF}
Given a game in standard normal form, the following tasks are all feasible in logarithmic space: Determining the
existence of a pure Nash equilibrium, a pure Pareto equilibrium, or a strong Nash equilibrium, and computing all
such equilibria.
\end{thm}
\proof  Let $P$, as usual, denote the set of players. We assume w.l.o.g. that each player has at least two
possible actions (in fact, a player with a single action can  be eliminated from the game by a simple logspace
transformation, yielding an equivalent game). The size of the input matrix is thus at least $2^{|P|}$.

Given that  {\em 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, which corresponds to polynomial space in
$|P|\times |A|$, where $P$ and $A$ are the sets of players and the set of all possible actions, respectively),
the Nash equilibria are easily identified  by scanning (i.e., enumerating) all global strategies $\bf x$ keeping
a logspace index of  $\bf x$ on the worktape, and checking in logarithmic space (in the size of the input)
whether no player can improve her utility by choosing another action.
 Given that all Nash
Equilibria can be generated in logarithmic space, they also can be generated in polynomial time.

The Pareto equilibria can be identified by successively enumerating all Nash equilibria  ${\bf x}$, and by an
additional loop for each $\bf x$, enumerating all Nash equilibria $\bf y$ (indexed in logarithmic space as
above) and outputting $\bf x$ if there is no  $\bf y$ such that, $\forall p\in P$, $u_p({\bf y})> u_p({\bf 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 scanning all possible
coalitions of the players (which can be indexed in logarithmic space, as their number is $2^{|P|}$) in order to
discard those equilibria $\bf x$ for which there exists a coalition $K\subseteq P$ and a combined strategy $y$
for $K$, such that for each $p\in K$, $u_p({\bf x})< u_p(\x_{-K}[{y}])$. Finally, note that, for a fixed
coalition $K$, the enumeration of all the combined strategies $y$ for $K$ can be carried out by means of an
additional nested loop, requiring logarithmic space for indexing each such strategy.  \qed

\vspace{-3mm}\subsection{Constraint Satisfaction Problems and Games in Graphical Normal Form}

Let us now consider games in GNF. We first establish an interesting connection between constraint satisfaction
problems and games. An instance of a {\em constraint satisfaction problem (CSP)} (also {\em constraint network})
is a triple $I=({\it Var},U,\C)$, where ${\it Var}$ is a finite set of variables, $U$ is a finite domain of
values, and $\C=\{C_1,C_2,\ldots,C_q\}$ is a finite set of constraints. Each constraint $C_i$ is a pair
$(S_i,r_i)$, where $S_i$ is a list of variables of length $m_i$ called the {\em constraint scope}, and $r_i$ is
an $m_i$-ary relation over $U$, called the {\em constraint relation}. (The tuples of $r_i$ indicate the allowed
combinations of simultaneous values for the variables $S_i$).  A {\em solution} of a CSP instance is a
substitution $\theta:{\it Var}\longrightarrow U$, such that for each $1\leq i\leq q$, $S_i\theta\in r_i$. The
problem of deciding whether a CSP instance has any solution is called {\em
constraint satisfiability (CS)}. %(This definition is taken almost verbatim from~\cite{jeav-etal-97}.)
Since we are interested in CSPs associated with games, where variables are players of games, we will use
interchangeably the terms variable and player, whenever no confusion arises.

Let $\G=\tuple{P,\N,A,U}$ be a game and $p\in P$ a player. Define the \emph{Nash constraint} $\nc(p)=(S_p,r_p)$
as follows: The scope $S_p$ consists of the players in $\{p\}\cup\N(p)$, and the relation $r_p$ contains
precisely all combined strategies $\x$ for $\{p\}\cup\N(p)$ such that there is no $y_p\in \St(p)$ such that
$u_p(\x) < u_p(\x_{-p}[y_p])$. Thus note that, for each Nash equilibrium $\x$ of $\G$, $\x \cap \St(S_p)$ is in
$r_p$.

The constraint satisfaction problem associated with $\G$, denoted by $\CSP(\G)$, is the triple $({\it
Var},U,\C)$, where ${\it Var}=P$, the domain $U$ contains all the possible actions of all players, and $\C = \{
\nc(p) \mid p\in P\}$, i.e., it is the set of Nash constraints for the players in $\G$.

\vspace{-1mm}\begin{exmp}\em 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 Nash constraints:
$\nc(F)=(\{F,P,R\},r_F)$, $\nc(G)=(\{G,P,F\},r_G)$, $\nc(R)=(\{R,F\},r_R)$, $\nc(P)=(\{P,F\},r_P)$, and
$\nc(M)=(\{M,R\},r_M)$, where the constraint scopes are shown in Figure~\ref{fig:r}. \qed

\begin{figure}[t]
\centering \scriptsize {\scriptsize
\begin{tabular}{rl}
$r_F:$ &
\begin{tabular}{|c|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  F & P & R \\
  \hline \hline
  m&m&m \\
  m&m&o \\
  o&m&o \\
  m&o&m \\
  o&o&m \\
  o&o&o \\
  \hline
\end{tabular}
\end{tabular}
\begin{tabular}{rl}
$r_G:$ &
\begin{tabular}{|c|c|c|}  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  G & P & F \\
  \hline \hline
  m&m&m \\
  o&m&m \\
  m&m&o \\
  o&m&o \\
  m&o&m \\
  o&o&m \\
  m&o&o \\
  0&o&o \\
  \hline
\end{tabular}
\end{tabular}
\begin{tabular}{c}
\begin{tabular}{rl}
$r_R:$ &
\begin{tabular}{|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  R & F \\
  \hline \hline
  o&m \\
  m&o \\
\hline
\end{tabular}
\end{tabular}
\begin{tabular}{rl}
$r_P:$ \ \ \ \ \ &
\begin{tabular}{|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  P & F \\
  \hline \hline
  m&m \\
  o&o \\
\hline
\end{tabular}
\end{tabular}\\ \ \\ \ \\
\begin{tabular}{rl}
$r_M:$ &
\begin{tabular}{|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  M & R \\
  \hline \hline
  m&m \\
  o&o \\
\hline
\end{tabular}
\end{tabular}
\end{tabular}
} \caption{Constraint relations of the game FRIENDS in Example \ref{esempio}.}\label{fig:r}
\end{figure}
\end{exmp}

%gianluigi: anticipo il commento in questo punto; inoltre mi sono accorto che non avevamo detto esplicitamente cosa fosse la
% struttura del CSP
%1. after proof of theorem 4.3. Although this is relatively clear, it 's good to point out explicitly
%that CSP(G) for acyclic-hypergraph G would also be acyclic.
The structure of a constraint satisfaction problem $I=({\it Var},U,\C)$ is represented by the hypergraph
$\HG(I)=(V,H)$, where $V={\it Var}$ and $H=\{{\it var}(S) \mid C=(S,r)\in \C\}$, and ${\it var}(S)$
denotes the set of variables in the scope $S$ of the constraint $C$. Therefore, by definition of
$\CSP(\G)$, the hypergraph of any game $\G$ coincides with the hypergraph of its associated constraint
satisfaction problem, and thus they have the same structural properties.
%For instance, if
%$\G$ is represented by means of an acyclic-hypergraph, then $\CSP(\G)$ is acyclic as well.

The following theorem establishes a fundamental relationship between games and CSPs.

\begin{thm}\label{theo:CSP}
A strategy $\x$ is a pure Nash equilibrium for a game $\G$ if and only if it is a solution of $\CSP(\G)$.
\end{thm}
\proof Let $\x$ be a Nash equilibrium for $\G$ and let $p$ be any player. Then, for each strategy $p_a\in
\St(p)$, $u_p(\x) \geq u_p(\x_{-p}[p_a])$. Since $u_p$ depends only on the players in $\{p\}\cup\N(p)$, their
combined strategy $\x'\subseteq \x$ is a tuple of $\nc(p)$, by construction. It follows that the substitution
assigning to each player $p$ its individual strategy $p_a\in\x$ is a solution of $\CSP(\G)$.

On the other hand, consider any solution $\theta$ of $\CSP(\G)$, and let $p$ be any player. Let
$P'=\{p\}\cup\N(p)$ and $\x'$ the combined strategy $\{ \theta(q) \mid q\in P' \}$. Then, $\x'$ is a tuple of
$\nc(p)$, because $\theta$ 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 the other players. It
follows that the global strategy containing $\theta(p)$ for each player $p$ is a Nash equilibrium for $\G$. \qed

The following theorem states the feasibility of the computation of $\CSP(\G)$.

\begin{thm}\label{thm:CostruisciCSP}Let $\G$ be a game having small neighborhood or in
graphical normal form. Then, computing $\CSP(\G)$ is feasible in polynomial time.
\end{thm}
\proof  Let $\G=\tuple{P,\N,A,U}$ be a game having small neighborhood.
 We show that $\nc(p)=(S_p,r_p)$ can be computed in polynomial time. We initialize $r_p$ with all
the combined strategies for $\{p\}\cup\N(p)$. The number of these combined strategies is bounded by
$$\maxAct(\G)^{|\N(p)|}=2^{\log(\maxAct(\G)^{|\N(p)|})} \leq 2^{\intr(\G)\times \log (||\G||)}=
||\G||^{\intr(\G)},$$
%gianluigi: ho inserito il richiamo
%3. Recall the definition of intricacy at the beginning of the proof.
\noindent where the intricacy $\intr(\G)$ of $\G$ is given by
 $$\frac{\maxN(\G)\times \log \maxAct(\G)}{\log ||\G||}.$$
 Since $\G$ has small neighborhood, $i(\G)$ is bounded by some constant, and
thus the set of all combined strategies for $p$ is polynomially bounded. The initialization process
computes for each $p$ all corresponding combined strategies (via a simple enumeration), and thus takes
polynomial time (in the size of $\G$).

Now, for each tuple $\x$ in $r_p$ we have to check whether it should be kept in $r_p$ or not. Let $m = u_p(\x)$.
For each action $a\in\Act(p)$, compute in polynomial time $m' = u_p(\x_{-p}[p_a])$ and delete $\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 constraints is yet easier. In fact,  this task is
feasible in logspace  for GNF  games. \qed

After Theorem \ref{theo:CSP}, 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 the same hypergraph and, as shown by
Gottlob et al. \citeyear{GLS99b}, a solution of an acyclic constraint satisfaction problem can be computed by (a
slight adaptation of) the well known Yannakakis's algorithm for evaluating acyclic conjunctive queries
\cite{yanna}, or by the \LCFL\ algorithm proposed by Gottlob et al.~\citeyear{GLS99b}, which shows this problem
is highly parallelizable --- see Section~\ref{sec:parallel}, for more information on the complexity class \LCFL.
For the sake of completeness, in Figure \ref{fig:algAciclico}, we report an algorithm for deciding the existence
of a Nash equilibrium and for computing Nash equilibria of acyclic-hypergraph games, based on these results. We
assume the reader is familiar with typical database operations like semi-joins \cite<for more details, see,
e.g.,>{maie-86}.

\begin{figure}[t]
  \centering
  \fbox{
  \parbox{0.86\textwidth}{\scriptsize
  \begin{tabular}{c}
  \begin{tabular}{l}
  \textbf{Function} NashEvaluation($JT:$ join tree of $\H(\G)$): \textbf{Boolean}\\
  % \textbf{var} $ne:$ Nash equilibrium (represented as a tuple);\\
  \textbf{begin}\\
  \ \ \ \ Bottom-Up($JT$);\\
  \ \ \ \ \textbf{let} $v=(S_v,r_v)$ be the root of $JT$;\\
  \ \ \ \ \textbf{if} $r_v=\emptyset$ \textbf{then return false};\\
  \ \ \ \ \textbf{else } \\
  \ \ \ \ \ \ \ Top-Down($JT$); \\
  \ \ \ \ \ \ \ Select-equilibrium($JT$); \\
  \ \ \ \ \ \ \ \textbf{output} $JT$; \\
  \ \ \ \ \ \ \ \textbf{return true;} \\
  \textbf{end;}
  \end{tabular} \\
    \hline
  \begin{tabular}{ll}
  \begin{tabular}{l}\\
  \textbf{Procedure} Bottom-Up(var\ $T:$ tree)\\
  \textbf{begin}\\
  \ \ \ $Done :=$ the set of all the leaves of $T$;\\
  \ \ \ \textbf{while} $\exists v\in T$ such that\\
  \ \ \ \ \ \ \ (i) $v\not\in Done$, and\\
  \ \ \ \ \ \ \ (ii) $\{c \mid c \mbox{ is child of } v\}\subseteq Done$ \textbf{do}\\
  \ \ \ \ \ \ \textbf{for each} $c=(S_c,r_c)$ \textbf{child} of $v$ \textbf{do}\\
  \ \ \ \ \ \ \ \ \ $r_v:=r_v  \semijoin r_c$;\\
  \ \ \ \ \ \ $Done:=Done \cup \{v\}$;\\
  \ \ \ \textbf{end while}\\
  \textbf{end;}\\
  \end{tabular}
  &
  \begin{tabular}{l}
  \textbf{Procedure} Top-Down(var\ $T:$ tree)\\
  \textbf{begin}\\
  \ \ \ \textbf{let} $v=(S_v,r_v)$ be the root of $T$;\\
%  \ \ \ \textbf{select} any combined strategy $t_v\in r_v$;\\
%  \ \ \ \textbf{delete} all tuples in $r_v$, but $t_v$;\\
  \ \ \ \textbf{for each} $c=(S_c,r_c)$ \textbf{child} of $v$ \textbf{do}\\
  \ \ \ \ \ \ $r_c:=r_c  \semijoin r_v$;\\
  \ \ \ \ \ \ \textbf{let} $T_c$ be the subtree of $T$ rooted at $c$;\\
  \ \ \ \ \ \ Top-Down($T_c$);\\
  \ \ \ \textbf{end for}\\
  \textbf{end;}\\
  \end{tabular}\\
  \end{tabular}\\
  \end{tabular}
  }
  }
  \caption{Evaluation of an acyclic game.}\label{fig:algAciclico}
\end{figure}

%gianluigi: non gli e' piaciuto l'uso della semijion; che fare?
%francescofinal: Ho aggiunto una citazione a Maier nel precedente paragrafo.
%1. second paragraph after the proof, where join-tree algorithm is described. This paragraph is just too full of
%undefined technical terms and notation. Although they are quite standard and readable, this isn't the best
%style. It would be good to put a citation there for interested readers, where all of the definitions could be
%found, and a disclaimer of some sort for the rest.
The algorithm takes in input a join tree $JT$ of $\H(G)$. With a small abuse of notation, each vertex of $JT$,
which is formally a hyperedge $H_v$ associated with a player $v$, is also used to denote the player herself as
well as the Nash constraint $(S_v,r_v)$ associated with~$v$. The algorithm consists of two phases. In the first
bottom-up phase, the constraint relation $r_v$ of each node $v=(S_v,r_v)$ of $JT$ is filtered by means of a
semijoin with the constraint relation $r_c$ (denoted by $r_v \semijoin r_c$) of each of her children $c$ in
$JT$. This semijoin eliminates all tuples from $r_v$ corresponding to combined strategies of the players in $P'=
(\N(c)\cup\{c\})\cap (\N(v)\cup\{v\}))$ that are not available (or no longer available) in $r_c$.

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 and
hence $\G$ does not have equilibria, or the tuples remaining in the root $p$ encode the
strategies that $p$ may choose in Nash equilibria of the game. In the top-down phase, this
property of the root is propagated down the tree by taking the semi-join of every vertex
with all its children. At the end, we get a tree such that all tuples encode strategies
belonging to Nash equilibria and, vice versa, all Nash equilibria are made from strategies
in the relations stored in $JT$. Then, by standard techniques developed for acyclic database
queries and CSPs, we can compute from $JT$ all Nash equilibria of $\G$ in a backtrack-free
way, and thus in time polynomial in the combined size of the input game and of the
equilibria in output. Note that this is the best we can do, as a game may have an
exponential number of equilibria.

%ggc
%gianluigi: dobbiamo? e' praticamente identico a top-down; ho per cui aggiungo solo due righe.
%francescofinal: Fatto.
%1. For completeness sake, pseudo-code for "Select-equilibrium" procedure should be included as well.
%
%todo
\begin{figure}[t]
  \centering
  \fbox{
  \parbox{0.63\textwidth}{\scriptsize
  \begin{tabular}{l}\\
  \textbf{Procedure} Select-equilibrium(var\ $T:$ tree)\\
  \textbf{begin}\\
  \ \ \ \textbf{let} $v=(S_v,r_v)$ be the root of $T$;\\
  \ \ \ \textbf{select} any combined strategy $t_v\in r_v$ s.t. $\forall t_v'\in r_v$, $u_v(t_v')\leq u_v(t_v)$;\\
  \ \ \ \textbf{delete} all tuples in $r_v$, but $t_v$;\\
  \ \ \ \textbf{for each} $c=(S_c,r_c)$ \textbf{child} of $v$ \textbf{do}\\
  \ \ \ \ \ \ $r_c:=r_c  \semijoin r_v$;\\
  \ \ \ \ \ \ \textbf{let} $T_c$ be the subtree of $T$ rooted at $c$;\\
  \ \ \ \ \ \ Select-equilibrium($T_c$);\\
  \ \ \ \textbf{end for}\\
  \textbf{end;}\\
  \end{tabular}\\
  }
  }
  \caption{Selection of a (Pareto) Nash equilibrium of an acyclic game.}\label{fig:select}
\end{figure}



For completeness, Figure \ref{fig:select} shows Procedure \textit{Select-equilibrium}, that
selects from $JT$ one Nash equilibrium.
 It is very similar to Procedure \emph{Top-Down},
 but for the selection step before semi-joins: for any vertex,
\textit{Select-equilibrium} first picks a combined strategy $t_v\in r_v$, deletes all other
tuples in $r_v$, and then performs the semi-joins with its children and calls itself
recursively, to propagate the choice of $t_v$ towards the leaves of the tree.
 Note that the selection of $t_v$ may be arbitrary, after the previous bottom-up and
 top-down steps. However, in Figure \ref{fig:select} we select strategies giving the best
 payoffs, in order to get a Nash equilibrium that cannot be dominated by any other
 Nash equilibrium.


\begin{thm}\label{theo:acyclic-small-neighbors} Deciding the
existence of pure Nash equilibria, as well as computing a Nash equilibrium is feasible in polynomial time for
all classes $\C$ of acyclic-hypergraph games such that every game $\G\in\C$ has small neighborhood or is in
graphical normal form.
%Moreover, all pure Nash equilibria of such games can
%be computed in time polynomial in the combined size of input and
%output.
\end{thm}

    From the above discussion, it immediately follows that this tractability result can be extended to the problem
of computing a Pareto Nash equilibrium.

\begin{thm}\label{theo:pareto-acyclic} Deciding the existence
of Pareto Nash equilibria, as well as computing a Pareto Nash equilibrium for pure strategies is feasible in
polynomial time for all classes $\C$ of acyclic-hypergraph games such that every game $\G\in\C$ has small
neighborhood or is in graphical normal form.
\end{thm}
\begin{proof}
Recall that Procedure \textit{Select-equilibrium} in Figure \ref{fig:select}, at each vertex
$v$ encountered during the visit of $JT$, select a combined strategy that guarantees to
 the player corresponding to $v$ the maximum payoff over the available choices
 (that, at this point, are all and only those strategies that may lead to Nash equilibria).
 In particular, the payoff of the first
player to be evaluated, say the root $p$, cannot be worse than the payoff of $p$ in any
other available strategy. Thus, the tuples left in $JT$ after this procedure encode a Pareto
Nash equilibrium 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 $JT$ we cannot compute easily {\em all}
   Pareto Nash equilibria of the game in input-output polynomial time.\qed
\end{proof}


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 problem even in the case of acyclic interactions among
players. However, the complexity is reduced by one level with respect to the arbitrary interaction case, because
checking whether a given equilibrium is strong is feasible in polynomial time in the acyclic case.

\begin{figure}[t]
  \centering
  \fbox{
  \parbox{0.86\textwidth}{\scriptsize
  \begin{tabular}{l}
  \textbf{Function} InCoalition$_{\x,JT}$($H_p:$ vertex, $st$: combined strategy): \textbf{boolean}\\
  %\textbf{var} $N^+,K_p:$ set of players;\\
  \textbf{begin}\\
  \ \ \ \textbf{let} $(S_p,r_p)$ be the constraint associated with player $p$
                   and $N^+ = \{p\}\cup \N(p)$;\\
  \ \ \ \textbf{guess} a tuple $st'\in r_p$ such that $st'$ matches $st$ on the players they have in common;\\
  \ \ \ \textbf{if} $p$'s strategy in $st'$ is different from her strategy in $\x$
                                                                      \textbf{ and }
  $u_p(\x_{-N^+}[st'])\leq u_p(\x)$ \textbf{then}\\
  \ \ \ \ \ \ \             \textbf{ return false};\\
  \ \ \ \textbf{else}\\
  \ \ \ \ \ \ \ \textbf{let} $K_p$ be the set of children of $H_p$ in the join
  tree $JT$;\\
  \ \ \ \ \ \ \ \textbf{if} $K_p=\emptyset$ \textbf{then}\\
  \ \ \ \ \ \ \ \ \ \ \             \textbf{ return true};\\
  \ \ \ \ \ \ \ \textbf{else}\\
  \ \ \ \ \ \ \ \ \ \ \
   \textbf{return} $\bigwedge_{H_{p'}\in K_p}$ InCoalition$_{\x,JT}$($H_{p'}$,$st'$);\\
  \ \ \ \textbf{end if}\\
  \textbf{end.}\\
  \end{tabular}
  }}  \caption{Algorithm for deciding the existence of a coalition improving $\x$.}\label{fig:InCoalition}
\end{figure}

\begin{lem}\label{lemStrongNP} Let $\G$ be an acyclic-hypergraph game that has small
neighborhood or is in graphical normal form, and let $\x$ be a global strategy. Then, deciding whether $\x\in
\SNE(\G)$ is feasible in polynomial time.
\end{lem}
\begin{proof}
Since $\G$ has small neighborhood or is in graphical normal form, from Theorem \ref{thm:CostruisciCSP} 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 $JT$ for deciding
in polynomial time whether the strategy $\x$ is not in $\SNE(\G)$, i.e., that there exists a coalition $C$ of
players getting an incentive to deviate all together from $\x$. Then, the result follows because $\Pol$ is
closed under complementation. Specifically, we next show an implementation of this task by an alternating Turing
machine $M$ with a logarithmic-space working tape. Therefore, the problem is in $\rm ALOGSPACE$, which is equal
to $\Pol$ \cite{CKS81}.

The machine $M$ for deciding whether $\x$ is not a strong Nash equilibrium works as follows:
\begin{itemize}
  \item guess a player $q$;
  \item guess a strategy $st_q$ for $q$ that is different from her
  choice in $\x$;
  \item root the tree $JT$ at the vertex corresponding to the characteristic edge
  $H_q$ of player~$q$;
  \item check that \emph{InCoalition}$_{\x,JT}(H_q,st_q)$ returns
  true, where \emph{InCoalition}$_{\x,JT}$ is the Boolean function
  shown in Figure \ref{fig:InCoalition}.
\end{itemize}

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 some of her neighbors $K_q$ deviate from $\x$ and hence
belong to $C$. However, in this case, all players in $K_q$ should be able to improve their payoffs. Again, to do
that, they can involve other players in the coalition, and so on.

Whether or not this process is successful is checked by the recursive Boolean function
\emph{InCoalition}$_{\x,JT}$, which takes in input a vertex $H_p$ of the join tree $JT$ and a combined strategy
$st$. Recall that each vertex of the join tree is an (hyper)edge of the hypergraph, corresponding to a player of
$\G$. In particular, $H_p$ is the characteristic edge of player $p$. \emph{InCoalition}$_{\x,JT}$ has to check
whether all players deviating from the given global strategy $\x$ are able to improve their payoffs. At the
first call of this function, the first parameter $H_q$ is the root of $JT$ and identifies the first player $q$
chosen for the coalition $C$. The second parameter $st$ is the strategy chosen by $q$, which is different from
$q$'s corresponding choice in $\x$. At a generic recursive call, the first parameter $H_p$ identifies a player
$p$ to be checked, and the second parameter $st$ encodes a combined strategy for the player $w$ associated with
the parent $H_{w}$ of $H_p$ in $JT$ and for $w$'s neighbors. Now, the function has to check that either $p$ does
not change her choice with respect to $\x$, or she changes and improves her payoff. To this end, the function
guesses a tuple $st'\in r_p$, where $r_p$ is the constraint relation associated with $p$. Then, $st'$ encodes a
combined strategy for $p$ and her neighbors. This strategy has to match the parameter $st$ on the players they
have in common, because $st$ contains the actions already chosen by the algorithm when the parent $H_w$ of $H_p$
has been evaluated. Then, if $p$'s choice in $st'$ is different from $p$'s choice in $\x$, it means that $p$ has
been non-deterministically chosen as a member of the coalition $C$. Thus, $p$ should improve her payoff, or she
immediately causes the fail of this computation branch of the nondeterministic Turing machine. Otherwise, that
is, if $p$ plays the same action as in $\x$, then she does not belong to $C$ and the function has to check,
recursively, that in the rest of the join tree all deviating players improve their payoffs. This is done by
propagating the current combined strategy $st'$ to the children of $H_p$ in $JT$. Observe that this propagation
is necessary even if $p$ does not  belong to $C$, because connected coalitions do not necessarily induce
connected subtrees in $JT$.  Indeed, it may happen that some player $z$ belonging to the coalition is a neighbor
of both $p$ and $w$, but her characteristic edge $H_z$ occurs far from $H_w$ in the join tree, possibly in the
subtree of $JT$ rooted at $p$. (For the sake of completeness, note that in this case $z$ should be a neighbor of
all players occurring in the path from $H_z$ to $H_w$ in $JT$, from the connectedness property of join trees.)

Finally, let us consider briefly the low-level implementation of the alternating Turing machine $M$. Existential
states correspond to guesses, while universal states correspond to the recursive calls to
\emph{InCoalition}$_{\x,JT}$, plus some further machinery for auxiliary computations. At each step, we have to
encode on the worktape the two parameters $p$ and $st$ and the local variables, while $\x$, $JT$, the game $\G$
and the pre-computed constraint relations are on the input tape. Note that $p$ may be encoded by the logspace
pointer to her position in the input tape, as well as any combined strategy $st_w$ may be encoded by a logspace
pointer to its corresponding entry in the constraint relation associated with $w$. Similar considerations apply
to the other local variables, e.g., the guessed combined strategy $st'$. Moreover, it is easy 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 $\Pol$. \cite<For a detailed description of such logspace ATM computations, we refer
the interested reader to>{gott-etal-01,GLSTCS}. \qed
\end{proof}

\begin{thm}\label{thmStrongNP} Let $\G$ be an acyclic-hypergraph game that has small
neighborhood or is in graphical normal form. Then, deciding whether $\G$ has strong Nash equilibria, i.e.,
$\SNE(\G)\neq\emptyset$ is $\NP$-complete. Hardness holds even if $\G$ is in graphical normal form and has
$3$-bounded neighborhood.
\end{thm}

\begin{proof}
{\em Membership.} Given the game $\G$, we can guess a global strategy $\x$ and verify in polynomial time, by
Lemma~\ref{lemStrongNP}, that $\x$ is in fact a strong Nash equilibrium.

{\em Hardness.} The reduction is from SAT. Consider a Boolean formula in conjunctive normal form $\Phi=c_1\wedge
\ldots \wedge c_m$ over variables $X_1,\ldots,X_n$ and assume, w.l.o.g, that $m=2^\ell$, for some $\ell >0$.
 As a running example, consider the formula
 $\Phi_s= (X_1\vee X_2)\wedge (X_1\vee X_3)\wedge
(X_1\vee \neg X_4 \vee X_8)\wedge (X_4) \wedge (\neg X_5 \vee \neg X_6)\wedge (X_1 \vee X_4 \vee X_6)\wedge (X_6
\vee X_7)\wedge (X_8)$.

% In fact, for the latter assumption, if $m$ is such that
%$2^{l-1}<m<2^l$, then we can construct in polynomial time a new
%Boolean formula $\Phi'$ by adding $2^l-m$ new clauses, each one
%containing a fresh variable. Obviously, such clause can be
%trivially satisfied, and hence $\Phi$ and $\Phi'$ are equivalent.

    From $\Phi$, we build the following GNF game $\G(\Phi)$. The players are partitioned in two sets $P_c$ and
$P_t$. The set $P_c$ contains exactly one player for each clause of $\Phi$, while players in $P_t$ are such that
$\DG(\G)$ is a complete binary tree, whose leaves are the players in $P_c$, as shown in Figure
\ref{fig:easyStrong} for $\Phi_s$.

\begin{figure}[t]
    \centering
    \includegraphics[width=0.98\textwidth]{easyStrong.eps}
    \caption{On the left: the dependency graph of the game $\G(\Phi_s)$. On the right:
    a coalition witnessing that $c_5$ and $c_7$ are playing in a conflicting way.}\label{fig:easyStrong}
\end{figure}

Players in $\G(\Phi)$ play actions corresponding to variables in $\Phi$ plus some further special actions.
 Intuitively, each player $c\in P_c$ may play a literal occurring in
 the clause she represents, while players in $P_t$ have to check
 that no pair of players $c_i,c_j\in P_c$
plays in a conflicting
 way, that is, plays complementary literals. To this end, the game
   rules are designed in such a way that players in $P_t$ may
   improve their payoffs if they are able to form a coalition
   proving that some pair of players are playing complementary
   literals. It is worthwhile 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 \ref{fig:easyStrong}, $c_5$ and $c_7$
   play $\bar{x_6}$ and $x_6$, respectively, which is detected by a
   coalition involving their lowest common ancestor, say $p$, and the
   players of $P_t$ occurring in the two paths from $c_5$ and $c_7$ to $p$.
   We show that a global strategy is a strong Nash equilibrium of
   this game if and only if there is no such a disproving coalition.
   Indeed, in this case, there are no conflicting clauses and thus
   the formula $\Phi$ is satisfiable by setting to true all literals
   played by the clause players.

Formally, each player $c\in P_c$ may play either a special action $B$ (read: bad) or an action $x_i$ (resp.
$\bar{x_i}$) called literal action, provided that $X_i$ is a variable occurring positively (resp. negatively) in
the corresponding clause of $\Phi$. Each player $t\in P_t$ may play an action in $\{v_i, w_i,\bar{w_i} \mid X_i
\mbox{ is a variable in } \Phi \}\cup \{T\}$, where $T$ can be read as ``okay with me!"

We next describe the utility functions, given any global strategy $\x$.

A player $c\in P_c$ 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$ \textbf{(C-i)}; otherwise, she gets payoff 0
\textbf{(C-ii)}.

%gianluigi: ha ragione; avevamo scritto cosi' perche' nel testo parlavamo di parent; ma basta specificare che
%           il parent se esiste devo giocare in un certo modo; poi la prova diventa ok.
%3. In rules T-i, T-ii, and T-iii, you have the condition "if t \neq root". This is unmotivated, and also makes
%the proof at the top of page 32 wrong.
 For a player $t\in P_t$, the utility function $u_t$ is such that:
\begin{description}
\bvs\item[(T-i)] $u_{t}(\x)=2$ if $t$ plays $w_i$, her parent (if any) plays $w_i$ or $v_i$, none of her
children plays $B$, and one of her children plays either $w_i$ or $x_i$ (depending on whether she is a leaf or
not);

\bvs\item[(T-ii)] $u_{t}(\x)=2$ if $t$ plays $\bar{w_i}$, her parent (if any) plays $\bar{w_i}$ or $v_i$, none
of her children plays $B$, and one of her children plays either $\bar{w_i}$ or $\bar{x_i}$;

\bvs\item[(T-iii)] $u_{t}(\x)=2$ if $t$ plays $v_i$, her parent (if any) plays $T$, and her children play either
$x_i$ and $\bar{x_i}$ or $w_i$ and $\bar{w_i}$;

\bvs\item[(T-iv)] $u_{t}(\x)=1$ if $t$ plays $T$;

\bvs\item[(T-v)] $u_{t}(\x)=0$ in all the other cases.
\end{description}

Then, $\G(\Phi)$ has the following properties.
\begin{description}
\item[$P_1:$] {\em Let $\x$ be a global strategy for $\G(\Phi)$. Then, $\x$ is a Nash equilibrium if and only if
all players in $P_t$ play $T$ in $\x$ and there is no player in $P_c$ playing $B$.}

If players in $P_t$ play $T$ and players in $P_c$ do not play $B$, then they get payoff 1 due to rules (T-iv)
and (C-i). In this case, no player has an incentive to deviate, since by changing 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, by contradiction, that there is
a player $c\in P_c$ choosing $B$. From (C-i) and (C-ii), it 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 player in $P_t$
that does not play $T$, and let $t\in P_t$ be a player at the lowest possible level of the 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 get payoff $0$ (T-V) and could improve to $1$ by playing $T$.
Therefore, $\N(t)\cap P_c\neq \emptyset$. Then, the only way for $t$ to get payoff greater than $0$ comes from
rule (T-iii), which means that her clause children play in a conflicting way, say $x_i$ and $\bar{x_i}$.
However, since $t$ does not play $T$, they both get payoff $0$ and thus could deviate from $\x$ by playing $B$
and getting payoff $1$. Contradiction.

\item[$P_2:$] {\em Let $\x$ be a Nash equilibrium for $\G(\Phi)$. 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 conflicting
way.}

(If part.) Since $\x$ is a Nash equilibrium, from Property $P_1$, all players in $P_t$ play $T$ and get payoff
$1$. If there are two clauses, say $c_1$ and $c_2$, playing $x_i$ and $\bar{x_i}$, respectively, we may identify
an improving coalition as follows: let $t$ be first common ancestor of $c_1$ and $c_2$, and let $P_1$ and $P_2$
be the sets of vertices (players) occurring in the paths from $t$ to $c_1$ and $c_2$, respectively. Then, let
$t$ change to $v_i$, and all the players in $P_1$ (resp. $P_2$) change to $w_i$ (resp. $\bar{w_i}$) in $\x$ --
see Figure \ref{fig:easyStrong}. Then, from the game rules above, all players in the coalition $K=P_1\cup P_2
\cup \{t\}$ get payoff 2, improving the payoff $1$ that they get in $\x$.

(Only-if part.) Let $K$ be a coalition of players improving the Nash equilibrium $\x$. From property $P_1$, all
players in $P_t\cap K$ should get payoff 2, as they get $1$ in $\x$. Let $t\in K$ by the player in $P_t$ at the
highest (close to the root) level in the tree, i.e., such that $parent(t)$, if any, does not belong to $K$. From
(T-iii), the children of $t$ must play either $x_i$ and $\bar{x_i}$ or $w_i$ and $\bar{w_i}$, depending on
whether they are or are not leaves of the tree. In the former case, we have identified two conflicting players
and thus the property is immediately proved. Hence, let us investigate the latter one. Let $t'$ and $t''$ be the
children of $t$ playing $w_i$ and $\bar{w_i}$, 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'$ must play $w_i$ and a child of
$t''$ must play $\bar{w_i}$, 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 $x_i$ and a leaf descendant
of $t''$ plays $\bar{x_i}$, qed.
\end{description}

\noindent The NP hardness of deciding the existence of a SNE follows from the following claim: \ \ $\Phi$ is
satisfiable \,$\Leftrightarrow$\, $\G(\Phi)$ admits a strong Nash equilibrium.

($\Rightarrow$) Assume $\Phi$ is satisfiable and take a satisfying assignment $\sigma$. Let $\x^\sigma$ be a
global strategy such that: each player $c\in P_c$ plays any literal occurring in the clause $c$ that is true
with respect to $\sigma$; and each player $t\in P_t$ plays $T$. From $P_1$, $\x^\sigma$ is a Nash equilibrium
for $\G(\Phi)$. Moreover, by construction no pair of players choose conflicting actions in $\x^\sigma$. Hence,
due to $P_2$, there exists no coalition of players getting an incentive by deviating from $\x^\sigma$, and thus
$\x^\sigma$ is strong. ($\Leftarrow$) Let $\x$ be a strong Nash equilibrium for $\G(\Phi)$. Then, there is no
coalition of players getting an incentive to deviate from $\x$. Due to $P_1$, no player in $P_c$ plays $B$, and
due to $P_2$ no pair of players play in a conflicting way. Hence, $\sigma^\x$ witnesses that $\Phi$ is
satisfiable. More precisely, it encodes an implicant of $\Phi$, that can be extended to a satisfying assignment
choosing any truth value for all Boolean variables occurring in $\Phi$ not chosen by any player in $\x$. \qed
\end{proof}

\section{Further Structurally Tractable Classes of Games}\label{sec:hypertree}

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. In this section, we prove that even more general and
structurally complicated classes of games can be dealt with in an efficient way. We consider the notions of {\em
treewidth} \cite{robe-seym-86} and {\em hypertree width} \cite{gott-etal-02}, which are the broadest known
generalizations of graph and hypergraph acyclicity, respectively \cite{GLS99b}. We show that tractability
results for acyclic games hold for these generalizations, too, and study the relationship between the two
notions.


\subsection{Hypertree Decompositions of Games}\label{sec:hypertreedef}

Let $\HG=(V,E)$ be a hypergraph. Denote by ${\it vert}(\HG)$ and ${\it edges}(\HG)$ the sets $V$ and $E$,
respectively. Moreover, for any set of edges $E'\subseteq {\it edges(\HG)}$, let ${\it vert}(E')=\bigcup_{h\in
E'} h$.

A {\em hypertree for a hypergraph $\HG$} is a triple $\tuple{T,\chi,\lambda}$, where $T=(N,E)$ is
a rooted tree, and $\chi$ and $\lambda$ are labeling functions which associate with each vertex
$p\in N$ two sets $\chi(p)\subseteq {\it vert}(\HG)$ and $\lambda(p)\subseteq edges(\HG)$.  If
$T'=(N',E')$ is a subtree of $T$, we define $\chi(T')= \bigcup_{v\in N'} \chi(v)$.
%Similarly, $\lambda(T')= \bigcup_{v\in N'} \lambda(v)$.
We denote
%the set of vertices $N$ of $T$ by $vertices(T)$, and
the root of $T$ by $root(T)$.  Moreover, for any $p\in N$, $T_p$ denotes the subtree of $T$ rooted at $p$.

\begin{defn}[Gottlob et al., 2002b\nop{\cite{gott-etal-02}}]\label{defn:hyper-decomp}\em A
{\em hypertree decomposition} of a hypergraph $\HG$ is a hypertree $\HD=\tuple{T,\chi,\lambda}$ for $\HG$, where
$T = (N,E)$, which satisfies all the following conditions:
\begin{enumerate}
\vspace{-0.2cm} \item for each edge $h\in edges(\HG)$, there exists $p\in N$
      such that $vert(h)\subseteq \chi(p)$ (we say that $p$
      {\em covers} $h$);
\item for each vertex $Y\in vert(\HG)$, the set $\{ p\in
  N \mid  Y \in \chi(p) \}$ induces a (connected) subtree of
 $T$;
\item for each $p\in N$, $\chi(p)\subseteq vert(\lambda(p))$; \item for each $p\in N$, $vert(\lambda(p)) \cap
\chi(T_p) \;\subseteq\; \chi(p)$.
\end{enumerate}
%Note that the inclusion in Condition~4 is actually an equality, because
%Condition~3 implies the reverse inclusion.
An edge $h\in edges(\HG)$ is {\em strongly covered} in $\HD$ if there exists $p\in N$ such that
$vert(h)\subseteq \chi(p)$ and $h\in \lambda(p)$. In this case, we say that $p$ strongly covers $h$.
%
A hypertree decomposition $\HD$ of hypergraph $\HG$ is a {\em complete decomposition} of $\HG$ if every edge of
$\HG$ is strongly covered in $\HD$.
%
The {\em width} of a hypertree decomposition $\tuple{T,\chi,\lambda}$ is $max_{p\in vertices(T)} |\lambda(p)|$.
The {\em hypertree width} $hw(\HG)$ of $\HG$ is the minimum width over all its hypertree decompositions.
%A $c$-width hypertree decomposition
%of $\HG$ is {\em optimal} if $c=hw(\HG)$.
\end{defn}

Note that for any constant $k$ checking whether a hypergraph has hypertree-width at most $k$ is feasible in
polynomial time \cite{gott-etal-02}.

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 hypertree decomposition 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 (hypergraph) acyclicity. In
particular, the class of acyclic-hypergraph games is precisely the class of games $\G$ whose hypergraph $\H(\G)$
has hypertree width 1.

\begin{exmp}\label{esempioPrimo}\em
Consider again the game $\rm FRIENDS$ in Example~\ref{esempio}. Figure~\ref{fig:friends-hyper} shows on the left
its associated hypergraph, and on the right a join tree for it. In fact, this join tree is a hypertree
decomposition of width 1 for the hypergraph, where, for each vertex $p$, $\lambda(p)$ is the set of hyperedges
reported in $p$ and $\chi(p)$ is the set of players occurring in these hyperedges.

For a more involved example, consider the extension $\rm FRIENDS'$ of $\rm FRIENDS$ where a new player
\emph{Laura} (short: $L$) joins the group. Laura would like to go with George to the cinema, and with Pauline
and Mary to the opera. Figure \ref{fig:friends-mod} shows on the left the hypergraph $\H(\makebox{\rm
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 2 shown on the right, in Figure \ref{fig:friends-mod}.
Here, for each vertex $p$ of the decomposition tree, the two sets denote its labels $\chi(p)$ and $\lambda(p)$,
respectively. \qed
\end{exmp}

\begin{figure}[t]
    \centering
    \includegraphics[width=0.9\textwidth]{FriendsMod.eps} \\
    \caption{$\H(\mbox{\rm FRIENDS'})$ and a hypertree decomposition for it.}\label{fig:friends-mod}
\end{figure}

A class of games $C$ is said to have bounded hypertree-width if there is a finite $k$ such that, for each game
$\G\in C$, $\G$ has $k$-bounded hypertree width. We next show that all the tractability results that hold for
acyclic-hypergraph games holds for bounded hypertree-width games, as well.

\begin{thm}\label{theo:small-neighbors} Deciding the
existence of pure Nash equilibria, as well as computing a Nash equilibrium is feasible in polynomial time for
all classes $\C$ of games having bounded hypertree-width and such that every game $\G\in\C$ has small
neighborhood or is in graphical normal form.
%Moreover, all pure Nash equilibria of such games can
%be computed in time polynomial in the combined size of input and
%output.
\end{thm}
\proof Let $\C$ be a class of games such that each game $\G\in \C$ has hypertree-width at most $k$, for some
$k>0$, and has small neighborhood or is in graphical normal form. Then, we can build the constraint satisfaction
problem $\CSP(\G)$ in polynomial time, by Theorem \ref{thm:CostruisciCSP}. Moreover, the hypertree width of $\G$
is at most $k$, and its hypergraph $\H(\G)$ is the same as the hypergraph $\H$ associated with $\CSP(\G)$. From
results by Gottlob et al.~\citeyear{gott-etal-01}, it follows that $\CSP(\G)$ can be solved in polynomial time,
which is equivalent to deciding the existence of Nash equilibria in polynomial time, by Theorem \ref{theo:CSP}.

Constructively, we can compute in polynomial time a hypertree decomposition of $\H$ having 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 decomposition tree), and finally solve this problem by using the
algorithm shown in Figure~\ref{fig:algAciclico}.~\qed

As for acyclic-hypergraph games, this result can be immediately extended to the problem of
computing a Pareto Nash equilibrium.

\begin{cor}\label{cor:pareto} Deciding the existence of Pareto Nash equilibria,
as well as computing a Pareto Nash equilibrium for pure strategies is feasible in polynomial time for all
classes $\C$ of games having bounded hypertree-width and such that every game $\G\in\C$ has small neighborhood
or is in graphical normal form.
\end{cor}
%gianluigi: ho aggiunto una prova intuitiva
%3. if generalizations are proven to be easy, why not just prove those?
%francescofinal: ho ritolto la prova.

\subsection{Treewidth and Hypertree Width of Games}\label{sec:hypertreeVStw}

We next consider the treewidth of game structures. Recall that any game may be represented either by the primal
graph or by the dual graph, as shown in Figure \ref{fig:friends-hyper} for the game FRIENDS. Therefore, a first
question is which graph is better as far as the identification of tractable classes of games is concerned. From
the results by Gottlob et al.~\citeyear{GLS99b}, we know that the notion of bounded treewidth for the primal
graph is generalized by the notion of bounded hypertree width, that is, looking at the hypertree width of the
game hypergraph we may identify wider classes of tractable games. Moreover, from the results by Greco and
Scarcello~\citeyear{GSijcai03}, it follows that looking at the treewidth of the dependency graph is better than
looking at the treewidth of the primal graph.\footnote{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 dependency graph.}

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 subject of this section:
\begin{enumerate}
\item Do tractability results for bounded treewidth for the primal graph extend to the wider class of games
having bounded treewidth for the dependency graph?

\item What is the relationship between bounded treewidth for the dependency graph and bounded hypertree width of
the game hypergraph?
\end{enumerate}

%polynomial time. After the results in the previous section, this is
%not very surprisingly. Moreover, similar results have been proved
%for bounded treewidth games in GNF in the mixed equilibria framework
%\cite{KLS01b}.

\begin{defn}[Robertson \& Seymour, 1986\nop{\cite{robe-seym-86}}]\em A {\em tree
decomposition}  of a graph $G=(V,E)$ is a pair $\tuple{T,\chi}$, where $T=(N,F)$ is a tree, and
$\chi$ is a labeling function assigning to each vertex $p\in N$ a set of vertices
$\chi(p)\subseteq V$, such that the following conditions are satisfied:
\begin{itemize}
\item[(1)] for each vertex $b$ of $G$, there exists $p\in N$ such that $b\in \chi(p)$;

\item[(2)]  for each edge  $\{b,d\}\in E$, there exists $p\in N$ such that $\{b,d\}\subseteq \chi(p)$;

\item[(3)] for  each vertex $b$ of $G$, the set $\{p\in N \mid  b\in  \chi(p)\}$ induces a connected subtree of $T$.
\nop{(Connectedness condition.)} %~\hfill~$\Box$
\end{itemize}
\end{defn}

Note that Condition 1 is subsumed by Condition 2 for graphs without isolated vertices. The {\em width} of the
tree decomposition $\tuple{T,\chi}$ is $\max_{p\in N}|\chi(p)-1|$. The {\em treewidth} of $G$ is the minimum
width over all its tree decompositions. This notion generalizes graph acyclicity, as the acyclic graphs are
precisely those graphs having treewidth 1. \footnote{Observe that the ``$-1$'' in the definition of treewidth
has been introduced in order to get this correspondence with acyclic graphs, as $2$ is the minimum cardinality
for the largest label in any tree decomposition.}

\begin{exmp}\em
Consider again the game $\rm FRIENDS'$ introduced in the Example~\ref{esempioPrimo}.
Figure~\ref{fig:friends-tree} shows on the left the cyclic dependency graph $\DG(\makebox{\rm FRIENDS'})$, and
on the right a tree decomposition of width 3 of this graph. \qed
\end{exmp}

\begin{figure}[t]
    \centering
    \includegraphics[width=0.8\textwidth]{FriendsTree.eps} \\
    \caption{$\DG(\mbox{\rm FRIENDS'})$ and a tree decomposition for it.}\label{fig:friends-tree}
\end{figure}

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 $\DG(\G)$ is at most $k$. Recall that, given a graph $\DG$, computing a
tree-decomposition of width at most $k$ of $\DG$ (if any) is feasible in polynomial (actually, linear) time
\cite{bodl-97}.

%ggc
%gianluigi: ho aggiunto una frase
%2. Does theorem 5.7 use any game-theoretic property or is it a purely graph-theoretic result?
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 treewidth has bounded hypertree width, too. We remark
that the previous results on the relationship between treewidth and hypertree width described in the literature
\cite<e.g.>{GLS99b} cannot be used here. Indeed, they deal with the primal graph and the dual graph
representations, while we are now interested in the dependency graph, which is more effective than 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~\citeyear{GSijcai03}.


\begin{thm}\label{theo:twVShw}
For each game $\G$, ${\it hypertreewidth}(\H(\G))\leq {\it treewidth}(\DG(\G))+1$.
\end{thm}
\begin{proof} Let $\TD$ be a tree decomposition of $\DG(\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 a hypertree decomposition of $\H(\G)$ having width $k$. Recall that $\H(\G)$ contains, for each player $p$,
the characteristic edge $\H(p)= \{p\} \cup \N(p)$. Let $\HD=\tuple{T,\chi,\lambda}$ be a hypertree such that:
\begin{itemize}
\item the tree $T$ has the same form as the decomposition tree $\TD$, i.e., there is a tree isomorphism $\delta:
vert(T)\longrightarrow vert(TD)$ between $T$ and  $\TD$;

%gianluigi: non mi e' chiaro a cosa si riferisca poiche' nel 2nd paragrafo a pag. 37 non c'e' la frase in question
%           \lambda(v) entra solo qui sotto, e mi sembra che sia corretto
%3. p.37 2nd paragraph: I think you want to say "\lambda(v) contains a hyperedge containing a player"
\item for each vertex $v\in T$, $\lambda(v)=\{ \H(p) \mid p\in \delta(v) \}$, i.e., $\lambda(v)$ contains the
characteristic edge of each player occurring in the vertex of the tree decomposition corresponding to $v$;

\item $\chi(v)$ is the set of all vertices occurring in the edges in $\lambda(v)$, i.e., contains all players in
$\delta(v)$ and their neighbors.
\end{itemize}

%Figure \ref{fig:RiduzioneTree} shows such reduction applied to the
%FRIENDS games presented in the previous section; in particular, we
%reported the graph $\DG(\mathit{FRIENDS})$, a tree decomposition
%$\TD$ and the generated hypertree decomposition $\HD$.

%\begin{figure}[t]
%    \centering
%    \includegraphics[width=0.9\textwidth]{RidTree.eps}
%    \caption{Construction of the hypertree decomposition in Theorem \ref{theo:twVShw}, for FRIENDS.}\label{fig:RiduzioneTree}
%\end{figure}
%
Note that the width of $\HD$ is $k$, as it is determined by the largest $\lambda$ 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
\ref{defn:hyper-decomp}: Conditions 3 and 4 are trivially satisfied because, for each vertex $v$, $\chi(v) =
vert(\lambda(v))$, by construction. Condition 1 is guaranteed by the fact that $\TD$ satisfies its corresponding
Conditions 1 and 2. We next show that Condition 2, i.e., the connectedness condition, holds, too.

%In the following, for the sake of exposition, given two nodes $a$ and $b$ of
%$TD$, we denote by $\pi(a,b)$ the set of vertices of $T$ occurring on the
%unique path connecting $a$ and $b$.

Let $v_1$ and $v_2$ be two vertices of $T$ such that there exists $p\in \chi(v_1)\cap \chi(v_2)$. Let
$v'_1=\delta(v_1)$ and $v'_2=\delta(v_2)$ be the sets of vertices in the tree decomposition $\TD$ corresponding
to $v_1$ and $v_2$, respectively. Since $p \in\chi(v_1)$ and $p \in \chi(v_2)$, there are two players $p_1$ and
$p_2$ such that (i) $\H(p_1)\in \lambda(v_1)$ and $p\in \H(p_1)$, and (ii) $\H(p_2)\in \lambda(v_2)$ and $p\in
\H(p_2)$. Then, by construction, $p_1\in v'_1$ and $p_2\in v'_2$ (see Figure \ref{fig:TDvsHD}).

We claim that, for each vertex $v$ in the unique path connecting $v_1$ and $v_2$ in $T$ (denoted by $v_1
\leftrightsquigarrow v_2$), $\lambda(v)$ contains a player from the set $\{p_1,p_2,p\}$, which entails that
$p\in \chi(v)$ and hence that Condition 2 is satisfied by $\HD$. This is equivalent to claim, on the tree
decomposition $\TD$, that each vertex $v'$ in the path $v_1'\leftrightsquigarrow v_2'$ contains a player in
$\{p_1,p_2,p\}$.

\begin{figure}[t]
    \centering
    \includegraphics[width=0.95\textwidth]{TDvsHD-bis.eps}
    \vspace{-4mm}\caption{Schema of the reduction in the proof of Theorem \ref{theo:twVShw}.}\label{fig:TDvsHD}\vspace{-2mm}
\end{figure}

If both $v_1'$ and $v_2'$ contain $p$, then the claim trivially holds because all the vertices in the path $v'_1
\leftrightsquigarrow v'_2$ must contain $p$, from Condition 3 of tree decompositions (the connectedness
condition).

Hence, let us assume that $v'_1$ does not contain $p$. Since $p\in H(p_1)$, this means that $p$ is a neighbor of
$p_1$ and thus there exists a vertex of $\TD$, say $v'_3\neq v'_1$,  whose labeling contains both $p$ and $p_1$.
Assume now that $v'_2$ contains $p$. Figure \ref{fig:TDvsHD}.1 shows the path comprising vertices $v'_1$,
$v'_3$, and $v'_2$ --- notice that $v'_1$ cannot be in the path $v'_3\leftrightsquigarrow v'_2$, otherwise it
should contain $p$ as well. The result follows by observing that, again from Condition 3 of tree decompositions,
all vertices in the path $v'_1 \leftrightsquigarrow v'_3$ must contain $p_1$, and all vertices in the path
$v'_3\leftrightsquigarrow v'_2$ must contain $p$. Similarly, assume that $v_2'$ does not contain $p$. In this
case, since $p$ is a neighbor of $p_2$ (recall the above discussion for $p_1$), there is a vertex $v'_4$ in
$\TD$ whose labeling contains both $p_2$ and $p$.  Figure \ref{fig:TDvsHD}.2 shows how these vertices should
look like in the tree decomposition $\TD$. Then, the result follows by observing that all vertices in the path
$v'_1 \leftrightsquigarrow v'_3$ contains $p_1$, all vertices in the path $v'_3 \leftrightsquigarrow v'_4$
contains $p$, and all vertices in the path $v'_4 \leftrightsquigarrow v'_2$ contains $p_2$. \qed
\end{proof}

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 hypertree width of
the game hypergraph is more effective than the corresponding technique based on the treewidth of
the dependency graph, because it allows us to identify strictly broader classes of tractable
games.


\begin{thm}\label{theo:twVShwStrict} There are classes $C$ of
games having hypertree width 1 but unbounded treewidth, i.e., such that, for any finite $k>0$, there is a game
$\G\in C$ such that the treewidth of $G$ is not bounded by $k$.
\end{thm}
\proof  Take the class of all games where every player depends on all other players. For every such game $\G$,
$\H(\G)$ is acyclic and thus its hypertree width is 1, while $\DG(\G)$ is a clique containing all players and
its treewidth is the number of players minus 1. \qed


    From Theorem \ref{theo:small-neighbors}, Corollary \ref{cor:pareto}, and Theorem \ref{theo:twVShw}, we immediately get
the following tractability results for bounded treewidth games.


\begin{cor}\label{cor:treewidth}
Deciding the existence of pure (Pareto) Nash equilibria, as well as computing a pure (Pareto) Nash equilibrium
is feasible in polynomial time for all classes $\C$ of games having bounded treewidth and such that every game
$\G\in\C$ has small neighborhood or is in graphical normal form. Moreover, all Nash equilibria of such games can
be computed in time polynomial in the combined size of input and output.
\end{cor}


\section{Parallel Complexity of Easy Games}\label{sec:parallel}

%ggc
%gianluigi
%francescofinal: Ho aggiunto i preliminari su LOGCFL
%3. Section 6 is not as well written as the rest of the paper. The sentence "LOGCFL coincides with the class
%SAC^1 of problems solvable by logspace-uniform families of semi-unbounded AC_1 Boolean circuits (SAC^1 circuits)
%of depth O(log n)" is very hard to understand. What does logspace-uniform mean? What do you mean by a
%log-uniform family? How does a family solve a problem, rather than an individual circuit?
%
%In the proof, why do you assume that a family of circuits rather than an individual circuit is given? You talk
%about computing the "appropriate circuit". What is the appropriate circuit?
%
%p.40 3 lines from bottom: SKEL(G',w) has not been defined
%
%p.41 line 3: G' has not been defined

In this section, we show that dealing with Nash equilibria for games with good structural properties is not only
tractable but also parallelizable. More precisely, we show that deciding the existence of Nash equilibria for
graphical games where the player interactions has a low degree of cyclicity is complete for the class $\LCFL$.
Also, we show that computing such an equilibrium belongs to the functional version of $\LCFL$.

The complexity class \LCFL\ consists of all decision problems that are logspace reducible to a context-free
language.
%
%We have: $\AC{0}\subseteq \NC{1}\subseteq \DL \subseteq \NL \subseteq
%\LCFL\subseteq\AC{1}\subseteq\NC{2}\subseteq \Pol$ \cite{john-90,papa-94}.
%Therefore, all problems
%in $\LCFL$ are highly parallelizable.
%
In order to prove the following theorem, we exploit a characterization of $\LCFL$ in terms of
circuits.
%result by \cite{venka}, stating that $\LCFL$ coincides with the class $\SAC$ of problems
%solvable by logspace-uniform families of semi-unbounded $\AC{1}$ Boolean circuits ($\SAC$
%circuits) of depth $O(\log n)$. In such circuits the OR gates have unbounded fan-in while all AND
%gates have fan-in $\leq$ 2, and $\neg$-gates are at the bottom level only.

We recall that a {\em Boolean circuit} $G_n$ with $n$ inputs is a finite directed acyclic graph
whose nodes are called {\em gates} and are labeled as follows. Gates of fan-in (indegree) zero are
called {\em circuit input gates} and are labeled from the set $\{ \mbox{\em false}, \mbox{\em
true}, z_1,$ $z_2, \ldots, z_n, \neg z_1, \neg z_2, \ldots, \neg z_n \}$. All other gates are
labeled either AND, OR, or NOT. The fan-in of gates labeled NOT must be one. The unique node with
fan-out (outdegree) zero is called {\em output gate}. The evaluation of $G_n$ on input string $w$
of length $n$ is defined in the standard way. In particular, any input gate $g$ labeled by $z_i$
(resp. $\neg z_i$) gets value {\em true} (resp. {\em false}) if the $i$th bit of $w$ is 1 (resp.
0); otherwise, $g$ gets value {\em false} (resp. {\em true}).

A Boolean circuit is thus given as a triple
%fnew: Ho cambiato V con N, E con A ed edges con arcs nel testo.
$(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 {\em 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 (including
input-gates) in $G$.

A family $\cal G$ of Boolean circuits is a sequence
%fnew: Ho inserito G_0
$(G_0,G_1,G_2,\dots)$, where the $n$th circuit $G_n$ has $n$ inputs. Such a family is {\em
logspace-uniform} if there exists a logspace Turing machine which,
%fnew: La seguente frase sostituisce: ``on input $1^n$'' che non funzionava
%      bene per n=0.
on the input string containing $n$ bits $1$, outputs the circuit $G_n$. Note that the size of the
$n$th circuit $G_n$ of a logspace-uniform family $\cal G$ is polynomial in $n$. Intuitively, this
uniformity condition is crucial in characterizations of low parallel complexity classes in terms of
 circuits, because hidden inherent sequentialities in the circuit construction process must be avoided.
% we have to avoid
%it must be avoided that the machines that build
%$ the circuits have too much power
In fact, the cicuits which serve as parallel  devices
for evaluating input strings of length $n$, and which must be
constructed for each $n$ separately,
should be
constructible in parallel themselves. This is assured by
requiring logspace uniformity, because LOGSPACE is a
highly parallelizable complexity class contained in  LOGCFL.

The language $L$ accepted by a family $\cal G$  of circuits is defined as follows: $L=
\bigcup_{n\geq 0} L_n$, where $L_n$ is the set of input strings accepted by the $n$th member $G_n$
of the family. An input string $w$ of length $n$ is accepted by the circuit $G_n$ if $G_n$
evaluates to $true$ on input $w$.
%(i.e., when the $i$th gate of $G_n$ is labeled {\em true}
%(resp. {\em false}) if the $i$th bit of $w$ is $1$ (resp. $0$)).

A family $\cal G$ of Boolean circuits has {\em bounded fan-in} if there exists a constant $c$ such
that each gate of each member $G_n$ of $\cal G$ has its fan-in bounded by $c$.

A family $\cal G$ of Boolean circuits is {\em semi-unbounded} if the following two conditions are
met:
\begin{itemize}
\item All circuits of $\cal 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
\item there is  a constant $c$ such that each AND gate
of any member $G_n$ of $\cal G$ has its fan-in bounded by $c$ (the OR gates may have unbounded
fan-in).
\end{itemize}

For $i\geq 1$, $\AC{i}$ denotes the class of all languages recognized by logspace-uniform families
of Boolean circuits of depth $O(\log^i n)$.

For $i\geq 1$, $\NC{i}$ denotes the class of all languages recognized by logspace-uniform families
of Boolean circuits of depth $O(\log^i n)$ having bounded fan-in.

For $i\geq 1$, ${\rm SAC}^{i}$ denotes the class of all languages recognized by semi-unbounded
logspace-uniform families of Boolean circuits of depth $O(\log^i n)$.

Venkateswaran~\citeyear{venka} proved the following important relationship between $\LOGCFL$ and
the semi-unbounded circuits:
 $$\LCFL=\SAC.$$


Since $\LCFL=\SAC\subseteq \AC{1}\subseteq \NC{2}$, the problems in \LCFL\ are all highly
parallelizable. In fact, each problem in $\LCFL$ is solvable in logarithmic time by a
concurrent-read concurrent-write parallel random access machine (CRCW PRAM) with a polynomial
number of processors, or in $\log^2$-time by an exclusive-read exclusive-write PRAM (EREW PRAM)
with a polynomial number of processors~\cite{john-90}.


We next show that the evaluation problem of $\SAC$ circuits can be transformed in logspace into the considered
Nash equilibrium existence problems.

\begin{figure}[bh!]
    \centering
    \begin{tabular}{c}
        \includegraphics[width=\textwidth]{ABCsenzaL.eps} \\
    \end{tabular}
    \vspace{-3mm}\caption{(A) A normalized circuit, (B)its skeleton tree, (C) a labeling corresponding to a proof tree.}\label{fig:circuiti}
\end{figure}


\begin{thm}
\label{theo:logcfl} The existence problem for pure Nash equilibria is $\LCFL$-complete for 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.
\end{thm}

\proof It is sufficient to show membership for bounded hypertree width (the largest of the 4 classes) and
hardness for acyclic-graph games (the smallest one).

\emph{Membership}. The Nash equilibrium existence problem for NF games of bounded hypertree width is in $\LCFL$
because, as shown in Section~\ref{sec:easy}, this problem can be transformed in logspace into a CSP of bounded
hypertree width, and, as shown by Gottlob et al.~\citeyear{gott-etal-01}, checking satisfiability of the latter
is in $\LCFL$. (Recall that $\LCFL$ is closed under logspace reductions.)

\emph{Hardness}. We assume that a logspace-uniform family $\C=\{G_1,G_2,\ldots\}$ of $\SAC$ circuits is given,
and we prove that the problem of checking whether a binary string $w$ is accepted by $\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.~\citeyear{gott-etal-01}, this circuit can be transformed in logspace into an equivalent normalized circuit
$C'$ which is stratified and strictly alternating (see Figure \ref{fig:circuiti} (A)), and a tree-shaped proof
skeleton $SKEL$ (see Figure \ref{fig:circuiti} (B)) which encompasses the common structure of all possible {\em
proof trees} for $(C',w)$. A proof tree is a subtree of $C'$ of gates having value 1 witnessing that $C'$
accepts $w$. Each proof tree corresponds to an appropriate labeling of SKEL with gates from $C'$ (for example,
the labeling shown in Figure \ref{fig:circuiti} (C)). A labeling is correct if the root of SKEL is labeled with
the output gate of $C'$, each AND gate labeled $g$ has two children that are labeled with the input gates to
$g$, each OR node of SKEL labeled $g$ has one child labeled with some input gate to $g$, and each leaf of $T$ is
labeled with an input gate to $C'$ whose output to the next higher level is 1. $C'$ accepts $w$ if and only if
there exists a proof 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 $\alpha$ and $\beta$. The possible actions for the players in $V$ are pairs
$(g,t)$, where $g$ is a gate and $t$ is a truth value in $\{\true,\false\}$. The utilities for players in $V$
are given as follows.
\begin{enumerate}
\item 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 $\neg$ gate and corresponds to an input
bit $0$ of the string $w$, or $g$ is not a $\neg$ gate and corresponds to an input bit $1$ of $w$. Otherwise,
the utility of $u$ is $0$. \item Each non leaf vertex $p\in 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 $g'$ is a
child of the gate $g$ in $C'$, or $p$ is an AND vertex and the unique children  of $p$ in $SKEL$ take actions
$(g',\true)$, and $(g'',\true)$, respectively, where $g'$ and $g''$ are the children of the gate $g$ in $C'$.
\item Each non leaf vertex $p\in 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$ in $SKEL$ take actions $(g',t')$, and
$(g'',t'')$, respectively, where $g'$ and $g''$ are the children of $g$ in $C'$ and $t'\wedge t''=\false$. \item
In all other cases, all actions of a non leaf vertex $p\in V$ have utility $-1$.
\end{enumerate}

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$ of its
respective action $(g,t)$. In particular, the root node $r$ is forced to be labeled with the
output gate $g^*$ of $C'$, and the action played by $r$ is $(g^*, \true)$ if and only if the
particular labeling is a proof tree and $(g^*,\false)$ otherwise.

It remains to define the actions and utilities for the special players  $\alpha$ and $\beta$.
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 $\alpha$, and $\{head,tail\}$ for $\beta$. The strategies where $\alpha$
plays $ok$ have utility $1$ for $\alpha$ if the root vertex $r$ of $SKEL$ plays $(g^*,\true)$) and
utility $0$ otherwise. Strategies where $\alpha$ plays $head$ (resp., $tail$) have utility 1 for
$\alpha$ if $r$ plays $(g^*,\false)$ and if $\beta$ plays $tail$ (resp., $head$), and $0$
otherwise. Thus, in case $r$ plays $(g^*,\false)$, player $\alpha$ tries to play the opposite of
player $\beta$. The strategies where $\beta$ plays $head$ (resp., $tail$) have utility 1 for
player $\beta$ if $\alpha$ plays the same action, and 0 otherwise.

Therefore,  in case $C'$ outputs $0$ on input $w$, $r$ plays $(g^*,\false)$, and thus $\alpha$
tries to play opposite to $\beta$ while $\beta$ tries to mimic $\alpha$. This is a classical
non-equilibrium situation. In summary, each Nash equilibrium of $\G$ corresponds to a proof tree
for $(C',w)$. Note also that $\DG(\G)$ is acyclic, and that the construction of $\G$ from $(C',w)$
can be done in logspace.~\qed

Note that, by Definition~\ref{defn:NE}, a Pareto Nash equilibrium exists if and only if a Nash equilibrium
exists.

\begin{cor} The existence problem for pure Pareto Nash equilibria
is $\LCFL$-complete for 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.
\end{cor}

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.~\citeyear{GLSTCS}, stating that witnesses (i.e., proof trees) of
LOGCFL decision problems can be computed in functional LOGCFL (i.e., in logspace with an oracle in LOGCFL, or,
equivalently, by using $\SAC$ circuits.

\begin{cor}
For the classes of games mentioned in Theorem~\ref{theo:logcfl}, the computation of a single pure Nash
equilibria can be done in functional LOGCFL, and is therefore in the parallel complexity class $NC_2$.
\end{cor}

\section{Conclusion}\label{sec:conclusion}


In this paper we have determined the precise complexity of pure Nash equilibria in strategic games.
As depicted in Figure~\ref{fig:results}, our study proceeded along three directions:
 representation 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, or for 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 $\Pol=\NP$), if there is no 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
fresh game-theoretic view of the class $\SigmaP{2}$, as the class of  problems whose positive
instances are characterized by a coalition of players who cooperate to provide an equilibrium, and
win against any other disjoint coalition, which fails in trying to improve the utility for all of
its players.

 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 tractable problem. In particular, while early studies in game theory
 mainly focused on games with a small number of players (e.g., the traditional two-player framework),
  we are interested here in large population games, too.
 In such cases, adopting the standard normal form is clearly impractical as, for each
 player, one should
specify her payoffs for any combination of choices of all players in the game.
 We thus considered a different representation for these games, known in literature
 as {\em graphical games} \cite{KLS01b}, where the payoffs of each player $p$ are functions of $p$'s neighbors
 only, that is, $p$'s utility function depends only on those players $p$ is directly interested in.
 These relationships among players may be represented as a graph or, more faithfully, as a
 hypergraph.
 % This game representation is of central importance in this paper.
 We showed that, if utility functions are represented as tables (graphical normal
 form) and the game structure is acyclic or has a low degree of cyclicity (i.e., it
 has bounded hypertree width), then deciding the existence
 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 equilibria framework \cite<e.g.>{KLS01b,KM02}.
 Moreover, in the case of quasi-acyclic structures,
 we were also able to extend tractability to classes of games where utility functions
 are given implicitly (as in the general form), provided that
 each player has a 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 and game structures.
 It is worthwhile noting that these aspects of game theory have
 received a renewed deal of attention recently.
 For instance, see Papadimitriou \citeyear{P04} for a recent work on the complexity of pure Nash equilibria
 in some particular classes of games, and the various contributions on different kinds of
 concise game representations \cite<e.g.>{KM01,koller,KLS01b,LT03,GP04,KM02}.

 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, Alvarez et al.~\citeyear{serna-05} considered a further version of general form
 games, called games in {\em implicit form},
 where also payoff values are given in a succinct way. They showed
 that, for such games, the
 complexity of deciding the existence of pure Nash equilibria increases from the first level to the second
 level of the polynomial hierarchy.
  We point out that our general form is slightly different from the general form adopted in the
  above mentioned paper,
%gggg  and and  caveat! Simplex semper sigillum veri -- duplex sigillum falsi!
and some confusion may  arise by reading their citation of the results  presented in our TARK'03
paper (whose full version is the present paper).
 In their terminology, our Turing-machine encoding of
  payoff functions in general form games
should be classified as non-uniform,  with a uniform time-bound.
% (and not as {\em uniform}, as they classify it).
  %
However, apart from such subtle technical issues, some of their results
  on general form games with non implicit actions are very similar to ours,
  but their contributions focus on games with a large number of actions, while our
  hardness results hold even for games with a fixed number of actions
  and payoff levels. Moreover, while we show that hardness holds even for acyclic games,
  they did not consider any restriction on player interactions.
 Observe that their results may be immediately strengthened,
 given that from our proofs about GNF games with arbitrary player interactions
 it follows that $\NP$-hardness holds even for constant-time utility functions (as discussed in
  Remark~\ref{rem:constanttime}).

 Another line of research studies games where the computation of
 {\em any} Nash equilibrium is not satisfactory, and one is rather interested
 in equilibria that satisfy some additional requirements (e.g., the best social welfare).
 Greco and Scarcello~\citeyear{GSecai04} proved that deciding the existence of such pure Nash
 equilibria, called {\em constrained Nash equilibria}, is intractable even for very simple
 requirements. However, they were also able to identify some restrictions (for player
 interactions and requirements) making both the existence and the computation problems easy.
 Recent contributions on this subject (on both pure and mixed Nash equilibria) have been done by
 Schoenebeck at al.~\citeyear{SVECC05} and Greco and Scarcello~\citeyear{GSuai05}.

 Finally, we observe that there is an interesting connection among strong Nash equilibria
 and some equilibria
 studied in cooperative/coalitional game theory \cite<e.g.>{MWG95}.
 In this framework, for each subset $K$ of the players, we are given the utility that players
 in $K$ may get, if they cooperate together. % (\emph{characteristic form}).
 The {\em core} of a game is the set of profiles $\x$ such that there is no subset of players
 that may improve their utilities by forming their own coalition, deviating from $\x$
  \cite{G53}. Recently, Conitzer and Sandholm~\citeyear{conitzer2} proposed a concise representation for coalition utilities,
  and showed that determining whether the core of such a game is nonempty is $\NP$-hard.
 An interesting future work may concern a detailed study of the complexity of these
 coalitional games, possibly exploiting suitable notions of quasi-acyclic structures for
 identifying relevant tractable classes.


%ggc Delle cose seguenti non abbiamo tenuto conto
%gianluigi: seguono in nop altri commenti di natura generica
     \nop{ I see the whole paper as
     being predominantly about graphical games, and the paper
     should be presented as such (in the title, abstract
     etc.)
     Right now the paper is a little confusing in that
     very general claims are made such as "determining
     whether a pure Nash equilibrium exists is NP-hard"
     before anything is said about the underlying
     representation.
     This is especially confusing because
     this problem is obviously not hard in the standard
     normal form representation (whereas problems about mixed
     equilibria do become hard even in that representation).
     The authors themselves claim that, from their paper,
     computational questions appear harder for pure
     equilibria than for mixed; I strongly believe that
     generally, the opposite is true, and maybe the
     difference in representation is what is caused the
     confusion.

It would also be nice to discuss the techniques from the existing graphical games literature
and compare -- I see at least some superficial similarities.

I would use "profile" rather than "global strategy," "combined strategy"

can anything be said about the complexity of counting the number of equilibria (#P hard?)

}

\section*{Acknowledgments}

Part of this work has been published in preliminary form in the Proceedings of the 9th ACM Conference on
Theoretical Aspects of Rationality and Knowledge (TARK'03).

Georg Gottlob's work was supported by the Austrian Science Fund (FWF) under project
%{\em Nr.\ Z29-N04}  and
{\em Nr. P17222-N04 Complementary Approaches to Constraint Satisfaction}, and by the {\em GAMES Network  of
Excellence of the EU}.

We thank the anonymous referees and
 Tuomas Sandholm for their very useful comments.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\bibliography{biblio}
%\bibliographystyle{theapa}

\begin{thebibliography}{}

\bibitem[\protect\BCAY{Alvarez, Gabarro, \BBA\ Serna}{Alvarez et~al.}{2005}]{serna-05}
Alvarez, C., Gabarro, J., \BBA\ Serna, M. \BBOP2005\BBCP.
\newblock \BBOQ Pure Nash equilibria in games with a large number of actions\BBCQ\
\newblock {\Bem Electronic Colloquium on Computational Complexity}, {\Bem Report TR05-031}.

\bibitem[\protect\BCAY{Aumann}{Aumann}{1959}]{A59}
Aumann, R. \BBOP1959\BBCP.
\newblock \BBOQ Accetable points in general cooperative n-person games\BBCQ\
\newblock {\Bem Contribution to the Theory of Games}, {\Bem IV}.

\bibitem[\protect\BCAY{Aumann}{Aumann}{1985}]{A85}
Aumann, R. \BBOP1985\BBCP.
\newblock \BBOQ What is game theory trying to accomplish?\BBCQ\
\newblock {\Bem Frontiers of Economics}, 28--76.

\bibitem[\protect\BCAY{Beeri, Fagin, Maier, \BBA\ Yannakakis}{Beeri
  et~al.}{1983}]{beer-etal-83}
Beeri, C., Fagin, R., Maier, D., \BBA\ Yannakakis, M. \BBOP1983\BBCP.
\newblock \BBOQ On the desirability of acyclic database schemes\BBCQ\
\newblock {\Bem Journal of the ACM}, {\Bem 30(3)}, 479--513.

\bibitem[\protect\BCAY{Bodlaender}{Bodlaender}{1997}]{bodl-97}
Bodlaender, H. \BBOP1997\BBCP.
\newblock \BBOQ Treewidth: Algorithmic techniques and results\BBCQ\
\newblock In {\Bem Proc. of the 22nd International Symposium on Mathematical Foundations of Computer Science (MFCS'97)}, \BPGS\
19--36, Bratislava, Slovakia.

\bibitem[\protect\BCAY{Chandra, Kozen, \BBA\ Stockmeyer}{Chandra
  et~al.}{1981}]{CKS81}
Chandra, A., Kozen, D., \BBA\ Stockmeyer, L. \BBOP1981\BBCP.
\newblock \BBOQ Alternation\BBCQ\
\newblock {\Bem Journal of the ACM}, {\Bem 28(1)}, 114--133.

\bibitem[\protect\BCAY{Conitzer \BBA\ Sandholm}{Conitzer \BBA\
  Sandholm}{2003a}]{conitzer2}
Conitzer, V.\BBACOMMA\  \BBA\ Sandholm, T. \BBOP2003a\BBCP.
\newblock \BBOQ Complexity of determining nonemptiness of the core\BBCQ\
\newblock In {\Bem Proc. of the 18th International Joint Conference on
  Artificial Intelligence (IJCAI'03)}, \BPGS\ 613--618, Acapulco, Mexico.

\bibitem[\protect\BCAY{Conitzer \BBA\ Sandholm}{Conitzer \BBA\
  Sandholm}{2003b}]{conitzer}
Conitzer, V.\BBACOMMA\  \BBA\ Sandholm, T. \BBOP2003b\BBCP.
\newblock \BBOQ Complexity results about nash equilibria\BBCQ\
\newblock In {\Bem Proc. of the 18th International Joint Conference on
  Artificial Intelligence (IJCAI'03)}, \BPGS\ 765--771, Acapulco, Mexico.

\bibitem[\protect\BCAY{Deng, Papadimitriou, \BBA\ Safra}{Deng et~al.}{2002}]{DPS02}
Deng, X., Papadimitriou, C., \BBA\ Safra, S. \BBOP2002\BBCP.
\newblock \BBOQ On the complexity of equilibria\BBCQ\
\newblock In {\Bem Proc. of the 34th Annual ACM Symposium on Theory of
  Computing (STOC'02)}, \BPGS\ 67--71, Montreal, Canada.

\bibitem[\protect\BCAY{Downey \BBA\ Fellows}{Downey \BBA\
  Fellows}{1995}]{downey}
Downey, R.\BBACOMMA\  \BBA\ Fellows, M. \BBOP1995\BBCP.
\newblock \BBOQ Fixed-parameter tractability and completeness i: Basic
  results\BBCQ\
\newblock {\Bem SIAM Journal on Computing}, {\Bem 24(4)}, 873--921.

\bibitem[\protect\BCAY{Fabrikant, Papadimitriou, \BBA\ Talwar}{Fabrikant
  et~al.}{2004}]{P04}
Fabrikant, A., Papadimitriou, C., \BBA\ Talwar, K. \BBOP2004\BBCP.
\newblock \BBOQ The complexity of pure nash equilibria\BBCQ\
\newblock In {\Bem Proc. of the 36th Annual ACM Symposium on Theory of
  Computing (STOC'04)}, \BPGS\ 604--612, Chicago, IL, USA.

\bibitem[\protect\BCAY{Fagin}{Fagin}{1983}]{fagi-83}
Fagin, R. \BBOP1983\BBCP.
\newblock \BBOQ Degrees of acyclicity for hypergraphs and relational database
  schemes\BBCQ\
\newblock {\Bem Journal of the ACM}, {\Bem 30(3)}, 514--550.

\bibitem[\protect\BCAY{Fotakis, Kontogiannis, Koutsoupias, Mavronicolas, \BBA\
  Spirakis}{Fotakis et~al.}{2002}]{FKKMS02}
Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., \BBA\
  Spirakis, P. \BBOP2002\BBCP.
\newblock \BBOQ The structure and complexity of nash equilibria for a selfish
  routing game\BBCQ\
\newblock In {\Bem Proc. of the 29th International Colloquium on Automata,
  Languages and Programming (ICALP'02)}, \BPGS\ 123--134, Malaga, Spain.

\bibitem[\protect\BCAY{Gal \BBA\ Pfeffer}{Gal \BBA\ Pfeffer}{2004}]{GP04}
Gal, Y.\BBACOMMA\  \BBA\ Pfeffer, A. \BBOP2004\BBCP.
\newblock \BBOQ Reasoning about rationality and beliefs\BBCQ\
\newblock In {\Bem Proc. of the 3rd International Joint Conference on
  Autonomous Agents and Multiagent Systems (AAMAS'04)}, \BPGS\ 774--781, New
  York, NY, USA.

\bibitem[\protect\BCAY{Garey \BBA\ Johnson}{Garey \BBA\
  Johnson}{1979}]{gare-john-90}
Garey, M.\BBACOMMA\  \BBA\ Johnson, D. \BBOP1979\BBCP.
\newblock {\Bem Computers and Intractability. A Guide to the Theory of
  \NP-completeness}.
\newblock Freeman and Comp., NY, USA.

\bibitem[\protect\BCAY{Gilboa \BBA\ Zemel}{Gilboa \BBA\ Zemel}{1989}]{GZ89}
Gilboa, I.\BBACOMMA\  \BBA\ Zemel, E. \BBOP1989\BBCP.
\newblock \BBOQ Nash and correlated equilibria: Some complexity
  considerations\BBCQ\
\newblock {\Bem Games and Economic Behaviour}, {\Bem 1}, 80--93.

\bibitem[\protect\BCAY{Gillies}{Gillies}{1953}]{G53}
Gillies, D. \BBOP1953\BBCP.
\newblock \BBOQ Some theorems on n-person games\BBCQ\
\newblock {\Bem PhD thesis, Princeton, Dept. of Mathematics}.

\bibitem[\protect\BCAY{Gottlob, Leone, \BBA\ Scarcello}{Gottlob
  et~al.}{2000}]{GLS99b}
Gottlob, G., Leone, N., \BBA\ Scarcello, S. \BBOP2000\BBCP.
\newblock \BBOQ A comparison of structural csp decomposition methods\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 124(2)}, 243--282.

\bibitem[\protect\BCAY{Gottlob, Leone, \BBA\ Scarcello}{Gottlob
  et~al.}{2001}]{gott-etal-01}
Gottlob, G., Leone, N., \BBA\ Scarcello, S. \BBOP2001\BBCP.
\newblock \BBOQ The complexity of acyclic conjunctive queries\BBCQ\
\newblock {\Bem Journal of the ACM}, {\Bem 48(3)}, 431--498.

\bibitem[\protect\BCAY{Gottlob, Leone, \BBA\ Scarcello}{Gottlob
  et~al.}{2002a}]{GLSTCS}
Gottlob, G., Leone, N., \BBA\ Scarcello, S. \BBOP2002a\BBCP.
\newblock \BBOQ Computing logcfl certificates\BBCQ\
\newblock {\Bem Theoretical Computer Science}, {\Bem 270(1-2)}, 761--777.

\bibitem[\protect\BCAY{Gottlob, Leone, \BBA\ Scarcello}{Gottlob
  et~al.}{2002b}]{gott-etal-02}
Gottlob, G., Leone, N., \BBA\ Scarcello, S. \BBOP2002b\BBCP.
\newblock \BBOQ Hypertree decompositions and tractable queries\BBCQ\
\newblock {\Bem Journal of Computer and System Sciences}, {\Bem 63(3)},
  579--627.

\bibitem[\protect\BCAY{Greco \BBA\ Scarcello}{Greco \BBA\
  Scarcello}{2003}]{GSijcai03}
Greco, G.\BBACOMMA\  \BBA\ Scarcello, S. \BBOP2003\BBCP.
\newblock \BBOQ Non-binary constraints and optimal dual-graph
  representations\BBCQ\
\newblock In {\Bem Proc. of the 18th International Joint Conference on
  Artificial Intelligence (IJCAI'03)}, \BPGS\ 227--232, Acapulco, Mexico.

\bibitem[\protect\BCAY{Greco \BBA\ Scarcello}{Greco \BBA\ Scarcello}{2004}]{GSecai04}
Greco, G.\BBACOMMA\  \BBA\ Scarcello, S. \BBOP2004\BBCP.
\newblock \BBOQ Constrained Pure Nash Equilibria in Graphical Games\BBCQ\
\newblock In {\Bem Proc. of the 16th Eureopean Conference on Artificial Intelligence
(ECAI'04)}, \BPGS\ 181--185, Valencia, Spain.

\bibitem[\protect\BCAY{Greco \BBA\ Scarcello}{Greco \BBA\ Scarcello}{2005}]{GSuai05}
Greco, G.\BBACOMMA\  \BBA\ Scarcello, S. \BBOP2005\BBCP.
\newblock \BBOQ Bounding the Uncertainty of Graphical Games: The Complexity of Simple Requirements, Pareto and Strong
Nash Equilibria\BBCQ\
\newblock to appear In {\Bem Proc. of the 21st Conference in Uncertainty in Artificial Intelligence
(UAI'05)}, Edinburgh, Scotland.

\bibitem[\protect\BCAY{Johnson}{Johnson}{1990}]{john-90}
Johnson, D. \BBOP1990\BBCP.
\newblock \BBOQ A catalog of complexity classes\BBCQ\
\newblock {\Bem Handbook of Theoretical Computer Science, Volume A: Algorithms
  and Complexity}, 67--161.

\bibitem[\protect\BCAY{Johnson, Papadimitriou, \BBA\ Yannakakis}{Johnson
  et~al.}{1998}]{JP88}
Johnson, D., Papadimitriou, C., \BBA\ Yannakakis, M. \BBOP1998\BBCP.
\newblock \BBOQ How easy is local search?\BBCQ\
\newblock {\Bem Journal of Computer and System Sciences}, {\Bem 37}, 79--100.

\bibitem[\protect\BCAY{Kearns, Littman, \BBA\ Singh}{Kearns
  et~al.}{2001a}]{KLS01}
Kearns, M., Littman, M., \BBA\ Singh, S. \BBOP2001a\BBCP.
\newblock \BBOQ An efficient exact algorithm for singly connected graphical
  games\BBCQ\
\newblock In {\Bem Proc. of the 14th International Conference on Neural
  Information Processing Systems (NIPS'01)}, \BPGS\ 817--823, Vancouver,
  British Columbia, Canada.

\bibitem[\protect\BCAY{Kearns, Littman, \BBA\ Singh}{Kearns
  et~al.}{2001b}]{KLS01b}
Kearns, M., Littman, M., \BBA\ Singh, S. \BBOP2001b\BBCP.
\newblock \BBOQ Graphical models for game theory\BBCQ\
\newblock In {\Bem Proc. of the 17th International Conference on Uncertainty in
  AI (UAI'01)}, \BPGS\ 253--260, Seattle, Washington, USA.

\bibitem[\protect\BCAY{Kearns \BBA\ Mansour}{Kearns \BBA\ Mansour}{2002}]{KM02}
Kearns, M.\BBACOMMA\  \BBA\ Mansour, Y. \BBOP2002\BBCP.
\newblock \BBOQ Efficient nash computation in large population games with
  bounded influence\BBCQ\
\newblock In {\Bem Proc. of the 18th International Conference on Uncertainty in
  AI (UAI'02)}, \BPGS\ 259--266, Edmonton, Alberta, Canada.

\bibitem[\protect\BCAY{Koller \BBA\ Megiddo}{Koller \BBA\ Megiddo}{1992}]{KM92}
Koller, D.\BBACOMMA\  \BBA\ Megiddo, N. \BBOP1992\BBCP.
\newblock \BBOQ The complexity of two-person zero-sum games in extensive
  form\BBCQ\
\newblock {\Bem Games and Economic Behavior}, {\Bem 2}, 528--552.

\bibitem[\protect\BCAY{Koller \BBA\ Megiddo}{Koller \BBA\ Megiddo}{1996}]{KM96}
Koller, D.\BBACOMMA\  \BBA\ Megiddo, N. \BBOP1996\BBCP.
\newblock \BBOQ Finding mixed strategies with small supports in extensive form
  games\BBCQ\
\newblock {\Bem International Journal of Game Theory}, {\Bem 14}, 73--92.

\bibitem[\protect\BCAY{Koller, Megiddo, \BBA\ von Stengel}{Koller
  et~al.}{1996}]{KMS96}
Koller, D., Megiddo, N., \BBA\ von Stengel, B. \BBOP1996\BBCP.
\newblock \BBOQ Efficient computation of equilibria for extensive two-person
  games\BBCQ\
\newblock {\Bem Games and Economic Behavior}, {\Bem 14}, 220--246.

\bibitem[\protect\BCAY{Koller \BBA\ Milch}{Koller \BBA\ Milch}{2001}]{KM01}
Koller, D.\BBACOMMA\  \BBA\ Milch, B. \BBOP2001\BBCP.
\newblock \BBOQ Multi-agent influence diagrams for representing and solving
  games\BBCQ\
\newblock In {\Bem Proc. of the 7th International Joint Conference on
  Artificial Intelligence (IJCAI'01)}, \BPGS\ 1027--1034, Seattle, Washington,
  USA.

\bibitem[\protect\BCAY{Leyton-Brown \BBA\ Tennenholtz}{Leyton-Brown \BBA\
  Tennenholtz}{2003}]{LT03}
Leyton-Brown, K.\BBACOMMA\  \BBA\ Tennenholtz, M. \BBOP2003\BBCP.
\newblock \BBOQ Local-effect games\BBCQ\
\newblock In {\Bem Proc. of the 18th International Joint Conference on
  Artificial Intelligence (IJCAI'03)}, \BPGS\ 772--780, Acapulco, Mexico.

\bibitem[\protect\BCAY{Maier}{Maier}{1986}]{maie-86}
Maier, D.  \BBOP1986\BBCP.
 \newblock {\em The Theory of Relational Databases}, Rochville, Md, Computer
Science Press.


\bibitem[\protect\BCAY{Mas-Colell, Whinston, \BBA\ Green}{Mas-Colell
  et~al.}{1995}]{MWG95}
Mas-Colell, A., Whinston, M., \BBA\ Green, J. \BBOP1995\BBCP.
\newblock {\Bem Microeconomic Theor}.
\newblock Oxford University Press.

\bibitem[\protect\BCAY{Maskin}{Maskin}{1985}]{M85}
Maskin, E. \BBOP1985\BBCP.
\newblock \BBOQ The theory of implementation in nash equilibrium\BBCQ\
\newblock {\Bem Social Goals and Organization: Essays in memory of Elisha
  Pazner}, 173--204.

\bibitem[\protect\BCAY{McKelvey \BBA\ McLennan}{McKelvey \BBA\
  McLennan}{1996}]{MM96}
McKelvey, R.\BBACOMMA\  \BBA\ McLennan, A. \BBOP1996\BBCP.
\newblock \BBOQ Computation of equilibria in finite games\BBCQ\
\newblock {\Bem Handbook of Computational Economics}, 87--142.

\bibitem[\protect\BCAY{Megiddo \BBA\ Papadimitriou}{Megiddo \BBA\
  Papadimitriou}{1991}]{MP91}
Megiddo, N.\BBACOMMA\  \BBA\ Papadimitriou, C. \BBOP1991\BBCP.
\newblock \BBOQ On total functions, existence theorems, and computational
  complexity\BBCQ\
\newblock {\Bem Theoretical Computer Science}, {\Bem 81(2)}, 317--324.

\bibitem[\protect\BCAY{Monderer \BBA\ Shapley}{Monderer \BBA\
  Shapley}{1993}]{MS93}
Monderer, D.\BBACOMMA\  \BBA\ Shapley, L. \BBOP1993\BBCP.
\newblock \BBOQ Potential games\BBCQ\
\newblock {\Bem Games and Economic Behavior}.

\bibitem[\protect\BCAY{Nash}{Nash}{1951}]{N51}
Nash, J. \BBOP1951\BBCP.
\newblock \BBOQ Non-cooperative games\BBCQ\
\newblock {\Bem Annals of Mathematics}, {\Bem 54(2)}, 286--295.

\bibitem[\protect\BCAY{Osborne \BBA\ Rubinstein}{Osborne \BBA\
  Rubinstein}{1994}]{OR94}
Osborne, M.\BBACOMMA\  \BBA\ Rubinstein, A. \BBOP1994\BBCP.
\newblock {\Bem A Course in Game Theory}.
\newblock MIT Press.

\bibitem[\protect\BCAY{Owen}{Owen}{1982}]{O82}
Owen, G. \BBOP1982\BBCP.
\newblock {\Bem Game Theory}.
\newblock Academic Press, New York.

\bibitem[\protect\BCAY{Papadimitriou}{Papadimitriou}{1994a}]{papa-94}
Papadimitriou, C. \BBOP1994a\BBCP.
\newblock {\Bem Computational Complexity}.
\newblock AAddison-Wesley, Reading, Mass.

\bibitem[\protect\BCAY{Papadimitriou}{Papadimitriou}{1994b}]{P94}
Papadimitriou, C. \BBOP1994b\BBCP.
\newblock \BBOQ On the complexity of the parity argument and other inefficient
  proofs of existence\BBCQ\
\newblock {\Bem Journal of Computer and System Sciences}, {\Bem 48(3)},
  498--532.

\bibitem[\protect\BCAY{Papadimitriou}{Papadimitriou}{2001}]{P01}
Papadimitriou, C. \BBOP2001\BBCP.
\newblock \BBOQ Algorithms, games, and the internet\BBCQ\
\newblock In {\Bem Proc. of the 28th International Colloqium on Automata,
  Languages and Programming (ICALP'01)}, \BPGS\ 1--3, Crete, Greece.

\bibitem[\protect\BCAY{Robertson \BBA\ Seymour}{Robertson \BBA\
  Seymour}{1986}]{robe-seym-86}
Robertson, N.\BBACOMMA\  \BBA\ Seymour, P. \BBOP1986\BBCP.
\newblock \BBOQ Graph minors ii. algorithmic aspects of tree width\BBCQ\
\newblock {\Bem Journal of Algorithms}, {\Bem 7}, 309--322.

\bibitem[\protect\BCAY{Rosenthal}{Rosenthal}{1973}]{R73}
Rosenthal, R. \BBOP1973\BBCP.
\newblock \BBOQ A class of games possessing pure-strategy nash equilibria\BBCQ\
\newblock {\Bem International Journal of Game Theory}, {\Bem 2}, 65--67.

\bibitem[\protect\BCAY{Schoenebeck \BBA\ Vadhan}{Schoenebeck \BBA\ Vadhan}{2005}]{SVECC05}
Schoenebeck, G.R.\BBACOMMA\  \BBA\ Vadhan, S.P. \BBOP2005\BBCP.
\newblock \BBOQ The Computational Complexity of
Nash Equilibria in Concisely Represented Games\BBCQ\
\newblock {\Bem Electronic Colloquium on Computational Complexity}, {\Bem Report TR05-052}.


\bibitem[\protect\BCAY{Stockmeyer \BBA\ Meyer}{Stockmeyer \BBA\
  Meyer}{1973}]{SM73}
Stockmeyer, L.\BBACOMMA\  \BBA\ Meyer, A. \BBOP1973\BBCP.
\newblock \BBOQ Word problems requiring exponential time: Preliminary
  report\BBCQ\
\newblock In {\Bem Proc. of the 5th Annual ACM Symposium on Theory of Computing
  (STOC'73)}, \BPGS\ 1--9.

\bibitem[\protect\BCAY{Vardi}{Vardi}{2000}]{vardi}
Vardi, M. \BBOP2000\BBCP.
\newblock \BBOQ Constraint satisfaction and database theory: a tutorial\BBCQ\
\newblock In {\Bem Proc. of the 19th ACM SIGMOD-SIGACT-SIGART Symposium on
  Principles of Database Systems}, \BPGS\ 76--85, Dallas, Texas, USA.

\bibitem[\protect\BCAY{Venkateswaran}{Venkateswaran}{1991}]{venka}
Venkateswaran, H. \BBOP1991\BBCP.
\newblock \BBOQ Properties that characterize logcfl\BBCQ\
\newblock {\Bem Journal of Computer and System Sciences}, {\Bem 43(2)},
  380--404.

\bibitem[\protect\BCAY{Vickrey}{Vickrey}{2002}]{koller}
Vickrey, D. amd~Koller, D. \BBOP2002\BBCP.
\newblock \BBOQ Multi-agent algortihms for solving graphical games\BBCQ\
\newblock In {\Bem Proc. of the 18th National Conference on Artificial
  Intelligence (AAAI'02)}, \BPG\ 345–251\ Edmonton, Alberta, Canada.

\bibitem[\protect\BCAY{Yannakakis}{Yannakakis}{1981}]{yanna}
Yannakakis, M. \BBOP1981\BBCP.
\newblock \BBOQ Algorithms for acyclic database schemes\BBCQ\
\newblock In {\Bem Proc. of the 7th International Conference on Very Large Data
  Bases (VLDB’81)}, \BPG\ 82–94\ Cannes, France.

\end{thebibliography}
\end{document}
