# Approximating Nash Equilibrium in Random Graphical Games

Morris Yau<EMAIL_ADDRESS>Massachusetts Institute of Technology

###### Abstract

Computing Nash equilibrium in multi-agent games is a longstanding challenge at
the interface of game theory and computer science. It is well known that a
general normal form game in $N$ players and $k$ strategies requires
exponential space simply to write down. This Curse of Multi-Agents prompts the
study of succinct games which can be written down efficiently. A canonical
example of a succinct game is the graphical game which models players as nodes
in a graph interacting with only their neighbors in direct analogy with markov
random fields. Graphical games have found applications in wireless, financial,
and social networks. However, computing the nash equilbrium of graphical games
has proven challenging. Even for polymatrix games, a model where payoffs to an
agent can be written as the sum of payoffs of interactions with the agent’s
neighbors, it has been shown that computing an $\epsilon$ approximate nash
equilibrium is PPAD hard for $\epsilon$ smaller than a constant. The focus of
this work is to circumvent this computational hardness by considering average
case graph models i.e random graphs. We provide a quasipolynomial time
approximation scheme (QPTAS) for computing an $\epsilon$ approximate nash
equilibrium of polymatrix games on random graphs with edge density greater
than $\text{\rm poly}(k,\frac{1}{\epsilon},\ln(N))$ with high probability.
Furthermore, with the same runtime we can compute an $\epsilon$-approximate
Nash equilibrium that $\epsilon$-approximates the maximum social welfare of
any nash equilibrium of the game. Our primary technical innovation is an
”accelerated rounding” of a novel hierarchical convex program for the nash
equilibrium problem. Our accelerated rounding also yields faster algorithms
for Max-2CSP on the same family of random graphs, which may be of independent
interest.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
  3. 3 Related Work
  4. 4 A Convex Hierarchy for Nash Equilibrium
  5. 5 Rounding Algorithms
  6. 6 Propagation of Mutual Information
  7. 7 Accelerated Rounding via Polynomial Approximation
  8. 8 Best Response Pursuit
    1. 8.1 Best response preliminaries:
    2. 8.2 Best Response Rounding Proof
  9. A Feasibility of Convex Hierarchy
  10. B Explicit Convex Constraints
  11. C Best Response Pursuit Lemmas
  12. D Miscellaneous

##  1 Introduction

Beginning with the seminal works of Nash [Nas50] and Von Neumann [vNM47], game
theory has been concerned with the study of strategic interactions amongst
rational agents. In his landmark 1951 paper, Nash defined his namesake
equilibrium and proved its existence for every game in mixed strategies. Since
the 1950’s, the rise of the internet heralded a new brand of commerce for
computational ecosystems comprised of many agents. Today, the applications of
game theory span a remarkable range from cryptocurrency and blockchain
technologies to the deployment and design of 5G networks and edge devices.
These developments brought computation to the forefront of game theory,
wherein the problem of computing the Nash equilibrium of two player games came
to be of paramount importance.

Towards resolving this problem in the negative, Daskalakis, Goldberg, and
Papadimitriou [DGP06] in their oft celebrated work proved that computing two
player nash equilibrium is PPAD-hard. As is standard in theoretical computer
science, the subsequent hope is to approximate the nash equilibrium to
additive error $\epsilon$. These efforts have proven fruitful, as a
quasipolynomial time approximation scheme was achieved by Lipton, Mehta, and
Markakis [LMM03]. Despite the good news, extending these techniques to larger
numbers of players is met with an immediate obstacle.

Quite simply, the normal form game between $N$ agents taking $k$ actions
requires $k^{N}$ space to write down. Even linear time algorithms would have
runtimes exponential in $N$. Thus, an algorithmic theory of multi-agent games
would have to be married with succinct models of multi-agent interactions. A
particularly attractive modeling choice is that of the graphical game
introduced by Kearns, Littman, and Singh [KLS13]. Graphical games are a class
of games where agents are represented as nodes in a graph interacting with
their neighbors. At one extreme, every game can be modeled by interactions on
the complete graph which offers no savings in space. At the other end of the
spectrum, games played on sparse graphs can be succinctly represented and
capture settings where agents are influenced by a comparatively small set of
neighbors. This is especially relevant in network settings where devices
compete for bandwidth resources with their proximal neighbors; in financial
networks where institutions transact with peer institutions; in social
networks where agents can influence a small set of trusted associates. As
such, graphical games are practically well motivated models for mitigating
what is colloquially known as the Curse of Multi-agents.

Of course, the elephant in the room is whether Nash equilibrium can be
efficiently computed in graphical games. The answer to this question ought to
depend on the structure of the game. However, even for polymatrix games, which
are graphical games where the payoff to each agent is the sum of the payoffs
of games played with the agent’s neighbors in a graph, it is PPAD hard to
compute a nash equilibrium. Even worse for the algorithmist, Rubinstein
[Rub14] showed that it is PPAD hard to $\epsilon$-approximate the nash
equilibrium of a polymatrix game for small constant $\epsilon>0$. Moreoever,
the hard instance is a simple $3$-regular graph. This astounding negative
result stands in stark contrast with the good news enjoyed by approximation
algorithms in two player games. In light of strong negative results, the next
natural step in the theoretical computer science toolbox is to consider
average case models for games. In this work, we aim to answer the question

Does there exist a large class of average case games on graphs, for which it
is possible to design efficient

algorithms for approximating nash equilibrium?

At a high level, our answer to this question is that for polymatrix games with
smooth payoffs on random graphs that are mildly dense, approximating a nash
equilibrium is as easy as approximating the nash equilibrium of a two player
game. That is to say, there exists a quasipolynomial time approximation
scheme. The intuitive reason for this is that for a random graph with smooth
payoffs, the effect of an agents neighbors can be captured by succinct
aggregate statistics of their actions reminiscent of both mean field theory in
statistical physics and the study of maximum constraint satisfaction problems
in approximation algorithms. It is this latter family of problems from which
we draw technical inspiration.

##  2 Preliminaries

We begin by introducing some notation and defining the polymatrix game. We
will also define what it means for a payoff function to be $L$-smooth.

#### Notation:

We work with $N\in{\mathbb{Z}}^{+}$ player games where each player can adopt
one of $k\in{\mathbb{Z}}^{+}$ strategies. For a graph $G$ let $V$ and $E$ be
the vertices and edges of the graph respectively. For a node $i\in V$ let
$N(i)$ denote the set of vertices that are neighbors of $i$. Let $a_{i}\in[k]$
denote the strategy of player $i$. Let $\vec{a}\in[k]^{N}$ denote the vector
of strategies $(a_{1},a_{2},...,a_{N})$ adopted by all $N$ players. Let
$\mathcal{P}(k,V)$ be the space of probability distributions over $[k]^{N}$.
Let $\Gamma\vcentcolon=\\{\\{\mu_{ip}\\}_{p\in[k]}\\}_{i\in[N]}$ denote a
product probability distribution over $[k]^{N}$ where
$\mu_{ip}=\mathbb{P}(a_{i}=p)$. The focus of this work will be on random
graphs drawn from $G(N,p)$ where $p$ is the probability of an edge existing
between any pair of vertices. We denote the average degree $d\vcentcolon=pN$.

######  Definition 2.1.

(Polymatrix Game) A polymatrix game is specified by a graph $G=(V,E)$ over $N$
vertices denoted $V$ and edges $E$. Furthermore, a set of payoff games
$\\{p_{ij}\\}_{(i,j)\in E}$ is defined on each edge of $G$. Each payoff game
$p_{ij}:[k]^{2}\rightarrow\mathbb{R}$ takes as input a pair of actions
$(a_{i},a_{j})$ each selected from a space of $k$ discrete actions and outputs
a real valued payoff. The payoff function to player $i$ is
$p_{i}(a_{1},a_{2},...,a_{N})=\sum_{j\in N(i)}p_{ij}(a_{i},a_{j})$. Note that
$p_{ij}(a_{i},a_{j})$ is the payoff to node $i$ and $p_{ji}(a_{j},a_{i})$ is
the payoff to node $j$.

To enable a fair comparison for $\epsilon$ approximate nash equilibrium, we
will rescale the payoffs so that the payoff to each agent is in the interval
$[0,1]$. See appendix for rescaling. Henceforth we will be using
$\\{f_{ij}\\}_{(i,j)\in E}$ as the rescaled payoff functions. Next we define
$L$-smooth payoff functions.

######  Definition 2.2.

(L-Smoothness) We say a polymatrix game is $L$-smooth for a constant $L>0$ if
for all nodes $i$ and $j\in[N]$, the payoff to node $i$ for the game $f_{ij}$
is upper bounded

$\max_{p,q\in[k]^{2}}|f_{ij}(p,q)|\leqslant\frac{L}{d}$

For example, if each payoff $p_{ij}(\cdot,\cdot)\in[0,1]$ and
$\min_{\vec{a}\in[k]^{N}}p_{i}(a_{1},...,a_{N})=0$ and
$\max_{\vec{a}\in[k]^{N}}p_{i}(a_{1},...,a_{N})=d$ then the rescaled payoff
$f_{ij}(a_{i},a_{j})=\frac{p_{ij}(a_{i},a_{j})}{d}$ is $L$-smooth for $L=1$.
Next we define the mixed nash equilibrium.

######  Definition 2.3.

(Mixed Nash Equilibrium) Let
$\Gamma\vcentcolon=\\{\\{\mu_{ip}\\}_{p\in[k]}\\}_{i\in[N]}$ define a
probability distribution over $[k]$ for all agents $i\in[N]$ where
$\mathbb{P}_{\Gamma}(a_{i}=p)=\mu_{ip}$. A mixed Nash equilibrium is
distribution over mixed strategies $\Gamma$ satisfying the following
equilibrium condition.

$\mathbb{E}_{\Gamma}[f_{i}(a_{1},...,a_{n})]\geqslant\mathbb{E}_{\Gamma}[f_{i}(a_{1},...,a_{i-1},w,...,a_{n})]$

For all $w\in[k]$ and for all $i\in[n]$.

######  Definition 2.4.

(Approximate Mixed Nash Equilibrium) We define an $\epsilon$-approximate Nash
equilibrium as a product distribution over mixed strategies
$\Gamma\vcentcolon=\\{\\{\mu_{ip}\\}_{p\in[k]}\\}_{i\in[N]}$ satisfying

$\mathbb{E}_{\Gamma}[f_{i}(a_{1},...,a_{n})]\geqslant\mathbb{E}_{\Gamma}[f_{i}(a_{1},...,a_{i-1},w,...,a_{n})]-\epsilon$

For all $w\in[k]$ and for all $i\in[n]$.

Without the smoothness assumption and for general graphs $G$, it is known that
computing an $\epsilon$-approximate nash equilibrium is PPAD hard for a small
constant $\epsilon$. In fact that hard instance is a three regular graph. This
paints a bleak picture for efficient equilbrium computation in possibly the
most amenable class of graphical games. In this work we find that for
polymatrix games with $L$-smooth payoffs defined on random graphs with density
greater than $\frac{k^{8}}{\epsilon^{4}}\ln^{3}(N)$, there exists a
$(Nk)^{O(\frac{L^{4}\ln(k)}{\epsilon^{4}})}$ time algorithm for finding an
$\epsilon$-approximate nash equilibrium with high probability
$1-N^{-\ln^{2}(N)}$ over the randomness in the graph.

######  Theorem 2.1 (Polymatrix Nash Equilibrium).

Let $(G,\\{p_{ij}\\}_{i,j\in[N]})$ be a polymatrix game defined on a $G$ with
rescaled and normalized payoffs $\\{f_{ij}\\}_{i,j\in[N]}$ that are
$L$-smooth. If $G$ is a random graph with edge density
$d=\frac{L^{8}k^{8}}{\epsilon^{8}}\ln^{3}(N)$. Then there is a
$(Nk)^{O(\frac{L^{4}\ln(k)}{\epsilon^{4}})}$ time deterministic algorithm for
finding an $\epsilon$-approximate nash equilibrium with high probability
$1-N^{-\ln^{2}(N)}$ over the randomness in the graph.

##  3 Related Work

There are a variety of works on approximating polymatrix nash equilibria.
Polymatrix zero sum games are polynomial time solvable [CCDP16]. Polymatrix
nash equilibrium can be approximated to a large additive constant [DFSS14].
Work on max-2CSP and combinatorial optimization via sum of squares include
[BRS11] [RT11] [GS11]. Finally, there is work on linear programming
relaxations for computing nash equilibrium [WHN16].

##  4 A Convex Hierarchy for Nash Equilibrium

#### Idealized Program:

Consider the following polynomial system $\mathcal{P}$ comprised of polynomial
inequalities in indeterminates $\\{a_{ir}\\}_{i\in[N],r\in[k]}$ where $a_{ir}$
is the indicator of the $r$’th action for player $i$. A pure nash equilibrium
is then a solution to the following polynomial system

$\mathcal{P}=\begin{cases}\sum_{j\in
N(i)}\sum_{p,q\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}-\sum_{j\in
N(i)}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}\geqslant 0&\forall w\in[k]\\\
a_{ip}^{2}-a_{ip}=0&\forall i\in[N],p\in[k]\\\
\sum_{p=1}^{k}a_{ip}-1=0&\forall i\in[N]\end{cases}$

Here the second constraint ensures $a_{ip}\in\\{0,1\\}$, which we refer to as
the ”booleanity” constraint. The third constraint ensures each agent can adopt
only one strategy, which we refer to as the ”coloring” constraint. The first
constraint is the pure nash equilibrium constraint. A pure nash equilibrium is
not guaranteed to exist so $\mathcal{P}$ is not necessarily feasible. However,
a mixed nash equilibrium is guaranteed to exist. Therefore we know there
exists a distribution over $[k]^{N}$ such that

$\mathcal{Q}=\begin{cases}\mathbb{E}_{\zeta}[\sum_{j\in
N(i)}\sum_{p,q\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}-\sum_{j\in
N(i)}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}]\geqslant 0&\forall w\in[k]\\\
\mathbb{E}_{\zeta}[a_{ip}^{2}-a_{ip}]=0&\forall i\in[N],\forall p\in[k]\\\
\mathbb{E}_{\zeta}[\sum_{p=1}^{k}a_{ip}-1]=0&\forall i\in[N]\\\
\mathbb{E}_{\zeta}[a_{ip}a_{jq}]=\mathbb{E}_{\zeta}[a_{ip}]\mathbb{E}_{\zeta}[a_{jq}]&\forall
i\neq j\in[N],\forall p,q\in[k]^{2}\end{cases}$

