slightly rewrite it (see Equations (30) and (31)). We observe that the
Correct-bit-no-guide Lemma (Lemma 8) is applicable for the $y_{j}$-team
(without any modifications).

We start our formal discussion with isolating the utility terms of Equation
(12) that depend on the choice of the $y_{j}$-team.

$\displaystyle\begin{aligned} \mathbb{E}[U^{y}_{j}]=&-\sum_{p\in
P}(1+g^{p})\left[\left(\mathbb{E}[\overline{X}^{p}_{j}]-\mathbb{E}[\overline{Y}_{j}]-i(p,j)\epsilon_{S}\right)^{2}+\operatorname{Var}[\overline{Y}_{j}]\right]&&\text{(imitation)}\\\
&+\epsilon_{G}\mathbb{E}[\overline{Y}_{j}]\mathbb{E}[\Delta_{j}]&&\text{(gradient)}\\\
&-\epsilon_{T}\sum_{p\in
P,k\in[K]}(1+g^{p})\left[\left(\mathbb{E}[\overline{X}^{p}_{j}]-\mathbb{E}[\tilde{Y}_{j,k}]-i(p,j)\epsilon_{S}\right)^{2}+\operatorname{Var}[\tilde{Y}_{j,k}]\right]&&(y\text{-bit
imitation)}\\\
&-\epsilon_{T}\mathbb{E}[U^{x}_{\text{bit}}(\overline{Y}_{j})]&&(x\text{-bit
imitation)}\\\
&+\epsilon_{T}\epsilon_{G}\sum_{k\in[K]}\mathbb{E}[\tilde{Y}_{j,k}]\mathbb{E}[\Delta_{j}]&&\text{(bit
gradient)}\\\
&+\epsilon_{T}\mathbb{E}[M^{y}_{j}]&&\text{(veto)}.\end{aligned}$

######  Definition 4.

We define the variable $\hat{X}_{j}$ that equals
$\mathbb{E}[\overline{X}^{p}_{j}]-i(p,j)\epsilon_{S}$ with probability
$\frac{1+g^{p}}{10}$ for every $p\in P$, and we denote
$\hat{x}_{j}=\mathbb{E}[\hat{X}_{j}]$.

With this notation we can rewrite

$\displaystyle\begin{aligned}
\mathbb{E}[U^{y}_{j}]=\text{}&-10\left[\left(\mathbb{E}[\overline{Y}_{j}]-\hat{x}_{j}\right)^{2}+\operatorname{Var}[\overline{Y}_{j}]\right]&&\text{(imitation)}\\\
&+\epsilon_{G}\mathbb{E}[\overline{Y}_{j}]\mathbb{E}[\Delta_{j}]&&\text{(potential)}\\\
&-\epsilon_{T}\sum_{p\in
P,k\in[K]}10\left[\left(\mathbb{E}[\tilde{Y}_{j,k}]-\hat{x}_{j}\right)^{2}+\operatorname{Var}[\tilde{Y}_{j,k}]\right]&&(y\text{-bit
imitation)}\\\
&-\epsilon_{T}\mathbb{E}[U^{x}_{\text{bit}}(\overline{Y}_{j})]&&(x\text{-bit
imitation)}\\\
&+\epsilon_{T}\epsilon_{G}\sum_{k\in[K]}\mathbb{E}[\tilde{Y}_{j,k}]\mathbb{E}[\Delta_{j}]&&\text{(bit
gradient)}\\\
&+\epsilon_{T}\mathbb{E}[M^{y}_{j}]&&\text{(veto)}.\end{aligned}$ (30)

By merging the imitation utility with the gradient utility and merging the
$y$-bit utility with the bit gradient utility we obtain

$\displaystyle\begin{aligned}
\mathbb{E}[U^{y}_{j}]=\text{}&-10\left[\left(\mathbb{E}[\overline{Y}_{j}]-\hat{x}_{j}-\frac{\epsilon_{G}\mathbb{E}[\Delta_{j}]}{20}\right)^{2}+\operatorname{Var}[\overline{Y}_{j}]\right]\\\
&-10\epsilon_{T}\left[\sum_{k\in[K]}\left(\mathbb{E}[\tilde{Y}_{j,k}]-\hat{x}_{j}-\frac{\epsilon_{G}\mathbb{E}[\Delta_{j}]}{20}\right)^{2}+\operatorname{Var}[\tilde{Y}_{j,k}]\right]\\\
&-\epsilon_{T}\mathbb{E}[U^{x}_{\text{bit}}(\overline{Y}_{j})]\\\
&+\epsilon_{T}\mathbb{E}[M^{y}_{j}].\end{aligned}$ (31)

Using the representation of Equation (31) for the common utility of the
$y_{j}$-team we deduce the following lemma.

######  Lemma 13 (Perfect-$y$-imitation Lemma).

For every $j\in J$, the $y_{j}$-team perfectly imitates
$\hat{x}_{j}+\frac{\epsilon_{G}\mathbb{E}[\Delta_{j}]}{20}$.

###### Proof Sketch.

The arguments of the proof are very similar to those of the No-guide-imitation
Lemma (Lemma 9). The first term in Equation (31) plays the role of the
imitation utility. The second term in Equation (31) plays the role of the bit
imitation utility. The factor $3+g_{r}$ is replaced by the factor $10$ which
does not affect the arguments; the real number $\hat{y}_{r}$ is replaced by
the real number $\hat{x}_{j}+\frac{\epsilon_{G}\mathbb{E}[\Delta_{j}]}{20}$
which again does not affect the arguments.

Note also that we argued the validity of the lemma _without_ imposing
Assumption 1. This is because the imitation target
$\hat{x}_{j}+\frac{\epsilon_{G}\mathbb{E}[\Delta_{j}]}{20}$ necessarily
belongs to $[0,1)$. ∎

####  5.2.4 Mutual imitation

In this subsection we combine our observation regarding the imitation of the
$x_{r}$-teams and the $y_{j}$-teams from which we deduce a stronger bound on
the mutual imitation of the groups. The Far-Perfect Corollary (Corollary 3)
and the Mild-imitation Corollary (Corollary 4) allow us to argue that in each
dimension there exists at most one $x_{r}$-team that does not perfectly
imitate $\hat{y}_{r}$. We call such a team _problematic_ and we denote its
corresponding imitation error by $E_{j}$; see Definition 5. Our observations
about perfect imitation of groups allow us to provide a formula for the
imitation error $E_{j}$. This formula improves the imitation bound: we obtain
that all groups approximately perfectly imitate their target (this is stronger
than mild imitation from the Mild-imitation Corollary (Corollary 4)).

Since the shifts of the samples are of size $\epsilon_{S}$ and
$2^{-N_{in}}\gg\epsilon_{S}\gg\overline{\epsilon}_{C}$ we know that for every
$j\in J$ there exists at most one $i\in I$ such that $\hat{y}_{i,j}$ lands
$\overline{\epsilon}_{C}$-close to the $2^{-N_{in}-1}$-grid. Therefore, by the
Mild-imitation Corollary (Corollary 4) and the Far-Perfect Corollary
(Corollary 3) we deduce that among the $x_{i,j}$ teams for $i\in I$ there
exists at most one team that does not perfectly imitate $\hat{y}_{i,j}$. This
observation leads us to the following definitions and notations.

######  Definition 5 (Problematic teams and imitation error).

For every $j\in J$ the unique $i$ such that $\overline{x}_{i,j}$ does not
perfectly imitate $\hat{y}_{i,j}$ is called a _problematic_ team and is
denoted by $i^{*}_{j}$. If all $\hat{y}_{i,j}$ are
$\overline{\epsilon}_{C}$-far from the $2^{-N_{in}-1}$-grid then we say that
_a problematic team does not exist_. We denote by
$E_{j}:=\mathbb{E}[\overline{X}_{i^{*}_{j},j}]-\hat{y}_{i^{*}_{j},j}$ the
_imitation error_ of the problematic sample.383838Note that we define the
imitation error as a _signed_ difference. The sign will play a substantial
role latter. If a problematic team does not exist we set $E_{j}=0$. A sample
$p=(i_{1},i_{2})$ is called _problematic_ if at least one of the teams
$x_{i_{1},1}$ or $x_{i_{2},2}$ is problematic.

