On the Complexity of Nash Equilibria in Anonymous Games

Introduction

The celebrated theorem of Nash [Nas50, Nas51] states that every game has an equilibrium point. The concept of Nash equilibrium has been tremendously influential in economics and social sciences ever since (e.g., see [HR04]), and its computation has been one the most well-studied problems in the area of Algorithmic Game Theory. For normal form games with a bounded number of players, much progress has been made during the past decade in understanding both the complexity of Nash equilibrium [AKV05, CDT06, CTV07, DGP09, CDT09, Meh14] as well as its efficient approximation [LMM04, BVV05, KPS06, DMP06, DMP07, BBM07, KT07, TS07, FNS07, KS07, ABOV07, TS10].

In this paper we study a large and important class of succinct multiplayer games called anonymous games (see [Sch73, Mil96, Blo99, Blo05, Kal05] for studies of such games in the economics literature). These are special multiplayer games in that the payoff of each player depends only on (1) the pure strategy of the player herself, and (2) the number of other players playing each pure strategy, instead of the full pure strategy profile. In such a game, the (expected) payoff of a player is highly symmetric over (pure or mixed) strategies of other players. For instance, two players switching their strategies would not affect the payoff of any other player. A consequence of this very special payoff structure is that $O(\alpha n^{\alpha-1})$ numbers suffice to completely describe the payoff function of a player, when there are $\alpha$ pure strategies shared by $n$ players. Notably this is polynomial in the number of players when $\alpha$ is bounded, and hence the game is succinctly representable. Throughout the paper, we focus on succinct anonymous games with a bounded number of pure strategies.

Other well-studied multiplayer games with a succinct representation include graphical, symmetric, and congestion games (for more details see [PR08]). While graphical and congestion games are both known to be hard to solve [FPT04, ARV08, SV08], there is indeed a polynomial-time algorithm for computing an exact Nash equilibrium in a symmetric game [PR08]. Because anonymous games generalize symmetric games by allowing player-dependent payoff functions, it is a natural question to ask whether there is an efficient algorithm for finding an (exact or approximate) Nash equilibrium in an anonymous game as well.

Culminating in a sequence of beautiful papers [DP07, Das08, DP08, DP09, DP14] Daskalakis and Papadimitriou obtained a polynomial-time approximation scheme (PTAS) for $\epsilon$-approximate Nash equilibria in anonymous games with a bounded number of strategies (see more discussion on related work in Section 1.1). However, the complexity of finding an exact Nash equilibrium in such games remains open, and was conjectured to be hard for PPAD in [DP09, DP14]. When the number of pure strategies is a sufficiently large constant, an anonymous game with rational payoffs may not have any rational equilibrium (e.g., by embedding in it a rational three-player game with no rational equilibrium). But for the case of two strategies, it remains unclear as whether every rational anonymous game has a rational Nash equilibrium, which was posed as an open problem in [DP14].

In this paper we give an affirmative answer to the conjecture of Daskalakis and Papadimitriou, by showing that it is PPAD-complete to find an $\epsilon$-approximate Nash equilibrium in an anonymous game, when the approximation parameter $\epsilon$ is exponentially small in $n$. To formally state our main result, let $(\alpha,c)$-Anonymous denote the problem of finding a $(2^{-n^{c}})$-approximate Nash equilibrium in an anonymous game with $\alpha$ pure strategies and payoffs from $$. Since we are interested in the additive approximation, all payoffs are normalized to take values in$$.

For any $\alpha\geq 7$ and $c>0$, the problem $(\alpha,c)$-Anonymous is PPAD-complete.

The greatest challenge to establishing the PPAD-completeness result stated above is posed by the rather complex but also highly symmetric payoff structure of anonymous games. Before discussing our approach and techniques in Section 1.3, we first review related work in Section 1.1, then define anonymous games formally and introduce some useful notation in Section 1.2.

Anonymous games have been studied extensively in the economics literature [Sch73, Ras83, Mil96, Blo99, Blo05, Kal05, ES05], where the game being considered is usually nonatomic and consists of a continuum of players but a finite number of strategies. For the discrete setting, two special families of anonymous games are symmetric games [PR08, BFH09] and congestion games [Ros73]. [PR08] gave a polynomial-time for finding an exact Nash equilibrium in a symmetric game. For congestion games, PLS-completeness of pure equilibria was established in [FPT04, ARV08, SV08] These PLS-hardness results have no implication to the setup of this paper since the number of pure strategies in the congestion games considered there are unbounded., and efficient approximation algorithms for various latency functions were obtained in [CFGS11, CFGS12, CS11].

While an anonymous game does not possess a pure Nash equilibrium in general, it was shown in [DP07, AS11, DP14] that when the payoff functions are $\lambda$-Lipschitz, there exists an $\epsilon$-approximate pure Nash equilibrium and it can be found in polynomial time, where $\epsilon$ has a linear dependency on $\lambda$. Furthermore, in [Bab13] Babichenko presented a best-reply dynamic for $\lambda$-Lipschitz anonymous games with two strategies which reaches an approximate pure equilibrium in $O(n\log n)$ steps.

Regarding our specific point of interest, i.e., (mixed) Nash equilibria in anonymous games with a scaling number of players but a non-scaling number of strategies, there have been a sequence of positive and negative results obtained by Daskalakis and Papadimitriou [DP07, DP08, Das08, DP09] (summarized in the journal version [DP14]). We briefly review these results below.