Here, $\mathcal{Q}$ is a set of constraints over a distribution $\zeta$ over
elements of $[k]^{N}$. The first constraint it the mixed nash equilibrium
constraint. The second and third are the booleanity and coloring constraints.
The final constraint ensures that $\zeta$ is a product distribution which
gives us a mixed strategy nash equilibrium. Indeed, a solution $\zeta$ to
constraints in $\mathcal{Q}$ would constitute a mixed Nash equilibrium.
However, finding $\zeta$ is evidently intractable. For starters we are
searching over the space of distributions over $[k]^{N}$, and the constraints
are desperately non-convex. Fortunately, there is a polynomial optimization
toolbox for satisfying constraints that take on the form of $\mathcal{Q}$.
Although an overview of polynomial optimization is beyond the scope of this
paper, we will introduce some of the fundamentals and discuss how the case of
Nash equilibrium requires conceptual modifications of the standard dogma.

#### The Relaxation Toolbox and the Problem of Feasibility:

In combinatorial optimization, one is often faced with maximizing a polynomial
subject to polynomial constraints e.g maximum cut. This reduces to solving
systems of polynomial inequalities and equalities. However, solving a
polynomial system for an ”integral” solution is NP-hard. Therefore, we must
settle for solving a convex relaxation of the original nonconvex polynomial
optimization. The convex relaxation solves for a distribution, or rather a
pseudo-distribution, over integral solutions to the original polynomial
optimization. After designing and solving the convex relaxation, a rounding
algorithm takes as input the pseudo-distribution (a distribution over large
cuts) and aims to produce an approximate solution to the original problem e.g
finding a large cut. The key problem with designing a convex relaxation for
Nash equilibrium is that the integral solution, the pure nash equilibrium, is
not guaranteed to exist. This is more than a technicality, as both the Sherali
Adams and Sum of Squares hierarchies of $\mathcal{P}$ are infeasible.

Alternatively, one may be motivated to relax the mixed nash equilibrium as
it’s guaranteed to exist and is also the object we are searching for. However,
this introduces a layer of misdirection that is hard to conceptually reason
about. If we’re searching for a distribution over $[k]^{N}$, then the
relaxation is attempting to find a pseudo-distribution over distributions over
$[k]^{N}$. Such an approach is hard to reason about and it is not the one
taken in this work. Rather, we search for mixed nash equilibrium by
identifying a simple fact about correlated equilibria.

#### Conditioning Preserving Correlated Equilibrium

A correlated equilibrium is a distribution $\zeta$ over $[k]^{N}$. An action
vector $\vec{a}=(a_{1},a_{2},...,a_{N})\in[k]^{N}$ is drawn from a
distribution $\zeta$ such that each agent $i\in[N]$ plays action $a_{i}$. The
distribution $\zeta$ satisfies that each agent $i$ has no incentive to deviate
from its prescribed action $a_{i}\in[k]$ given that all other agents take
actions drawn from $\zeta$ conditioned on $a_{i}$ denoted $\zeta|_{a_{i}}$.
The key insight is the following fact.

In an $L$-smooth polymatrix game on a $G(N,p)$ random graph for
$p\geqslant\frac{L^{8}k^{8}}{\epsilon^{8}}\ln^{3}(N)$, any correlated
equilibrium that remains a correlated equilibrium after conditioning on all
possible actions of all possible small subsets of agents is approximately a
mixed nash equilibrium over the agents whose actions are not conditioned upon.

At a high level, a correlated equilibrium is not a Nash equilibrium because
the distribution $\zeta$ over $[k]^{N}$ is not a product distribtution.
However, if we take a correlated equilibrium and condition $\zeta$ on the
action of a random agent $a_{i}$, then the total entropy of $\zeta|_{a_{i}}$
decreases which brings it closer to being a product distribution. It stands to
reason that conditioning on the actions of a few agents
$S=\\{a_{i_{1}},a_{i_{2}},...,a_{i_{y}}\\}$ can remove most of the
correlations in $\zeta|_{S}$ thus bringing it to an approximate product
distribution. If $\zeta$ is a correlated equilibrium that continues to be a
correlated equilibrium after conditioning on the actions of a small number of
agents, then the resulting conditional distribution $\zeta|_{S}$ would be
close to a mixed nash equilibrium. One caveat is that the agents who’s actions
have been conditioned upon don’t necessarily participate in the resulting Nash
equilibrium so some small modifications will have to be made to the resulting
equilibrium.

Our goal is then to reformulate this high level idea into a convex program and
design a rounding algorithm. This is the subject of the next few sections,
which we start with an overview of the fundamentals of polynomial
optimization. For a more thorough overview, see [NES00] [Las06] [Sho87]
[Par03].

#### Polynomial Optimization Fundamentals:

First we define the pseudoexpectation functional
$\widetilde{\mathbb{E}}[\cdot]$.

######  Definition 4.1.

Let $\mathbb{a}\vcentcolon=\\{a_{ir}\\}_{i\in[N],r\in[k]}$. A degree $\ell$
pseudoexpectation
$\widetilde{\mathbb{E}}:\mathbb{R}[\mathbb{a}]^{\leqslant\ell}\rightarrow\mathbb{R}$
is a linear functional from the space of degree up to $\ell$ polynomials in
variables $\mathbb{a}$ to the reals. Pseudoexpectations satisfy the following
desirable properties.

  1. 1.

Firstly, $\widetilde{\mathbb{E}}[1]=1$ just like an expectation.

  2. 2.

Secondly, pseudoexpectations are linear functionals so that for any collection
of degree less than $\ell$ polynomials $\\{P_{i}(\mathbb{a})\\}_{i\in[t]}$, we
have
$\widetilde{\mathbb{E}}[\sum_{i=1}^{t}P_{i}(\mathbb{a})]=\sum_{i=1}^{t}\widetilde{\mathbb{E}}[P_{i}(\mathbb{a})]$.

  3. 3.

Finally, for sum of squares pseudoexpectation functionals, we additionally
require that $\widetilde{\mathbb{E}}[SoS_{\ell}(\mathbb{a})]\geqslant 0$ where
$SoS_{\ell}(\mathbb{a})$ is the space of polynomials of degree less than
$\ell$ that can be written as the sum of squares of polynomials.

We are often searching for a pseudoexpectation functional satisfying certain
constraints. To distinguish between different pseudoexpectation functionals,
we index $\widetilde{\mathbb{E}}_{\zeta}$ by an index $\zeta$. Occasionally,
we will refer to $\zeta$ as a pseudodistribution, but this is only for
indexing purposes. Pseudoexpectations for degree $\ell$ polynomials over $N$
variables can be found in $N^{O(\ell)}$ time with some additional care
required for bit precision issues. This follows from the duality of the sum of
squares proof system and semidefinite programming see [NES00] [Las06] [Sho87]
[Par03].

1 Input:  Polymatrix game $(G,\\{f_{ij}\\}_{i,j\in[N]})$

Let $\ell=\frac{L^{4}\ln(k)}{\epsilon^{4}}$, and search for a degree $\ell$
pseudoexpectation $\widetilde{\mathbb{E}}_{\zeta}[\cdot]$ satisfying the
following

  1. 1.

Conditioning Preserving Correlated Equilibrium: For all $i\in[N]$, for all
$w\in[k]$, and for all $S_{i}\subset\\{\\{a_{jr}\\}_{j\in[N]/i}\\}_{r\in[k]}$
of size $|S_{i}|\leqslant\ell-2$.

$\widetilde{\mathbb{E}}_{\zeta}[(\sum_{j\in
N(i)}\sum_{p,q\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}-\sum_{j\in
N(i)}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}+\epsilon)\prod_{a_{uv}\in
S_{i}}a_{uv}]\geqslant 0$

  2. 2.

Booleanity: $\forall i\in[N]$, $\forall p\in[k]$, and for all
$S\subset\\{a_{ir}\\}_{i\in[N],r\in[k]}$ satisfying $|S|\leqslant\ell-2$ we
have

$\widetilde{\mathbb{E}}_{\zeta}[(a_{ip}^{2}-a_{ip})\prod_{a_{uv}\in
S}a_{uv}]=0$

  3. 3.

Coloring: $\forall i\in[N]$ and for all
$S\subset\\{a_{ir}\\}_{i\in[N],r\in[k]}$ of size $|S|\leqslant\ell-1$ we have

$\widetilde{\mathbb{E}}_{\zeta}[(\sum_{p=1}^{k}a_{ip}-1)\prod_{a_{uv}\in
S}a_{uv}]=0$

  4. 4.

Normalization:

$\widetilde{\mathbb{E}}_{\zeta}[1]=1$

  5. 5.

Sum of Squares: $\forall p(\mathbb{a})\in
SoS_{\ell}(\\{a_{ir}\\}_{i\in[N],r\in[k]})$ we constrain

$\widetilde{\mathbb{E}}_{\zeta}[p(\mathbb{a})]\geqslant 0$

Algorithm 1 Convex Hierarchy for Polymatrix Nash Equilibrium

#### Formulating a Semidefinite Program:

Algorithm 1 searches for a pseudoexpectation $\widetilde{\mathbb{E}}_{\zeta}$
satisfying the following constraints. We have the normalization and sum of
squares constraints, which are standard. Furthermore we have the booleanity
and coloring constraints which are also standard. Collectively the booleanity
and coloring constraints enforce that $a_{ip}\in\\{0,1\\}$ and that each
player can adopt only one action at a time in expectation. These constraints
are also relaxed through the sherali adams hierarchy. This implies that the
constraints still hold for any set of fixings of the actions of up to $\ell-2$
players. Finally, we have the conditioning preserving correlated equilibrium
constraint. For all $i\in[N]$, for all $w\in[k]$, and for all
$S_{i}\subset\\{\\{a_{jr}\\}_{j\in[N]/i}\\}_{r\in[k]}$ of size
$|S_{i}|\leqslant\ell-2$.

$\widetilde{\mathbb{E}}_{\zeta}[(\sum_{j\in
N(i)}\sum_{p,q\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}-\sum_{j\in
N(i)}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}+\epsilon)\prod_{a_{uv}\in
S_{i}}a_{uv}]\geqslant 0$

This constraint ensures that the equilibrium (possibly correlated) we are
searching for continues to be an equilibrium even if any small subset of
$\ell-2$ players fix their actions. Here the equilibrium condition is
constrained to hold for every player who’s actions are not fixed. Ultimately,
the conditioning preserving correlated equilibrium constraint is our
replacement for both the Nash equilibrium constraint of $\mathcal{Q}$ and the
product distribution constraint
$\mathbb{E}_{\zeta}[a_{ip}a_{jq}]=\mathbb{E}_{\zeta}[a_{ip}]\mathbb{E}_{\zeta}[a_{jq}]$
of $\mathcal{Q}$. It turns out that the conditioning preserving correlated
equilibria are close to mixed nash equilibria in a very precise sense which
we’ll exploit in the rounding algorithms detailed in Section 5.

#### Hybridized Hierarchies and Proof Systems:

Note that we are neither working with the Sherali-Adams nor Sum of Squares
relaxation. We are also not working with a standard hybridized hierarchy
because the Nash constraint for player $i$ only holds for multilinear
polynomials that do not include $\\{a_{ir}\\}_{r\in[k]}$. As such, it will be
important to design a rounding algorithm which is oblivious to the weakenings
in the relaxation.

Although it is possible that the sum of squares relaxation of pure nash
equilibrium is feasible, it’s not immediately obvious how to prove such a
statement as the pure nash equilibrium is not guaranteed to exist. We
circumvent this problem, by explicitly designing the relaxation hierarchy for
the polymatrix mixed nash equilibrium. Note, that the relaxation is infeasible
without the L-smooth payoffs assumption.

#### Explicit Constraints:

As we’re not working with a standard relaxation, it’s important to explicitly
list the constraints of our convex program. These details are left for Section
B

#### Runtime:

The runtime of our algorithm is dominated by the convex program solve of
Algorithm 1. The subsequent rounding analysis succeeds with small additive
error in the constraints, which allows us to apply the ellipsoid algorithm
[GLS81]. The subsequent rounding procedures require no more than
$(Nk)^{O(\frac{L^{4}\ln(k)}{\epsilon^{4}})}$ time upper bounded by an
exhaustive search over the variable space.

######  Lemma 4.2.

Algorithm 1 can be solved via the ellipsoid algorithm [GLS81] to
$2^{-\text{\rm poly}(N,k)}$ additive accuracy in
$(Nk)^{O(\frac{L^{4}\ln(k)}{\epsilon^{4}})}$ time.

###### Proof.

Algorithm 1 is a convex program in
$(Nk)^{O(\frac{L^{4}\ln(k)}{\epsilon^{4}})}$ variables and
$(Nk)^{O(\frac{L^{4}\ln(k)}{\epsilon^{4}})}$ convex and explicitly bounded
constraints with a feasible region of size greater than $2^{-\text{\rm
poly}(N,k)}$. Furthermore, both Lemma 7.2 and Algorithm 4 hold for any
$2^{-\text{\rm poly}(N,k)}$ additive error in the constraints. Therefore, the
ellipsoid algorithm [GLS81] produces a solution to Algorithm 1 in
$(Nk)^{O(\frac{L^{4}\ln(k)}{\epsilon^{4}})}$ time. ∎

##  5 Rounding Algorithms

In this section we present our rounding algorithm. Our rounding proceeds in
two phases. In the first phase we adopt the conditioning procedure of [BRS11]
to bring $\widetilde{\mathbb{E}}_{\zeta}$ close to a product distribution
which we denote $\widetilde{\mathbb{E}}_{\hat{\zeta}}$. Here, to achieve
quasipolynomial running time we must improve the $k$ dependence of the [BRS11]
analysis. Towards these ends, we develop a novel polynomial approximation
argument of the pseudo-covariance matrix, which accelerates the [BRS11]
rounding at the expense of an additional $\text{\rm poly}(k)$ in the edge
density of the graph. This argument is the key to our quasipolynomial time
algorithm.

In the second phase of our rounding, we must take the approximate product
distribution $\widetilde{\mathbb{E}}_{\hat{\zeta}}$ and turn it into a mixed
nash equilibrium. This is done via the BestResponsePursuit Algorithm 2. At a
high level, Algorithm 2 takes all players which do not have the mixed nash
equilibrium constraint satisfied, which we denote $K_{1}$, and attempts to set
them to best respond to the mixed strategies of the players in $V/K_{1}$. Of
course this does not work because $K_{1}$ could be a clique. This would only
work, if the following condition is satisfied. For all $i\in V$, the fraction
of edges between $i$ and $K_{1}$ is small i.e
$\frac{N_{K_{1}}(i)}{d}\leqslant\frac{\epsilon}{L}$. If this is the case, then
setting every player in $K_{1}$ to best respond to the mixed strategies of
player in $V/K_{1}$ would result in an $2\epsilon$ approximate mixed nash
equilibrium. This is a consequence of the $L$-smoothness assumption.