######  Lemma 14 (Error-formula Lemma).

Under Assumption 1, for every $j\in J$ we have

$E_{j}=-\frac{\epsilon_{G}}{6+2g_{r^{*}(j)}}\mathbb{E}[\Delta_{j}]\pm\tilde{O}(2^{-K}).$

###### Proof.

We fix $j\in J$. We note that for every $i\in I$ we have

$\displaystyle\begin{aligned}
\mathbb{E}[\overline{X}_{i,j}]&=\mathbb{E}[\overline{Y}_{j}]+i\epsilon_{S}\pm
O(2^{-K})&&\text{ for every }i\neq i^{*}_{1}\\\
\mathbb{E}[\overline{X}_{i,j}]&=\mathbb{E}[\overline{Y}_{j}]+i\epsilon_{S}+E_{j}&&\text{
for }i=i^{*}_{1}.\end{aligned}$ (32)

The equations in the first line follow from perfect imitation. The equality in
the second line follows from the definition of $E_{j}$. By the fact that the
$y_{j}$-team perfectly imitates
$\hat{x}_{j}+\frac{\epsilon_{G}\mathbb{E}[\Delta_{j}]}{20}$
(Perfect-$y$-imitation Lemma 13) and the definition of $\hat{x}_{j}$ we have

$\displaystyle\mathbb{E}[\overline{Y}_{j}]=\sum_{i\in
I}\frac{3+g_{i,j}}{10}\left(\mathbb{E}[\overline{X}_{i,j}]-i\epsilon_{S}\right)+\frac{\epsilon_{G}\mathbb{E}[\Delta_{j}]}{20}\pm
O(2^{-K})$ (33)

By plugging the Equations of (32) for every $i\in I$ in (33) the terms
$i\epsilon_{S}$ as well as term $\mathbb{E}[\overline{Y}_{j}]$ cancel out and
we obtain

$\displaystyle
0=\frac{3+g_{r^{*}(j)}}{10}E_{j}+\frac{\epsilon_{G}\mathbb{E}[\Delta_{j}]}{20}\pm
O(2^{-K}),$

and the lemma follows. ∎

The Error-formula Lemma (Lemma 14) has two important consequences. First, the
Error-formula Lemma significantly improves the imitation bound of the Mild-
imitation Corollary (Corollary 4). While the Mild-imitation Corollary states
that the imitation is bounded by $\tilde{O}(\overline{\epsilon}_{C}^{2})$, in
the Error-formula Lemma 14 we see that the imitation is bounded by
$\tilde{O}(\epsilon_{G}^{2})$. In particular, so far the driving force of most
arguments we applied was the imitation term. The Error-formula Lemma shows
that this term is in fact negligible in every equilibrium since it is bounded
by $\tilde{O}(\epsilon_{G}^{2})$. Circuit’s computations and the potential
utility, which have the weights of $\epsilon_{C}\gg\epsilon_{G}^{2}$ and
$\epsilon_{P}\gg\epsilon_{G}^{2}$ will be the driving forces of the upcoming
arguments. The second important consequence is that $E_{j}$ and
$\mathbb{E}[\Delta_{j}]$ have opposite signs. Namely, whenever
$\mathbb{E}[\Delta_{j}]>0$ the team $x_{r^{*}(j)}$ _under-estimates_ the
target $\hat{y}_{r^{*}(j)}$. Whenever $\mathbb{E}[\Delta_{j}]<0$ the team
$x_{r^{*}(j)}$ _over-estimates_ the target $\hat{y}_{r^{*}(j)}$. This
consequence will play a significant role in the final argument; see Lemma 19.

The following corollary follows immediately from the Error-formula Lemma
(Lemma 14).

######  Corollary 5 (Perfect-dimension Corollary).

For every $j\in J$ if the $x_{i,j}$-teams perfectly imitate $\hat{y}_{i,j}$
for every $i\in I$ then we have
$|\mathbb{E}[\Delta_{j}]|\leq\tilde{O}(\frac{2^{-K}}{\epsilon_{G}})$.

###### Proof.

Perfect imitation implies $E_{j}\leq O(2^{-K})$ and hence
$|\mathbb{E}[\Delta_{j}]|\leq\tilde{O}(\frac{2^{-K}}{\epsilon_{G}})$. ∎

In order that the Perfect-dimension Corollary will be applicable for the
reduction we need to have two additional properties of an equilibrium which
have not been proved yet.

  1. 1.

All $x_{r}$-teams should perfectly imitate $\hat{y}_{r}$. So far, we know it
only for $x_{r}$-teams such that $\hat{y}_{r}$ is sufficiently far from the
$2^{-N_{in}-1}$-grid (see the Far-Perfect Corollary 3) and for teams such that
$g_{r}=0$ (the No-guide-imitation Lemma 9).

  2. 2.

The term $|\mathbb{E}[\Delta_{j}]|$ should be equal to (or approximate) the
actual terms $\triangle_{j}(z)$ for some point $z$ that is near to the points
$\\{(x^{p}),y\\}$. So far, we have proved neither that these points are
actually close to each other nor that the computations in the circuits are
done correctly.

In the remainder of the proof we show that these two properties are indeed
satisfied in every equilibrium.

####  5.2.5 Correct circuit computations

In this subsection we show several results on the correctness of computations
inside the circuits (i.e., by the circuit players). We start with several
definitions of correct computation. We prove the existence of two samples
where the computations are correct. The Pure-input Lemma (Lemma 16) allows us
to define (yet another) notion that captures the “location of the team
$\overline{x}_{r}$”: $x^{c}_{r}$, see Definition 7, which looks at the actions
of the circuit’s input players rather than on the group $x_{r}$. Then our goal
is to show that samples that are chosen by the guide player have approximately
correct computation (see Definition 6). To do so, we formulate (yet another)
Correct-bit Lemma 17 and apply it inductively in the Strong-perfect-imitation
Lemma (Lemma 18).

We recall that $W^{p}_{l}$ denotes the indicator of wrong computation of the
player $l$ in the circuit $C^{p}$ is wrong.

######  Definition 6.

We say that _the computations at the sample $p\in P$ are correct_ if
$\Pr[W^{p}_{l}=1]=0$ for every $l\in\mathcal{L}$. The computations are _weakly
correct_ if
$\sum_{l\in\mathcal{L}}\Pr[W^{p}_{l}=1]\leq\frac{\epsilon_{P}}{\epsilon_{C}}$.

Note that correct computations is a demanding definition for correctness of
circuit’s computations. In particular, it requires that all the relevant bits
$\overline{x}^{b}_{r}$ in both dimensions will be pure because otherwise the
input players $l^{p}$ for $l\in\mathcal{L}_{in}$ have a positive probability
of mismatching $\overline{x}^{b}_{r}$. Moreover, it requires that all circuit
players $l^{p}$ (including the outputs $\phi^{p}_{k}$ and
$\triangle^{p}_{j,k}$) will play a pure and correct action.

We say that a sample $p\in P$ is _perfect_ if strongly perfect imitation
occurs at the sample $p$ (see Definition 3) and the computations at the sample
$p$ are correct (see Definition 6 above).

######  Lemma 15 (Perfect-imitation+computation-sample Lemma).

There exists a perfect sample $p\in P$.

###### Proof.

For every coordinate $j\in J$ there exists at most one problematic team
$x_{i,j}$ (by the Far-Perfect Corollary 3) and hence two non-problematic
teams; i.e., teams $x_{r}$ where the real number $\hat{y}_{r}$ is
$\overline{\epsilon}_{C}$-far from the $2^{-N_{in}-1}$-grid. In such a non-
problematic team by the Far-Perfect Corollary (Corollary 3), the imitation in
all these teams is strongly perfect, and in particular all bits
$\overline{x}^{b}_{r,k}$ for $k\in[N_{in}]$ are pure. We let $p\in P$ be a
point with both coordinates be non-problematic (we have at least four such
points). We show that correct computation happens in the sample $p$.