In [DP07], Daskalakis and Papadimitriou presented a PTAS for finding an $\epsilon$-approximate Nash equilibrium in an anonymous game with two pure strategies, with running time $n^{O(1/\epsilon^{2})}\cdot U$, where $U$ denotes the number of bits required to describe the payoffs. The running time was subsequently improved in [Das08] to $\text{poly}(n)\cdot(1/\epsilon)^{O(1/\epsilon^{2})}\cdot U$. The first PTAS in [DP07] is based on the existence of an $\epsilon$-approximate Nash equilibrium consisting of integer multiples of $\epsilon^{2}$, while the second PTAS in [Das08] is based on the existence of an $\epsilon$-approximate Nash equilibrium satisfying the following special property: either at most $O(1/\epsilon^{3})$ players play mixed strategies, or all players who mix play the same mixed strategy. Later [DP08] extended the result of [DP07], giving the only known PTAS for anonymous games with any bounded number of pure strategies with time $n^{g(\alpha,1/\epsilon)}\cdot U$ for some function $g$ of $\alpha$, number of pure strategies, and $1/\epsilon$.

All three PTAS obtained in [DP07, Das08, DP08] are so-called oblivious algorithms [DP09], i.e., algorithms that enumerate a set of mixed strategy profiles that is independent of the input game as candidates for approximate Nash equilibria (hence, the game is used only to verify if a given mixed strategy profile is an $\epsilon$-approximate Nash equilibrium). In [DP09], Daskalakis and Papadimitriou showed that any oblivious algorithm for anonymous games must have running time exponential in $1/\epsilon$. In contrast to this negative result, they also presented a non-oblivious PTAS for two-strategy anonymous games with running time $\text{poly}(n)\cdot(1/\epsilon)^{O(\log^{2}(1/\epsilon))}\cdot U$.

2 Anonymous Games and Polymatrix Games

Before giving a high-level description of our approach and techniques in Section 1.3, we first give a formal definition of anonymous games and introduce some useful notation. Consider a multiplayer game with $n$ players $[n]=\{1,\ldots,n\}$ and $\alpha$ pure strategies $[\alpha]=\{1,\ldots,\alpha\}$ with $\alpha$ being a constant. For each pure strategy $b\in[\alpha]$, let $\psi_{b}(\mathbf{t})$ denote the number of $b$’s in a tuple $\mathbf{t}\in[\alpha]^{n-1}$, and define $\Psi(\mathbf{t})=(\psi_{1}(\mathbf{t}),\ldots,\psi_{\alpha}(\mathbf{t})),$ which we will refer to as the histogram of pure strategies in $\mathbf{t}$.

In an anonymous game, the payoff of each player $p\in[n]$ depends only on $\Psi(\mathbf{s}_{-p})$ and her own strategy $s_{p}$, given a pure strategy profile $\mathbf{s}\in[\alpha]^{n}$. (We follow the convention and use $\mathbf{s}_{-p}\in[\alpha]^{n-1}$ to denote the pure strategy profile of the $n-1$ players other than player $p$ in $\mathbf{s}$.) Informally, $\Psi(\mathbf{s}_{-p})$ can be described as what player $p$ “sees” in the game when $\mathbf{s}$ is played.

is the set of all histograms of pure strategies played by $n-1$ players. Specifically, when $\mathbf{s}\in[\alpha]^{n}$ is played, the payoff of player $p$ is given by $\textsf{\emph{payoff}}_{p}(s_{p},\Psi(\mathbf{s}_{-p}))$.

As usual, a mixed strategy is a probability distribution $\mathbf{x}=(x_{1},\ldots,x_{\alpha})$, and a mixed strategy profile ${\mathcal{X}}$ is an ordered tuple of $n$ mixed strategies $(\mathbf{x}_{p}:p\in[n])$, one for each player $p$. Given ${\mathcal{X}}$, let $u_{p}(b,{\mathcal{X}})$ denote the expected payoff of $p$ playing $b\in[\alpha]$, which has the following explicit expression:

where $\text{Pr}_{{\mathcal{X}}}[p,\mathbf{k}]$ denotes the probability of player $p$ seeing histogram $\mathbf{k}$ under ${\mathcal{X}}$:

Note that $s_{q}$ denotes the pure strategy of player $q$ from a profile $\mathbf{s}_{-p}\in\Psi^{-1}(\mathbf{k})$. We also use $u_{p}({\mathcal{X}})$ to denote the expected payoff of player $p$ from playing $\mathbf{x}_{p}$:

It is worth pointing out that, while $u_{p}(b,{\mathcal{X}})$ contains exponentially many terms, it can be computed in polynomial time using dynamic programming [DP07, DP14] when $\alpha$ is a constant. For a detailed presentation of the algorithm for $2$-strategy anonymous games, see [DP14]. This then implies that checking whether a given profile $\mathcal{X}$ is a (approximate) Nash equilibrium is in polynomial time.

Next we define (approximate) Nash equilibria of an anonymous game.

Given an anonymous game $\mathcal{G}=(n,\alpha,\{\textsf{\emph{payoff}}_{p}\})$, we say a mixed strategy profile $\mathcal{X}$ is a Nash equilibrium of $\mathcal{G}$ if $u_{p}(\mathcal{X})\geq u_{p}(b,\mathcal{X})$ for all players $p\in[n]$ and strategies $b\in[\alpha]$.

For $\epsilon\geq 0$, we say $\mathcal{X}$ is an $\epsilon$-approximate Nash equilibrium if $u_{p}(\mathcal{X})+\epsilon\geq u_{p}(b,\mathcal{X})$ for all $p\in[n]$ and $b\in[\alpha]$. For $\epsilon\geq 0$, we say $\mathcal{X}$ is an $\epsilon$-well-supported Nash equilibrium if $u_{p}(a,\mathcal{X})+\epsilon<u_{p}(b,\mathcal{X})$ implies that $x_{p,a}=0$, for all $p\in[n]$ and $a,b\in[\alpha]$.