A priori, $K_{1}$ does not satisfy this condition. However, given $K_{1}$ it
is possible to show that there exists a set $W$ such that $K_{1}\subset W$,
$|W|\leqslant\frac{4}{3}|K_{1}|$, and for all $i\in V/W$, we have
$\frac{N_{W}(i)}{d}\leqslant\frac{\epsilon}{L}$. Then we can hope to form a
set $U\subseteq W$ such that $\frac{|U|}{|W|}\geqslant\frac{9}{10}$ and for
all $i\in U$, $\frac{N_{W}(i)}{d}\leqslant\frac{\epsilon}{L}$. This allows us
to set the players in $U$ to best respond to the mixed strategies of players
in $V/W$. After this is done, we are left with a set of players $K_{2}=W/U$,
where $|K_{2}|\leqslant\frac{|K_{1}|}{5}$. Now iterating the entire procedure
on $K_{2}$ instead of $K_{1}$ we can hope to iteratively contract the set of
players not participating in the mixed nash equilibrium until only a small set
of players are left. This small set of players can then all be set to best
respond.

Each iteration of the above argument comes at a cost to the approximation of
the mixed nash equilibrium so it is important to keep track of the sources of
error as they add up over multiple iterations. The details of this argument is
the subject of Section 8. Next we state the guarantees of the conditioning
rounding procedure. To start we define a notion of distance quantifying how
far a probability distribution is from a product distribution.

######  Definition 5.1.

Let $\Delta(i)$ be the local correlation at node $i\in[N]$ defined to be.

$\Delta(i)\vcentcolon=\frac{1}{|N(i)|}\sum_{j\in
N(i)}\sum_{(p,q)\in[k]^{2}}|\widetilde{\mathbb{E}}[a_{ip}a_{jq}]-\widetilde{\mathbb{E}}[a_{ip}]\widetilde{\mathbb{E}}[a_{jq}]|]$

Let $\Delta$ be the average local correlation of the nodes in $G$.

$\Delta\vcentcolon=\frac{1}{2|E|}\sum_{(i,j)\in
E}\sum_{(p,q)\in[k]^{2}}|\widetilde{\mathbb{E}}[a_{ip}a_{jq}]-\widetilde{\mathbb{E}}[a_{ip}]\widetilde{\mathbb{E}}[a_{jq}]|]$

Intuitively, correlation/covariance capture how far a pair of random variables
$a_{i}$ and $a_{j}$ are from a product distribution. The average covariance
over all pairs of random variables over all edges of $G$ is then a measure of
how far a distribution in $\mathcal{P}(k,V)$ is from a product distribution.

######  Fact 5.2 (Conditioning).

For a degree $\ell$ pseudoexpectation $\widetilde{\mathbb{E}}_{\zeta}$ over
the polynomial system $\\{x_{i}^{2}=x_{i}\\}_{i=1}^{N}$, the following
conditioning procedure is well defined.

$\widetilde{\mathbb{E}}_{\zeta}[p(x_{1},...,x_{N})|x_{i}=1]\vcentcolon=\frac{\widetilde{\mathbb{E}}_{\zeta}[p(x_{1},...,x_{N})x_{i}]}{\widetilde{\mathbb{E}}_{\zeta}[x_{i}]}$

for any $p(x_{1},...,x_{N})\in\mathbb{R}[x_{1},...,x_{N}]^{\leqslant\ell}$

Note that the conditioning preserving correlated equilibrium constraint for
player $i$ is preserved after conditioning on the actions of any player $j\neq
i$. Furthermore, this holds for any set of $\ell-1$ such conditionings. Next,
we will prove our conditioning rounding result for the class of low threshold
rank graphs, which are a generalization of expander graphs and include the
$G(N,p)$ graphs we study in this work.

######  Definition 5.3.

We say a graph $G$ has $(\rho,\tau)$ threshold rank if the normalized
adjacency matrix $\frac{1}{d}A$ of $G$ with eigenvalues
$\\{\lambda_{i}\\}_{i=1}^{N}$ satisfies
$|\\{i\in[N]|\lambda_{i}\geqslant\rho\\}|=\tau$.

In particular, the $G(N,p)$ random graphs considered in this work have
$(\frac{1}{\sqrt{d}},1)$ threshold rank. The following lemma is the main
rounding guarantee of the conditioning procedure.

######  Lemma 5.4.

Consider the following procedure,

  1. 1.

Initialize seed set $S=\emptyset$, and assignments $\cal{R}=\emptyset$

  2. 2.

Let $a_{1},a_{2},...,a_{N}$ be random variables such that
$\mathbb{P}(a_{i}=p)=\widetilde{\mathbb{E}}_{\zeta}[a_{ip}]$ for all $p\in[k]$
and for all $i\in[N]$.

  3. 3.

Let $i\in V/S$ be drawn uniformly at random, and append $i$ to $S$

  4. 4.

draw $p_{i}\sim a_{i}$ and append $p_{i}$ to $\cal{R}$

  5. 5.

Update
$\widetilde{\mathbb{E}}_{\zeta}[\cdot]\leftarrow\widetilde{\mathbb{E}}_{\zeta}[\cdot|a_{i}=p_{i}]$

  6. 6.

While $|S|\leqslant\frac{L^{4}\ln(k)}{\epsilon^{4}}-2$ go to step (2.)

Let $\widetilde{\mathbb{E}}_{\hat{\zeta}}$ be the pseudoexpectation that is
the output of the algorithm above, and let $\Delta_{\hat{\zeta}}$ be its
associated local correlation. When the algorithm terminates we have
$S\vcentcolon=\\{i_{1},i_{2},...,i_{r}\\}$ and
$R\vcentcolon=\\{p_{i_{1}},p_{i_{2}},...,p_{i_{r}}\\}$. Let $\cal{U}$ be the
distribution over $\\{(i_{y},p_{y})\\}_{y\in[r]}$ induced by the algorithm.
Then

$\mathbb{E}_{\\{(i_{y},p_{y})\\}_{y\in[r].}\sim\cal{U}}[\Delta_{\hat{\zeta}}|a_{i_{1}}=p_{i_{1}},a_{i_{2}}=p_{i_{2}},...,a_{i_{r}}=p_{i_{r}}]\leqslant\frac{\epsilon^{2}}{L^{2}}$

The conditioning algorithm selects a player at random and fixes/conditions
their actions according to the local probability distribution prescribed by
$\widetilde{\mathbb{E}}_{\zeta}$. Iterating this algorithm reduces the local
correlation. The proof of Lemma 7.2 is left for Section 6. Additionally, it
turns out there’s no need for the procedure to be executed iteratively. One
could simply enumerate all possible conditionings of the actions of $\ell-2$
agents. One such conditioning is guaranteed to bring the local correlation
down to $\epsilon$. Next, we move onto the guarantees of Algorithm 2.

######  Lemma 1 (Best Response Pursuit).

Let $\widetilde{\mathbb{E}}_{\zeta}$ be a pseudoexpectation satisfying the
constraints in Algorithm 1. Let $\Delta_{\zeta}\leqslant\epsilon^{2}$ be the
local correlation of $\widetilde{\mathbb{E}}_{\zeta}$. Let $K_{1}\subset V$ be
the set of nodes satisfying $\Delta_{\zeta}(i)\geqslant 2\epsilon$. Let
$\mu_{ip}=\widetilde{\mathbb{E}}[a_{ip}]\text{ for all }i\in[N]\text{ and for
all }p\in[k]$. Let
$\Gamma_{1}\leftarrow\\{\\{\mu_{ip}\\}_{p=1}^{k}\\}_{i=1}^{N}$. We define
$K_{2},K_{3},...,K_{T}$ and $\Gamma_{2},\Gamma_{3},...,\Gamma_{T}$ iteratively
as follows. Let $W=Flag(K_{t},G)$ and let
$(K_{t+1},\Gamma_{t+1})=BestRespond(W,\Gamma_{t})$. Here we iterate until
$K_{T}=\emptyset$. Then we have for all $i\in V$ with probability
$1-N^{-\ln^{2}(N)}$ over the randomness of the graph,

$\sum_{j\in
N(i)}\sum_{(p,q)\in[k]^{2}}f_{ij}(p,q)\widetilde{\mathbb{E}}_{\Gamma_{T}}[a_{ip}]\widetilde{\mathbb{E}}_{\Gamma_{T}}[a_{jq}]-\sum_{q\in[k]}f_{ij}(w,q)\widetilde{\mathbb{E}}_{\Gamma_{T}}[a_{jq}]\leqslant
120L\epsilon$

Given Lemma 1 we can conclude the following guarantee holds for our rounding
algorithm.

######  Lemma 5.5 (Rounding).

Let $\widetilde{\mathbb{E}}_{\zeta}$ be the pseudoexpectation output by
Algorithm 1, which is then passed to the conditioning procedure in Lemma 7.2.
Let $\widetilde{\mathbb{E}}_{\hat{\zeta}}$ be the pseudoexpectation output by
the conditioning procedure in Lemma 7.2. Then Algorithm 2,
BestResponsePursuit($\widetilde{\mathbb{E}}_{\hat{\zeta}}$) outputs a product
distribution
$\Gamma\vcentcolon=\\{\mu_{ip}\\}_{i\in[N],p\in[k]}\in\mathcal{P}(k,V)$
satisfying that for all $i\in[N]$ and for all $w\in[k]$

$\sum_{j\in
N(i)}\sum_{p,q\in[k]^{2}}f_{ij}(p,q)\mathbb{E}_{\Gamma}[a_{ip}]\mathbb{E}_{\Gamma}[a_{jq}]-\sum_{j\in
N(i)}\sum_{q\in[k]}f_{ij}(w,q)\mathbb{E}_{\Gamma}[a_{jq}]\geqslant-\epsilon$

That is to say $\Gamma$ is an $\epsilon$-approximate mixed nash equilibrium

###### Proof.

Using Lemma 7.2 we obtain $\widetilde{\mathbb{E}}_{\hat{\zeta}}$ satisfying
local correlation $\Delta\leqslant\frac{\epsilon^{2}}{L^{2}}$. Then using
Lemma 1 we obtain a product distribution $\Gamma$ satisfying

$\sum_{j\in
N(i)}\sum_{p,q\in[k]^{2}}f_{ij}(p,q)\mathbb{E}_{\Gamma}[a_{ip}]\mathbb{E}_{\Gamma}[a_{jq}]-\sum_{j\in
N(i)}\sum_{q\in[k]}f_{ij}(w,q)\mathbb{E}_{\Gamma}[a_{jq}]\geqslant-\epsilon$

as desired. ∎

We now have all the ingredients to prove Theorem 2.1 See 2.1

###### Proof.

We have by Lemma 4.2 that Algorithm 1 can be solved in
$(Nk)^{O(\frac{L^{4}\ln(k)}{\epsilon^{4}})}$ time. We have by Lemma 5.5 that
the conditioning procedure and Algorithm 2 produce an $\epsilon$-approximate
Nash equilibrium with high probability $1-N^{-\ln^{2}(N)}$. The runtime of
both procedures is upper bounded by the time it takes to exhaustively search
over all $\ell-2$ size subsets of conditionings of $\mathbb{a}$. This can be
done in time $(Nk)^{O(\frac{L^{4}\ln(k)}{\epsilon^{4}})}$. ∎

1 Input:  $\widetilde{\mathbb{E}}_{\zeta}$

Result: $\Gamma=\\{\\{\mu_{ip}\\}_{p=1}^{k}\\}_{i=1}^{N}$

2 $\mu_{ip}\leftarrow\widetilde{\mathbb{E}}[a_{ip}]\text{ for all
}i\in[N]\text{ and for all }p\in[k]$

3 $K_{1}\leftarrow\emptyset$

4 for $i\in[N]$ do

5 if $\Delta(i)\geqslant 2\epsilon$ then

6 $K_{1}\leftarrow K_{1}\cup\\{i\\}$

7

8$\Gamma_{1}\leftarrow\\{\\{\mu_{ip}\\}_{p=1}^{k}\\}_{i\in V/K_{1}}$

9 for $t\in[T]$ do

10 $W=Flag(K_{t},G)$

11 $(\Gamma_{t+1},K_{t+1})\leftarrow BestRespond(W,\Gamma_{t})$

12 $\Gamma\leftarrow\Gamma_{t+1}$

13 if $K_{t+1}=\emptyset$ then

14 break

15

16

$\textbf{Return: }\Gamma$

Algorithm 2 Best Response Pursuit

Data: $K\subseteq V$

Result: $W\subseteq V$

1 $W\leftarrow K$

2 $H_{old}\leftarrow K$

3 while $|H_{old}|\geqslant\ln^{3}(N)$ do

4 $H_{new}\leftarrow\emptyset$

5 for $i\in\overline{W}$ do

6 if
$\frac{|N_{H_{old}}(i)|}{d}\geqslant\max(10\frac{|H_{old}|}{N},10\frac{\ln(n)}{d})$
then

7 $H_{new}\leftarrow H_{new}\cup\\{i\\}$

8

9

10 $W\leftarrow W\cup H_{new}$

11 $H_{old}\leftarrow H_{new}$

12

13$\textbf{Return: }W$

Algorithm 3 Flag

1 Input: $\Gamma=\\{\\{\mu_{ip}\\}_{p=1}^{k}\\}_{i\in V/W},W$

Result: $\hat{\Gamma}=\\{\\{\hat{\mu}_{ip}\\}_{p=1}^{k}\\}_{i\in V/Q},Q$

2 $\\{\hat{\mu}_{ip}\\}_{p=1}^{k}\\}_{i\in
V/W}\leftarrow\\{\\{\mu_{ip}\\}_{p=1}^{k}\\}_{i\in V/W}$

3 if $|W|\leqslant\ln^{3}(N)$ then

4 $Q\leftarrow\emptyset$

5else

6 $Q\leftarrow\emptyset$

7 for $i\in W$ do

8 if $\frac{|N_{W}(i)|}{|N(i)|}\geqslant\epsilon$ then

9 $Q\leftarrow\\{i\\}$

10

11

12

13

14for $i\in W/Q$ do

15 for $p\in[k]$ do

