

\section{PTAS}
\input{AGG_PTAS_fin}


\section{Hardness Results}~\label{section:Hardness Results}

\input{AGG_mpnash11_fin}

\input{AGG_hardness_fin}


\section{Conclusions and Open Problems}
\input{AGG_conclusion_fin}

\bibliographystyle{plain}

\subsection*{A Copy Gadget}

As a preliminary to the hardness results of the next two subsections, we describe a \emph{copy gadget} which will prove useful
in both NP-completeness and PPAD-completeness results.  Intuitively, to simulate games $G$ of high treewidth by treewidth 1 action graph games $H$, we create several ``copies'' of each player, but only one copy of each edge relating players, thus ending up with a very ``sparse'' simulation, whose treewidth we can control.  Explicitly, given an AGG
$A$, and an agent $i$ whose strategy set consists of the two strategies $S_i=\{f_i,t_i\}$, our copy gadget will add two additional players $a,c$, of which player $c$ will be the ``copy'' and player $a$ is an auxiliary player, whose inclusion will allow player $i$'s strategies to be disconnected from player $c$'s.  We add strategies for $a$ and $c$ that are $\{f_a,t_a\}$ and $\{f_c,t_c\}$ respectively, and set the incentives so that in any Nash equilibrium $\Pr[
s(i)=t_i] = \Pr[s(b)=t_b]$ (and $\Pr[ s(i)=f_i] = \Pr[s(b)=f_b]$).

\begin{figure}
\begin{center}
\epsfig{file=copy_gadget.eps,width=.4\textwidth} \caption{The
\emph{copy gadget}---in any Nash equilibrium
$\Pr[s(b)=f_b]=\Pr[s(i)=f_i]$.}\label{fig:copy gadget}
\end{center}
\end{figure}