for all players $i\in[n]$. We need the following result on such games:

The problem of computing a $(1/n)$-well-supported Nash equilibrium in a polymatrix game is PPAD-complete.

3 Our Approach and Techniques

A commonly used approach to establishing the PPAD-hardness of approximate equilibria is to design gadget games that can perform certain arithmetic operations on entries of mixed strategies of players (e.g. see [DGP09, CDT09]). Such gadgets would then yield a reduction from the problem of solving a generalized circuit [DGP09, CDT09], a problem complete in PPAD. However, we realized that this approach may not work well with anonymous games; we found that it was impossible to design an anonymous game $G_{=}$ that enforces equality constraints. For example, we can rule out the existence of an anonymous game $G_{=}$ with 4 players and 2 pure strategies such that $\mathbf{x}$ is a Nash equilibrium of $G_{=}$ if and only if $x_{1}=x_{2}\in[\mu,\nu]\subseteq$ and $x_{3}=x_{4}\in[\mu^{\prime},\nu^{\prime}]\subseteq$, where we use $x_{i}$ to denote the probability that player $i$ plays the first pure strategy.

Instead we show the PPAD-hardness of anonymous games via a reduction from the problem of finding a $(1/n)$-well-supported equilibrium in a two-strategy polymatrix game (see Section 1.2). Given a $2n\times 2n$ polymatrix game $\mathbf{A}$, our reduction constructs an anonymous game $\mathcal{G}_{\mathbf{A}}$ with $n$ “main” players $\{P_{1},\ldots,P_{n}\}$ (and two auxiliary players). We have each main player $P_{i}$ simulate in a way a player $i$ in the polymatrix game, as discussed below, such that any $\epsilon$-well-supported Nash equilibrium of $\mathcal{G}_{\mathbf{A}}$ with an exponentially small $\epsilon$ can be used to recover a $(1/n)$-well-supported Nash equilibrium of the polymatrix game $\mathbf{A}$ efficiently. We then prove a connection between approximate Nash equilibria and well-supported Nash equilibria of anonymous games to finish the proof of Theorem 1.

The greatest challenge to establishing such a reduction is posed by the complex but highly structured, symmetric expression of expected payoffs in an anonymous game. As discussed previously in Section 1.2, the expected payoff $u_{p}(b,\mathcal{X})$ of player $p$ is a linear form of probabilities $\text{Pr}_{\cal{X}}[p,\mathbf{k}]$, each of which is function over mixed strategies of all players other than $p$. This rather complex function makes it difficult to reason about the set of well-supported Nash equilibria of an anonymous game, not to mention our goal is to embed a polymatrix game in it. To overcome this obstacle, we need to find a special (but hard enough) family of anonymous games with certain payoff structures which allow us to perform a careful analysis and understand their well-supported equilibria. The bigger obstacle for our reduction, however, is to in some sense remove the anonymity of the players and break the inherent symmetry underlying an anonymous game.

To see this, a natural approach to obtain a reduction from polymatrix games is to directly encode the $2n$ variables of $\mathbf{y}$ in mixed strategies of the $n$ “main” players $\{P_{1},\ldots,P_{n}\}$. More specifically, let $\{s_{1},s_{2}\}$ denote two special pure strategies of $\mathcal{G}_{\mathbf{A}}$, and we attempt to encode $(y_{2i-1},y_{2i})$ in $(x_{i,s_{1}},x_{i,s_{2}})$, probabilities of $P_{i}$ playing $s_{1},s_{2}$, respectively. The reduction would work if expected payoffs of $P_{i}$ from $s_{1}$ and $s_{2}$ in $\mathcal{G}_{\mathbf{A}}$ can always match closely expected payoffs of player $i$ from rows $2i-1$ and $2i$ in $\mathbf{A}$, given by two linear forms $\mathbf{A}_{2i-1}\cdot\mathbf{y}$ and $\mathbf{A}_{2i}\cdot\mathbf{y}$ of $\mathbf{y}$. However, it seems difficult, if not impossible, to construct $\mathcal{G}_{\mathbf{A}}$ with this property, since anonymous games are highly symmetric: the expected payoff of $P_{i}$ is a symmetric function over mixed strategies of all other players. This is not the case for polymatrix games: a linear form such as $\mathbf{A}_{2i}\cdot\mathbf{y}$ in general has different coefficients for different variables, so different players contribute with different weights to the expected payoff of a player (and the problem of finding a well-supported equilibrium in $\mathbf{A}$ clearly becomes trivial if we require that every row of $\mathbf{A}$ has the same entry).

An alternative approach is to encode the $2n$ variables of $\mathbf{y}$ in probabilities $\text{Pr}_{\cal{X}}[p,\mathbf{k}]$. This may look appealing because expected payoffs $u_{p}(b,\mathcal{X})$ are linear forms of these probabilities so one can set the coefficients $\textsf{payoff}_{p}(b,\mathbf{k})$ to match them easily with those linear forms $\mathbf{A}_{j}\cdot\mathbf{y}$ that appear in the polymatrix game $\mathbf{A}$. However, the histogram $\mathbf{k}$ seen by a player $p$ (as a vector-valued random variable) is the sum of $n-1$ vector-valued random variables, each distributed according to the mixed strategy of a player other than $p$. The way these probabilities $\text{Pr}_{\cal{X}}[p,\mathbf{k}]$ are derived in turn imposes strong restrictions on them, For example, as it is pointed out in [DP07, DP08] for anonymous games with two strategies, players can always be partitioned into a few sets such that the probabilities $\text{Pr}_{\cal{X}}[p,\mathbf{k}]$ over $\mathbf{k}$ must follow approximately a Poisson or a discretized Normal distribution on each set respectively. which makes it a difficult task to obtain a correspondence between the $2n$ free variables in $\mathbf{y}$ and the probabilities $\text{Pr}_{\cal{X}}[p,\mathbf{k}]$.