16 if $\mathbb{E}_{\Gamma}[\sum_{j\in
N_{\overline{W}}(i)}\sum_{q\in[k]}f_{i,j}(p,q)a_{jq}]\geqslant\max_{p^{\prime}\in[k]}\mathbb{E}[\sum_{j\in
N_{\overline{W}}(i)}\sum_{q\in[k]}f_{i,j}(p^{\prime},q)a_{jq}]$ then

17 $r_{ip}\leftarrow 1$

18

19 else

20 $r_{ip}\leftarrow 0$

21

22

23$\hat{\mu}_{ip}\leftarrow\frac{r_{ip}}{\sum_{p\in[k]}r_{ip}}$ for all  $i\in
W/Q$ and for all  $p\in[k]$

24 $\textbf{return: }(\\{\\{\hat{\mu}_{ip}\\}_{p=1}^{k}\\}_{i\in V/Q},Q)$

Algorithm 4 BestResponse($\Gamma,W$)

##  6 Propagation of Mutual Information

In the next two sections we work towards a proof of Lemma 7.2. First we
present an upper bound on the local correlation $\Delta_{\zeta}$ in terms of
the global mutual information defined to be
$\frac{1}{N^{2}}\sum_{i,j\in[N]^{2}}I(a_{i},a_{j})$. Here
$\\{a_{i}\\}_{i\in[N]}$ are the $\ell$-local random variables over the agent’s
actions provided by the level $\ell$ sherali-adams hierarchy on the booleanity
constraints. The pairwise mutual information $I(a_{i},a_{j})$ is therefore
well defined. Once we relate $\Delta_{\zeta}$ to
$\frac{1}{N^{2}}\sum_{i,j\in[N]^{2}}I(a_{i},a_{j})$ we can use a standard
conditioning argument to show that after a small number of rounds of
conditioning $\frac{1}{N^{2}}\sum_{i,j\in[N]^{2}}I(a_{i},a_{j})$ is small.
This would in turn show that $\Delta_{\zeta}$ is small.

######  Lemma 6.1.

Let $\Delta_{\zeta}$ denote the local correlation of pseudodistribution
$\widetilde{\mathbb{E}}_{\zeta}$ on a $(\rho,\tau)$ threshold rank graph $G$
defined as

$\Delta_{\zeta}\vcentcolon=\frac{1}{2|E|}\sum_{(i,j)\in
E}\sum_{(p,q)\in[k]^{2}}|\widetilde{\mathbb{E}}[a_{ip}a_{jq}]-\widetilde{\mathbb{E}}[a_{ip}]\widetilde{\mathbb{E}}[a_{jq}]|]$

Let $f(x)=\sum_{r=1}^{p}\alpha_{r}x^{r}$ be a univariate polynomial satisfying
$|x|\leqslant f(x)\leqslant|x|+\epsilon^{\prime}$ for $x\in[-1,1]$. Let
$H\in\mathbb{R}^{kN\times kN}$ be a matrix row indexed by $i\in[N]$ and
$p\in[k]$ and column indexed by $j\in[N]$ and $q\in[k]$. We define
$H_{\\{(i,p),(j,q)\\}}=f(\widetilde{\mathbb{E}}[a_{ip}a_{jq}]-\widetilde{\mathbb{E}}[a_{ip}]\widetilde{\mathbb{E}}[a_{jq}])$.
Then we have that

$\Delta_{\zeta}\leqslant\frac{\rho
k}{N}\|H\|_{*}+\tau\sqrt{2(\epsilon^{\prime}k^{2})^{2}+\frac{2}{N^{2}}\sum_{i,j\in[N]^{2}}I(a_{i},a_{j})}$

###### Proof.

We begin with the local correlation

$\Delta_{\zeta}\vcentcolon=\frac{1}{2|E|}\sum_{(i,j)\in
E}\sum_{(p,q)\in[k]^{2}}|\widetilde{\mathbb{E}}[a_{ip}a_{jq}]-\widetilde{\mathbb{E}}[a_{ip}]\widetilde{\mathbb{E}}[a_{jq}]|]=\frac{1}{|E|}\langle
A,K\rangle$

where
$K_{ij}:=\sum_{(p,q)\in[k]^{2}}|\widetilde{\mathbb{E}}[a_{ip}a_{jq}]-\widetilde{\mathbb{E}}[a_{ip}]\widetilde{\mathbb{E}}[a_{jq}]|$.
Let $M$ be a matrix such that
$M_{ij}=\sum_{(p,q)\in[k]^{2}}f(\widetilde{\mathbb{E}}[a_{ip}a_{jq}]-\widetilde{\mathbb{E}}[a_{ip}]\widetilde{\mathbb{E}}[a_{jq}])$
for univariate polynomial $f$ satisfying $|x|\leqslant
f(x)\leqslant|x|+\epsilon^{\prime}$. Here $f(x)$ is the polynomial defined in
Lemma D.1. We use the univariate polynomial entrywise upper bound to obtain

$\frac{1}{|E|}\langle A,K\rangle\leqslant\frac{1}{|E|}\langle A,M\rangle$

Now we split the eigenvalues of $G$ into those larger than $\rho$ and those
less than $\rho$.

$\frac{1}{|E|}\langle
A,M\rangle=\frac{1}{N}\langle\frac{N}{|E|}A,M\rangle=\frac{1}{N}\sum_{i=1}^{N}\lambda_{i}\langle
v_{i}v_{i}^{T},M\rangle=\frac{1}{N}(\sum_{|\lambda_{i}|\leqslant\rho}\lambda_{i}\langle
v_{i}v_{i}^{T},M\rangle+\sum_{|\lambda_{i}|\geqslant\rho}\lambda_{i}\langle
v_{i}v_{i}^{T},M\rangle)$

Taking absolute values in the second term we upper bound by

$\leqslant\frac{1}{N}\Big{(}\sum_{|\lambda_{i}|\leqslant\rho}\lambda_{i}\langle
v_{i}v_{i}^{T},M\rangle+\sum_{|\lambda_{i}|\geqslant\rho}|\lambda_{i}||\langle
v_{i}v_{i}^{T},M\rangle|\Big{)}$

Using the fact that the eigenvalues of the normalized adjacency matrix is
upper bounded by $1$ and taking cauchy schwarz we obtain

$\leqslant\frac{1}{N}\Big{(}\sum_{|\lambda_{i}|\leqslant\rho}\lambda_{i}\langle
v_{i}v_{i}^{T},M\rangle+\sum_{|\lambda_{i}|\geqslant\rho}(\sum_{(r,s)\in[N]^{2}}v_{ir}^{2}v_{is}^{2})^{1/2}\|M\|_{F}\Big{)}$

$=\frac{1}{N}\Big{(}\sum_{|\lambda_{i}|\leqslant\rho}\lambda_{i}\langle
v_{i}v_{i}^{T},M\rangle+\sum_{|\lambda_{i}|\geqslant\rho}(\sum_{r=1}^{N}v_{ir}^{2})\|M\|_{F}\Big{)}$

Using the fact that $\|v_{i}\|^{2}=1$ we obtain

$=\frac{1}{N}\Big{(}\sum_{|\lambda_{i}|\leqslant\rho}\lambda_{i}\langle
v_{i}v_{i}^{T},M\rangle+\sum_{|\lambda_{i}|\geqslant\rho}\|M\|_{F}\Big{)}$

Using the $(\rho,\tau)$ threshold rank condition we obtain.

$=\frac{1}{N}\Big{(}\sum_{|\lambda_{i}|\leqslant\rho}\lambda_{i}\langle
v_{i}v_{i}^{T},M\rangle+\tau\sqrt{\sum_{i,j\in[N]^{2}}(M_{ij})^{2}}\Big{)}$

Let $v^{\oplus k}=(v,v,...,v)\in\mathbb{R}^{k}$. Let
$\overline{v}_{i}:=(v_{i1}^{\oplus k},v_{i2}^{\oplus k},...,v_{iN}^{\oplus
k})\in\mathbb{R}^{kN}$. Let $H\in\mathbb{R}^{kN\times kN}$ be a matrix row
indexed by $i\in[N]$ and $p\in[k]$ and column indexed by $j\in[N]$ and
$q\in[k]$. We define
$H_{\\{(i,p),(j,q)\\}}=f(\widetilde{\mathbb{E}}[a_{ip}a_{jq}]-\widetilde{\mathbb{E}}[a_{ip}]\widetilde{\mathbb{E}}[a_{jq}])$.
Let $\phi_{1},...,\phi_{kN}$ be the eigenvalues of $H$ with corresponding
eigenvectors $q_{1},...,q_{kN}$. Then we have

$=\frac{1}{N}\Big{(}\sum_{|\lambda_{i}|\leqslant\rho}\lambda_{i}\langle\overline{v}_{i}\overline{v}_{i}^{T},H\rangle+\tau\sqrt{\sum_{i,j\in[N]^{2}}(M_{ij})^{2}}\Big{)}$

$=\frac{1}{N}\Big{(}\sum_{|\lambda_{i}|\leqslant\rho}\lambda_{i}\langle\overline{v}_{i}\overline{v}_{i}^{T},\sum_{j=1}^{kN}\phi_{j}q_{j}q_{j}^{T}\rangle+\tau\sqrt{\sum_{i,j\in[N]^{2}}(M_{ij})^{2}}\Big{)}$

$=\frac{1}{N}\Big{(}\sum_{j=1}^{kN}\phi_{j}\sum_{|\lambda_{i}|\leqslant\rho}\lambda_{i}\langle\overline{v}_{i}\overline{v}_{i}^{T},q_{j}q_{j}^{T}\rangle+\tau\sqrt{\sum_{i,j\in[N]^{2}}(M_{ij})^{2}}\Big{)}$

Applying absolute values and noting that
$\langle\overline{v}_{i}\overline{v}_{i}^{T},q_{j}q_{j}^{T}\rangle$ is a
square we upper bound by

$\leqslant\frac{1}{N}\Big{(}\sum_{j=1}^{kN}|\phi_{j}|\sum_{|\lambda_{i}|\leqslant\rho}|\lambda_{i}|\langle\overline{v}_{i}\overline{v}_{i}^{T},q_{j}q_{j}^{T}\rangle+\tau\sqrt{\sum_{i,j\in[N]^{2}}(M_{ij})^{2}}\Big{)}$

Upper bounding $\lambda_{i}\leqslant\rho$ we obtain

$\leqslant\frac{1}{N}\Big{(}\sum_{j=1}^{kN}|\phi_{j}|\sum_{|\lambda_{i}|\leqslant\rho}\rho
k\langle\frac{1}{\sqrt{k}}\overline{v}_{i}\frac{1}{\sqrt{k}}\overline{v}_{i}^{T},q_{j}q_{j}^{T}\rangle+\tau\sqrt{\sum_{i,j\in[N]^{2}}(M_{ij})^{2}}\Big{)}$

Using the fact that
$\langle\frac{1}{\sqrt{k}}\overline{v}_{i}\frac{1}{\sqrt{k}}\overline{v}_{i}^{T},q_{j}q_{j}^{T}\rangle$
is a square for all $i\in[N]$ we upper bound by

$\leqslant\frac{1}{N}\sum_{j=1}^{kN}|\phi_{j}|\rho
k\sum_{i\in[N]}\langle\frac{1}{\sqrt{k}}\overline{v}_{i}\frac{1}{\sqrt{k}}\overline{v}_{i}^{T},q_{j}q_{j}^{T}\rangle+\frac{\tau}{N}\sqrt{\sum_{i,j\in[N]^{2}}(M_{ij})^{2}}$

$=\frac{1}{N}\sum_{j=1}^{kN}|\phi_{j}|\rho
k\sum_{i\in[N]}\langle\frac{1}{\sqrt{k}}\overline{v_{i}},q_{j}\rangle^{2}+\frac{\tau}{N}\sqrt{\sum_{i,j\in[N]^{2}}(M_{ij})^{2}}$

We know that $\frac{1}{\sqrt{k}}\overline{v}_{i}$ for $i\in[N]$ forms an
orthonormal basis, and $\|q_{j}\|^{2}=1$. Therefore, we upper bound the first
term by

$\leqslant\frac{1}{N}\sum_{j=1}^{kN}|\phi_{j}|\rho
k+\frac{\tau}{N}\sqrt{\sum_{i,j\in[N]^{2}}(M_{ij})^{2}}$

$=\frac{1}{N}\sum_{j=1}^{kN}|\phi_{j}|\rho
k+\frac{\tau}{N}\sqrt{\sum_{i,j\in[N]^{2}}(M_{ij}-\sum_{(p,q)\in[k]^{2}}|cov(a_{ip},a_{jq})|+\sum_{(p,q)\in[k]^{2}}|cov(a_{ip},a_{jq})|)^{2}}$

Applying $(a+b)^{2}\leqslant 2a^{2}+2b^{2}$ to the second term we obtain

$\leqslant\frac{1}{N}\sum_{j=1}^{kN}|\phi_{j}|\rho
k+\tau\sqrt{\frac{1}{N^{2}}\sum_{i,j\in[N]^{2}}\big{(}2(M_{ij}-\sum_{(p,q)\in[k]^{2}}|cov(a_{ip},a_{jq})|)^{2}+2(\sum_{(p,q)\in[k]^{2}}|cov(a_{ip},a_{jq})|)^{2}})$

Using the fact that $M$ is entrywise $\epsilon^{\prime}k^{2}$ close to $K$ we
have

$\leqslant\frac{\rho
k}{N}\|H\|_{*}+\tau\sqrt{2(\epsilon^{\prime}k^{2})^{2}+\frac{2}{N^{2}}\sum_{i,j\in[N]^{2}}(\sum_{(a,b)\in[k]^{2}}|cov(a_{ip},a_{jq})|)^{2}}$

Applying pinsker’s inequality we obtain

$\leqslant\frac{\rho
k}{N}\|H\|_{*}+\tau\sqrt{2(\epsilon^{\prime}k^{2})^{2}+\frac{4}{N^{2}}\sum_{i,j\in[N]^{2}}I(a_{i},a_{j})}$

which is the desired inequality. ∎

Now we have upper bounded $\Delta_{\zeta}$ by a relation involving
$\frac{4}{N^{2}}\sum_{i,j\in[N]^{2}}I(a_{i},a_{j})$ and $\|H\|_{*}$. In the
next section we bound $\|H\|_{*}$.

##  7 Accelerated Rounding via Polynomial Approximation

The following lemma is a self contained fact about the nuclear norm of
matrices that are written as the sum of PSD matrices.

######  Lemma 7.1.