Each circuit player $l^{p}$ interacts with her predecessors and with at most
two successors. We proceed inductively on the depth of the circuit to argue
that $\mathbb{P}[W^{p}_{l}=1]=0$. Consider a player $l^{p}$ that is located at
depth $d=d_{l}$. We argue that by choosing the action that performs correct
computations of the predecessors, player $l^{p}$ ensures a utility of
$\geq-2\epsilon_{C}(\epsilon_{T}+g^{p})2^{-2(d+1)}$, see Equation (12). If
this player is not an output player, her maximal loss is twice the penalty for
wrong computation of her successors who are located in depth of at least
$d+1$. For an output player her affect on $\mathbb{E}[\Phi]$ is bounded by
$g^{p}$ and hence her utility from playing the correct computation bit is at
least $-\epsilon_{P}g^{p}\gg-2\epsilon_{C}(\epsilon_{T}+g^{p})2^{-2(d+1)}$. On
the other hand, if player $l^{p}$ chooses the wrong bit her utility will be at
most $-\epsilon_{C}(\epsilon_{T}+g^{p})2^{-2d}+O(g^{p}\epsilon_{P})$. Since
$2^{-2d}>2^{-2d+1}+O(\frac{\epsilon_{P}}{\epsilon_{C}})$ the result follows. ∎

The following lemma states that the input players of every circuit $C^{p}$
that is chosen by the guide player are pure. Moreover, for circuits
$C^{p^{\prime}}$ of other samples that share a coordinate with $p$, the input
bits corresponding to this coordinate agree.

######  Lemma 16 (Pure-input Lemma).

Let $g^{p}=g^{i_{1},i_{2}}>0$. Then, all circuit-input players $l^{p}$ for
$l\in\mathcal{L}_{in}$ are playing pure. Moreover, for every
$p^{\prime}=(i^{\prime}_{1},i_{2})$ and every $l\in\mathcal{L}_{in}$ that
corresponds to an input from $x_{i_{2},2}$ the circuit-input player
$l^{p^{\prime}}$ is playing pure and $l^{p^{\prime}}=l^{p}$ (i.e., their pure
actions match). Similarly, for every $p^{\prime}=(i_{1},i^{\prime}_{2})$ and
every $l\in\mathcal{L}_{in}$ that corresponds to an input from $x_{i_{1},1}$
the circuit-input player $l^{p^{\prime}}$ is playing pure and
$l^{p^{\prime}}=l^{p}$.

###### Proof.

We first argue that the circuit loss of the $i$-th sample cannot exceed
$\epsilon_{P}$: There exists of a perfect sample (see the Perfect-
imitation+computation-sample Lemma 15) with $O(2^{-2K})$-imitation loss and no
loss at all in the circuit computation; combined with the fact that $g^{p}>0$
we have that if circuit loss of the $i$-th sample was larger, the guide player
would strictly prefer the perfect sample.

The bound on the total circuit loss implies weakly correct computations,
because each computation mistake is multiplied by a factor of $\epsilon_{C}$.
In particular, the computation loss of each input line
$\mathbb{P}[W^{p}_{l}=1]$ for $l\in\mathcal{L}_{in}$ should not exceed
$\frac{\epsilon_{P}}{\epsilon_{C}}$. Namely, the corresponding bit
$\overline{X}_{r,k}$ should match the action $L^{p}$ with probability
$1-\frac{\epsilon_{P}}{\epsilon_{C}}$. This can happen only if
$\overline{X}_{r,k}$ is a $Bernoulli(q)$ random variable with
$q\in[0,\frac{\epsilon_{P}}{\epsilon_{C}}]\cup[1-\frac{\epsilon_{P}}{\epsilon_{C}},1]$.
In case $q\in[0,\frac{\epsilon_{P}}{\epsilon_{C}}]$ the unique best-reply of
player $l^{p}$ is $0$. In case $q\in[1-\frac{\epsilon_{P}}{\epsilon_{C}},1]$
the unique best-reply of player $l^{p}$ is $1$.

To see the moreover part, we use the fact that $\overline{X}_{r,k}$ is almost
pure (i.e., a $Bernoulli(q)$ random variable). Therefore, similarly to the
argument for $l^{p}$, the unique best reply of the input-circuit player
$l^{p^{\prime}}$ is to also match the closest pure realization of
$\overline{X}_{r,k}$. ∎

The Pure-input Lemma (Lemma 16) provides us another useful notion of
“location” of the team $x_{r}$ (so far we had $\mathring{x}_{r}$ and
$\mathbb{E}[\overline{X}_{r}]$ to capture it).

######  Definition 7.

For $r\in R$ such that there exists $p\in P(r)$ with $g^{p}>0$ we define
$x^{c}_{r}\in[0,1]_{2^{-N_{in}}}$ to be the (pure) real number of precision
$2^{-N_{in}}$ which is induced by the input players
$(l^{p})_{l\in\mathcal{L}_{in}}$ that correspond to the input of $x_{r}$. For
$p$ such that $g^{p}>0$ we denote by $x^{c,p}$ the (pure) point of precision
$2^{-N_{in}}$ which is induced by the input players
$(l^{p})_{l\in\mathcal{L}_{in}}$

Note that by the moreover part of the Pure-input Lemma (Lemma 16) this
definition is well defined (i.e., does not depend on the choice of $p\in
P(r)$). Although $x^{c}_{r}$ is defined through the actions of the _circuit_
players (rather than by actions of the $x_{r}$-team players) this notion
captures well the “location” of $x_{r}$ since the input bits
$\overline{X}^{b}_{r,k}$ for $k\in[N_{in}]$ match the bits of $x^{c}_{r}$ with
high probability.

We present, yet another, analogue of a Correct-bit lemma. This time, the lemma
refers to bits $k\leq N_{in}$ that _serve_ as an input for the circuits
(unlike the Correct-bit-no-circuit Lemma 6), the lemma is valid for every
choice of the guide player (unlike the Correct-bit-no-guide Lemma 8), but it
assumes that all corresponding circuit input players are playing purely some
string $x^{c}_{r}$ and that the imitation target $\hat{y}_{r}$ is located very
close to the segment $[x^{c}_{r},x^{c}_{r}+2^{-N_{in}})$ which corresponds to
the set of real numbers whose binary representation is $x^{c}_{r}$.

######  Lemma 17 (Correct-bit-matched-input Lemma).

Let $r\in R$, $1\leq k\leq N_{in}$. Suppose that all of the following hold:

$\hat{y}_{r}$ agrees:

$\hat{y}_{r}\in\Big{(}x^{c}_{r}-\tilde{O}(\sqrt{\epsilon_{P}}),x^{c}_{r}+2^{-N_{in}}+\tilde{O}(\sqrt{\epsilon_{P}})\Big{)}$;
and

No veto:

$\mathbb{P}[M^{x}_{r}<k]=0$; and

More significant bits agree:

$\mathbb{P}[X_{r,k^{\prime}}=x^{c}_{r,k}]=1$ for every $k^{\prime}<k$.

Then also $\mathbb{P}[X_{r,k}=x^{c}_{r,k}]=1$.

###### Proof.

Intuitively, the fact that the corresponding input player in the circuit plays
the imitating bit, only increases the incentives of the bit player to match
it. Formally, one may verify that all the arguments in the proof of the
Correct-bit-no-circuit Lemma (Lemma 6) are valid for this case; instead of
arguing that the circuit utility is irrelevant (as in the Correct-bit-no-
circuit Lemma 6) we argue that it is relevant but has better utility when
$x_{r,k}=x^{c}_{r,k}$. Note that the possible imitation loss of
$\tilde{O}(\epsilon_{P})$ is negligible with respect to the gain from
imitating correctly the circuit inputs $\epsilon_{C}$. ∎