Our reduction indeed follows the first approach of encoding $(y_{2i-1},y_{2i})$ in $(x_{i,s_{1}},x_{i,s_{2}})$ of player $P_{i}$. More exactly, the former is the normalization of the latter into a probability distribution. Now to overcome the difficulty posed by symmetry, we enforce the following “scaling” property in every well-supported Nash equilibrium $\mathcal{X}$ of $\mathcal{G}_{\mathbf{A}}$: probabilities of $P_{i}$ playing $\{s_{1},s_{2}\}$ satisfy

where $N$ is exponentially large in $n$. This property is established by designing an anonymous game called generalized radix game $\mathcal{G}_{n,N}^{*}$, and then using it as the base game in the construction of $\mathcal{G}_{\mathbf{A}}$. We show that (1) holds approximately for every anonymous game that is payoff-wise close to $\mathcal{G}_{n,N}^{*}$. In particular, (1) holds for any well-supported equilibrium of $\mathcal{G}_{\mathbf{A}}$, as long as we make sure $\mathcal{G}_{\mathbf{A}}$ is close to $\mathcal{G}_{n,N}^{*}$. The “scaling” property plays a crucial role in our reduction because, as the base game for $\mathcal{G}_{\mathbf{A}}$, it helps us reason about well-supported Nash equilibria of $\mathcal{G}_{\mathbf{A}}$; it also removes anonymity of the $n$ “main” players $P_{i}$ (since they must play the two special pure strategies $\{s_{1},s_{2}\}$ with probabilities of different scales) and overcome the symmetry barrier.

Equipped with the “scaling” property (1), we prove a key technical lemma called the estimation lemma. It shows that one can compute efficiently coefficients of a linear form over probabilities of histograms $\text{Pr}_{\mathcal{X}}[P_{i},\mathbf{k}]$ seen by player $P_{i}$, which guarantees to approximate additively $x_{j,s_{1}}$ (or $x_{j,s_{2}}$) i.e. probability of another player $P_{j}$ plays $s_{1}$ (or $s_{2}$), whenever the profile $\mathcal{X}$ satisfies the “scaling” property (this holds when $\mathcal{G}_{\mathbf{A}}$ is close to $\mathcal{G}_{n,N}^{*}$ and $\mathcal{X}$ is a well-supported equilibrium of $\mathcal{G}_{\mathbf{A}}$). As

given (1), these linear forms for $x_{j,s_{1}},x_{j,s_{2}}$ can be combined to derive a linear form of $\text{Pr}_{\mathcal{X}}[P_{i},\mathbf{k}]$ to approximate additively any linear form of $\mathbf{y}$, particularly $\mathbf{A}_{2i-1}\cdot\mathbf{y}$ or $\mathbf{A}_{2i}\cdot\mathbf{y}$ that appear as expected payoffs of player $i$ in the polymatrix game $\mathbf{A}$. The proof of the estimation lemma is the technically most involved part of the paper. We indeed derive explicit expressions for coefficients of the desired linear form where substantial cancellations yield an additive approximation of $x_{j,s_{1}}$ or $x_{j,s_{2}}$.

Finally we combine all ingredients highlighted above to construct an anonymous game $\mathcal{G}_{\mathbf{A}}$ from polymatrix game $\mathbf{A}$. This is done by first using the estimation lemma to compute, for each main $P_{i}$ coefficients of linear forms of probabilities $\text{Pr}_{\mathcal{X}}[P_{i},\mathbf{k}]$ seen by $P_{i}$ that yield additive approximations of $x_{j,s_{1}}$ and $x_{j,s_{2}}$. We then perturb payoff functions of players $P_{i}$ in the generalized radix game $\mathcal{G}_{n,N}^{*}$ using these coefficients so that 1) the resulting game $\mathcal{G}_{\mathbf{A}}$ is close to $\mathcal{G}_{n,N}^{*}$ and thus, any well-supported equilibrium $\mathcal{X}$ of $\mathcal{G}_{\mathbf{A}}$ automatically satisfies the “scaling” property; 2) expected payoffs of $P_{i}$ playing $s_{1},s_{2}$ in a well-supported equilibrium $\mathcal{X}$ of $\mathcal{G}_{\mathbf{A}}$ match additively expected payoffs of player $i$ playing rows $2i-1,2i$ in $\mathbf{A}$, given $\mathbf{y}$ derived from $\mathcal{X}$ by normalizing $(x_{j,s_{1}},x_{j,s_{2}})$ for each $j$. The correctness of the reduction, i.e., $\mathbf{y}$ is a $(1/n)$-well-supported equilibrium of $\mathbf{A}$ whenever $\mathcal{X}$ is an $\epsilon$-well-supported equilibrium of $\mathcal{G}_{\mathbf{A}}$ with an exponentially small $\epsilon$, follows from these properties of $\mathcal{G}_{\mathbf{A}}$.

4 Organization

In Section 2, we define the radix game, and show that it has a unique Nash equilibrium as a warm-up. We also use it to define the generalized radix game which serves as the base of our reduction. In section 3, we characterize well-supported Nash equilibria of anonymous games that are close to the generalized radix game (i.e., those that can be obtained by adding small perturbations to payoffs of the generalized radix game). In section 4, we prove the PPAD-hardness part of the main theorem. Our reduction relies on a crucial technical lemma, called the estimation lemma, which we prove in Section 5. We prove the membership in Section 6, and conclude with open problems in Section 7.

Warm-up: Radix Game