Let $f(x)=\sum_{r=1}^{p}\alpha_{r}x^{r}$. Let $H\in\mathbb{R}^{kN\times kN}$
be a matrix row indexed by $i\in[N]$ and $p\in[k]$ and column indexed by
$j\in[N]$ and $q\in[k]$. We define
$H_{\\{(i,p),(j,q)\\}}=f(\widetilde{\mathbb{E}}[a_{ip}a_{jq}]-\widetilde{\mathbb{E}}[a_{ip}]\widetilde{\mathbb{E}}[a_{jq}])$.
Then

$\|H\|_{*}\leqslant Nk\sum_{r=1}^{p}|\alpha_{r}|$

In particular, for $f(x)$ defined in Lemma D.1 where $|x|\leqslant
f(x)\leqslant|x|+\epsilon^{\prime}$

$\|H\|_{*}\leqslant\frac{18Nk}{\sqrt{\pi}\epsilon^{\prime}}$

###### Proof.

Let $Q_{\\{(ip),(jq)\\}}=cov(a_{ip},a_{jq})=\langle v_{ip},v_{jq}\rangle$. Let
$Q^{\odot r}$ be the entrywise $r$’th power of $Q$. We know

$Q^{\odot r}_{\\{(ip),(jq)\\}}\vcentcolon=cov(a_{ip},a_{jq})^{r}=\langle
v_{ip},v_{jq}\rangle^{r}=\langle v_{ip}^{\otimes r},v_{jq}^{\otimes r}\rangle$

Thus we have $Q^{\odot r}$ is positive semidefinite, which can also be seen by
applying the Schur product theorem. Thus we can upper bound the nuclear norm

$\|Q^{\odot r}\|_{*}=Tr(Q^{\odot
r})=\sum_{i\in[N],p\in[k]}\|v_{ip}\|^{2r}\leqslant Nk$

where the inequality follows from the fact that $\langle
v_{ip},v_{jq}\rangle\leqslant 1$. This implies we can upper bound the nuclear
norm of $H$ as follows

$\|H\|_{*}=\|\sum_{r=1}^{p}\alpha_{r}Q^{\odot
r}\|_{*}\leqslant\sum_{r=1}^{p}\|\alpha_{r}Q^{\odot
r}\|_{*}=\sum_{r=1}^{p}|\alpha_{r}|\|Q^{\odot r}\|_{*}\leqslant
Nk\sum_{r=1}^{p}|\alpha_{r}|$

Where the first inequality follows from triangle inequality, and the second
inequality follows from the nonnegativity of the nuclear norm. Using Lemma D.1
we upper bound by
$\sum_{r=1}^{p}|\alpha_{r}|\leqslant\frac{18}{\sqrt{\pi}}p\leqslant\frac{18}{\sqrt{\pi}\epsilon^{\prime}}$
which allows us to conclude

$\|H\|_{*}\leqslant\frac{18Nk}{\sqrt{\pi}\epsilon^{\prime}}$

as desired. ∎

Finally we are ready to prove Lemma 7.2

######  Lemma 7.2.

Let $a_{1},a_{2},...,a_{N}$ be random variables such that
$\mathbb{P}(a_{i}=p)=\widetilde{\mathbb{E}}[a_{ip}]$ for all $p\in[k]$ and for
all $i\in[N]$. Consider the following procedure,

  1. 1.

Initialize seed set $S=\emptyset$, and assignments $\cal{R}=\emptyset$

  2. 2.

Let $i\in V/S$ be drawn uniformly at random, and append $i$ to $S$

  3. 3.

draw $p_{i}\sim a_{i}$ and append $p_{i}$ to $\cal{R}$

  4. 4.

While $|S|\leqslant\frac{\ln(k)}{L^{4}\epsilon^{4}}$ go to step (2.)

When the procedure terminates we have
$S\vcentcolon=\\{i_{1},i_{2},...,i_{r}\\}$ and
$R\vcentcolon=\\{p_{i_{1}},p_{i_{2}},...,p_{i_{r}}\\}$. Let $\cal{U}$ be the
distribution over $\\{(i_{y},p_{y})\\}_{y\in[r]}$ induced by the procedure.
Then

$\mathbb{E}_{\\{(i_{y},p_{y})\\}_{y\in[r].}\sim\cal{U}}[\Delta|a_{i_{1}}=p_{i_{1}},a_{i_{2}}=p_{i_{2}},...,a_{i_{r}}=p_{i_{r}}]\leqslant\frac{\epsilon^{2}}{L^{2}}$

###### Proof.

Let $\epsilon^{\prime}=\frac{\epsilon^{2}}{k^{2}}$. Then our bound on $\Delta$
is as follows. By Lemma 6.1 we have

$\Delta\leqslant\frac{\rho
k}{N}\|H\|_{*}+\tau\sqrt{2(\epsilon^{\prime}k^{2})^{2}+\frac{2}{N^{2}}\sum_{i,j\in[N]^{2}}I(a_{i},a_{j})}$

For $G(N,p)$ random graphs, with $d=pN$ we have $\rho=\frac{1}{\sqrt{d}}$ and
$\tau=1$ so we obtain

$=\frac{k}{N\sqrt{d}}\|H\|_{*}+\sqrt{2(\epsilon^{\prime}k^{2})^{2}+\frac{2}{N^{2}}\sum_{i,j\in[N]^{2}}I(a_{i},a_{j})}$

Setting $\epsilon^{\prime}=\frac{\epsilon}{k^{2}}$ we obtain

$=\frac{k}{\sqrt{d}N}\|H\|_{*}+\sqrt{2\epsilon^{2}+\frac{2}{N^{2}}\sum_{i,j\in[N]^{2}}I(a_{i},a_{j})}$

Applying Lemma 7.1 we have
$\|H\|_{*}\leqslant\frac{Nk}{\epsilon^{\prime}}=\frac{Nk^{3}}{\epsilon}$ which
yields

$\leqslant\frac{k}{N\sqrt{d}}N\frac{k^{3}}{\epsilon}+\sqrt{2\epsilon^{4}+\frac{2}{N^{2}}\sum_{i,j\in[N]^{2}}I(a_{i},a_{j})}$

Setting $d=\frac{k^{8}}{\epsilon^{4}}$ we obtain

$\leqslant\epsilon+\sqrt{2\epsilon^{2}+\frac{2}{N^{2}}\sum_{i,j\in[N]^{2}}I(a_{i},a_{j})}$

At this point we have established

$\mathbb{E}_{\\{(i_{y},p_{y})\\}_{y\in[r]}\sim\cal{U}}[\Delta|a_{i_{1}}=p_{i_{1}},a_{i_{2}}=p_{i_{2}},...,a_{i_{r}}=p_{i_{r}}]\\\
\leqslant\epsilon+\mathbb{E}_{\\{(i_{y},p_{y})\\}_{y\in[r]}\sim\cal{U}}\left[\sqrt{2\epsilon^{2}+\frac{2}{N^{2}}\sum_{i,j\in[N]^{2}}I(a_{i},a_{j}|a_{i_{1}}=p_{i_{1}},a_{i_{2}}=p_{i_{2}},...,a_{i_{r}}=p_{i_{r}})}\right]$
(1)

We have by Jensen’s inequality

$\leqslant\epsilon+\sqrt{2\epsilon^{2}+\mathbb{E}_{\\{(i_{y},p_{y})\\}_{y\in[r]}\sim\cal{U}}\left[\frac{2}{N^{2}}\sum_{i,j\in[N]^{2}}I(a_{i},a_{j}|a_{i_{1}}=p_{i_{1}},a_{i_{2}}=p_{i_{2}},...,a_{i_{r}}=p_{i_{r}})\right]}$

Finally via Lemma D.2 we have
$\frac{1}{N^{2}}\sum_{i,j\in[N]^{2}}I(a_{i},a_{j}|a_{i_{1}},a_{i_{2}},...,a_{i_{r}})\leqslant\epsilon^{2}$
after $\frac{\ln(k)}{\epsilon^{2}}$ rounds of conditioning. Thus we conclude

$\mathbb{E}_{\\{(i_{y},p_{y})\\}_{y\in[r]}\sim\cal{U}}[\Delta|a_{i_{1}}=p_{i_{1}},a_{i_{2}}=p_{i_{2}},...,a_{i_{r}}=p_{i_{r}}]\leqslant\epsilon$

as desired. If we used $\frac{L^{4}\ln(k)}{\epsilon^{4}}$ ∎

In the next section we present the guarantees of the Best Response Pursuit
Algorithm 2.

##  8 Best Response Pursuit

When local correlation is smaller than $\epsilon^{2}$, this implies via markov
that the number of nodes $i$ with $\Delta(i)\geqslant\epsilon$ is less than
$\epsilon N$. Let these ’bad’ nodes be $K_{1}$, and let $\overline{K_{1}}$ be
the set of ’good’ nodes. A naive strategy is to set all the nodes in $K_{1}$
to best respond to the nodes in $\overline{K}_{1}$. This would succeed if all
the nodes in $V$ had less than a $10\epsilon$ fraction of edges incident to
$K_{1}$. Setting all the nodes in $K_{1}$ to best respond would satisfy the
Nash equilibrium constraints to error $10L\epsilon$. Thus, a preliminary goal
is to assemble a set $K$ such that $K_{1}\subseteq W$ satisfying that every
node in $\overline{W}$ satisfies that no more than a $10\epsilon$ fraction of
edges are incident to $W$. Given such a set $W$, we could set all the nodes in
$W$ to best response and the nodes $i\in\overline{W}$ will continue to satisfy
$\Phi(i)\leqslant\epsilon+10L\epsilon$. Unfortunately, this does not guarantee
that all the nodes $i\in W$ will satisfy $\Phi(i)\leqslant 10L\epsilon$ as
their may be nodes in $W$ with too many edges in $W$. Indeed, we will not be
able to set all the nodes in $W$ to best response. However, we can set most of
the nodes in $W$ to best respond. This leaves us with a set $K_{2}\subset W$
which has not been set to best response with
$|K_{2}|\leqslant\frac{|K_{1}|}{2}$. Now we can iterate the same procedure on
$K_{2}$ as had been performed on $K_{1}$ which contracts the set of bad nodes
geometrically whilst controlling the error in the constraints of the good
nodes.

###  8.1 Best response preliminaries:

#### Notation:

let $Q\subseteq V$ and let $\overline{Q}$ be the complement of $Q$ in $V$. Let
$G_{Q}\vcentcolon=(Q,E_{Q})$ be a subgraph of $G$ where
$E_{Q}\vcentcolon=\\{(i,j)\in E|(i,j)\in Q\\}$. Let
$N_{Q}(i)\vcentcolon=\\{j\in Q|(i,j)\in Q\\}$. Let $\Gamma$ denote the product
distribution that sets
$\mathbb{P}_{\Gamma}(a_{ip})=\widetilde{\mathbb{E}}[a_{ip}]$. Let $\Gamma_{Q}$
be the product distribution defined over the nodes in $Q$ such that
$\mathbb{P}_{\Gamma_{Q}}(a_{ip})=\mathbb{P}_{\Gamma}(a_{ip})$ for all $i\in
Q$.

Let $\Psi_{\Gamma_{Q}}(\cdot):\overline{Q}\rightarrow\mathbb{R}^{k}$ denote a
function taking as input a node $\overline{Q}$ and outputting a vector
$v=(v_{1},...,v_{k})\in\mathbb{R}^{k}$.

$v_{p}\vcentcolon=\begin{cases}1&\mathbb{E}_{\Gamma_{Q}}[\sum_{j\in
N_{Q}(i)}\sum_{q\in[k]}f_{i,j}(p,q)a_{jq}]\geqslant\mathbb{E}_{\Gamma_{Q}}[\sum_{j\in
N_{Q}(i)}\sum_{q\in[k]}f_{i,j}(p^{\prime},q)a_{jq}]\text{ }\forall
p^{\prime}\in[k]\\\ 0&\text{otherwise}\end{cases}$

Furthermore let
$\Lambda_{\Gamma_{Q}}(i)\vcentcolon=\frac{\Psi_{\Gamma_{Q}}(i)}{\|\Psi_{\Gamma_{Q}}(i)\|_{1}}$.
With a slight abuse of notation, we will sometimes interpret
$\Lambda_{\Gamma_{Q}}(i)$ as a probability distribution over $[k]$ for all
$i\in\overline{Q}$. We also use $\Gamma_{Q}\bigcup\Lambda_{\Gamma_{Q}}(i)$ for
$i\in\overline{Q}$ to denote appending the best response distribution over
actions of node $i$ onto the distribution $\Gamma_{Q}$ defined over the nodes
$Q$. Similarly we use the notation $\Gamma_{Q}\bigcup_{i\in
Y}\Lambda_{\Gamma_{Q}}(i)$ to denote appending the best response distribution
of all nodes $i\in Y$ to $\Gamma_{Q}$ where $Y$ is any set of nodes disjoint
from $Q$.

We begin our discussion with a few definitions. First we define
$\Delta_{\zeta}(i)$ to be the average covariance of player $i$ with players
that are neighbors of $i$.

######  Definition 8.1.

Let $\Delta_{\zeta}(i)$ for $i\in[N]$ be defined as

$\Delta_{\zeta}(i)\vcentcolon=\sum_{j\in
N(i)}\sum_{(p,q)\in[k]^{2}}|\widetilde{\mathbb{E}}_{\zeta}[a_{ip}a_{jq}]-\widetilde{\mathbb{E}}_{\zeta}[a_{ip}]\widetilde{\mathbb{E}}_{\zeta}[a_{jq}]|$

Next we define $\Phi_{\Gamma}(i)$ for a product distribution
$\Gamma\in\mathcal{P}(k,V)$ to be the value of the Nash equilibrium
constraint.

######  Definition 8.2.

Let $\Gamma\in\mathcal{P}(k,V)$ be a product distribution defined to be
$\Gamma\vcentcolon=\\{\widetilde{\mathbb{E}}_{\zeta}[a_{ip}]\\}_{i\in[N],p\in[k]}$.
Then we define

$\Phi_{\Gamma}(i)\vcentcolon=\max_{w\in[k]}\Big{(}\sum_{j\in
N(i)}\sum_{q\in[k]}f_{ij}(w,q)\widetilde{\mathbb{E}}_{\zeta}[a_{jq}]-\sum_{j\in
N(i)}\sum_{(p,q)\in[k]^{2}}f_{ij}(p,q)\widetilde{\mathbb{E}}_{\zeta}[a_{ip}]\widetilde{\mathbb{E}}_{\zeta}[a_{jq}]\Big{)}$

Clearly we are trying to find a pseudoexpectation
$\widetilde{\mathbb{E}}_{\zeta}$ such that $\Phi_{\Gamma}(i)\leqslant\epsilon$
for all $i\in[N]$. The next lemma shows that after the rounding procedure in
Lemma 7.2 we satisfy the constraints of $\Phi_{\Gamma}(i)$ up to an error that
scales with the average pairwise covariance