\begin{definition}~\label{def:copy gadget}
Given an AGG $A=\langle P,\bold{S},G,u \rangle$, and an agent $i$
with two strategy choices $S_i=\{f_i,t_i\}$, we create AGG
$A'=\langle P',\bold{S'},G',u' \rangle$ from $A$ via the addition of
a \emph{copy gadget on $i$} as follows:
\begin{itemize}
    \item{$P':=P \cup \{a,c\}.$}
    \item{$\bold{S'}:=(S_1,\ldots,S_{|P|},S_a,S_c)$, where $S_a=\{f_a,t_a\}$, and $S_c=\{f_c,t_c\}$, where $f_a,t_a,f_c,t_c \not \in S$.}
    \item{$G'$ consists of the graph $G$ with the additional vertices corresponding to $f_a,t_a,f_c,t_c$, and the directed edges $(f_i,f_a), (t_a,f_c),(f_c,t_a)$.}
    \item{$u'$ is identical to $u$ for all strategies in $S'\backslash \{S_a \cup S_c\}$, and for a configuration $D$, $u'(f_a)=D(f_i),$ $u'(t_a)=1-D(f_c),$ and $u'(f_c)=1-2 D(t_a).$}
\end{itemize}
\end{definition}
See Figure~\ref{fig:copy gadget} for a depiction of the copy gadget.

\begin{lemma}~\label{lemma:copy gadget}
Given an AGG $A$ and an agent $i$, the addition of a copy gadget on
$i$ yields $A'$ that satisfies the following properties:
\begin{itemize}
    \item{The description size of $A'$ is at most a constant larger than $A$.}
\iffalse    \item{For every $\epsilon$--Nash equilibrium $M'$ of $A'$, the restriction of $M'$ to agents $1,\ldots,n_A$ is a Nash equilibrium of $A$, and for any equilibrium $M$ of $A$, there exist distributions $M_a:=(p_{a,f},p_{a,t}), M_b:=(p_{b,f},p_{b,t})$ over strategies for agents $a$ and $b$ such that $M$ together with $M_a,M_b$ is an equilibrium of $A'$.}\fi
    \item{In the strategy graph $G_{A'}$, $f_c$ and $t_c$ are not path connected to either $f_i$ or $t_i$.}
    \item{In every $\epsilon^2$--Nash equilibrium with agent $i$'s profile $(p_{i,f},1-p_{i,f})$, agent $c$'s profile will have $|p_{c,f}-p_{i,f}|\leq \epsilon$ (and $|p_{b,t}-p_{i,t}|\leq \epsilon$).}
\end{itemize}
\end{lemma}

\begin{proof}
The first two properties follow directly from
Definition~\ref{def:copy gadget}.  For the third property, assume
otherwise and consider the case where $p_{c,f} > \epsilon+p_{i,f}$.  Agent
$a$'s expected utility for playing $f_a$ is $p_{i,f}$, and is
$p_{c,f}$ for playing $t_a$, thus our assumption that $p_{c,f} >
\epsilon+p_{i,f}$ implies that agent $a$ must be playing $t_a$ with probability at least $1-\epsilon$ since the game
is at $\epsilon^2$--equilibrium.  Given that $a$ plays $t_a$ with probability at least $1-\epsilon$, agent $b$ maximizes
her utility by playing $t_c$, and thus $p_{c,f}\leq \epsilon$, which contradicts our assumption that $p_{c,f}$ is the larger of $p_{c,f},p_{i,f}$, namely at least $\frac{1}{2}$.  An analogous argument applies to rule out the case $p_{c,f} < p_{i,f}-\epsilon$.
\end{proof}

\subsection{PPAD-Completeness}

Our PPAD-Completeness results are reductions from the problem of
computing equilibria in graphical games, and rely on the following
fact due to~\cite{CDT06}.

\begin{fact}~\label{fact:PPAD}
For the class of graphical games with $n$ players, maximum degree $3$ and
payoffs in $\{0,1,2\}$, it is PPAD--complete to compute $\epsilon$-Nash equilibria where
$\epsilon \propto 1/poly(n)$.
\end{fact}

\begin{theorem}~\label{thm:PPAD tw1}
Computing a Nash equilibrium for AGGs with strategy graph $G_A$ is
PPAD-complete even if \\$treewidth(G_A)=1$, and $G_A$ has constant degree.
\end{theorem}

\begin{proof}
From Theorem \ref{th:generalTheoremForGames} this problem is in PPAD.

To show PPAD-hardness, we reduce from the known PPAD-hard problem of Fact \ref{fact:PPAD}.  Given an instance of such a graphical game $H$, we construct an AGG $A_H'$ with
treewidth $1$ and maximum degree 4 with similar description size to
$H$ such that there a polynomial time mapping from $\epsilon$--Nash equilibria of $A_H'$ to the $\epsilon$--Nash equilibria of $H$.  We construct $A_H'$ via the
intermediate step of constructing an AGG $A_H$ which will be
equivalent to $H$ and might have large treewidth.  From $A_H$, we
construct $A_H'$ using our copy gadget to reduce the treewidth of
the associated strategy graph.  See Figure~\ref{fig:H to A_H} for a
depiction of the reduction.

The construction of $A_H$ is straightforward: for each player $i_H$
in the graphical game, we have a corresponding player $i_A$ in the
AGG with strategy set $S_{i_A}=\{f_i,t_i\}$, corresponding to the
two strategies that $i_H$ may play in $H$.  For each undirected edge between players
$(i,j) \in H$, we add directed edges between the $t$ nodes $(t_j,t_i),(t_i,t_j)$, and edges between the $f$ nodes $(f_j,f_i),(f_i,f_j)$ to the strategy graph
$G_{A_H}$ of $A_H$.  We define utilities $u$ by simulating the utility functions from the original game $H$: from each $f$ strategy connected to $i_A$ in the AGG we know that if it is played then the corresponding $t$ strategy is not played and vice versa; thus we have recovered the strategy choice of each neighbor of $I_H$ in original graphical game; we then apply the utility function of the graphical game to compute the utility in the AGG.  We do the symmetric procedure for the $t$ nodes of the AGG.  From the
construction, it is clear that $H$ and $A_H$ represent the same game
via the correspondence $i_H \rightarrow i_A$, and in particular an
$\epsilon$--Nash equilibrium of one game will correspond to an
$\epsilon$--Nash equilibrium of the other game via the natural
mapping.

We obtain $A_H'$ from $A_H$ by making three copies of each $i_A$ via
the copy gadget.  Thus for each $i$ there are agents $i_A,
i_A^1,i_A^2,i_A^3$ with $S_{i_A^k}=\{f_{i_A}^k,t_{i_A}^k\}$.
Finally, for each of the (at most three) outgoing edges of $f_{i_A}$
that are not part of copy gadgets, i.e the edges of the form
$(f_{i_A},f_{j_A})$, we replace the edge by $(f_{i_A}^k,f_{j_A})$,
with each $f_{i_A}^k$ having at most one outgoing edge, and modify
the utility function $u$ analogously so as to have the utility of
strategy $f_{j_A}$ depend on $f_{i_A}^k$ instead of $f_{i_A}$.
Analogous replacements are made for the outgoing edges of $t_{i_A}$.
Since the copied strategies $f_{i_A}^k,t_{i_A}^k$ are disconnected
from the original strategies $f_{i_A},t_{i_A}$ the longest path in
the strategy graph $G_{A_H'}$ associated with $A_H'$ has length at
most 4, with maximum degree 6, and $treewidth(G_{A_H})=1$.  (See
Figure~\ref{fig:H to A_H}.) Lemma~\ref{lemma:copy gadget} guarantees
that the transformation from $A_H$ to $A_H'$ increases the
representation size by at most a constant factor.  Further, from an $\frac{1}{144}\epsilon^2$--Nash equilibrium of $A_H'$ we can extract an $\epsilon$--Nash equilibrium of $A_H$ by simply ignoring the new players: all of the copies $i_A^k$ of a player $i_A$ will play strategies with probabilities within $\frac{1}{12}\epsilon$ of the probabilities of playing the original by Lemma~\ref{lemma:copy gadget}; thus the joint distribution of any triple of these will have joint distribution within $\frac{1}{4}\epsilon$ of the ``true'' joint distribution; since each utility has magnitude at most 2 the computed utilities will be within $\frac{1}{2}\epsilon$ of the utilities computed in $A_H$; thus each of the mixed strategies of a player $i_A$ in $A_H'$, interpreted as a strategy in $A_H$ will yield utility within $\epsilon$ of optimal.  From Fact \ref{fact:PPAD} we conclude that finding an $\frac{1}{144}\epsilon^2$--Nash equilibrium of $A_H'$ is PPAD complete for any polynomial $\epsilon$, yielding the desired result.
\end{proof}


\begin{figure}
\begin{center}
\epsfig{file=HtoA_H.eps,width=.6\textwidth} \caption{The
transformation from the graphical game $H$ to the AGG $A_H'$.  For
simplicity, the internal strategies and edges associated with the
copy gadgets are omitted.}~\label{fig:H to A_H}
\end{center}
\end{figure}

We now turn our attention to AGGs that have a constrained number of
player types.

\begin{theorem}~\label{thm:PPAD sym}
Computing a Nash equilibrium for symmetric AGGs ($1$ player type) is
PPAD-complete even if the strategy graph $G_A$ has bounded degree.
\end{theorem}

To show PPAD-hardness, as above we reduce from the known PPAD-hard problem of
computing Nash equilibria in graphical games of degree at most $3$
where each player chooses between $2$ strategies $f,t$ and has
utility $0$, $1$, or $2$.  Given such a graphical game $H$, we will
reduce it to an AGG $A_H$ that has strategies $f_i,t_i$
corresponding to the two strategies that agent $i$ may choose in
$H$.  Intuitively, if our reduction is to be successful there are
several properties of $G_H$ that seem necessary.  First, in every
Nash equilibrium of $G_H$, there must be at least one agent playing
either $f_i$ or $t_i$ for every $i$.  This is accomplished by giving
agents a bonus payment if they choose either of the two strategies
of a sparsely-played $f_i,t_i$ pair.  Second, there must be some
unambiguous mapping between the number of agents playing $f_i$ and
$t_i$ in $A_H$ to a choice of actions of agent $i$ in $H$.  This is
accomplished via the MAJORITY function: if more agents play $f_i$
than $t_i$ in $A_H$, we say that $i$ plays $f$.  This motivating intuition is formalized in the
proof below.

\begin{prevproof}{Theorem}{thm:PPAD sym}
From Theorem \ref{th:generalTheoremForGames} this problem is in PPAD

To show PPAD-hardness, we reduce from the known PPAD-hard problem of
computing Nash equilibria in graphical games of degree at most $3$
where each player chooses between $2$ strategies and has utility
$0$, $1$, or $2$.  Given an instance of such a graphical game $H$,
with $n$ agents, and some $\epsilon>0$ we construct the symmetric
AGG $A_H$ so that an $\epsilon$--Nash equilibrium of $A_H$ can be
efficiently mapped to a $2 \epsilon$--Nash equilibrium of $H$.  We
construct $A_H=\langle P,\bold{S},G_{A},u \rangle$ as follows:
\begin{itemize}
    \item{$P:=\{1,\ldots,3 c n\}$ with $c>\frac{64}{\epsilon^2}$.}
    \item{$\bold{S}:= (S,\ldots,S)$, that is, each player has identical (symmetric) strategy set $S:=\{f_1,t_1,\ldots,f_n,t_n\}$ where strategies $f_i$ and $t_i$ correspond to the two strategies of the $i^{th}$ agent of $H$.}
    \item{For every undirected edge $(i,j)$ in the graph of $H$, the strategy graph $G_A$ has the eight directed edges $(f_i,f_j)$, $(f_j,f_i)$, $(f_i,t_j)$, $(t_j,f_i)$, $(t_i,f_j)$, $(f_j,t_i)$, $(t_i,t_j)$, $(t_j,t_i).$  Furthermore, for all $i \in \{1,\ldots, n\}$, $G_A$ contains the edges $(f_i,t_i),(t_i,f_i)$ and the self loops $(f_i,f_i)$ and $(t_i,t_i)$.}
    \item{To simplify the description of the utility function $u$, it will be useful to define the indicator functions\\ $I_1[D(f_1,t_1)],\ldots,I_n[D(f_n,t_n)]$ where $$I_i[D(f_i,t_i)]:= \left\{ \begin{array}{cc} f & \text{if $D(f_i) \ge D(t_i)$} \nonumber \\ t & \text{if $D(f_i)< D(t_i)$} \nonumber \end{array} \right.$$ Let $u$ assign utility to $f_i$ as a function of $D(\nu(i))$, where $\nu(i)$ denotes $i$'s neighbors, by applying the utility function for agent $i$ from $H$ on the simulated actions of her neighbors $j_1,j_2,j_3$ evaluated as $I_{j_1}[D(f_{j_1},t_{j_1})],I_{j_2}[D(f_{j_2},t_{j_2})],$ and $I_{j_3}[D(f_{j_3},t_{j_3})]$, respectively.  Finally, if $D(f_i)+D(t_i) \leq c$, $u$ assigns an extra $100$ utility to strategies $f_i$ and $t_i$.}
\end{itemize}
Observe that the description size of $A_H$ is polynomial in $cn$,
and thus is polynomial in the description size of $H$.  From Fact~\ref{fact:PPAD} our theorem will follow if we show that any $\epsilon^2$--Nash equilibrium of $A_H$ can
be efficiently mapped to an $\epsilon$--Nash equilibrium of $H$.

Consider the map from mixed strategy profiles of $A_H$ to mixed
strategy profiles of $H$ given by $\phi: \bold{M_A} \rightarrow
\bold{M_H}$ that assigns $M_H=[ (p_{1,f},
1-p_{1,f}),\ldots,(p_{n,f}, 1-p_{n,f}) ]$ by setting
$p_{i,f}:=\Pr_{M_A} (I_i=f)$ where the probability is taken over the
distribution over $\Delta$ defined by $M_A$.  It is clear that the
map $\phi$ can be computed efficiently, as it essentially involves simply evaluating multinomial distributions on 4 outcomes.

Before showing that $\phi$ maps $\epsilon$--equilibria to
$2\epsilon$--equilibria we first show that the ``extra utility" of 100 correctly incentivizes a large number of players to play on each strategy pair. We observe that in any mixed strategy
profile there will be at least one agent, $j$, who has probability at most $1/3$ of receiving a payoff of at least $100$.  Since his payoff from the simulation of $H$ is at most 2, such an agent's
expected utility is at most $35+\frac{1}{3}$, and thus any Nash equilibrium
mixed strategy profile must satisfy $100 \Pr( D(f_i)+D(t_i) < c) <
36, \forall i \in \{1,\ldots,n\}.$  If this were not the case, then
agent $j$ could improve her expected utility to at least $36$ by
always choosing strategy $f_i$, a contradiction.  The above
inequality implies that $$\mathbb{E}\left[\max\left(D(f_i),D(t_i)\right)
\right] > \frac{c}{4}.$$

We now proceed with the proof of correctness of the map $\phi$.  Let
$M_A$ be an $\epsilon$--Nash equilibrium of $A_H$, and
$M_H=\phi(M_A)$.  Consider a player $i$ in the graphical game, and a strategy of his that he plays with probability at least $\epsilon$.  Without loss of generality let this strategy be $f_i$.  We show that his utility for playing $f_i$ is at least his utility for playing his other choice, $t_i$, minus $\epsilon$; taken together, these statements imply that $M_H$ is an $\epsilon$--Nash equilibrium of the graphical game, as desired.

Since $\mathbb{E}\left[\max\left(D(f_i),D(t_i)\right)
\right] > \frac{c}{4}$, we have that if $f_i$ is played with probability at least $\epsilon$, namely if $\Pr(D(f_i)\geq D(t_i))\geq \epsilon$ then (by Chernoff bounds) we must have $\mathbb{E}[D(f_i)]\geq\frac{c}{6}$.  This implies that for at least one of the $3cn$ players $j$ in $A_H$, his probability of playing $f_i$ is at least $\frac{1}{18n}$, which is at least $2\epsilon$.  Thus, since $M_A$ is, by assumption, an $\epsilon^2$--Nash equilibrium, we have that player $j$'s utility for playing $f_i$ is at most $\frac{1}{2}\epsilon$ below his utility for playing $t_i$, when the other players play from $M_A$.  Further, by construction, each of these two utilities are within $\frac{1}{4}\epsilon$ of the utilities for player $i$ in the graphical game to play $f_i,t_i$ respectively, when the other players play from $M_H$: this is because fixing player $j$'s move from $M_{A,j}$ to one of $f_i,t_i$ changes each $I_k$ by at most the probability of $j$ playing one of $(f_k,t_k)$ divided by the standard deviation of $\max\left(D(f_i),D(t_i)\right)$, which is at least the square root of its expectation, $\sqrt{\frac{c}{4}}=\frac{4}{\epsilon}$.  Thus by the triangle inequality we have that player $i$'s utility for playing $f_i$ is no more than $\epsilon$ worse than playing $t_i$.  Since our choice of $i$ was arbitrary and a corresponding argument applies to the $t$ strategies, we conclude that $M_H$ is an $\epsilon$--Nash equilibrium of $H$, as desired.
\end{prevproof}

\subsection{NP--Completeness}

Both of our NP--completeness results are reductions from the
NP-Complete problem CIRCUITSAT and follow an approach employed
in~\cite{SV_2006}.

\begin{fact}~\label{fact:NP-complete}
It is NP-complete to decide satisfiability for the class of circuits consisting of AND, OR, and NOT gates, with maximum degree $3$ (in-degree plus out-degree).
\end{fact}

In our reductions from CIRCUITSAT, given a circuit $C$, we construct
an AGG $A_C$ that computes $C$ in the sense that pure strategy Nash
equilibria of $A_C$ map to valid circuit evaluations.
To this game we add two agents that have a simple pure-strategy equilibrium if $C$
evaluates to $true$, but when $C$ evaluates to $false$ play \emph{pennies}---a simple game
that has no pure strategy Nash equilibria.  Thus the existence of a
pure strategy Nash equilibrium is equivalent to the satisfiability of
$C$.

\begin{theorem}~\label{thm:NP tw1}
Deciding the existence of a pure strategy Nash equilibrium for AGGs
with strategy graph $G_A$ is NP-complete even if $treewidth(G_A)=1$,
and $G_A$ has constant degree.
\end{theorem}

\begin{proof}
Membership in NP is clear.  To show hardness, given a circuit $C$,
we construct the associated AGG $A_C:=\langle P,\bold{S},G_{A},u
\rangle$ as follows:
\begin{itemize}
    \item{$P:=\{1,\ldots,n, p_1,p_2\}$, where $n$ is the number of gates in $C$, and the gate corresponding to player $n$ is the output gate.}
    \item{$\bold{S}:= \left((f_1,t_1),\ldots,(f_n,t_n), (f_{p_1},t_{p_1}), (f_{p_2},t_{p_2})\right)$.}
    \item{For every pair of gates $i,j$ for which the output of gate $i$ is an input to gate $j$, $G_A$ has the edges $(f_i,f_j),$ and $(f_i,t_j)$.  Furthermore, we add edges $(f_n,f_{p_1}), (f_n,t_{p_1}), (f_n,f_{p_2}), (f_n,t_{p_2})$, and the edges $(f_{p_1}, f_{p_2})$, $(f_{p_1},t_{p_2})$, $(f_{p_2},f_{p_1})$, $(f_{p_2},t_{p_1})$.}
    \item{The utility function $u$ is defined as follows: if agent $i$ corresponds to an input gate, than strategies $f_i,t_i$ both have utility 0.  For any other agent $i$ corresponding to a gate of $C$, the payoff of strategy $f_i$ is $1$ or $0$ according to whether $f_i$ is the correct output value of gate $i$ given the values corresponding to the strategies played by neighboring agents/strategies.  Similarly for the payoff for strategy $t_i$. If $D(f_n)=0$, then $f_{p_1}$ and $t_{p_1}$ have utility 0, otherwise the utility of $p_1$ is 1 if $D(f_{p_1})=D(f_{p_2})$, and is 0 otherwise.  The utility of $p_2$ is 1 if $D(f_{p_1}) \neq D(f_{p_2})$, and is 0 otherwise.}
\end{itemize}
From the construction it is clear that if $C$ is satisfiable, there
is a pure strategy profile for agents $1,\ldots,n$ with agent $n$
playing $t_n$, such that agents $1,\ldots,n$ can not improve their
utility by deviating from their strategies.  Furthermore, $p_1$ will
be indifferent between her strategies, and $p_2$ will play the
opposite of $p_1$; in particular, there will be a pure strategy Nash
equilibrium.  If $C$ is not satisfiable, then any pure strategy
profile that is an equilibrium for agents $1,\ldots, n$ will have
$D(f_n)=1$, and thus $p_1$ will be incentivized to agree with $p_2$,
and $p_2$ will be incentivized to disagree, and thus $A_C$ will
admit no pure strategy Nash equilibrium.

To complete the proof, note that we can apply the copy gadget to
each agent of $A_C$, as was done in the proof of
Theorem~\ref{thm:PPAD tw1} to yield the game $A_C'$ that has
strategy graph of treewidth 1, and a mapping from equilibria of $A_C'$ to equilibria of $A_C$.
\end{proof}

\begin{theorem}~\label{thm:NP sym}
Deciding the existence of a pure strategy Nash equilibrium for
symmetric AGGs ($1$ player type) is NP-complete even if the strategy
graph $G_A$ has bounded degree.
\end{theorem}

\begin{proof}
Membership in NP is clear; to show hardness we proceed as was done
in the proof of Theorem~\ref{thm:NP tw1}, and obtain AGG $A_C$ from
circuit $C$.  Now, we make $A_C$ symmetric by retaining the same number of agents, but allowing each of them to
pick any of the strategies.   We modify the strategy graph $G$ by
adding edges $(f_x,t_x),(t_x,f_x),(f_x,f_x),(t_x,t_x)$ for each player $x$ from $A_C$, and extend
the utility function $u$ so that if $D(f_x)+D(t_x) >1$ then strategies
$f_x$ and $t_x$ have utility $-1$.  Thus in any pure strategy Nash
equilibrium $D(f_x)+D(t_x)=1$, and the reasoning in the proof of
Theorem~\ref{thm:NP tw1} applies to complete our reduction.
\end{proof}

\section{Introduction}~\label{section:Introduction}

What is the likely behavior of autonomous agents in a variety of competitive environments?  This question has been the motivation for much of economic theory.  Partly due to the increasing prevalence of vast online networks over which millions of individuals exchange information, goods, and services, and the corresponding increasing importance of understanding the dynamics of such interactions, the Computer Science community has joined in the effort of studying game-theoretic questions.


Computing equilibria in games and markets has been extensively studied in the Economics and Operations Research communities since the 1960's, see e.g. \cite{Lemke-Howson,Rosenmuller,Wilson,Scarf,Taal}. Computational tractability has been recently recognized as an important prerequisite for modeling competitive environments and measuring the plausibility of solution concepts in Economics: if finding an equilibrium is computationally intractable, should we believe that it naturally arises? And, is it plausible that markets converge to solutions of computationally intractable problems?  Probably not --- but if so, we should certainly know about it.

Computing Nash equilibria in games, even in the case of two players, has been recently shown to be an intractable problem; in particular, it was shown to be complete for the class of fixed point computation problems termed PPAD~\cite{DP_2006,CD_2006}. This result on the intractability of computing Nash equilibria has sparked considerable  effort to find efficient algorithms for approximating such equilibria, and has increased the importance of considering special classes of games for which Nash equilibria might be efficiently computable.

For two-player games the hardness of computing approximate equilibria persists even if the required approximation is inverse polynomial in the number of strategies of the game \cite{CDT06}; similarly, hardness persists in graphical games if the required approximation is inverse polynomial in the number of players \cite{DP_2006,CDT06}. The same hardness results apply to special cases of the problem, e.g. win-lose games, where the payoff values of the game are restricted to $\{0,1\}$ \cite{Val05}, sparse bimatrix games, where the number of non-zero entries of each row an column of the payoff matrices is a constant, and two-player symmetric games \cite{GaleKuhnTucker}. The emerging question of the research in this field is: { Is there a Polynomial Time Approximation Scheme (PTAS) for Computing Nash Equilibria?} And, { which special cases of the problem are computationally tractable?}

The zero-sum two-player case is well-known to be tractable by reduction to linear programming \cite{vonNeumanLP}. Tractability persists in the case of low-rank two-player games, in which the sum $A+B$ of the payoff matrices of the players, instead of being $0$, has fixed rank; in this case, a PTAS exists for finding mixed Nash equilibria \cite{KannanTheobald}. In $n$-player graphical games, a PTAS has been provided if the tree-width is $O(\log n)$ and the maximum degree is bounded \cite{DasPapEC06}; in the case of dense graphical games, a quasi-polynomial time approximation scheme exists \cite{DasPapExhaustive}.

An important line of research on tractable special cases has explored games with symmetries. Mutli-player symmetric games with about logarithmically few strategies per player can be solved exactly in polynomial time by reduction to the existential theory of reals \cite{PapRough}. For congestion games, a pure Nash equilibrium can be computed in polynomial time if the game is a symmetric network congestion game \cite{FabPapTalwar}, and an approximate pure Nash equilibrium if the game is symmetric but not necessarily a network game and the utilities satisfy a ``bounded-jump condition'' \cite{ChienSinclair}. Another important class of games for which computing an approximate equilibrium is tractable is the class of anonymous games, in which each player is different, but does not care about the identities of the other players, as it happens for example congestion games, certain auction settings, and social phenomena \cite{Blonski99}; a PTAS for anonymous games with a fixed number
 of strategies has been provided in \cite{DP:anonymous07,DasPapExhaustive}. For a thorough study of the problem of computing pure Nash equilibria in symmetric and anonymous games see \cite{BFH_2007}.

In this paper, we consider another special class of games,  {\em Action Graph Games} (AGGs), that were introduced by Bhot and Leyton-Brown \cite{B_LB_2004}.  AGGs is a fully general game representation that succinctly captures both `local' dependencies as in graphical games, as well as partial indifference to other agents' identities as in anonymous games.  Strategies are represented as nodes in a graph, called \emph{strategy graph},  and the utility of an agent for selecting a strategy-node depends on the number of other agents selecting each of the neighboring strategies.  The only attribute that distinguishes players is the set of strategies that each player is allowed to play.  In particular, all agents who play a given strategy get the same payoff.  A variety of natural games can be concisely represented as AGGs, and we refer the reader to~\cite{B_LB_2004,J_LB_2007} for further discussion.

In the remainder of this section, we discuss previous work on AGGs and summarize our results. In the end of the section, we provide definitions.

\subsection{Previous Work}

Action graph games were first defined by Bhat and Leyton-Brown~\cite{B_LB_2004} who considered the problem of computing Nash equilibria of these games.  In particular, they analyzed the complexity of computing the Jacobian of the payoff function---a computation that is, in practice, the bottleneck of the continuation method of computing a Nash equilibrium.  They considered this computation for both general AGGs and AGGs with a single player type (symmetric AGGs), and found that this computation is efficient in the latter case.  For pure Nash equilibria, Jiang and Leyton-Brown~\cite{J_LB_2007}
show that deciding the existence of such equilibria in AGGs is $\mathbf{NP}$-complete, even in the case of a single player type and bounded degree.  On the other hand, they provide a polynomial time algorithm for finding pure-Nash equilibria in AGGs with constant number of player types when the strategy graph has bounded tree-width.

\subsection{Our Results}
We examine, and largely resolve the computational complexity of computing Nash equilibria in action graph games. We give a polynomial algorithm for computing an $\epsilon$-Nash equilibrium
for AGGs with constant treewidth and degree and a constant number of agent
types (and arbitrarily many strategies), together with hardness
results for the cases when either the treewidth or the number of
agent types is unconstrained.  In particular, we show that even if
the strategy graph is a tree with bounded degree but the number of agent types
is unconstrained, it is NP--complete to decide the existence of a
pure-strategy Nash equilibrium and PPAD--complete to compute a mixed
Nash equilibrium; similarly for AGGs in which all agents are a
single type if we allow the strategy graph to have arbitrary treewidth.  These hardness results
suggest that, in some sense, our PTAS is as strong of a positive
result as one can expect.   While Bhat and Leyton-Brown studied heuristics for computing mixed
Nash equilibria \cite{B_LB_2004}, the authors know of no previous
complexity theoretic results concerning computing mixed Nash
equilibria for AGGs apart from the $\mathbf{PPAD}$-hardness result that follows from
them being a generalization of normal-form games.

\subsection{Definitions}~\label{subsection:Action Graph Games}

In this section we give a formal definition of AGGs and introduce the terminology that will be used in the remainder of this paper.  We follow the notation and terminology introduced in~\cite{J_LB_2007}. \\

\begin{definition}
An \emph{action-graph game}, $A$, is a tuple $\langle P,\bold{S},G,u
\rangle$ where
\begin{itemize}
     \item{$P:=\{1,\ldots, n\}$ is the set of agents.}
     \item{$\bold{S}:=(S_1,\ldots,S_n),$ where $S_i$ denotes the set of pure strategies that agent $i$ may play.}
     \item{For convenience, let $S := \bigcup_i S_i = \{s_1,\ldots,s_{|S|}\}$ denote the set of all strategies, and thus each $S_i \subseteq S$.
        Also, we write $S_i = \{s_{i, 1}, s_{i, 2}, \ldots, s_{i,
        |S|_i}\}$
        Furthermore, we'll let $s(i)$ denote the strategy played by agent $i$.}
     \item{For any $S' \subset S$, let $\Delta(S')$ denote the set of valid configurations of agents to strategies $s \in S'$; we represent a configuration $D(S') \in \Delta(S')$ as an $|S'|$-tuple $D(S')=\{n_1,\ldots,n_{|S'|}\}$ where $n_i$ is the number of agents playing the $i^{th}$ strategy of $S'$.}
     \item{$G$ is a directed graph with one node for each action $s_i$.  Let $\nu : S\rightarrow 2^S$, be the neighbor relation induced by graph $G$, where $s' \in \nu(s)$ if the edge $(s',s) \in G$.  Note that self-loops are allowed, and thus it is possible that $s \in \nu(s)$.  We refer to $G$ as the \emph{strategy graph} of $A$.}
     \item{The utility function $u$ assigns identical utilities to all agents playing a given strategy $s$, with the utility depending only on the number of agents playing neighboring strategies.  Formally, $u: \Delta(S) \rightarrow \mathbb{R}^{|S|}$, via maps $u_1,\ldots,u_{|S|}$ where $u_i: \Delta[\nu(s_i)] \rightarrow \mathbb{R}$ defines the common utility of all agents playing strategy $s_i$.}
\end{itemize}
\end{definition}



Note that AGGs are fully expressive because any games can be
written as an action graph game in which the strategy sets of different players are disjoint, and the strategy graph $G$ is complete.

We now define a further type of possible symmetry between agents
that will be important in our analysis of the complexity of
computing Nash equilibria.

\begin{definition}
We say that an AGG has $k$ \emph{player types} if there exists a
partition of the agents into $k$ sets $P_1,\ldots,P_k$, such that if
$p,p' \in P_i$, then $S_p = S_{p'}$.  (The terminology
of~\cite{J_LB_2007} refers to such games as $k$-symmetric AGGs.)
\end{definition}

Since agents who play the same
strategy receive the same utility, all agents of a given type are
identical---for example an AGG with a single player type is a
symmetric game.  While the number of player types does not
significantly alter the description size, decreasing the number of
player types constrains the space of possible Nash equilibria; this is the motivation for considering AGGs with few player types as a possible class of tractable games.


A \emph{strategy profile},
$M:=[m_1,\ldots, m_n]$, with $m_i =(p_{i,1},\ldots,p_{i,|S_i|})$
assigns to each agent a probability distribution over the possible
strategies that the agent may play, with $\Pr[
s(i)=s_{i,k}]=p_{i,k}$ where $s_k$ is the $k^{th}$ element of $S_i$.  Thus a given strategy profile induces an expected utility for each player $\mathbb{E}[u|M] = \sum_{D \in \Delta} u(D) \Pr(D),$ where the probability is with respect to the strategy profile $M$.

\begin{definition}
A strategy profile $M$ is a \emph{Nash-equilibrium} if no player
can increase her expected utility by changing her strategy $m_i$ given the strategy profiles $m_{-i}$ of the other agents. That is,
for all strategy profiles $m_i'$. $\mathbb{E}[u_i|m_{-i},m_i] \ge \mathbb{E}[u_i|m_{-i},m_i']$.
\end{definition}

\begin{definition}
A strategy $m\in M$ is an
$\epsilon$-\emph{Nash-equilibrium} if no player can increase her
expected utility by more than $\epsilon$ by changing her strategy profile.
\end{definition}

Note that there is the slightly stronger definition of an $\epsilon$--Nash equilibrium in which, for all agents $i$, the expected utility of playing every strategy $s$ in the support of $m_i$ is at most $\epsilon$ less than the expected utility of playing a different $s' \in S_i$.  We do not stress the distinction, as our PTAS finds such an $\epsilon$--Nash equilibrium, and our hardness results apply to the weaker definition given above. 
\subsection*{Mapping Action Graph Games to Graphical Games}
\label{sec:actiontographical}

We show the following result which reduces the problem of computing a Nash equilibrium of an action graph game to the problem of computing a Nash equilibrium of a graphical game. Since the latter is in PPAD \cite{PapParityArgument}, it follows that the former is in PPAD as well.
\begin{theorem} \label{th:generalTheoremForGames}
Any action-graph game $A$ can be mapped in polynomial time to a
graphical game $\mathcal{G}$ so that there is a polynomial-time computable
surjective mapping from the set of Nash equilibria of $\mathcal{G}$ to the set
of Nash equilibria of $A$.
\iffalse Moreover, the problem of computing a Nash equilibrium in an action-graph game is polynomial-time reducible to the problem of computing a Nash equilibrium of a 2-player game.\fi
\end{theorem}
\begin{proof}
Let us define a bounded division-free straight-line program to be an arithmetic
binary circuit with nodes performing addition, subtraction, or multiplication on their
inputs, or evaluating to pre-set constants, with the additional constraint that the values
of all the nodes remain in [0, 1].

We will show that there exists a bounded division-free staight-line program of polynomial size in the description of the action graph game which, given a mixed strategy profile $M:= \{(p_{i,1},\ldots,p_{i,|S_i|})\}_{i=1}^n$, computes, for every agent $i$, $i=1,\ldots,n$, and for every pure strategy $s_i$, $s_i \in S_i$, of that agent, the expected utility that this agent gets for playing pure strategy $s_i$. The proof then follows from Theorems 1 and 2 of \cite{DasFabPap:ICALP06}.

Without loss of generality, we will show that there exists a straight-line program of polynomial size for computing the expected utility of agent $1$ for playing pure strategy $s_{1,1}$. For this purpose, let $\mathcal{N}:=\nu(s_{1,1})$ and $\Delta:=\Delta(\nu(s_{1,1}))$. Also, for any subset $P' \subseteq P$ of the agents, let $\Delta_{P'}$ be the set of valid configurations of the agents of the set $P'$ to the strategies in $\mathcal{N}$, represented as $|\mathcal{N}|$-tuples of numbers; then, for every $D \in \Delta_{P'}$, let $\Pr_{P'}[D]$ be the probability that configuration $D$ arises from the set of agents $P'$, where the measure $\Pr_{P'}$ is taken over the mixed strategies of agents in $P'$. Using this notation, the expected payoff of agent $1$ for playing $s_{1,1}$ can be written as follows

\begin{align}
\mathcal{U}_{1,s_{1,1}}:=\sum_{D \in \Delta_{P\setminus\{1\}}} u_{s_{1,1}}(D + 1_{s_{1,1}}) \Pr{}_{P\setminus \{1\}}[D], \label{eq:costis1}
\end{align}
where $1_{s_{1,1}}$ is an $|\mathcal{N}|$-tuple of numbers having a $1$ at the coordinate corresponding to strategy $s_{1,1}$ and $0$ everywhere else, and where $D + 1_{s_{1,1}}$ represents coordinate-wise addition.


From Equation \eqref{eq:costis1}, it follows that, if there is a bounded division-free straight-line program of polynomial size which computes the values $\{\Pr{}_{P\setminus\{1\}}[D]\}_{D \in \Delta_{P\setminus\{1\}}}$, a straight-line program for computing $\mathcal{U}_{1,s_{1,1}}$ can be constructed at an additional cost of $O(|\Delta_{P\setminus\{1\}}|) = O(|A|)$ arithmetic gates. To conclude the proof, we prove the following lemma.



\begin{lemma}
Let $P_j=\{j+1,\ldots,n\} \subseteq P$ and suppose that there exists a bounded division-free staight-line program computing the values $\{\Pr_{P_j}[D]\}_{D \in \Delta_{P_j}}$. Also, suppose that the size of this straight-line program is bounded by $g$. Then there exists a straight-line program of size bounded by $g+O(|A|\cdot(|A|+|S|))$ which computes the values $\{\Pr_{P_j \cup \{j\}}[D]\}_{D \in \Delta_{P_j \cup \{j\}}}$.
\end{lemma}

\begin{proof}
Note first that $|\Delta_{P_j \cup \{j\}}| = O(|A|)$, where $|A|$ is the description size of the action graph game. Then, for every $D\in\Delta_{P_j \cup \{j\}}$, it holds that
\begin{align}
\Pr{}_{P_j \cup \{j\}} [D] &= \sum_{s_{j,k} \in S_j \setminus \mathcal{N}}{\Pr{}_{\{j\}}[\text{$j$ plays $s_{j,k}$}] \Pr{}_{P_j}[D]}\notag\\&~~~~~~~~~~~~~~~~~~~~ +\sum_{\begin{minipage}{2.5cm}\centering $s_{j,k} \in S_j \cap \mathcal{N}$,\\ $D' \in \Delta_{P_j}$:\\ $1_{s_{j,k}}+D' = D$ \end{minipage}}{ \Pr{}_{\{j\}}[1_{s_{j,k}}] \Pr{}_{P_j}[D']}, \label{eq:costis2}
\end{align}
where in the above expression $\Pr_{P_j}[D]=0$, if $D \notin \Delta_{P_j}$. Observe that in \eqref{eq:costis2} the first summation has at most $|S|$ terms and the second at most $|A|$ terms. Hence, given the values $\{\Pr_{P_j}[D]\}_{D \in \Delta_{P_j}}$, the above expression can be evaluated with $O(|A|+|S|)$ arithmetic operations. The result follows.
\end{proof}

From the lemma above it follows that there exists a straight-line program of size bounded by $O(n\cdot|A|\cdot(|A|+|S|)) = O(|A|^3)$ for computing $\{\Pr{}_{P\setminus\{1\}}[D]\}_{D \in \Delta_{P\setminus\{1\}}}$. This concludes the proof of the theorem, since all the intermediate values of the computations described above are in $[0,1]$.
\end{proof}