The following lemma states that whenever $\hat{y}_{r}$ has the same binary
representation (up to the $N_{in}$-th bit) as $x^{c}_{r}$, the imitation of
$x_{r}$ is perfect and there are no computation errors in the $x_{r}$ inputs
of the circuit.

######  Lemma 18 ($\hat{y}$-imitation Lemma).

For every $r\in R$, if393939This lemma indirectly assumes that $g^{p}>0$ for
some $p\in P(r)$ because the notion $x^{c}_{r}$ is defined only for such
indices $r\in R$.
$\hat{y}_{r}\in\Big{(}x^{c}_{r}-\tilde{O}(\sqrt{\epsilon_{P}}),x^{c}_{r}+2^{-N_{in}}+\tilde{O}(\sqrt{\epsilon_{P}})\Big{)}$
then $\mathbb{E}[\overline{X}_{r}]\in[x^{c}_{r},x^{c}_{r}+2^{-N_{in}})$.
Moreover, if $\hat{y}_{r}\in[x^{c}_{r},x^{c}_{r}+2^{-N_{in}}]$ then the
$x_{r}$ team perfectly imitates $\hat{y}_{r}$.

###### Proof.

At a high level, we apply the Correct-bit-matched-input Lemma (Lemma 17)
inductively on the bits $k=1,2,...,N_{in}$ to get that
$(\overline{x}^{b}_{r},k)_{k\in[N_{in}]}$ matches $x^{c}_{r}$ bit-by-bit. This
ensures that
$\mathbb{E}[\overline{X}_{r}]\in[x^{c}_{r},x^{c}_{r}+2^{-N_{in}})$
irrespective of the bits $N_{in}+1,...,K$. To get the moreover part we apply
the Correct-bit-no-circuit Lemma (Lemma 6) inductively on the bits
$k=N_{in}+1,...,K-3$.

##### Base case:

For $k=1$ the “No veto” and “More significant bits agree” conditions of the
Correct-bit-matched Lemma (Lemma 17) are satisfied trivially. Therefore
$X^{b}_{r,1}=x^{c}_{r,1}$ with probability 1.

##### Inductive step ($k\leq N_{in}$):

Now we apply the same argument as we did in the proof of the
$\mathring{x}$-far-imitation Lemma (Lemma 7). If the player vetoes the bit
$k=1$, she does it by a veto that matches the bit $x^{c}_{r,1}$ in the first
bit of the veto (see Equation (5)). Since the bit player $x_{r,1}$ also
matches $x^{c}_{r,1}$ the veto player will be better of by switching to the
corresponding veto on bit $k=2$; i.e., the following deviations are profitable
$(1,\vec{0})\to(2,\vec{0})$, $(1,00\vec{1})\to(2,0\vec{1})$,
$(1,0\vec{1})\to(2,\vec{1})$, $(1,1\vec{0})\to(2,\vec{0})$,
$(1,11\vec{0})\to(2,1\vec{0})$, and $(1,\vec{1})\to(2,\vec{1})$. Such a change
does not affect any terms of the utility except for the veto utility which is
improved by $\epsilon_{T}$. Now the conditions for bit $k=2$ of the Correct-
bit-matched Lemma (Lemma 17) are satisfied and we may proceed to the next bit.
We proceed so inductively till bit $N_{in}$.

##### Inductive step ($N_{in}<k\leq K-3$):

To prove the moreover part we proceed similarly by an inductive application of
the Correct-bit-no-circuit Lemma (Lemma 6) combined with no-veto argument as
above. ∎

####  5.2.6 Completing the proof

Let $p=(i_{1},i_{2})$ be a sample with $g^{p}>0$. We argue that
$|\triangle_{j}(x^{c,p})|\leq\epsilon_{R}$ for both $j=1,2$ (see Definition 7
for $x^{c,p}$). This is sufficient for the reduction by Lemma 3.

######  Lemma 19 (Final Lemma).

If $|\triangle_{j}(x^{c,p})|\geq\epsilon_{R}$ then all teams $x_{r}$ for $r\in
R$ perfectly imitate their target.

###### Proof.

Assume by way of contradiction that $x_{r}$ does not perfectly imitate
$\hat{y}_{r}$. Assume without loss of generality that $r=(i,1)$. By the no-
guide-imitation Lemma (Lemma 8) we know that $g_{r}>0$ and in particular for
$p=(i,i_{2})$ we have $g^{(i,i_{2})}>0$ for some $i_{2}\in I$. We show that
the guide player will improve her utility by choosing a different sample
$p^{\prime}=(i^{\prime},i_{2})$ for $i^{\prime}\neq i$ instead of $p$. We
analyse each of the three significant terms in the guide player utility (see
Equation (29)) and show that it is better for the sample $p^{\prime}$ (with a
strict inequality in at least one term).

##### Imitation utility.

The imitation utility in dimension $j=2$ remains unchanged. For the dimension
$j=1$ note that $\hat{y}_{i,1}$ is $\overline{\epsilon}_{C}$-close to the
$2^{-N_{in}-1}$-grid by the Far-Perfect Corollary (Corollary 3). Therefore,
$\hat{y}_{i^{\prime},1}$ is $\Omega(\epsilon_{S})$-far from the
$2^{-N_{in}-1}$-grid (because $\hat{y}_{i^{\prime},1}$ is $\epsilon_{S}$-far
from $\hat{y}_{i,1}$). Thus, again by the Far-Perfect Corollary, we deduce
that the imitation of the team $x_{i^{\prime},1}$ is strongly perfect. This
strictly improves upon the non-perfect imitation of the $x_{i,1}$-team.

##### Circuit utility.

For every $l\in\mathcal{L}_{in}$ that corresponds to an input of the dimension
$j=2$ the term $W^{p}_{l}$ remains unchanged because by the Pure-input Lemma
(Lemma 16) the circuit’s input players are playing pure and identically in the
circuits of the samples $p$ and $p^{\prime}$ circuits. Whereas, the mixed
strategy of the $x_{i_{2},2}$-teams remains unchanged.

For every $l\in\mathcal{L}_{in}$ that corresponds to an input of the dimension
$j=1$ we have $\mathbb{P}[W^{p^{\prime}}_{l}]=0$. Hence these terms of the
circuit utility are (weakly) superior at $p^{\prime}$.

Finally, in both circuits, $C^{p}$ and $C^{p^{\prime}}$, since the input bits
are pure, by an inductive argument on the depth of the wires we deduce that
$\mathbb{P}[W^{p}_{l}]=\mathbb{P}[W^{p^{\prime}}_{l}]=0$ for every
$l^{p},l^{p^{\prime}}\notin\mathcal{L}_{in}$ and we have an indifference.

##### Potential utility.

Note that $\phi^{p}=\phi(x^{c,p})$ and
$\phi^{p^{\prime}}=\phi(x^{c,p^{\prime}})$; i.e., the actual potentials are
computed at $p$ and $p^{\prime}$ because the computations in both circuits
($C^{p}$ and $C^{p^{\prime}}$) are done correctly. We present the analysis for
the case of $\triangle_{1}(x^{c,p})>\epsilon_{R}$. The arguments for
$\triangle_{1}(x^{c,p})<-\epsilon_{R}$ are symmetric. We denote $r=(i,1)$ and
$r^{\prime}=(i^{\prime},1)$. We consider three cases:

##### Case 1: $x^{c}_{r}<x^{c}_{r^{\prime}}$.

Since the potential is computed correctly in both points $x^{c,p}$ and
$x^{c,p^{\prime}}$ (see Pure-Input-Lemma 16) by definition of $\triangle$ we
have
$\phi(x^{c,p^{\prime}})=\phi(x^{c,p})+\triangle_{1}(x^{c,p})>\phi(x^{c,p^{\prime}})$.

##### Case 2: $x^{c}_{r}=x^{c}_{r^{\prime}}$.

The potential remains unchanged. Note that here the gradient term remains
unchanged too.