######  Lemma 2.

Let
$\Gamma\vcentcolon=\\{\widetilde{\mathbb{E}}_{\zeta}[a_{ip}]\\}_{i\in[N],p\in[k]}$
be a product distribution where $\widetilde{\mathbb{E}}_{\zeta}$ is the output
of Lemma 7.2. Then we have that for all $i\in[N]$

$\Phi_{\Gamma}(i)\leqslant\epsilon+L\Delta_{\zeta}(i)$

We defer the proof of Lemma 2 to Section C. WithLemma 2, it suffices to show
that our rounding Algorithm 2 produces a product distribution such that
$\Delta(i)\leqslant\frac{\epsilon}{L}$ for all $i\in[N]$.

######  Lemma 8.3.

If global correlation $\Delta\leqslant\epsilon^{2}$ then no more than
$\epsilon N$ nodes satisfy $\Delta(i)\geqslant 2\epsilon$

###### Proof.

Assume the contrary, if more than $\epsilon N$ nodes had $\Delta(i)\geqslant
2\epsilon$ then

$\Delta\vcentcolon=\frac{1}{|E|}\sum_{i=1}^{N}|N(i)|\Delta(i)\geqslant\frac{pN}{2pN^{2}}\sum_{i=1}^{N}\Delta(i)\geqslant\epsilon^{2}$

which is a contradiction. ∎

Finally, we need a lemma that says the Nash constraint is still $2\epsilon$
approximately satisfied if an $\frac{\epsilon}{L}$ fraction of the neighbors
of $i$ play best response or in fact any response.

######  Lemma 3.

Let $Q$ be a subset of the vertices $V$ in graph $G$. Let Let
$\mathcal{P}(k,Q)$ denote the space of product distributions over $[k]$
actions in $|Q|$ dimensions for agents in the vertices $Q$. Let $\Gamma_{Q}$
be a product distribution in $\mathcal{P}(k,Q)$. Similarly, let
$\mathcal{P}(k,\overline{Q})$ denote the space of product distributions over
$[k]$ actions in $|\overline{Q}|$ dimensions for agents in the vertices
$\overline{Q}$. Then for all $i\in Q$ we have

$\max_{\Gamma_{\overline{Q}}\in\mathcal{P}(k,\overline{Q})}\Phi_{\Gamma_{Q}\bigcup\Gamma_{\overline{Q}}}(i)\leqslant\Phi_{\Gamma_{Q}}(i)+L\frac{|N_{\overline{Q}}(i)|}{|N(i)|}$

Here $\Phi_{\Gamma_{Q}\bigcup\Gamma_{\overline{Q}}}(i)$ is the value of the
nash equilibrium constraint on agent $i$ over the vertices in
$Q\bigcup\overline{Q}=V$ whereas $\Phi_{\Gamma_{Q}}(i)$ is only evaluated over
with respect to the vertices $Q$.

The proof is deferred to Section C. The next subsection is devoted to the
proof of Lemma 1.

###  8.2 Best Response Rounding Proof

In this section we prove Lemma 1, which provides guarantees for Algorithm 2.
First we present the guarantees for Algorithm 3

######  Lemma 4.

Let $H$ be a subset of $V$ with $|H|\geqslant ln^{3}(N)$. Then $W=Flag(H,G)$
satisfies the following

  1. 1.

$|W|\leqslant\frac{4}{3}|H|$

  2. 2.

$\frac{|N_{W}(i)|}{d}\leqslant\frac{40|H|}{3N}+10\frac{\ln^{2}(N)}{d}$ for all
$i\in\overline{W}$

with high probability $1-N^{-\ln^{3}(N)}\ln(N)$ over the randomness of $G$.

Next we present guarantees for Algorithm 4.

######  Lemma 5.

Let $W\subseteq V$ and let $\Gamma\in\mathcal{P}(k,N)$ be a product
distribution over $k$ elements in $N$ dimensions. We represent the product
distribution $\Gamma\vcentcolon=\\{\\{\mu_{ip}\\}_{p\in[k]}\\}_{i\in V}$ where
$\mu_{ip}=\mathbb{P}[a_{ip}=1]$. Let
$\Gamma_{\overline{W}}=\\{\\{\mu_{ip}\\}_{p\in[k]}\\}_{i\in\overline{W}}$ .
Let $\zeta\vcentcolon=\max_{i\in\overline{W}}\Phi_{\Gamma_{\overline{W}}}(i)$.
Let $\gamma\vcentcolon=\max_{i\in\overline{W}}\frac{|N_{W}(i)|}{d}$. Then
$BestRespond(W,\Gamma)$ outputs $(B,\hat{\Gamma})$ satisfying
$|B|\leqslant\frac{|W|}{10}$ and
$\max_{i\in\overline{B}}\Phi_{\hat{\Gamma}}(i)\leqslant\max(\zeta+L\gamma,10L\epsilon)$

Finally we move on to prove Lemma 1 See 1

###### Proof.

Let $\zeta_{t}\vcentcolon=\max_{i\in\overline{W}}\Phi_{\Gamma_{t}}(i)$, and
let $\gamma_{t}\vcentcolon=\max_{i\in\overline{W}}\frac{|N_{W}(i)|}{d}$. For
any $t\in[T-1]$ we have,

$\zeta_{t+1}\leqslant\max(\zeta_{t}+L\gamma_{t+1},100L\epsilon)\leqslant\max(\zeta_{t}+L(\frac{4c}{3}|K_{t+1}|+c\frac{\ln^{2}(N)}{d}),100L\epsilon)$

Here the first inequality follows from Lemma 5. The second inequality follows
from Corollary LABEL:cor:append-lemma which establishes that
$\gamma_{t}\leqslant\frac{4c}{3}|K_{t}|+c\frac{\ln^{2}(N)}{d}$. Next, we
continue to upper bound by

$\leqslant\max(\zeta_{t}+L(\frac{4c}{3}\frac{1}{4^{t}}\epsilon+c\frac{\ln^{2}(N)}{d}),100L\epsilon)\leqslant\max(\zeta_{0},100L\epsilon)+L\frac{4c}{3}\sum_{i=1}^{t}\frac{1}{4^{i}}\epsilon+Lc\frac{t\ln^{2}(N)}{d}$

Here the first inequality follows from Lemma 5 where we have
$|K_{t+1}|\leqslant\frac{|K_{t}|}{4}$. The second inequality follows from the
generic observation that for a sequence $a_{1},a_{2},...,a_{T}\in\mathbb{R}$
satisfying $a_{t+1}=\max(a_{t}+c_{t+1},b)$, we can conclude
$a_{t+1}\leqslant\max(a_{0},b)+\sum_{i=1}^{t+1}c_{i}$.

$\leqslant
100L\epsilon+L\frac{16c}{9}\epsilon+Lc\frac{t\ln^{2}(N)}{d}\leqslant
100L\epsilon+L\frac{16c}{9}\epsilon+Lc\frac{\ln^{3}(N)}{d}\leqslant
100L\epsilon+L\frac{16c}{9}\epsilon+Lc\epsilon$

The first inequality follows from the base case $\zeta_{0}\leqslant
2\epsilon$. The second inequality follows from $t\leqslant\ln(N)$, which holds
because $K_{t}$ contracts exponentially until $K_{T-1}\leqslant\ln^{3}(N)$.
Note that the above bound is independent of $t$ because we have carried out
all the geometric sums. Therefore, $\zeta_{T}\leqslant
100L\epsilon+L\frac{16c}{9}\epsilon$ which guarantees for all $i\in V$ that

$\Phi_{\Gamma_{T}}(i)\leqslant 100L\epsilon+20L\epsilon$

∎

## Acknowledgements

The author would like to thank Prasad Raghavendra, Ankur Moitra, and Costis
Daskalakis for helpful discussions.

## References

  * [BRS11] Boaz Barak, Prasad Raghavendra, and David Steurer.  Rounding semidefinite programming hierarchies via global correlation.  CoRR, abs/1104.4680, 2011.
  * [CCDP16] Yang Cai, Ozan Candogan, Constantinos Daskalakis, and Christos H. Papadimitriou.  Zero-sum polymatrix games: A generalization of minmax.  Math. Oper. Res., 41:648–655, 2016.
  * [DFSS14] Argyrios Deligkas, John Fearnley, Rahul Savani, and Paul Spirakis.  Computing approximate nash equilibria in polymatrix games, 2014.
  * [DGP06] Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou.  The complexity of computing a nash equilibrium.  In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’06, page 71–78, New York, NY, USA, 2006. Association for Computing Machinery.
  * [GLS81] Martin Grötschel, Lovász László, and Alexander Schrijver.  The ellipsoid method and its consequences in combinatorial optimization.  Combinatorica, 1:169–197, 06 1981.
  * [GS11] V. Guruswami and A. Sinop.  Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with psd objectives.  In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 482–491, Los Alamitos, CA, USA, oct 2011. IEEE Computer Society.
  * [KLS13] Michael J. Kearns, Michael L. Littman, and Satinder P. Singh.  Graphical models for game theory.  CoRR, abs/1301.2281, 2013.
  * [Las06] Jean Bernard Lasserre.  A sum of squares approximation of nonnegative polynomials.  SIAM Rev., 49:651–669, 2006.
  * [LMM03] Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta.  Playing large games using simple strategies.  In Proceedings of the 4th ACM Conference on Electronic Commerce, EC ’03, page 36–41, New York, NY, USA, 2003. Association for Computing Machinery.
  * [Nas50] John F. Nash.  Equilibrium points in n-person games.  Proceedings of the National Academy of Sciences, 36(1):48–49, 1950\.
  * [NES00] Yu. NESTEROV.  Squared functional systems and optimization problems.  LIDAM Reprints CORE 1472, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE), January 2000.
  * [Par03] Pablo A. Parrilo.  Semidefinite programming relaxations for semialgebraic problems.  Mathematical Programming, 96:293–320, 2003.
  * [RT11] Prasad Raghavendra and Ning Tan.  Approximating csps with global cardinality constraints using SDP hierarchies.  CoRR, abs/1110.1064, 2011.
  * [Rub14] Aviad Rubinstein.  Inapproximability of nash equilibrium.  CoRR, abs/1405.3322, 2014.
  * [Sho87] N. Z. Shor.  Class of global minimum bounds of polynomial functions.  Cybernetics, 23(6):731–734, Nov 1987.
  * [vNM47] J. von Neumann and O. Morgenstern.  Theory of games and economic behavior.  Princeton University Press, 1947.
  * [WHN16] Xiaodi Wu, Aram Harrow, and Anand Natarajan.  Tight sos-degree bounds for approximate nash equilibria.  05 2016.

##  Appendix A Feasibility of Convex Hierarchy

######  Lemma A.1.

Let $(G,\\{f_{ij}\\}_{i,j\in[N]})$ be a polymatrix game defined on graph $G$
with rescaled payoffs $\\{f_{ij}\\}_{i,j\in[N]}$ that are $L$-smooth. If $G$
is a random graph with edge density $\frac{k^{8}}{\epsilon^{4}}\ln^{3}(N)$ we
have the constraints of Algorithm 1 are feasible for
$\ell=\frac{L^{4}\ln(k)}{\epsilon^{4}}$. In particular, any mixed nash
equilibrium of the game is a feasible pseudodistribution.

###### Proof.

Let $\zeta\in\mathcal{P}(N,k)$ be the product distribution over $[k]^{N}$
corresponding to a mixed nash equilibrium. Since $\zeta$ is a distribution we
immediately satisfy $\widetilde{\mathbb{E}}_{\zeta}[1]=1$ and
$\widetilde{\mathbb{E}}_{\zeta}[p(\mathbb{a})]\geqslant 0$ for all
$p(\mathbb{a})\in SoS_{\ell}(\\{a_{ir}\\}_{i\in[N],r\in[k]})$. Furthermore, it
is immediate that $\widetilde{\mathbb{E}}[(a_{ip}^{2}-a_{ip})\prod_{a_{uv}\in
S}a_{uv}]=0$ for all $i\in[N]$ and $p\in[k]$, and for all $S\subset\mathbb{a}$
of size $|S|\leqslant\ell-2$. It is also immediate that
$\widetilde{\mathbb{E}}[(\sum_{p=1}^{k}a_{ip}-1)\prod_{a_{uv}\in S}a_{uv}]=0$
for all $i\in[N]$ and for all $S\subset\mathbb{a}$ of size
$|S|\leqslant\ell-1$. Next we have

$\mathbb{E}_{\zeta}[(\sum_{j\in
N(i)}\sum_{p,q\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}-\sum_{j\in
N(i)}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}+2\epsilon)\prod_{a_{uv}\in S}a_{uv}]$

Let $R\subseteq S$ where for all $a_{uv}\in R$ we have $u\in N(i)$. This
enables us to write

$=\mathbb{E}_{\zeta}[(\sum_{j\in
N(i)}\sum_{p,q\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}-\sum_{j\in
N(i)}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}+2\epsilon)\prod_{a_{uv}\in
R}a_{uv}\prod_{a_{uv}\in S/R}a_{uv}]$

Using the fact that $\zeta$ is a product distribution we obtain

$=\mathbb{E}_{\zeta}[(\sum_{j\in
N(i)}\sum_{p,q\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}-\sum_{j\in
N(i)}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}+2\epsilon)\prod_{a_{uv}\in
R}a_{uv}]\mathbb{E}_{\zeta}[\prod_{a_{uv}\in S/R}a_{uv}]$ (2)

Since $\prod_{a_{uv}\in S/R}a_{uv}$ is a sum of squares, we have
$\mathbb{E}_{\zeta}[\prod_{a_{uv}\in S/R}a_{uv}]\geqslant 0$. So to show (2)
is nonnegative, it suffices to show

$\mathbb{E}_{\zeta}[(\sum_{j\in
N(i)}\sum_{p,q\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}-\sum_{j\in
N(i)}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}+2\epsilon)\prod_{a_{uv}\in
R}a_{uv}]\geqslant 0$ (3)

Moving on, we break $N(i)$ into $N(i)/R$ and $R$ and write (3) accordingly,

$\hyperref@@ii[eq:feasible2]{\textup{(\ref*{eq:feasible2})}}=\mathbb{E}_{\zeta}[(\sum_{j\in
N(i)/R}\sum_{p,q\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}-\sum_{j\in
N(i)/R}\sum_{q\in[k]}f_{ij}(w,q)a_{jq})\\\ +\sum_{j\in
R}\sum_{(p,q)\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}-\sum_{j\in
R}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}+2\epsilon)\prod_{a_{uv}\in R}a_{uv}]$ (4)