In this section, we first define a $(n+2)$-player anonymous game $\mathcal{G}_{n,N}$, called the radix game. As a warmup for the next section, we show that it has a unique Nash equilibrium. We then use the radix game to define the generalized radix game $\mathcal{G}_{n,N}^{*}$, by making a duplicate of a pure strategy in $\mathcal{G}_{n,N}$. The latter will serve as the base game for our polynomial-time reduction from polymatrix games.

The radix game $\mathcal{G}_{n,N}$ to be defined has a unique Nash equilibrium of a specific form: given $N\geq 2$ as an integer parameter of the game, each of the $n$ “main” players mixes over the first two strategies with probabilities $1/N^{i}$ and $1-1/N^{i}$, respectively, for each $i\in[n]$, in the unique Nash equilibrium. The remaining two “special” players are created to achieve the aforementioned property.

Let $n\geq 1$ and $N\geq 2$ denote two integer parameters. Let $\delta=1/N$.

Let $\mathcal{G}_{n,N}$ denote the following anonymous game with $n+2$ players $\{P_{1},\ldots,P_{n},Q,R\}$ and $6$ pure strategies $\{s,t,q_{1},q_{2},r_{1},r_{2}\}$. We refer to $\{P_{1},\ldots,P_{n}\}$ as the main players. Each main player $P_{i}$ is only interested in strategies $s$ and $t$ (e.g., by setting her payoff of playing any other four actions to be $-1$ no matter what other players play). Player $Q$ is only interested in strategies $\{q_{1},q_{2}\}$, and player $R$ is only interested in strategies $\{r_{1},r_{2}\}$.

Next we define the payoff function of each player. When describing the payoff of a player below we always use $\mathbf{k}=(k_{s},k_{t},k_{q_{1}},k_{q_{2}},k_{r_{1}},k_{r_{2}})$ to denote the histogram of strategies this player sees.

For each $i\in[n]$, the payoff of player $P_{i}$ when she plays $s$ only depends on $k_{s}$:

The payoff of player $P_{i}$ when she plays $t$ only depends on $k_{r_{1}}$:

The payoff of player $Q$ when she plays $q_{1}$ or $q_{2}$ is given by

The payoff of player $R$ when she plays $r_{1}$ or $r_{2}$ is given by

This finishes the definition of the radix game $\mathcal{G}_{n,N}$.

$\mathcal{G}_{n,N}$ is an anonymous game with payoff functions taking values from $$.

Since the main players $P_{i}$ are only interested in $\{s,t\}$, $Q$ is only interested in $\{q_{1},q_{2}\}$, and $R$ is only interested in $\{r_{1},r_{2}\}$, each Nash equilibrium $\mathcal{X}$ of $\mathcal{G}_{n,N}$ can be fully specified by a $(n+2)$-tuple $\mathcal{X}=(x_{1},\ldots,x_{n},y,z)\in^{n+2}$, where $x_{i}$ denotes the probability of $P_{i}$ playing strategy $s$ for each $i\in[n]$, $y$ denotes the probability of $Q$ playing $q_{1}$, and $z$ denotes the probability of $R$ playing $r_{1}$.

Given $\mathcal{X}=(x_{1},\ldots,x_{n},y,z)$ we calculate the expected payoff of each player as follows (we skip $\mathcal{X}$ in the expected payoffs $u_{p}(b,\mathcal{X})$, when $\mathcal{X}$ is clear from the context, and we use $u_{i}$ to denote the expected payoff of $P_{i}$ instead of $u_{P_{i}}$ for convenience):

Given $\mathcal{X}=(x_{1},\ldots,x_{n},y,z)$, the expected payoff of player $P_{i}$ for playing $s$ is

The expected payoff of $P_{i}$ for playing $t$ is $u_{i}(t)=2z$.

The expected payoff of player $Q$ for playing $q_{1}$ is

The expected payoff of $Q$ for playing $q_{2}$ is $u_{Q}(q_{2})=z$.

The expected payoff of $R$ for playing $r_{1}$ is $u_{R}(r_{1})=y$ and that for $r_{2}$ is $u_{R}(r_{2})=1-y$.

We show that $x_{i}=\delta^{i}$ in a Nash equilibrium $\mathcal{X}$ of $\mathcal{G}_{n,N}$. We start with the following lemma.

In a Nash equilibrium $\mathcal{X}=(x_{1},\ldots,x_{n},y,z)$ of $\mathcal{G}_{n,N}$, we have that $z=\prod_{i\in[n]}x_{i}$.

Assume for contradiction that $z>\prod_{i}x_{i}$. As $u_{Q}(q_{2})>u_{Q}(q_{1})$ and $\mathcal{X}$ is a Nash equilibrium, player $Q$ never plays $q_{1}$ and thus, $y=0$. This in turn implies $u_{R}(r_{2})=1>0=u_{R}(r_{1})$ and $z=0$, which contradicts with the assumption that $z>\prod_{i}x_{i}\geq 0$.

Next, assume for contradiction that $z<\prod_{i}x_{i}$, giving us that $u_{Q}(q_{2})<u_{Q}(q_{1})$. Player $Q$ never plays $q_{2}$ and $y=1$. This implies that $u_{R}(r_{1})>u_{R}(r_{2})$ and thus $z=1$, which contradicts with the assumption that $z<\prod_{i}x_{i}\leq 1$ (as $x_{i}\in$). This finishes the proof of the lemma. ∎

We now show that the radix game $\mathcal{G}_{n,N}$ has a unique Nash equilibrium $\mathcal{X}$ with $x_{i}=\delta^{i}$.

In a Nash equilibrium $\mathcal{X}=(x_{1},\ldots,x_{n},y,z)$ of $\mathcal{G}_{n,N}$, we have $x_{i}=\delta^{i}$ for all $i\in[n]$.