##### Case 3: $x^{c}_{r}>x^{c}_{r^{\prime}}$.

We show that this case is impossible by showing that every one of the
following two sub-cases is impossible.

##### Case 3.1: $\mathbb{E}[\overline{X}_{r}]\geq x^{c}_{r}+2^{-N_{in}-1}$.

The distance
$|\mathbb{E}[\overline{X}_{r}]-\mathbb{E}[\overline{X}_{r^{\prime}}]|$ is
bounded by $O(\epsilon_{S}+\overline{\epsilon}_{C})$ because both groups
$x_{r}$ and $x_{r^{\prime}}$ imitate up to $2\overline{\epsilon}_{C}$ their
targets $\hat{y}_{r}$ and $\hat{y}_{r^{\prime}}$ (see the Mild-imitation
Corollary (Corollary 4)) and the distance of $\hat{y}_{r}$ from
$\hat{y}_{r^{\prime}}$ is at most $2\epsilon_{S}$ by the definition of the
shifts. Therefore, $\mathbb{E}[\overline{X}_{r^{\prime}}]\geq
x^{c}_{r}+2^{-N_{in}-1}-O(\epsilon_{S}+\overline{\epsilon}_{C})$. So we deduce
that $x^{c}_{r}\leq x^{c}_{r^{\prime}}$ (because the first $N_{in}$ bits of
the $x_{r^{\prime}}$ team are at least $x^{c}_{r}$). This contradicts the
assumption of Case 3.

##### Case 3.2: $\mathbb{E}[\overline{X}_{r}]\leq x^{c}_{r}+2^{-N_{in}-1}$.

We make two sub-claims

  1. 1.

$x^{c}_{r}\leq\mathbb{E}[\overline{X}_{r}]$.

  2. 2.

$\mathbb{E}[\overline{X}_{r}]\leq\hat{y}_{r}$.

By combining these two sub-claims we deduce that $x^{c}_{r}\leq\hat{y}_{r}$
and in particular $\hat{y}_{r}\in[x^{c}_{r},x^{c}_{r}+2^{-N_{in}})$. But in
this case, by the $\hat{y}$-imitation Lemma (Lemma 18), $x_{r}$-team strongly
perfectly imitates $\hat{y}_{r}$. It remains to prove the two sub-claims.

##### Sub-claim 1: $x^{c}_{r}\leq\mathbb{E}[\overline{X}_{r}]$

Since $g^{p}>0$ we know that the bit of $\overline{x}_{r,k}$ matches
$x^{c}_{r,k}$ for every $k\in[N_{in}]$ with probability of at least
$\frac{\epsilon_{P}}{\overline{\epsilon}_{C}}$ (otherwise, a perfect sample
whose existence has been proved in the Perfect-imitation+computation (Lemma
15) will be superior for the guide player). Therefore,
$\mathbb{E}(\overline{X}_{r})\geq
x^{c}_{r}-\tilde{O}(\frac{\epsilon_{P}}{\overline{\epsilon}_{C}})$. Also,
$|\mathbb{E}(\overline{X}_{r})-\hat{y}_{r}|\leq O(\sqrt{\epsilon_{P}})$ again
because otherwise the perfect sample would be superior. Therefore, we have
$\hat{y}_{r}\geq x^{c}_{r}-O(\sqrt{\epsilon_{P}})$. By the $\hat{y}$-imitation
Lemma (Lemma 18) we get that $x^{c}_{r}\leq\mathbb{E}[\overline{X}_{r}]$.

##### Sub-claim 2: $\mathbb{E}[\overline{X}_{r}]\leq\hat{y}_{r}$

Recall that we have assumed that $\triangle(x^{c,p})>\epsilon_{R}$. By the
$\lambda$-Lipschitness of $\triangle_{j}$ and the fact that $\triangle_{j}$ is
computed correctly (see the Pure-Input Lemma 16) we deduce that

$\displaystyle\mathbb{E}[\Delta_{1}]=\triangle(x^{c,p})\pm
O(\lambda)\geq\epsilon_{R}-O(\lambda).$ (34)

Therefore,

$\displaystyle\mathbb{E}[\overline{X}_{r}]-\hat{y}_{r}=E_{1}$
$\displaystyle=\frac{-\epsilon_{G}}{6+g_{r}}\mathbb{E}[\Delta_{1}]\pm\tilde{O}(2^{-K})$
(Error-formula Lemma (Lemma 14))
$\displaystyle\leq\frac{-\epsilon_{G}}{6+g_{r}}\Big{(}\epsilon_{R}-O(\lambda)\Big{)}\pm\tilde{O}(2^{-K})$
(Eq. (34)) $\displaystyle\leq 0.$

∎

The Final Lemma 19 combined with the Perfect-dimension Corollary (Corollary 5)
complete the proof because if $|\triangle_{j}(x^{c,p})|\leq\epsilon_{R}$ we
are done. And if $|\triangle_{j}(x^{c,p})|\geq\epsilon_{R}$ we have perfect
imitation for all $x_{i,j}$ groups for $i\in I$ and by the Perfect-dimension
Corollary we have
$|\triangle_{j}(x^{c,p})|\leq\tilde{O}(\frac{2^{-K}}{\epsilon_{G}})\ll\epsilon_{R}$.

###  5.3 Equilibrium Analysis: Including Boundaries

In this section we sketch the equilibrium analysis without imposing
Assumptions 1.

We start this section with two lemmata that demonstrate the behavior of the
$x_{r}$ teams in cases where the corresponding imitation target $\hat{y}_{r}$
is located from the wrong side of the boundary.

######  Lemma 20.

If $1-2^{-N_{in}-1}\leq\hat{y}_{r}<1$ then the $x_{r}$ team strongly perfectly
imitates $\hat{y}_{r}$. If $\hat{y}_{r}\geq 1$ then the $x_{r}$-team strongly
perfectly imitates $1-2^{-K}$.

Similarly, if $0\leq\hat{y}_{r}<2^{-N_{in}-1}$ then the $x_{r}$ team strongly
perfectly imitates $\hat{y}_{r}$. If $\hat{y}_{r}<0$ then the $x_{r}$-team
strongly perfectly imitates $0$.

###### Proof.

We prove the first part of the lemma. The second part is proved symmetrically.

Since $1-2^{-N_{in}-1}\leq\hat{y}_{r}$ for every $k$-th bit player $x_{r,k}$
for $k\in[N_{in}]$ it is easy to see that their action $x_{r,k}=1$ is strictly
better than $x_{r,k}=0$ _for every_ probability of them being vetoed. This is
because the imitation loss and the bit imitation losses after playing
$x_{r,k}=0$ is at least $\Omega(2^{-2N_{in}})\gg\epsilon_{C}$. From here we
can deduce that the veto player has no incentive to veto any of them; i.e.,
$\mathbb{P}[M^{x}_{r}>N_{in}]=1$.

For the case of $\hat{y}_{r}<1$ we can inductively repeat Imitation the
Correct-bit-no-circuit Lemma (Lemma 6) to deduce that perfect imitation
occurs. For the case of $\hat{y}_{r}\geq 1$ it remains dominant strategy for
the bit players to play $x_{r,k}=1$ (irrespective of their probability for
being vetoed). ∎

######  Lemma 21.

For every $j\in J$ and every $i\in\\{-1,0\\}$ we have $\hat{y}_{i,j}<1$.
Moreover, if $\hat{y}_{(1,j)}\geq 1$ then both other teams $x_{i,j}$ for
$i\in\\{-1,0\\}$ perfectly imitate $\hat{y}_{i,j}$.

Similarly, for every $j\in J$ and every $i\in\\{0,1\\}$ we have
$\hat{y}_{i,j}>0$. Moreover, if $\hat{y}_{(-1,j)}\leq 0$ then both other teams
$x_{i,j}$ for $i\in\\{0,1\\}$ perfectly imitate $\hat{y}_{i,j}$.

###### Proof.

We prove the first part of the lemma. The second part is proved symmetrically.