$=\mathbb{E}_{\zeta}[\big{(}\sum_{j\in
N(i)/R}\sum_{p,q\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}-\sum_{j\in
N(i)/R}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}\big{)}\prod_{a_{uv}\in R}a_{uv}\\\
+\sum_{j\in R}\sum_{(p,q)\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}\prod_{a_{uv}\in
R}a_{uv}-\sum_{j\in R}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}\prod_{a_{uv}\in
R}a_{uv}+2\epsilon\prod_{a_{uv}\in R}a_{uv}]$ (5)

By linearity

$=\mathbb{E}_{\zeta}[\big{(}\sum_{j\in
N(i)/R}\sum_{p,q\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}-\sum_{j\in
N(i)/R}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}\big{)}\prod_{a_{uv}\in R}a_{uv}]\\\
+\widetilde{\mathbb{E}}_{\zeta}[\sum_{j\in
R}\sum_{(p,q)\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}\prod_{a_{uv}\in
R}a_{uv}-\sum_{j\in R}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}\prod_{a_{uv}\in
R}a_{uv}+2\epsilon\prod_{a_{uv}\in R}a_{uv}]$ (6)

Using the fact that $\zeta$ is a product distribution we obtain

$=\mathbb{E}_{\zeta}[\big{(}\sum_{j\in
N(i)/R}\sum_{p,q\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}-\sum_{j\in
N(i)/R}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}\big{)}]\widetilde{\mathbb{E}}_{\zeta}[\prod_{a_{uv}\in
R}a_{uv}]\\\ +\widetilde{\mathbb{E}}_{\zeta}[\sum_{j\in
R}\sum_{(p,q)\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}\prod_{a_{uv}\in
R}a_{uv}-\sum_{j\in R}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}\prod_{a_{uv}\in
R}a_{uv}+2\epsilon\prod_{a_{uv}\in R}a_{uv}]$ (7)

Again we use the fact that $\prod_{a_{uv}\in R}a_{uv}$ is a sum of squares so
$\widetilde{\mathbb{E}}_{\zeta}[\prod_{a_{uv}\in R}a_{uv}]\geqslant 0$. We
also use the fact that $\zeta$ is a mixed nash equilibrium so

$\mathbb{E}_{\zeta}[\big{(}\sum_{j\in
N(i)/R}\sum_{p,q\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}-\sum_{j\in
N(i)/R}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}\big{)}]\geqslant-\epsilon$

Plugging both these facts back into the first term of (7) we obtain

$\hyperref@@ii[eq:feasible3]{\textup{(\ref*{eq:feasible3})}}\geqslant\widetilde{\mathbb{E}}_{\zeta}[\sum_{j\in
R}\sum_{(p,q)\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}\prod_{a_{uv}\in
R}a_{uv}-\sum_{j\in R}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}\prod_{a_{uv}\in
R}a_{uv}+\epsilon\prod_{a_{uv}\in R}a_{uv}]$ (8)

By $L$-smoothness we have $f_{ij}(p,q)\geqslant-\frac{L}{d}$. Therefore, the
first term $\widetilde{\mathbb{E}}_{\zeta}[\sum_{j\in
R}\sum_{(p,q)\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}\prod_{a_{uv}\in R}a_{uv}]$ is
lower bounded by $\widetilde{\mathbb{E}}_{\zeta}[\frac{-L}{d}\sum_{j\in
R}\sum_{(p,q)\in[k]^{2}}a_{ip}a_{jq}\prod_{a_{uv}\in R}a_{uv}]$. Similarly,
using the fact that $f_{ij}(p,q)\leqslant\frac{L}{d}$, we conclude that the
second term $-\widetilde{\mathbb{E}}_{\zeta}[\sum_{j\in
R}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}\prod_{a_{uv}\in R}a_{uv}]$ is lower bounded
by $-\widetilde{\mathbb{E}}_{\zeta}[\frac{L}{d}\sum_{j\in
R}\sum_{q\in[k]}a_{jq}\prod_{a_{uv}\in R}a_{uv}]$. Plugging both relations
into (8) we obtain

$\geqslant\widetilde{\mathbb{E}}_{\zeta}[\frac{-L}{d}\sum_{j\in
R}\sum_{(p,q)\in[k]^{2}}a_{ip}a_{jq}\prod_{a_{uv}\in
R}a_{uv}-\frac{L}{d}\sum_{j\in R}\sum_{q\in[k]}a_{jq}\prod_{a_{uv}\in
R}a_{uv}+\epsilon\prod_{a_{uv}\in R}a_{uv}]$ (9)

$=\widetilde{\mathbb{E}}_{\zeta}[\big{(}\frac{-L}{d}\sum_{j\in
R}\sum_{(p,q)\in[k]^{2}}a_{ip}a_{jq}-\frac{L}{d}\sum_{j\in
R}\sum_{q\in[k]}a_{jq}+\epsilon\big{)}\prod_{a_{uv}\in R}a_{uv}]$ (10)

Using the booleanity constraint we lower bound by

$\geqslant\widetilde{\mathbb{E}}_{\zeta}[\big{(}-\frac{L|R|(k^{2}+k)}{d}+\epsilon\big{)}\prod_{a_{uv}\in
R}a_{uv}]$ (11)

Plugging $d=\frac{Lk^{8}\ln^{3}(N)}{\epsilon^{5}}$ and
$|R|=\frac{\ln(k)}{\epsilon^{4}}$ we obtain

$-\frac{L|R|(k^{2}+k)}{d}+\epsilon\geqslant 0$

Since $\prod_{a_{uv}\in R}a_{uv}$ is a sum of squares we conclude
$\hyperref@@ii[eq:feasible5]{\textup{(\ref*{eq:feasible5})}}\geqslant 0$ as
desired. TODO: Change $d=\frac{Lk^{8}\ln^{3}(N)}{\epsilon^{5}}$ ∎

##  Appendix B Explicit Convex Constraints

#### Moment Matrices:

Let $M_{\ell}(\\{a_{ir}\\}_{i\in[N],r\in[k]})$ be the moment matrix with rows
indexed by subsets $I\subseteq\\{a_{ir}\\}_{i\in[N],r\in[k]}$ for
$|I|\leqslant\ell$. Similarly, columns are indexed by subsets
$J\subseteq\\{a_{ir}\\}_{i\in[N],r\in[k]}$ for $|J|\leqslant\ell$. We require
that

$M_{\ell}(\mathbb{a})\succeq 0$ $M_{\ell}(\mathbb{a})_{\emptyset,\emptyset}=1$

Note that the PSD constraint implies via the cholesky decomposition that

$M_{\ell}(\mathbb{a})=V^{T}V$

for a matrix $V\in\mathbb{R}^{{Nk\choose\ell}\times{Nk\choose\ell}}$ with
columns equal to $v_{H}$ for all $H\subset\\{a_{ir}\\}_{i\in[N],r\in[k]}$
satisfying $|H|\leqslant\ell$. Now, given the vectors
$\\{v_{H}\\}_{H\subset\\{a_{ir}\\}_{i\in[N],r\in[k]},|H|\leqslant\ell}$ we add
the linear constraints that

$\widetilde{\mathbb{E}}[\prod_{a_{uv}\in H}a_{uv}]\vcentcolon=\langle
v_{H_{1}},v_{H_{2}}\rangle$

for all $H_{1}$ and $H_{2}$ satisfying $H_{1}\cup H_{2}=H$. Henceforth we may
refer to $\widetilde{\mathbb{E}}[\prod_{(u,v)\in H}a_{uv}]$ without ambiguity.
Also note that we have satisfied the $\widetilde{\mathbb{E}}[1]=1$ and
$\widetilde{\mathbb{E}}[p(\mathbb{a})]\geqslant 0$ constraints for all
$p(\mathbb{a})\in SoS_{\ell}(\mathbb{a})$. At this point, we can define the
linear functional
$\widetilde{\mathbb{E}}:\mathbb{R}_{\leqslant\ell}[\mathbb{a}]\rightarrow\mathbb{R}$
from the degree less than $\ell$ polynomials to the reals so that
$\widetilde{\mathbb{E}}[\sum_{i}\alpha_{i}p_{i}(a)]=\sum_{i}\alpha_{i}\widetilde{\mathbb{E}}[p_{i}(a)]$.

The booleanity and color constraints are relaxed in the manner prescribed by
the Sherali-Adams hierarchy. We add linear constraints for all $i\in[N]$ and
$p\in[k]$

$\widetilde{\mathbb{E}}[(a_{ip}^{2}-a_{ip})\prod_{a_{uv}\in
S}a_{uv}]=\widetilde{\mathbb{E}}[a_{ip}^{2}\prod_{a_{uv}\in
S}a_{uv}]-\widetilde{\mathbb{E}}[a_{ip}\prod_{a_{uv}\in S}a_{uv}]=0$

for all $S\subset\\{a_{ir}\\}_{i\in[N],r\in[k]}$ with size
$|S|\leqslant\ell-2$. Additionally, we add linear constraints for all
$i\in[N]$

$\widetilde{\mathbb{E}}[(\sum_{r=1}^{k}a_{ir}-1)\prod_{a_{uv}\in
S}a_{uv}]=\sum_{r\in[k]}\widetilde{\mathbb{E}}[a_{ir}\prod_{a_{uv}\in
S}a_{uv}]-\widetilde{\mathbb{E}}[\prod_{a_{uv}\in S}a_{uv}]=0$

for all $S\subset\\{a_{ir}\\}_{i\in[N],r\in[k]}$ satisfying
$|S|\leqslant\ell-1$. Finally, we add the linear constraints for conditioning
preserving correlated equilibrium. For all $i\in[N]$ and for all $w\in[k]$

$\widetilde{\mathbb{E}}[\big{(}\sum_{j\in
N(i)}\sum_{p,q\in[k]^{2}}f_{ij}(p,q)a_{ip}a_{jq}\big{)}\prod_{a_{uv}\in
S}a_{uv}]-\widetilde{\mathbb{E}}[\big{(}\sum_{j\in
N(i)}\sum_{q\in[k]}f_{ij}(w,q)a_{jq}\big{)}\prod_{a_{uv}\in
S}a_{uv}]+\epsilon\geqslant 0$

for all $S\subset\\{a_{jr}\\}_{j\in[N]/i,r\in[k]}$ with size
$|S|\leqslant\ell-2$.

##  Appendix C Best Response Pursuit Lemmas

See 2

###### Proof.

We begin with the definition

$\Phi_{\Gamma}(i)=\max_{w\in[k]}\Big{(}\sum_{j\in
N(i)}\sum_{q\in[k]}f_{ij}(w,q)\widetilde{\mathbb{E}}[a_{jq}]-\sum_{j\in
N(i)}\sum_{(p,q)\in[k]^{2}}f_{ij}(p,q)\widetilde{\mathbb{E}}[a_{ip}]\widetilde{\mathbb{E}}[a_{jq}]\Big{)}$

Let $w^{*}$ be the argmax over $w\in[k]$ in the equation above. Then we
rewrite the equation as

$=\sum_{j\in
N(i)}\sum_{(p,q)\in[k]^{2}}f_{ij}(p,q)(\widetilde{\mathbb{E}}[a_{ip}a_{jq}]-\widetilde{\mathbb{E}}[a_{ip}]\widetilde{\mathbb{E}}[a_{jq}])\\\
+\sum_{j\in
N(i)}\sum_{q\in[k]}f_{ij}(w^{*},q)\widetilde{\mathbb{E}}[a_{jq}]-\sum_{j\in
N(i)}\sum_{(p,q)\in[k]^{2}}f_{ij}(w^{*},q)\widetilde{\mathbb{E}}[a_{ip}a_{jq}]$

The second line is the conditioning preserving correlated equilibrium
constraint which we know is less than $\epsilon$. Therefore we upper bound by

$\leqslant\epsilon+\sum_{j\in
N(i)}\sum_{(p,q)\in[k]^{2}}f_{ij}(p,q)(\widetilde{\mathbb{E}}[a_{ip}a_{jq}])-\widetilde{\mathbb{E}}[a_{ip}]\widetilde{\mathbb{E}}[a_{jq}])$

We upper bound via $\ell_{1,\infty}$ holders and use the fact that
$f_{i,j}(a,b)\leqslant\frac{L}{d}$.

$\leqslant\epsilon+\frac{L}{d}\sum_{j\in
N(i)}\sum_{(p,q)\in[k]^{2}}|\widetilde{\mathbb{E}}[a_{ip}a_{jq}]-\widetilde{\mathbb{E}}[a_{ip}]\widetilde{\mathbb{E}}[a_{jq}]|]=\epsilon+L\Delta(i)$

∎

See 3

###### Proof.

We have by definition

$\Phi_{\Gamma_{Q}\bigcup\Gamma_{\overline{Q}}}(i)\vcentcolon=\max_{w\in[k]}\mathbb{E}_{\Gamma_{Q}\bigcup\Gamma_{\overline{Q}}}[\sum_{j\in
N_{Q\bigcup\overline{Q}}(i)}\sum_{q\in[k]}f_{i,j}(w,q)a_{jq}-\sum_{j\in
N_{Q\bigcup\overline{Q}}(i)}\sum_{(p,q)\in[k]^{2}}f_{i,j}(p,q)a_{ip}a_{jq}]$

Using the fact that $N_{Q\bigcup\overline{Q}}(i)=N_{Q}(i)\bigcup
N_{\overline{Q}}(i)$ we obtain

$=\max_{r\in[k]}\mathbb{E}_{\Gamma_{Q}\bigcup\Gamma_{\overline{Q}}}[\sum_{j\in
N_{Q}(i)}\sum_{p\in[k]}f_{i,j}(w,p)a_{jp}+\sum_{j\in
N_{\overline{Q}}(i)}\sum_{p\in[k]}f_{i,j}(w,p)a_{jp}\\\ -(\sum_{j\in
N_{Q}(i)}\sum_{(p,q)\in[k]^{2}}f_{i,j}(p,q)a_{ip}a_{jq}+\sum_{j\in
N_{\overline{Q}}(i)}\sum_{(p,q)\in[k]^{2}}f_{i,j}(p,q)a_{ip}a_{jq})]$ (12)

Using the $L$-smooth assumption we obtain

$\leqslant\max_{w\in[k]}\mathbb{E}_{\Gamma_{Q}\bigcup\Gamma_{\overline{Q}}}[\sum_{j\in
N_{Q}(i)}\sum_{p\in[k]}f_{i,j}(w,p)a_{jp}-\sum_{j\in
N_{Q}(i)}\sum_{(p,q)\in[k]^{2}}f_{i,j}(p,q)a_{ip}a_{jq}+2L\frac{|N_{\overline{Q}}(i)|}{|N(i)|}]$