First we show that $\prod_{i\in[n]}x_{i}=\prod_{i\in[n]}\delta^{i}$. Consider for contradiction the following two cases:

Case 1: $\prod_{i\in[n]}x_{i}<\prod_{i\in[n]}\delta^{i}$. Then there is an $i\in[n]$ such that $x_{i}<\delta^{i}$. For $P_{i}$, we have

This implies that $x_{i}=1$, contradicting with the assumption that $x_{i}<\delta^{i}<1$ as $N\geq 2$.

Case 2: $\prod_{i\in[n]}x_{i}>\prod_{i\in[n]}\delta^{i}$. Then there is an $i\in[n]$ such that $x_{i}>\delta^{i}$. For $P_{i}$, we have

This implies that $x_{i}=0$, contradicting with the assumption that $x_{i}>\delta^{i}>0$.

As a result, we must have $\prod_{i}x_{i}=\prod_{i}\delta^{i}$, which also implies that $x_{i}>0$ for all $i\in[n]$.

Now we show that $x_{i}=\delta^{i}$ for all $i$. Assume for contradiction that $x_{i}\neq\delta^{i}$ for some $i\in[n]$.

Case 1: $x_{i}<\delta^{i}$. Then the same strict inequality (2) holds for $P_{i}$, which implies that $x_{i}=1$, contradicting with the assumption that $x_{i}<\delta^{i}<1$ as $N\geq 2$.

Case 2: $x_{i}>\delta^{i}$. Then the same strict inequality (3) holds for $P_{i}$, which implies that $x_{i}=0$, contradicting with the assumption that $x_{i}>\delta^{i}>0$.

Notice that Lemma 7 and 8 together imply that $\mathcal{G}_{n,N}$ has a unique Nash equilibrium because of Lemma 7 as well as the fact that $0<z<1$ implies $u_{R}(r_{1})=y=1-y=u_{R}(r_{2})$ and thus $y=1/2$.

2 Generalized Radix Game

We use $\mathcal{G}_{n,N}$ to define an anonymous game $\mathcal{G}^{*}_{n,N}$, called the generalized radix game, with the same set of $n+2$ players $\{P_{1},\ldots,P_{n},Q,R\}$ but seven strategies $\{s_{1},s_{2},t,q_{1},q_{2},r_{1},r_{2}\}$. To this end, we replace strategy $s$ in $\mathcal{G}_{n,N}$ with two of its duplicate strategies $s_{1},s_{2}$ in $\mathcal{G}^{*}_{n,N}$ and make sure that the players in $\mathcal{G}^{*}_{n,N}$ treat both $s_{1}$ and $s_{2}$ the same as the old strategy $s$, and have their payoff functions derived from those of players in $\mathcal{G}_{n,N}$ in this fashion. We will show in the next section that in any Nash equilibrium of $\mathcal{G}^{*}_{n,N}$, player $P_{i}$ must have probability exactly $\delta^{i}$ distributed among $s_{1},s_{2}$.

For readers who are familiar with previous PPAD-hardness results of Nash equilibria in normal form games [DGP09, CDT09], this is the same trick used to derive the game generalized matching pennies from matching pennies. We define $\mathcal{G}^{*}_{n,N}$ formally as follows.

Let $n\geq 1$ and $N\geq 2$ be two parameters. Let $\delta=1/N$. We use $\mathcal{G}^{*}_{n,N}$ to denote an anonymous game with the same $n+2$ players $\{P_{1},\ldots,P_{n},Q,R\}$ as $\mathcal{G}_{n,N}$ but now $7$ pure strategies $\{s_{1},s_{2},t,q_{1},q_{2},r_{1},r_{2}\}$. The payoff function $\emph{{payoff}}_{T}^{*}$ of a player $T$ in $\mathcal{G}^{*}_{n.N}$ is defined using $\emph{{payoff}}_{T}$ of the same player $T$ in $\mathcal{G}_{n,N}$ as follows:

where $\phi(s_{1})=\phi(s_{2})=s$ and $\phi(b)=b$ for every other pure strategy.

Since the payoff of player $P_{i}$ is always $-1$ when playing $q_{1},q_{2},r_{1}$ or $r_{2}$, she is only interested in $s_{1},s_{2}$ and $t$. Similarly $Q$ is only interested in $q_{1},q_{2}$ and $R$ is only interested in $r_{1},r_{2}$. As a result, a Nash equilibrium $\mathcal{X}$ of $\mathcal{G}^{*}_{n,N}$ can be fully specified by $2n+2$ numbers $(x_{i,1},x_{i,2},y,z:i\in[n])$, where $x_{i,1}$ (or $x_{i,2}$) denotes the probability of $P_{i}$ playing strategy $s_{1}$ (or strategy $s_{2}$, respectively), so the probability of $P_{i}$ playing $t$ is $1-x_{i,1}-x_{i,2}$. We also let $x_{i}=x_{i,1}+x_{i,2}$ for each $i\in[n]$.

Given the definition of $\mathcal{G}^{*}_{n,N}$ from $\mathcal{G}_{n,N}$, Lemma 8 suggests $x_{i}=x_{i,1}+x_{i,2}=\delta^{i}$, for all $i\in[n]$, in every Nash equilibrium $\mathcal{X}$ of $\mathcal{G}^{*}_{n,N}$. This indeed follows from the main lemma of the next section concerning $\epsilon$-well-supported Nash equilibria of not only the generalized radix game $\mathcal{G}_{n,N}^{*}$ itself, but also anonymous games obtained by perturbing payoff functions of $\mathcal{G}_{n,N}^{*}$.

Generalized Radix Game after Perturbation