Note that it is sufficient to prove that $\hat{y}_{0,j}<1$ because
$\hat{y}_{0,j}>\hat{y}_{-1,j}$. Assume by way of contradiction that
$\hat{y}_{0,j}\geq 1$. This implies (by definition of the sampling shifts)
that $\hat{y}_{1,j}\geq 1+\epsilon_{S}$.

We denote $E_{i,j}=\hat{y}_{i,j}-\mathbb{E}[\overline{X}_{i,j}]$ the imitation
error of the $x_{i,j}$-team. By Lemma 20 we know that if $\hat{y}_{i,j}\leq 1$
then we have perfect imitation. So the only possible case not to have perfect
imitation is if $\hat{y}_{i,j}>1$, and in such a case
$E_{i,j}=\hat{y}_{i,j}-\mathbb{E}[\overline{X}_{i,j}]\geq\hat{y}_{i,j}-1\geq
0$. Note also that $E_{1,j}\geq E_{0,j}+\epsilon_{S}\geq\epsilon_{S}$.

The term $\mathbb{E}[Y_{j}]-\hat{x}_{j}$ (see Definition 4) can be
equivalently viewed as the expectation of $E_{i,j}$ when we draw $i$ from
$\\{-1,0,1\\}$ with corresponding probabilities $\frac{3+g_{i,j}}{10}$. So by
the above observation we deduce that
$\mathbb{E}[Y_{j}]-\hat{x}_{j}\geq\frac{3}{10}\epsilon_{S}$ (because it is the
expectation of a positive random variable that gets a value of $\epsilon_{S}$
with probability of at least $\frac{3}{10}$). This contradicts404040The
Perfect-$y$-imitation Lemma (Lemma 13) is applicable here because its proof
does not rely on Assumption 1. the Perfect-$y$-imitation Lemma (Lemma 13)
which implies that
$(\mathbb{E}[Y_{j}]-\hat{x}_{j}\pm\tilde{O}(\epsilon_{G}))^{2}\leq O(2^{-2K})$
and, in particular, $\mathbb{E}[Y_{j}]$ is $\tilde{O}(\epsilon_{G})$-close to
$\hat{x}_{j}$.

The moreover part is a straightforward consequence of Lemma 20 because if
$\hat{y}_{1,j}\geq 1$ and $\hat{y}_{0,j}<1$ we can bound
$1-2^{-N_{in}-1}<y_{i,j}<1$ for $i\in\\{0,1\\}$. ∎

With Lemmata 20, and 21 the modifications that are needed to the equilibrium
analysis of Section 5.2 are minor. We briefly overview the equilibrium
analysis and mention which (cosmetic) changes are required.

The Vetoed-mix-significant-bits Lemma (Lemma 4) and the
$\mathring{x}$-utility-approximation Lemma (5) do not rely on Assumption 1.
The analogue of the Correct-bit-no-circuit Lemma (Lemma 6), the
$\mathring{x}$-far-imitation Lemma (Lemma 7), the Correct-bit-no-guide Lemma
(Lemma 8), and the No-guide-imitation Lemma (Lemma 9) for the boundary case is
Lemma 20. In the boundary case the situation is simpler and positive results
on perfect imitation can be deduced independently of guide player’s mixed
strategy. The only place we rely on Assumption 1 in the proof of the Perfect-
imitation-sample Lemma (Lemma 10) is when we state that every non-perfectly
imitating $x_{r}$ satisfies $\mathring{x}_{r}$ is located close to the grid;
see Footnote 35. This property remains true in the boundary case (Lemma 20).
The Mild-imitation Lemma (Lemma 11), 12, and the Perfect-$y$-imitation Lemma
(Lemma 13) do not rely on Assumption 1.

Given $j\in J$ we extend the definitions of a problematic team $r^{*}(j)$ and
of an imitation error $E_{j}$ in Definition 5 to the boundary cases. In case
$\hat{y}_{i,j}>1$ for some $i\in I$ we know by Lemma 21 that the only team
that might have an imitation error is $r=(1,j)$. This observation leads us to
the following definition.

######  Definition 8 (Problematic teams and imitation error (boundary
version)).

In case $\hat{y}_{i,j}>1$ we define the problematic team to be $r^{*}=(1,j)$.
Correspondingly, the imitation error is defined by
$E_{j}=(1-2^{-K})-\hat{y}_{1,j}$.

In case $\hat{y}_{i,j}<0$ we define the problematic team to be $r^{*}=(-1,j)$.
Correspondingly, the imitation error is defined by $E_{j}=0-\hat{y}_{-1,j}$.

In case $\hat{y}_{r}\in[0,1]$ we stick to the original definitions of
problematic team and imitation error. See Definition 5.

We proceed with the overview of the equilibrium analysis for remaining
lemmata. The property that is used in the proof of the Error-formula Lemma
(Lemma 14) is the fact that in each coordinate we have a single problematic
team. By Lemma 21 and definition 8 this is true also for the boundary case.
The Perfect-imitation+computation-sample Lemma (Lemma 15), the Pure-input
Lemma (Lemma 16), and the $\hat{y}$-imitation Lemma (Lemma 18), do not rely on
Assumption 1, while Lemma 20 is complementary to the Correct-bit-matched-input
Lemma (Lemma 17). The Final Lemma (Lemma 19) does not rely on Assumption 1.
This completes the reduction of 2D-GD-FixedPoint to 5-Pt-Potential.

##  6 Reducing Polytensor Games via Domain’s Modification

To complete the proof of Theorem 1 we need to show that 5-Polytensor
IdenticalInterest can be polynomially reduced to Deg-5-GD-FixedPoint.

######  Proposition 2.

$c-$Polytensor-IdenticalInterest can be polynomially reduced to
Deg-5-GD-FixedPoint.

It have been observed in [DP11] that there is a one-to-one correspondence of
local maxima of the potential function defined on the _product of simplices_
(i.e., the mixed action profiles in the game) and mixed Nash equilibria in the
congestion games. However, since we have restricted the domain of GD-
FixedPoint to be the _hypercube_ (rather than product of simplices), this
observation is insufficient, and mild additional arguments are required. The
proof below provides these additional arguments.

###### Proof.

We recall that $n$ denotes the number of players. We denote by $A_{i}$ the
number actions of player $i\in[n]$. We denote $A=\sum_{i\in[n]}A_{i}$. The
mixed strategies of player $i$ are denoted by
$x_{i}\in\Delta(A_{i})\subset[0,1]^{A_{i}}$ where $x_{i,k}$ denotes the
probability of player $i$ for choosing her $k$-th action. The potential of the
game is a multilinear function
$U:\times_{i\in[n]}\Delta(A_{i})\rightarrow[-1,1]$. The same multilinear
function $U$ can be viewed as a function with larger domain
$U:[0,2]^{A_{1}}\times...\times[0,2]^{A_{n}}=[0,2]^{A}\rightarrow[-2^{A},2^{A}]$.
For every point $x=((x_{1,k})_{k\in A_{1}},...,(x_{n,k})_{k\in
A_{n}})\in[0,2]^{A}$ we denote

$s_{i}:=\sum_{k\in A_{i}}x_{i,k}.$

As an input to Deg-5-GD-FixedPoint we consider the function
$\phi:[0,2]^{A}\rightarrow\mathbb{R}$ that is given by

$\displaystyle\phi(x):=-C\sum_{i\in[n]}(s_{i}-1)^{2}+U(x)$ (35)

where $C=4\cdot 2^{A}$ and we set $\epsilon=\frac{1}{3}\epsilon_{N}2^{-n}$. We
argue that every $x=((x_{1,k})_{k\in A_{1}},...,(x_{n,k})_{k\in A_{n}})$ that
is a solution for $\textsc{GD-FixedPoint}(\phi,\epsilon)$ corresponds to an
$\epsilon_{N}$-Nash equilibrium of the congestion game after normalization of
the strategies. Namely, we argue that the profile of actions
$((\frac{1}{s_{1}}x_{1,k})_{k\in A_{1}},...,(\frac{1}{s_{n}}x_{n,k})_{k\in
A_{n}})$ is an $\epsilon_{N}$-Nash equilibrium.