$=\max_{w\in[k]}\mathbb{E}_{\Gamma_{Q}}[\sum_{j\in
N_{Q}(i)}\sum_{p\in[k]}f_{i,j}(w,p)a_{jp}-\sum_{j\in
N_{Q}(i)}\sum_{(p,q)\in[k]^{2}}f_{i,j}(p,q)a_{ip}a_{jq}]+2L\frac{|N_{\overline{Q}}(i)|}{|N(i)|}$

Using the definition of $\Phi_{Q}(i)$ we conclude

$=\Phi_{Q}(i)+2L\frac{|N_{\overline{Q}}(i)|}{|N(i)|}$

as desired. ∎

To prove Lemma 4 we will need the following supporting lemma.

######  Lemma C.1.

For any subset of nodes $H\subset[N]$, the number of nodes $i\in\overline{H}$
satisfying $|N_{H}(i)|\geqslant\max(10\frac{|H|}{N}d,10\ln(n))$ is less than
$\frac{H}{4}$.

###### Proof.

We proceed by an application of the chernoff and union bound. Let’s fix the
set $H$. Then for any node $i\in[N]$, the probability
$|N_{H}(i)|\geqslant\max(10\frac{|H|}{N}|E(i)|,10\ln(n))$ is upper bounded as
follows. Let $e_{j}$ be the following random variable with $e_{j}=1$ if $j\in
H$ and $e_{j}=0$ otherwise. Here the randomness is taken with respect to the
randomness in generating the graph. Let
$\mu\vcentcolon=\mathbb{E}[\frac{1}{N}\sum_{j=1}^{N}e_{j}]=\frac{|H|}{N}\frac{d}{N}$.
We define a constant $\delta>0$ such that $(1+\delta)\mu
N=\max(10\frac{|H|}{N}d,10\ln(n))\geqslant 10\frac{|H|}{N}d$. This implies
$\delta>9$. Now let
$\tau\vcentcolon=\mathbb{P}[\frac{1}{N}\sum_{j=1}^{N}e_{j}\geqslant(1+\delta)\mu]$.
Using the chernoff bound we obtain.

$\tau\vcentcolon=\mathbb{P}[\frac{1}{N}\sum_{j=1}^{N}e_{j}\geqslant(1+\delta)\mu]\leqslant\exp(-\delta\mu
N)\leqslant\exp(-9\mu N)$

If $\mu N\geqslant\ln(N)$ then we have $\tau\leqslant\exp(-9\ln(N))$. On the
other hand, if $\mu N\leqslant\ln(N)$ we define $\delta$ such that
$(1+\delta)\mu N=\max(10\frac{|H|}{N}d,10\ln(n))\geqslant 10\ln(N)$ which
implies $\delta\mu N\geqslant 9\ln(N)$. Thus we have in this case

$\tau\vcentcolon=\mathbb{P}[\frac{1}{N}\sum_{j=1}^{N}e_{j}\geqslant(1+\delta)\mu]\leqslant\exp(-\delta\mu
N)\leqslant\exp(-9\ln(N))$

Now let
$H^{*}\vcentcolon=\\{i\in\overline{H}||N_{H}(i)|\geqslant\max(10\frac{|H|}{N}d,10\ln(n))\\}$.
We need to show $|H^{*}|\leqslant\frac{|H|}{4}$. Let $w_{i}$ for $i\in[N]$ be
a random variable where $w_{i}=1$ if $i\in H^{*}$ and $w_{i}=0$ otherwise. Let
$\mu^{\prime}\vcentcolon=\mathbb{E}[\frac{1}{N}\sum_{i=1}^{N}w_{i}]=\tau$. Let
$\delta^{\prime}>0$ be defined such that
$(1+\delta^{\prime})\mu^{\prime}N=\frac{|H|}{4}$ then by chernoff bound we
have

$\mathbb{P}(\frac{1}{N}\sum_{i=1}^{N}w_{i}\geqslant\mu^{\prime}(1+\delta^{\prime}))\leqslant\Big{(}\frac{e^{\delta^{\prime}}}{(1+\delta^{\prime})^{(1+\delta^{\prime})}}\Big{)}^{\mu^{\prime}N}=\exp((\delta^{\prime}-(1+\delta^{\prime})\ln(1+\delta^{\prime}))\mu^{\prime}N)$

Using the fact that $(1+\delta^{\prime})\mu^{\prime}N=\frac{|H|}{4}$ we obtain

$\leqslant\exp(\frac{|H|}{4}-\ln(1+\delta^{\prime})\frac{|H|}{4})$ (13)

Next we use the fact that
$\delta^{\prime}=\frac{|H|}{4\mu^{\prime}N}-1\geqslant\frac{1}{4N}\exp(9\ln(N))-1\geqslant\frac{N^{8}}{4}-1$.
Plugging $\delta^{\prime}\geqslant\frac{N^{8}}{4}-1$ into

$\leqslant\exp(-8\ln(N)\frac{|H|}{4})\leqslant N^{-2|H|}$

Since there are no more than ${N\choose|H|}\leqslant N^{|H|}$ subsets of size
$|H|$ we conclude via union bound that $|H^{*}|\leqslant\frac{|H|}{4}$ with
probability $1-N^{-2|H|}N^{|H|}\geqslant 1-N^{-|H|}\geqslant
1-N^{-\ln^{3}(N)}$ as desired.

∎

See 4

###### Proof.

Let $H_{1}\vcentcolon=H$. Then we have by Lemma C.1 that $Flag(H_{1},G)$
iteratively appends $H_{2},...,H_{y}$ to $H_{1}$ where
$H_{i}\leqslant\frac{1}{4^{j-1}}H_{1}$ for all $j\in[2,y]$. Thus
$|W|\leqslant\frac{4}{3}|H|$. Furthermore, each iteration of of
$Flag(H_{1},G)$ ensures that for all $i\in\overline{W}$

$\frac{|N_{W}(i)|}{d}=\frac{1}{d}|N_{\bigcup_{j\in[y]}H_{j}}(i)|=\sum_{j=1}^{y}\frac{|N_{H_{j}}(i)|}{d}\leqslant\sum_{j=1}^{y}10\max\Big{(}\frac{|H_{j}|}{N},\frac{\ln(N)}{d}\Big{)}$
(14)

$\leqslant
10\sum_{j=1}^{y}\Big{(}\frac{|H_{j}|}{N}+\frac{\ln(N)}{d}\Big{)}\leqslant\frac{40}{3N}|H_{1}|+10\frac{\ln^{2}(N)}{d}$

Here the first inequality follows from the fact that at each iteration
$Flag(H_{1},G)$ performs the following operation. For
$W=\bigcup_{r=1}^{j}H_{r}$ we define $H_{j+1}$ to be

$H_{j+1}\vcentcolon=\Big{\\{}i\in\overline{W}\Big{|}\frac{|N_{H_{j}}(i)|}{d}\geqslant\max\Big{(}10\frac{|H_{j}|}{N},10\frac{\ln(n)}{d}\Big{)}\Big{\\}}$

Thus for all $i\in\overline{W}$ we have

$\frac{|N_{H_{j}}(i)|}{d}\leqslant\max\Big{(}10\frac{|H_{j}|}{N},10\frac{\ln(n)}{d}\Big{)}$

Continuing to bound (14), we separate the max into a sum to conclude

$\leqslant
10\sum_{j=1}^{y}\Big{(}\frac{|H_{j}|}{N}+\frac{\ln(N)}{d}\Big{)}\leqslant\frac{40}{3N}|H_{1}|+10\frac{\ln^{2}(N)}{d}$

We have established
$\frac{|N_{W}(i)|}{d}\leqslant\frac{40|H|}{3N}+10\frac{\ln^{2}(N)}{d}$ for all
$i\in\overline{W}$ as desired. ∎

See 5

###### Proof.

First, using Lemma 3 we have
$\max_{i\in\overline{W}}\Phi_{\hat{\Gamma}}(i)\leqslant\zeta+L\gamma$ which
concludes the lemma for $i\in\overline{W}$. To conclude the lemma it suffices
to show that $BestRespond(W,\Gamma)$ sets a subset $A\subseteq W$ to best
respond to $\Gamma_{\overline{W}}$, and that for all $i\in A$,
$\frac{|N_{W}(i)|}{d}\leqslant 10\epsilon$.

To show this, let $\kappa\in\mathbb{R}^{+}$ be a constant such that
$|W|=\kappa N$. Let $e_{1},...,e_{\kappa^{2}N^{2}}$ be the indicator random
variables distributed $Bern(p)$ for the presence of an edge between any pair
of nodes in $W$. Let $\mu=p$, and let $\delta\mu=\frac{10\epsilon d}{\kappa
N}=\frac{10\epsilon}{\kappa}p=\frac{10\epsilon}{\kappa}\mu$ which implies
$\delta=\frac{10\epsilon}{\kappa}$. Then for $|W|\leqslant\epsilon N$ we have
$\delta\geqslant 10$. Therefore, we invoke the upper chernoff bound to obtain

$\mathbb{P}[\frac{1}{\kappa^{2}N^{2}}\sum_{i=1}^{\kappa^{2}N^{2}}e_{i}\geqslant\frac{10\epsilon
d}{\kappa N}]\leqslant\exp(-\frac{9\epsilon d}{\kappa
N}\kappa^{2}N^{2})=\exp(-9\epsilon d\kappa
N)=\exp(-9\frac{1}{\epsilon^{3}}\ln^{3}(N)\kappa N)$

We also know there are no more than ${N\choose\kappa N}\leqslant N^{\kappa N}$
subsets of $V$ of size $\kappa N$. Therefore, applying union bound we conclude
that $W$ has fewer than $10\epsilon d\kappa N$ edges with high probability
$1-N^{-\ln^{3}(N)}$. Furthermore, via markov we conclude that no more than
$\frac{1}{10}|W|$ nodes $i\in W$ satisfy $N_{W}(i)\geqslant 100\epsilon d$.
Equivalently, there exists a subset $A\subseteq W$ of size
$|A|\geqslant\frac{9|W|}{10}$ such that $\frac{|N_{W}(i)|}{d}\leqslant
100\epsilon$ for all $i\in A$. By Lemma 3, we conclude $\max_{i\in
A}\Phi_{\hat{\Gamma}}(i)\leqslant 100L\epsilon$.

Putting everything together, for $BestResponsd(W,\Gamma)$ outputs $B=W/A$ such
that $\overline{B}=\overline{W}\bigcup A$. Thus we conclude,

$\max_{i\in\overline{B}}\Phi_{\hat{\Gamma}}(i)=\max_{i\in\overline{W}\bigcup
A}\Phi_{\hat{\Gamma}}(i)=\max(\max_{i\in\overline{W}}\Phi_{\hat{\Gamma}}(i),\max_{i\in
A}\Phi_{\hat{\Gamma}}(i))\leqslant\max(\zeta+L\gamma,100L\epsilon)$

as desired.

∎

##  Appendix D Miscellaneous

######  Lemma D.1.

(Bernstein, Jackson, folklore) There exists a series of polynomials
$\\{g_{p}(x)\\}_{p=1}^{n}$ where
$g_{p}(x)\vcentcolon=\sum_{r=1}^{p}\alpha_{r}x^{r}$ and
$\\{\alpha_{r}\\}_{r=1}^{n}$ is a series of coefficients satisfying
$\alpha_{r}\leqslant\frac{18}{\sqrt{\pi}}r^{-3/2}$ and
$|g_{n}(x)-|x||\leqslant\frac{6}{n}$.

######  Lemma D.2 ([RT11]).

There exists $t\leqslant k$ such that $E_{i_{1},...,i_{t}\sim W}E_{i,j\sim
W}[I(X_{i},X_{j}|X_{i_{1}},...,X_{i_{t}})]\leqslant\frac{\ln(q)}{k-1}$ where
$q$ is alphabet size.

###### Proof.

Linearity of expectation we have for any $t\leqslant k-2$

$E_{i,i_{1},...i_{t}\sim
W}[H(X_{i}|X_{i_{1}},...,X_{i_{t}})]=E_{i,i_{1},...i_{t}\sim
W}[H(X_{i}|X_{i_{1}},...,X_{i_{t-1}})-E_{i_{1},...,i_{t-1}\sim
W}E_{i,i_{t}\sim W}[I(X_{i},X_{i_{t}}|X_{i_{1}},...,X_{i_{t-1}})]$

adding equalities from $t=1$ to $k-2$ we get

$E[H(X_{i})]-E_{i_{1},...,i_{k-2}\sim
W}[H(X_{i}|X_{i_{1}},...,X_{i_{k-2}})]=\sum_{i\leqslant t\leqslant
k-1}E_{i,j,X_{i_{1}},...,X_{i_{t-1}}\sim
W}[I(X_{i},X_{j}|X_{i_{1}},...,X_{i_{t}})]$

Lemma follows from $H(X)\leqslant\ln(q)$ ∎

######  Definition D.3.

(Payoff Rescaling) For each game $p_{ij}$ for $(i,j)\in E$, let

$U_{i}\vcentcolon=\max_{a_{1},a_{2},...,a_{N}\in[k]}\sum_{j\in
N(i)}p_{ij}(a_{i},a_{j})$

and let

$L_{i}\vcentcolon=\min_{a_{1},a_{2},...,a_{N}\in[k]}\sum_{j\in
N(i)}p_{ij}(a_{i},a_{j})$

Then let
$f_{ij}(a_{i},a_{j})=(p_{ij}(a_{i},a_{j})-\frac{L_{i}}{|N(i)|})\frac{1}{U_{i}-L_{i}}$
such that $\sum_{j\in N(i)}f_{ij}(a_{i},a_{j})\in[0,1]$ for all
$\vec{a}\in[k]^{N}$.

######  Fact D.4.

Let $x_{1},...,x_{N}$ be i.i.d bernoulli random variables with
$\mu=\mathbb{E}[x_{i}]$. Upper chernoff bound, for any $\delta>0$

$\mathbb{P}(\frac{1}{N}\sum_{i=1}^{N}x_{i}\geqslant(1+\delta)\mu)\leqslant\Big{(}\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\Big{)}^{\mu
N}$

Lower chernoff bound. For $\delta\in[0,1]$

$\mathbb{P}(\frac{1}{N}\sum_{i=1}^{N}x_{i}\geqslant(1-\delta)\mu)\leqslant\exp\Big{(}\frac{-\delta^{2}\mu
N}{2}\Big{)}$