For $\xi\geq 0$, we say an anonymous game $\mathcal{G}$ is $\xi$-close to $\mathcal{G}_{n,N}^{*}$ if

$\mathcal{G}$ has the same set $\{P_{1},\ldots,P_{n},Q,R\}$ of players and same set of $7$ strategies as $\mathcal{G}_{n,N}^{*}$.

For each player $T\in\{P_{1},\ldots,P_{n},Q,R\}$, her payoff function $\emph{{payoff}}_{T}$ in $\mathcal{G}$ satisfies

for all $b\in\{s_{1},s_{2},t,q_{1},q_{2},r_{1},r_{2}\}$ and all histograms $\mathbf{k}$ of strategies played by $n+1$ players.

To characterize $\epsilon$-well-supported Nash equilibria of a game $\mathcal{G}$ $\xi$-close to $\mathcal{G}_{n,N}^{*}$ we first show that when $\epsilon$, $\xi$ are small enough, each player in $\mathcal{G}$ remains only interested in a subset of strategies, i.e., $\{s_{1},s_{2},t\}$ for $P_{i}$, $\{q_{1},q_{2}\}$ for $Q$, and $\{r_{1},r_{2}\}$ for $R$, in any $\epsilon$-well-supported Nash equilibrium of $\mathcal{G}$.

Let $\mathcal{G}$ be an anonymous game $\xi$-close to $\mathcal{G}_{n,N}^{*}$ for some $\xi\geq 0$. When $2\hskip 0.56917pt\xi+\epsilon<1$, every $\epsilon$-well-supported Nash equilibrium of $\mathcal{G}$ satisfies: player $P_{i}$ only plays $\{s_{1},s_{2},t\}$; player $Q$ only plays $\{q_{1},q_{2}\}$; player $R$ only plays $\{r_{1},r_{2}\}$.

We only prove (1) since the proof of (2) and (3) is similar.

Given an $\epsilon$-well-supported Nash equilibrium $\mathcal{X}$, as the payoff of $P_{i}$ when playing $b\notin\{s_{1},s_{2},t\}$ is always $-1$ in $\mathcal{G}_{n,N}^{*}$, her expected payoff when playing $b$ in $\mathcal{G}$ is at most $-1+\xi$; as the payoff of $P_{i}$ when playing $b\in\{s_{1},s_{2},t\}$ is always nonnegative in $\mathcal{G}_{n,N}^{*}$, her expected payoff in $\mathcal{G}$ is at least $-\xi$. It follows from $2\hskip 0.56917pt\xi+\epsilon<1$ and the assumption of $\mathcal{X}$ being an $\epsilon$-well-supported equilibrium that $P_{i}$ only plays strategies in $\{s_{1},s_{2},t\}$ with positive probability. ∎

It follows from Lemma 10 that an $\epsilon$-well-supported Nash equilibrium of $\mathcal{G}$ can be fully described by a tuple of $2n+2$ numbers $(x_{i,1},x_{i,2},y,z:i\in[n])$, when $\xi,\epsilon$ satisfy $2\hskip 0.56917pt\xi+\epsilon<1$: $x_{i,1}$ denotes the probability of $P_{i}$ playing $s_{1}$, $x_{i,2}$ denotes the probability of $P_{i}$ playing $s_{2}$, $y$ denotes the probability of $Q$ playing $q_{1}$, and $z$ denotes the probability of $R$ playing $r_{1}$.

Recall that $\delta=1/N\leq 1/2$. Let $\kappa=\prod_{i\in[n]}\delta^{i}.$ We prove the main lemma of this section.

Let $\mathcal{G}$ denote an anonymous game that is $\xi$-close to $\mathcal{G}_{n,N}^{*}$. Suppose that $\xi,\epsilon\geq 0$ satisfy

Then every $\epsilon$-well-supported Nash equilibrium of $\mathcal{G}$ satisfies $x_{i,1}+x_{i,2}=\delta^{i}\pm\tau\delta^{i}$ for all $i\in[n]$.

Let $\mathcal{X}=(x_{i,1},x_{i,2},y,z:i\in[n])$ be an $\epsilon$-well-supported Nash equilibrium of $\mathcal{G}$. For each $i\in$ $[n]$ we let $x_{i}=x_{i,1}+x_{i,2}$. Since $\mathcal{G}$ is $\xi$-close to $\mathcal{G}_{n,N}^{*}$, we have the following estimates:

The expected payoff of $P_{i}$ for playing strategy $s_{1}$ or $s_{2}$ is

where we write $k_{s_{1}},k_{s_{2}}$ to denote the numbers of players that play $s_{1},s_{2}$ respectively, as seen by player $P_{i}$ (same below). The expected payoff of $P_{i}$ for playing $t$ is $u_{i}(t)=2z\pm\xi$.

The expected payoff of $Q$ for playing $q_{1}$ is

The expected payoff of $Q$ for playing $q_{2}$ is $u_{Q}(q_{2})=z\pm\xi$.

The expected payoff of $R$ for playing $r_{1}$ is $u_{R}(r_{1})=y\pm\xi$ and for $r_{2}$ is $u_{R}(r_{2})=(1-y)\pm\xi$.

To rest of the proof follows those of Lemma 7 and Lemma 8. First we show that $z$ must satisfy

The proof is the same as that of Lemma 7, using the assumption that $\mathcal{X}$ is $\epsilon$-well-supported.

Given (5), next we show that the $x_{i}$’s satisfy

To this end we follow the proof of the first part of Lemma 8 and consider the following two cases:

Case 1: $\prod_{i\in[n]}x_{i}<\kappa-(6\xi+3\epsilon)$. Then there exists an $i\in[n]$ such that $x_{i}<\delta^{i}$. For $P_{i}$:

This implies that $P_{i}$ does not play $t$ in $\mathcal{X}$, an $\epsilon$-well-supported Nash equilibrium of $\mathcal{G}$, and thus, $x_{i}=x_{i,1}+x_{i,2}=1$, contradicting with $x_{i}<\delta^{i}<1$ as $N\geq 2$.

Case 2: $\prod_{i\in[n]}x_{i}>\kappa+(6\xi+3\epsilon)$. Then there exists an $i\in[n]$ such that $x_{i}>\delta^{i}$. For $P_{i}$:

This implies that $P_{i}$ plays neither $s_{1}$ nor $s_{2}$ and thus, we have $x_{i,1}=x_{i,2}=0$ and $x_{i}=0$ as well, contradicting with $x_{i}>\delta^{i}>0$.

By (5) and (6), $z=\kappa\pm(8\xi+4\epsilon)$. (6) also implies that $x_{i}>0$ since $\kappa>0$ and $\kappa\geq 72\xi+36\epsilon$ by (4).

Finally, assume for contradiction that either $x_{i}<(1-\tau)\delta^{i}$ or $x_{i}>(1+\tau)\delta^{i}$ for some $i\in[n]$.

Case 1: $x_{i}<(1-\tau)\delta^{i}$. Then using $\tau\leq 1/2$ and $1\leq 1/(1-\tau)\leq 2$, we have

Plugging in the definition of $\tau$ in (4), we have $u_{i}(s_{1})-u_{i}(t)>\epsilon$ and thus, $x_{i}=1$, which contradicts with the assumption that $x_{i}<(1-\tau)\delta^{i}<1$.

Case 2: $x_{i}>(1+\tau)\delta^{i}$. Then using $\tau\leq 1/2$ and $2/3\leq 1/(1+\tau)\leq 1$, we have

The same inequality holds for $u_{i}(s_{2})-u_{i}(t)$. Plugging in (4), we have $u_{i}(s_{1})-u_{i}(t)<-\epsilon$ as well as $u_{i}(s_{2})-u_{i}(t)<-\epsilon$. This in turn implies that $x_{i,1}=x_{i,2}=0$ and thus, $x_{i}=0$, which contradicts with the assumption that $x_{i}>(1+\tau)\delta^{i}>0$.

Reduction from Polymatrix Games to Anonymous Games

In this section we prove the hardness part of Theorem 1. For this purpose we present a polynomial time reduction from the problem of finding a $1/n$-well-supported Nash equilibrium in a polymatrix game to the problem of finding an $\epsilon$-well-supported Nash equilibrium in an anonymous game with $7$ strategies, for some exponentially small $\epsilon$. We first give some intuition behind this quite involved reduction in Section 4.1. Details of the reduction and the proof of its correctness are then presented in Section 4.2 and 4.3, respectively, with a key technical lemma proved in Section 5. We finish the proof of the hardness part in Section 4.4 by showing that any approximate Nash equilibrium of an anonymous game can be converted into a well-supported equilibrium efficiently (since Theorem 1 is concerned with approximate Nash equilibria).

Given as input a polymatrix game specified by a matrix $\mathbf{A}\in^{2n\times 2n}$, our goal is to construct in polynomial time an anonymous game $\mathcal{G}_{\mathbf{A}}$, and show that every $\epsilon$-well-supported Nash equilibrium of $\mathcal{G}_{\mathbf{A}}$, where $\epsilon=1/2^{n^{6}}$, can be used to recover a $(1/n)$-well-supported equilibrium of $\mathbf{A}$ in polynomial time. Note that this is not exactly the PPAD-hardness result as claimed in Theorem 1 but we will fill in the gap in Section 4.4 with some standard arguments.

Given $\mathbf{A}$, we construct $\mathcal{G}_{\mathbf{A}}$ by perturbing payoff functions of the Generalized Radix game ${\cal{G}}^{*}_{n,N}$ with $N=2^{n}$, so that $\mathcal{G}_{\mathbf{A}}$ is $\xi$-close to $\mathcal{G}^{*}_{n,N}$ for some exponentially small $\xi>0$ to be specified later. (Thus, $\mathcal{G}_{\mathbf{A}}$ has the same set of $n+2$ players $\{P_{1},\ldots,P_{n},Q,R\}$ as well as the same set of $7$ strategies $\{s_{1},s_{2},t,q_{1},q_{2},r_{1},r_{2}\}$ as $\mathcal{G}^{*}_{n,N}$.) By Lemma 10 and Lemma 11 we know that every $\epsilon$-well-supported equilibrium of $\mathcal{G}_{\mathbf{A}}$ can be fully described by a tuple $\mathcal{X}=(x_{i,1},x_{i,2},y,z:i\in[n])$ that satisfies

for each $i\in[n]$, where $\delta=1/N=1/2^{n}$.

we get a $(1/n)$-well-supported Nash equilibrium $\mathbf{y}=(y_{1},\ldots,y_{2n})$ of $\mathbf{A}$. By (7) we have

where $\xi^{*}$ is a parameter small enough to make sure that the resulting game is $\xi$-close to $\mathcal{G}_{n,N}^{*}$.

However, perturbing the generalized radix game so that (9) and (10) hold is challenging. While

Let $\mathbf{A}\in^{2n\times 2n}$ denote the input polymatrix game. We need the following parameters:

We remark that we do not attempt to optimize the parameters here but rather set them in different scales to facilitate the analysis later.

Given $\mathbf{A}\in^{2n\times 2n}$, $\cal{G}_{\mathbf{A}}$ is an anonymous game $\xi$-close to ${\cal{G}}^{*}_{n,N}$ where $\xi={2^{-n^{4}}}$.