The gradient in the direction $(i,k)$ is given by

$\displaystyle\nabla_{i,k}\phi(x):=-2C(s_{i}-1)+U(e_{i,k},x_{-i})$

If $s_{i}<0.5$ then $x_{i,1}<0.5$ and
$\nabla_{i,1}\phi(x)>C+U(e_{i,1},x_{-i})\geq 2^{A}$ and it cannot be a GD-
FixedPoint solution.

If $s_{i}>1.5$ then there exists $x_{i,k}>0$ and
$\nabla_{i,k}\phi(x)<-C+U(e_{i,k},x_{-i})\leq-2^{A}$ and it cannot be a GD-
FixedPoint solution.

Therefore, every solution must satisfy $0.5\leq s_{i}\leq 1.5$, and assume by
way of contradiction that $((\frac{1}{s_{1}}x_{1,k})_{k\in
A_{1}},...,(\frac{1}{s_{n}}x_{n,k})_{k\in A_{n}})$ is not an
$\epsilon_{N}$-Nash equilibrium. Some player $i$, without loss of generality
$i=1$, has a profitable deviation to a pure action $k$ which improves her
utility by at least $\epsilon_{N}$. Without loss of generality $k=1$. Namely,

$U(e_{1,1},(\frac{1}{s_{2}}x_{2,k})_{k\in
A_{2}},...,(\frac{1}{s_{n}}x_{n,k})_{k\in A_{n}})\geq
U((\frac{1}{s_{1}}x_{1,k})_{k\in A_{1}},(\frac{1}{s_{2}}x_{2,k})_{k\in
A_{2}},...,(\frac{1}{s_{n}}x_{n,k})_{k\in A_{n}})+\epsilon_{N}.$

Consider the gradient in the direction
$(-x_{1,1}+s_{1},-x_{1,2},...-x_{1,k},0,0,...,0)$ which corresponds to the
direction in which player 1 increases the weight on her first action and
proportionally decreases the weights from the point $x_{1}$ such that the term
$s_{1}$ will remains fixed. The gradient in this direction is given by

$\displaystyle\begin{aligned}
&\nabla_{(-x_{1,1}+s_{1},-x_{1,2},...-x_{1,k},0,0,...,0)}\phi(x)=\\\
&s_{1}[-2C(s_{1}-1)+U(e_{1,1},x_{-1})]+\sum_{k}x_{1,k}[2C(s_{1}-1)-U(e_{1,k},x_{-1})]=\\\
&s_{1}U(e_{1,1},x_{-1})-U(x)=\\\
&\Pi_{i\in[n]}{s_{i}}\left[U(e_{1,1},\frac{x_{2}}{s_{2}},...,\frac{x_{n}}{s_{n}})-U(\frac{x_{1}}{s_{1}},\frac{x_{2}}{s_{2}},...,\frac{x_{n}}{s_{n}})\right]>\Pi_{i\in[n]}{s_{i}}\epsilon_{N}\geq\epsilon_{N}2^{-n}.\end{aligned}$
(36)

If, by way of contradiction, we have $|\nabla_{1,k}\phi(x)|\leq\epsilon$ for
every $k$, then we have

$\displaystyle|\nabla_{(-x_{1,1}+s_{1},-x_{1,2},...-x_{1,k},0,0,...,0)}\phi(x)|\leq(s_{1}-x_{1,1})\nabla_{1,1}\phi(x)+\sum_{k\geq
2}x_{1,k}|\nabla_{1,k}\phi(x)|\leq 2s_{1}\epsilon\leq\epsilon_{N}2^{-n}$

which contradicts Inequality (36).

Finally, we observe that the potential in Equation (35) is a valid potential
for Deg-5-GD-FixedPoint. First, since $U$ is a $5$-polytensor game, the
utility $U(x)$ is a multilinear degree 5 polynomial. Note also that the
monomials of the term $-C\sum_{i}(s_{i}-1)^{2}$ are
$-Cx_{i,k}x_{i,k^{\prime}}$ which are either multilinear (for $k\neq
k^{\prime}$) or strictly concave (for $k=k^{\prime}$). Namely, all the
monomials of the potential are of maximal degree 5 and also are component-wise
concave. ∎

## References

  * [AAE13] Baruch Awerbuch, Yossi Azar, and Amir Epstein.  The price of routing unsplittable flow.  SIAM J. Comput., 42(1):160–177, 2013.
  * [ABPW17] Omer Angel, Sébastien Bubeck, Yuval Peres, and Fan Wei.  Local max-cut in smoothed polynomial time.  In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 429–437. ACM, 2017.
  * [ADG+11] Sebastian Aland, Dominic Dumrauf, Martin Gairing, Burkhard Monien, and Florian Schoppmann.  Exact price of anarchy for polynomial congestion games.  SIAM J. Comput., 40(5):1211–1233, 2011.
  * [ARV08] Heiner Ackermann, Heiko Röglin, and Berthold Vöcking.  On the impact of combinatorial structure on congestion games.  J. ACM, 55(6):25:1–25:22, 2008.
  * [AS08] Heiner Ackermann and Alexander Skopalik.  Complexity of pure Nash equilibria in player-specific network congestion games.  Internet Mathematics, 5(4):323–342, 2008.
  * [Bab16] Yakov Babichenko.  Query complexity of approximate Nash equilibria.  Journal of the ACM (JACM), 63(4):36, 2016.
  * [BCC19] Ali Bibak, Charles Carlson, and Karthekeyan Chandrasekaran.  Improving the smoothed complexity of FLIP for max cut problems.  In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 897–916. SIAM, 2019.
  * [BHLR08] Avrim Blum, MohammadTaghi Hajiaghayi, Katrina Ligett, and Aaron Roth.  Regret minimization and the price of total anarchy.  In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 373–382. ACM, 2008.
  * [BJ12] Samuel R. Buss and Alan S. Johnson.  Propositional proofs and reductions between NP search problems.  Ann. Pure Appl. Log., 163(9):1163–1182, 2012.
  * [BKM20] Shant Boodaghians, Rucha Kulkarni, and Ruta Mehta.  Smoothed efficient algorithms and reductions for network coordination games.  In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 73:1–73:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [BM04] Josh Buresh-Oppenheim and Tsuyoshi Morioka.  Relativized NP search problems and propositional proof systems.  In 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 21-24 June 2004, Amherst, MA, USA, pages 54–67. IEEE Computer Society, 2004.
  * [BM20] Sébastien Bubeck and Dan Mikulincer.  How to trap a gradient flow.  In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 940–960. PMLR, 2020.
  * [BR17] Yakov Babichenko and Aviad Rubinstein.  Communication complexity of approximate Nash equilibria.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 878–889. ACM, 2017.
  * [BR20] Yakov Babichenko and Aviad Rubinstein.  Communication complexity of Nash equilibrium in potential games.  In FOCS 2020, 2020.
  * [Bub15] Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  Found. Trends Mach. Learn., 8(3-4):231–357, 2015.
  * [CD09] Xi Chen and Xiaotie Deng.  On the complexity of 2d discrete fixed point problem.  Theor. Comput. Sci., 410(44):4448–4456, 2009.
  * [CDDT10] Xi Chen, Decheng Dai, Ye Du, and Shang-Hua Teng.  On the complexity of equilibria in markets with additively separable utilities.  In Moshe Dror and Greys Sosic, editors, Proceedings of the Behavioral and Quantitative Game Theory - Conference on Future Directions, BQGT ’10, Newport Beach, California, USA, May 14-16, 2010, page 61:1. ACM, 2010.
  * [CDHS18] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford.  Accelerated methods for nonconvex optimization.  SIAM J. Optim., 28(2):1751–1772, 2018.
  * [CDHS20] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford.  Lower bounds for finding stationary points I.  Math. Program., 184(1):71–120, 2020.
  * [CDO15] Xi Chen, David Durfee, and Anthi Orfanou.  On the complexity of Nash equilibria in anonymous games.  In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 381–390, 2015.
  * [CDT09] Xi Chen, Xiaotie Deng, and Shang-Hua Teng.  Settling the complexity of computing two-player Nash equilibria.  J. ACM, 56(3):14:1–14:57, 2009.
  * [CGV+20] Xi Chen, Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Mihalis Yannakakis, and Xinzhi Zhang.  Smoothed complexity of local max-cut and binary max-CSP.  In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1052–1065. ACM, 2020.
  * [CPY17] Xi Chen, Dimitris Paparas, and Mihalis Yannakakis.  The complexity of non-monotone markets.  J. ACM, 64(3):20:1–20:56, 2017.
  * [CV07] Artur Czumaj and Berthold Vöcking.  Tight bounds for worst-case equilibria.  ACM Trans. Algorithms, 3(1):4:1–4:17, 2007.
  * [Das08] Constantinos Daskalakis.  The Complexity of Nash Equilibria.  PhD thesis, University of California, Berkeley, 2008.
  * [DFS20] Argyrios Deligkas, John Fearnley, and Rahul Savani.  Tree Polymatrix Games are PPAD-hard.  CoRR, abs/2002.12119, 2020.
  * [DGP09] Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou.  The complexity of computing a Nash equilibrium.  SIAM Journal on Computing, 39(1):195–259, 2009.
  * [DP] Constantinos Daskalakis and Christos H. Papadimitriou.  Continuous local search - corrigendum.
  * [DP11] Constantinos Daskalakis and Christos Papadimitriou.  Continuous local search.  In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 790–804. SIAM, 2011.
  * [DSZ20] Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis.  The complexity of constrained min-max optimization.  CoRR, abs/2009.09623, 2020.
  * [DTZ18] Constantinos Daskalakis, Christos Tzamos, and Manolis Zampetakis.  A converse to Banach’s fixed point theorem and its CLS-completeness.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 44–50. ACM, 2018.
  * [EPRY20] Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, and Mihalis Yannakakis.  Tarski’s theorem, supermodular games, and the complexity of equilibria.  In 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, pages 18:1–18:19, 2020.
  * [ER17] Michael Etscheid and Heiko Röglin.  Smoothed analysis of local search for the maximum-cut problem.  ACM Trans. Algorithms, 13(2):25:1–25:12, 2017.
  * [FG18] Aris Filos-Ratsikas and Paul W. Goldberg.  Consensus halving is PPA-complete.  In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 51–64. ACM, 2018.
  * [FGHS20] John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Savani.  The complexity of gradient descent: CLS = PPAD $\cap$ PLS.  CoRR, abs/2011.01929, 2020.
  * [FGMS17] John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani.  CLS: new problems and completeness.  CoRR, abs/1702.06017, 2017.
  * [FGMS20] John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani.  Unique end of potential line.  J. Comput. Syst. Sci., 114:1–35, 2020.
  * [FPT04] Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar.  The complexity of pure Nash equilibria.  In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 604–612. ACM, 2004.
  * [FS20] John Fearnley and Rahul Savani.  A faster algorithm for finding Tarski fixed points.  CoRR, abs/2010.02618, 2020.
  * [GHH+18] Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubáček, Karel Král, Hagar Mosaad, and Veronika Slívová.  ARRIVAL: next stop in CLS.  In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 60:1–60:13, 2018.
  * [GK20] Elazar Goldenberg and Karthik C. S.  Hardness amplification of optimization problems.  In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 1:1–1:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [GKP19] Anat Ganor, Karthik C. S., and Dömötör Pálvölgyi.  On communication complexity of fixed point computation.  CoRR, abs/1909.10958, 2019.
  * [GKRS19] Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov.  Adventures in monotone complexity and TFNP.  In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, pages 38:1–38:19, 2019.
  * [GR18] Mika Göös and Aviad Rubinstein.  Near-optimal communication lower bounds for approximate Nash equilibria.  In 59th IEEE Annual Symposium on Foundations of Computer Science, (FOCS) 2018, Paris, France, October 7-9, 2018, pages 397–403, 2018\.
  * [GV14] Jugal Garg and Vijay V. Vazirani.  On computability of equilibria in markets with production.  In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1329–1340. SIAM, 2014.
  * [HHKS13] Tobias Harks, Martin Hoefer, Max Klimm, and Alexander Skopalik.  Computing pure Nash and strong equilibria in bottleneck congestion games.  Math. Program., 141(1-2):193–215, 2013.
  * [HJ72] Joseph T Howson Jr.  Equilibria of polymatrix games.  Management Science, 18(5-part-1):312–318, 1972.
  * [JPY88] David S Johnson, Christos H Papadimitriou, and Mihalis Yannakakis.  How easy is local search?  Journal of computer and system sciences, 37(1):79–100, 1988.
  * [KP09] Elias Koutsoupias and Christos H. Papadimitriou.  Worst-case equilibria.  Comput. Sci. Rev., 3(2):65–69, 2009.
  * [Kre90] Mark W. Krentel.  On finding and verifying locally optimal solutions.  SIAM J. Comput., 19(4):742–749, 1990.
  * [Meh14] Ruta Mehta.  Constant rank bimatrix games are PPAD-hard.  In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 545–554, 2014.
  * [MM20] Aniket Murhekar and Ruta Mehta.  Approximate Nash equilibria of imitation games: Algorithms and complexity.  In Amal El Fallah Seghrouchni, Gita Sukthankar, Bo An, and Neil Yorke-Smith, editors, Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’20, Auckland, New Zealand, May 9-13, 2020, pages 887–894. International Foundation for Autonomous Agents and Multiagent Systems, 2020.
  * [MS96] Dov Monderer and Lloyd S Shapley.  Potential games.  Games and Economic Behavior, 14(1):124–143, 1996.
  * [PR08] Christos H Papadimitriou and Tim Roughgarden.  Computing correlated equilibria in multi-player games.  Journal of the ACM (JACM), 55(3):14, 2008.
  * [Ros73] Robert W. Rosenthal.  A class of games possessing pure-strategy Nash equilibria.  International Journal of Game Theory, 2(1):65–67, Dec 1973.
  * [Rou15] Tim Roughgarden.  Intrinsic robustness of the price of anarchy.  J. ACM, 62(5):32:1–32:42, 2015.
  * [RT00] Tim Roughgarden and Éva Tardos.  How bad is selfish routing?  In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, pages 93–102. IEEE Computer Society, 2000.
  * [Rub16] Aviad Rubinstein.  Settling the complexity of computing approximate two-player Nash equilibria.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 258–265. IEEE, 2016.
  * [Rub18] Aviad Rubinstein.  Inapproximability of Nash equilibrium.  SIAM Journal on Computing, 47(3):917–959, 2018.
  * [RW16] Tim Roughgarden and Omri Weinstein.  On the communication complexity of approximate fixed points.  In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 229–238. IEEE Computer Society, 2016.
  * [SV08] Alexander Skopalik and Berthold Vöcking.  Inapproximability of pure Nash equilibria.  In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 355–364. ACM, 2008.
  * [SY91] Alejandro A. Schäffer and Mihalis Yannakakis.  Simple local search problems that are hard to solve.  SIAM J. Comput., 20(1):56–87, 1991.
  * [SZZ18] Katerina Sotiraki, Manolis Zampetakis, and Giorgos Zirdelis.  PPP-completeness with connections to cryptography.  In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 148–158. IEEE Computer Society, 2018.
  * [Vav93] Stephen A. Vavasis.  Black-box complexity of local minimization.  SIAM J. Optim., 3(1):60–80, 1993.
  * [Vet02] Adrian Vetta.  Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions.  In 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings, page 416. IEEE Computer Society, 2002.
  * [Yan68] E. B. Yanovskaya.  Equilibrium points in polymatrix games.  Lithuanian Mathematical Journal, 1968.