# Randomness Requirements and Asymmetries in Nash Equilibria††thanks: We thank
Farid Arthaud for helpful feedback on earlier drafts and discussions and Ziyu
Zhang for helpful discussions.

Edan Orzech
MIT CSAIL
<EMAIL_ADDRESS>Martin Rinard
MIT CSAIL
<EMAIL_ADDRESS>
###### Abstract

In general, Nash equilibria in normal-form games may require players to play
(probabilistically) mixed strategies. We define a measure of the complexity of
finite probability distributions and study the complexity required to play NEs
in finite two player $n\times n$ games with rational payoffs. Our central
results show that there exist games in which there is an exponential vs.
linear gap in the complexity of the mixed distributions that the two players
play at (the unique) NE. This gap induces gaps in the amount of space required
to represent and sample from the corresponding distributions using known
state-of-the-art sampling algorithms. We also establish upper and lower bounds
on the complexity of any NE in the games that we study. These results
highlight (i) the nontriviality of the assumption that players can any mixed
strategy and (ii) the disparities in resources that players may require to
play NEs in the games that we study.

##  1 Introduction

A known result in game theory is the existence of Nash Equilibria (NEs) in any
finite normal-form game [27]. In general, NEs may require players to play
(probabilistically) mixed strategies, a requirement that corresponds to the
reduction of the existence of NEs to the existence of fixed points of a
continuous function, where the continuum is the (product) set of mixed
strategies of all players.

We define a measure of the complexity of finite probability distributions and
study the complexity required to play NEs in finite two player $n\times n$
games (i.e. each player’s set of pure strategies is $[n]$) with rational
payoffs. Our central results show that there exist games in which there is an
exponential vs. linear gap in the complexity of the mixed distributions that
the two players play at (the unique) NE. This gap induces gaps in the amount
of space required to represent and sample from the corresponding distributions
using known state-of-the-art sampling algorithms [23, 14, 36, 35, 31, 10, 30,
9]. We also establish upper and lower bounds on the complexity of any NE in
the games that we study. These results highlight (i) the nontriviality of the
assumption that players can play any mixed strategy and (ii) the disparities
in resources that players may require to play NEs in the games that we study.

######  Definition 1.1.

Let $x=(x_{1},...,x_{n})$ be a distribution where
$x_{1},...,x_{n}\in\mathbb{Q}$. Represent $x$ uniquely as
$\left(\frac{p_{1}}{q},...,\frac{p_{n}}{q}\right)$ where
$p_{1},...,p_{n},q\in\mathbb{N}$, $q>0$ and $\gcd(p_{1},...,p_{n})=1$.111Here
$0\in\mathbb{N}$. Define the complexity of $x$ to be $C(x)=q$.

In this paper we only consider distributions with rational
coefficients.222Call a distribution $x\in\Delta[n]$ rational if all its
coefficients are rational. As stated in Avis et al. [5], for 2-player games
with rational payoffs, every NE can be described as a convex combination of
extreme NEs, and those constitute NE strategy profiles where all the mixed
strategies are rational (as the extreme NEs are vertices of rational
polytopes). In particular, if the game is nondegenerate, then the extreme NEs
are the only NEs of the game. However, for completeness, if $x$ is a
distribution that does not have this form, define $C(x)=\infty$. For instance
$C\left(\left(\frac{1}{2},\frac{1}{3},\frac{1}{6}\right)\right)=6$. We then
define the capabilities of the players.

######  Definition 1.2.

For player $i$, we say that $i$ has capability $c_{i}$ if they can play only
strategies from the set $\left\\{x\in\Delta[n]\mid C(x)\leq c_{i}\right\\}$.

The bounded-randomness game is then defined as follows:

######  Definition 1.3.

In a bounded-randomness game, the two players have (integral) randomness
capabilities $c_{1},c_{2}\geq 1$. The set of all strategies (pure and mixed)
available to player $i$ is $\left\\{x\in\Delta[n]\mid C(x)\leq
c_{i}\right\\}$.

The game is defined by two payoff matrices $A,B\in\mathbb{Z}^{n\times n}$ (see
Section 3 for further details on this choice of games). For the set of NEs of
the game, $\operatorname{NE}(A,B)$, let
$C_{1}(A,B)=\min_{(x,y)\in\operatorname{NE}}C(x),C_{2}(A,B)=\min_{(x,y)\in\operatorname{NE}}C(y)$.
In words, $C_{i}(A,B)$ is the minimal capability required from player $i$ to
play any NE strategy. By the best-response condition (see [29], Chapter 3),
and because deterministic distributions have complexity 1, it follows that
having players with capabilities $\geq C_{i}(A,B)$ is a necessary condition
for the existence of a NE in the corresponding bounded-randomness game.

##### Our results

We study upper and lower bounds on the minimum capabilities $C_{i}(A,B)$
required to play NEs. Our main results are as follows. First, we prove an
upper bound on $C_{i}(A,B)$ as a function of $n$ and the payoff matrices
$A,B$.

######  Theorem 1.4.

For every $A,B\in\mathbb{Z}^{n\times n}$ there holds

$\displaystyle C_{1}(A,B)\leq\left(\max_{i,j}B_{i,j}\right)^{n}\cdot
2^{O(n\log n)},~{}C_{2}(A,B)\leq\left(\max_{i,j}A_{i,j}\right)^{n}\cdot
2^{O(n\log n)}$

In particular, if $A,B$ have entries which are $poly(n)$, then
$C_{i}(A,B)=2^{O(n\log n)}$.

We then prove lower bounds via explicit constructions. Each construction is
also slightly modified to produce lower bounds for constant-sum games. The
first bound is a $2^{\tilde{\Omega}(\sqrt{n})}$ lower bound. Let
$\mathbb{Z}_{2}=\left\\{0,1\right\\}$.

######  Theorem 1.5.

There is a function $f(n)=\tilde{\Theta}(\sqrt{n})$ such that

  1. 1.

for every $n$ there are $A,B\in\mathbb{Z}_{2}^{n\times n}$ such that
$C_{1}(A,B)=2^{f(n)}$ and $C_{2}(A,B)=n$;

  2. 2.

for every $n$ there are $A,B\in\mathbb{Z}_{2}^{n\times n}$ such that the game
$(A,B)$ is a constant-sum game and $C_{1}(A,B)=C_{2}(A,B)=2^{f(n)}$.

To prove these bounds, we construct block matrices in which the block sizes
are prime numbers, and the lower bound is the product of those sizes. In
addition, the proof uses some well-known properties of prime numbers.
Afterwards, using a different idea, we strengthen the result with a
$2^{\Omega(n)}$ lower bound:

######  Theorem 1.6.

There is a function $g(n)=\Theta(n)$ such that

  1. 1.

for every $n$ there are $A,B\in\mathbb{Z}_{2}^{n\times n}$ such that
$C_{1}(A,B)=2^{g(n)}$ and $C_{2}(A,B)=n$;

  2. 2.

for every $n$ there are $A,B\in\mathbb{Z}_{2}^{n\times n}$ such that the game
$(A,B)$ is a constant-sum game and $C_{1}(A,B)=C_{2}(A,B)=2^{g(n)}$.

To prove these bounds, we study a pair of linear recurrences. These
recurrences have appealing properties which align with our goal of proving the
lower bound. For example, the set of NEs of this construction is characterized
by linear dependencies in these recurrences. In both lower bound
constructions, when players have unlimited mixing capabilities and $n\geq 8$,
there is a unique NE and it is fully-mixed (i.e. every pure strategy is picked
with probability $>0$). The lower bound constructions in Theorem 1.5, Item 1
and Theorem 1.6, Item 1 are instances of what are sometimes called imitation
games [25, 26]. Our proofs for Theorem 1.5, Item 2 and Theorem 1.6, Item 2
exploit the high symmetry in the lower bound constructions of the
corresponding Item 1s.

######  Example 1.7.

Consider the following $8\times 8$ game game defined by the following payoff
matrices:

$\displaystyle A=\left(\begin{array}[]{cccccccc}1&0&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&0\\\ 0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\
0&0&0&0&0&1&0&0\\\ 0&0&0&0&0&0&1&0\\\
0&0&0&0&0&0&0&1\end{array}\right),~{}~{}~{}B=\left(\begin{array}[]{cccccccc}0&1&1&0&0&0&0&0\\\
0&0&1&1&0&0&0&0\\\ 0&1&0&1&1&0&0&0\\\ 0&0&1&0&1&1&0&0\\\ 0&0&0&1&0&1&1&0\\\
0&0&0&0&1&0&1&1\\\ 0&0&0&0&0&1&0&1\\\ 1&0&0&0&0&0&0&0\end{array}\right)$ (17)

Then the unique NE is given by the pair of distributions $(x,y)$ of players 1,
2 respectively, where

$\displaystyle
x=\left(\frac{6}{34},\frac{2}{34},\frac{3}{34},\frac{1}{34},\frac{4}{34},\frac{5}{34},\frac{4}{34},\frac{9}{34}\right),~{}y=\left(\frac{1}{8},\frac{1}{8},\frac{1}{8},\frac{1}{8},\frac{1}{8},\frac{1}{8},\frac{1}{8},\frac{1}{8}\right)$

$C(x)=34,~{}C(y)=8$, therefore $C_{1}(A,B)=34,~{}C_{2}(A,B)=8$.

The lower bound constructions in Theorem 1.5, Item 2 and Theorem 1.6, Item 2
are the corresponding constant-sum versions of the games that we use to prove
the lower bounds in Theorem 1.5, Item 1 and Theorem 1.6, Item 1.

######  Example 1.8.

Consider the $8\times 8$ constant-sum game defined by the following payoff
matrices:

$\displaystyle A^{\prime}=\left(\begin{array}[]{cccccccc}1&0&0&1&1&1&1&1\\\
1&1&0&0&1&1&1&1\\\ 1&0&1&0&0&1&1&1\\\ 1&1&0&1&0&0&1&1\\\ 1&1&1&0&1&0&0&1\\\
1&1&1&1&0&1&0&0\\\ 1&1&1&1&1&0&1&0\\\
0&1&1&1&1&1&1&1\end{array}\right),~{}~{}~{}B^{\prime}=\left(\begin{array}[]{cccccccc}0&1&1&0&0&0&0&0\\\
0&0&1&1&0&0&0&0\\\ 0&1&0&1&1&0&0&0\\\ 0&0&1&0&1&1&0&0\\\ 0&0&0&1&0&1&1&0\\\
0&0&0&0&1&0&1&1\\\ 0&0&0&0&0&1&0&1\\\ 1&0&0&0&0&0&0&0\end{array}\right)$ (34)

the unique NE is given by the pair of distributions $(x^{\prime},y^{\prime})$
of players 1, 2 respectively, where

$\displaystyle
x^{\prime}=\left(\frac{6}{34},\frac{2}{34},\frac{3}{34},\frac{1}{34},\frac{4}{34},\frac{5}{34},\frac{4}{34},\frac{9}{34}\right),~{}y^{\prime}=\left(\frac{9}{34},\frac{4}{34},\frac{5}{34},\frac{4}{34},\frac{1}{34},\frac{3}{34},\frac{2}{34},\frac{6}{34}\right)$

$C(x^{\prime})=C(y^{\prime})=34$, therefore
$C_{1}(A^{\prime},B^{\prime})=C_{2}(A^{\prime},B^{\prime})=34$.

We note that neither of these examples is minimal — the $4\times 4$ game
corresponding to Example 1.7 (which has previously appeared in Bonifaci et al.
[7]) is a minimal game wrt $n$ such that $C_{1}(A,B)>n\geq C_{2}(A,B)$ (with
$C_{1}(A,B)=5$ and $C_{2}(A,B)=4$) and the $4\times 4$ game corresponding to
Example 1.8 is a minimal game such that $C_{1}(A,B),C_{2}(A,B)>n$ (with
$C_{i}(A,B)=5$).

##### Organization

In Section 2 we overview related work. In Section 3 we define the problem
setup. In Section 4 we prove basic lemmas. In Section 5 we prove the upper and
lower bounds, and in particular prove Theorems 1.4, 1.5 and 1.6. In Appendix A
consider the special cases of $2\times 2$ games and permutation games.

##  2 Related Work

###  2.1 Sampling Algorithms

Modern algorithms for sampling from discrete rational probability
distributions take as input the numerators of the corresponding probabilities
(the denominator is then the sum of the numerators) [23, 36, 31, 35, 30, 10,
14, 9]. The algorithms preprocess the input to construct an auxiliary data
structure (such as a binary decision tree or a prefix sum array), then use
this data structure to convert a sequence of random bits into a sample from
the specified finite distribution.

For these algorithms the input size (with a standard binary encoding of the
integers) for the NE distribution of player 2, namely the uniform
distribution, is $\Theta(n)$, while the input size for the NE distribution of
player 1 in Theorem 1.5, Item 1 is $\tilde{\Theta}(n\sqrt{n})$ (Corollary 5.5)
and in Theorem 1.6, Item 1 it is $\Theta(n^{2})$ (Corollary 5.26). The sizes
of the auxiliary data structures vary depending on the algorithm, specifically
$\Theta(n\log n)$ for the uniform distribution and
$\tilde{\Theta}(n\sqrt{n}),\Theta(n^{2})$ [30, 31, 35]; $r+\Theta(\log n)$ for
the uniform distribution and $r+\tilde{\Theta}(\sqrt{n}),r+\Theta(n)$ for the
said distributions, where $r\leq n$ is a space-time tradeoff parameter [10,
9].

These results highlight the differences in resources required to represent,
transmit, and work with the different probability distributions we consider in
this paper.

###  2.2 Playing Games with Bounded Entropy

In the context of playing games with bounded randomness, the most common
approach to quantify the complexity of mixed strategy is via their entropy.
There are two lines of research: one-shot games and repeated games.

##### One-shot games

Halpern and Pass [19] consider games with costly computation, where players
also aim to minimize their cost (either absolute or relative to other
players). The cost can be manifested in the amount of randomness (random bits)
the players use in their strategies. They show that the existence of a NE
depends on the players’ abilities to use randomness, and that NEs always exist
in games where randomization is free (yet other computational aspects can
still be costly).

Many papers in this context focus on $\varepsilon$-NEs (namely additive
$\varepsilon$-approximate NEs) with small supports [6, 15, 2, 13, 24, 17].
Such an approximate NE will also have a small entropy, but a small support is
not necessary for having small entropy. It is known [13] that uniform
strategies with support of size at most two are sufficient to obtain a
$\frac{1}{2}$-approximate NE, and Feder et al. [15] show that to achieve a
better approximation factor one needs to consider mixed strategies with
supports of size $\Omega(\log n)$. On the other hand, Lipton et al. [24]
proves the existence of $\varepsilon$-NEs with supports of size
$O\left(\frac{\log n}{\varepsilon^{2}}\right)$ (for any $\varepsilon>0$) by
constructing an algorithm that finds one. Anbalagan et al. [2] refutes the
existence of $\varepsilon$-well-supported NEs333Strategy profiles where each
strategy is comprised of pure strategies each of which is an
$\varepsilon$-best response to the other strategies in the profile. with
supports of size $k$ for any constant $k$. There is also work on the existence
of pure NEs in random games [17] and the existence of NEs with supports of
size two [6].

##### Repeated games with bounded entropy

Repeated games with bounded entropy have been studied in the last 25 years
[11, 20, 22, 28, 32, 33]. First, there is the work of Neyman and Okada [28],
where they characterized the maxmin value of a (finitely/infinitely) repeated
zero-sum game, when a player who is restricted to mixed strategies with
(sufficiently) bounded entropy plays against an unrestricted player. Budinich
and Fortnow [11] analyze a repeated version of the matching pennies game,
derive results on the amount of entropy needed from both players to play an
$\varepsilon$-NE, and study their optimal payoffs when they have bounded
entropies. Hubáček et al. [20] generalize those results (in both aspects) to a
large set of repeated games that contains 2-player repeated zero-sum games. In
both papers, the conclusion is that these games require $\Omega(N)$ random
bits to play a NE, where $N$ is the number of repetitions, while other games
require only $O(1)$ random bits. Arthaud [4] advances this line of work by
establishing a 0-1 law: in every repeated game, there is either a NE that
requires only $O(1)$ entropy from all players, or every NE of the repeated
game requires $\Omega(n)$ entropy from at least one of the players.
Kalyanaraman and Umans [22] give both randomized and derandomized algorithms
to find sparse $\varepsilon$-NEs (where strategies have small supports) in a
learning settings where players have limited access to random bits. Valizadeh
and Gohari [32, 33] study the maxmin value in 2-player zero-sum repeated games
in settings where one player is restricted to playing strategies with bounded
entropy, while the second player is unrestricted. They study both asymptotic
and nonasymptotic aspects of the value.

Our approach is different in that our measure of distribution complexity is
sensitive to the numerators and denominators in the representation of the
distribution, and not just to the amount of “uniformity” in it (which is
captured by the entropy function).

###  2.3 Imitation Games

Our constructions involve imitation games, which are games where one player
receives positive payoff iff the player plays the same pure strategy as the
other player (for some notion of ‘same’). These games were first defined in
[25], where they were leveraged to derive a simple proof of Kakutani’s fixed-
point theorem [21]. Computing a NE was shown to be as hard in imitation games
as in symmetric games, and it is known [16] that computing a NE in symmetric
games is as hard as in general normal-form games. In both reductions the NE
profiles remain the same as distributions, up to adding zero-probability
events or swapping one of the mixed strategies in the profile with a uniform
distribution. In [26], the authors continue utilizing imitation games to
derive additional simple proofs in computational complexity.

##  3 Problem Setup

##### 2-player normal-form games

We consider 2-player $n\times n$ normal-form games with nonnegative integer
payoffs (see [29] for reference). We write such a game as $(A,B)$, where
$A,B\in\mathbb{Z}^{n\times n}$ are the payoff matrices of players 1, 2
respectively. This makes $[n]$ the set of pure strategies for the two players.
These induce the payoff functions $u_{1},u_{2}:[n]\times[n]\to\mathbb{N}$
defined by $u_{1}(i,j)=A_{i,j},u_{2}(i,j)=B_{i,j}$. Let $\Delta X$ be the set
of distributions over $X$. Then $u_{1},u_{2}$ are naturally extended to
payoffs of mixed strategy profiles
$u_{1},u_{2}:\Delta[n]\times\Delta[n]\to\mathbb{R}$ by
$u_{1}(\sigma_{1},\sigma_{2})=\operatorname*{\mathbb{E}}_{(i,j)\sim(\sigma_{1},\sigma_{2})}(u_{1}(i,j))=\sigma_{1}^{T}A\sigma_{2}$
and similarly $u_{2}(\sigma_{1},\sigma_{2})=\sigma_{1}^{T}B\sigma_{2}$. For a
finite set $X$, let $U_{X}$ be the uniform distribution on $X$. In addition to
the definition of $\operatorname{NE}(A,B)$, let $\operatorname{PNE}(A,B)$ be
the set of pure NEs of the game. When $A,B$ are known from context, we simply
write $\operatorname{NE}$, $\operatorname{PNE}$.

As for the choice of these games, we assume that the payoffs are rational, and
because (expected) payoff functions are linear, we further assume wlog that
the payoffs are in $\mathbb{N}$. We will also consider constant-sum games,
i.e. $A,B$ that satisfy $A+B=u{\bf 1}_{n\times n}$ where $u\in\mathbb{N}$ is
constant. The argument above shows that this is wlog compared to zero-sum
games in the setting of rational payoffs.

##### Binary-payoff games

To prove our results, we will focus for the most part on these games. We will
further assume that $\operatorname{PNE}(A,B)=\emptyset$, for otherwise
$C_{i}(A,B)=1$. This means that $A_{i,j}\cdot B_{i,j}=0$ and
$\sum_{j}A_{i,j},\sum_{i}B_{i,j}>0$ for all $i,j$.

##### Linear algebra

In this paper we consider only $n\times n$ payoff matrices, and sometimes
treat them as matrices in $\mathbb{Z}^{n\times n}$. Let
$A\in\mathbb{Z}^{n\times n}$. For $I,J\subseteq[n]$, let
$A_{I,J}=(A_{i,j})_{i\in I,j\in J}\in\mathbb{Z}^{|I|\times|J|}$. Denote with
$A[i|j]:=A_{[n]\setminus\left\\{i\right\\},[n]\setminus\left\\{j\right\\}}$
the $(i,j)$th minor of $A$. Let $\kappa_{i,j}:=(-1)^{i,j}\det(A[i|j])$ be the
$(i,j)$th cofactor of $A$. Note that $\det A=\sum_{i,j}A_{i,j}\kappa_{i,j}$
and $(A^{-1})_{i,j}=\frac{1}{\det A}\kappa_{j,i}$. Now we define
$K(A):=\sum_{i,j}\kappa_{i,j}$. For $i\in[n]$ and $b\in\mathbb{Z}^{n}$, let
$A\stackrel{{\scriptstyle i}}{{\leftarrow}}b$ result from $A$ by replacing
column $i$ with $b$. Then we get $K(A)=\sum_{i}\det(A\stackrel{{\scriptstyle
i}}{{\leftarrow}}\bf 1)$. The quantity $K(A)$ can be used to upper bound
$C_{2}(A,B)$, and similarly with $K(B),C_{1}(A,B)$ (see Theorem 4.5). Denote
with $\bf 1,\bf 0$ the all-ones, all-zeros vectors of length $n$. For
$i\in[n]$, let $e_{i}\in\mathbb{R}^{n}$ be 1 at entry $i$ and 0 everywhere
else. For $I\subseteq[n]$, let $=\sum_{i\in I}e_{i}$.

##  4 Basic Lemmas

We begin with two lemmas about games, then prove linear algebra lemmas.

######  Lemma 4.1.

Any $(x,y)\in\operatorname{NE}(I_{n},B)$ satisfies
$\operatorname{supp}x\subseteq\operatorname{supp}y$ and
$y=U_{\operatorname{supp}y}$.

###### Proof.

Because
$\operatorname{supp}x\subseteq\operatorname{BR}_{1}(y)\subseteq\operatorname{supp}y$.
Part 2 follows from the best-response condition [29]. ∎

######  Lemma 4.2.

Let $A,B\in\mathbb{Z}^{n\times n}$, such that $A$ does not contain a column of
0s, and $B$ does not contain a row of 0s. Then it is possible to add a dummy
strategy to each player which does not change the set of NEs (up to projecting
the NE mixed strategies on the first $n$ pure strategies). In particular, if
the game is constant-sum with $A+B={\bf 1}_{n\times n}$, then it will remain
such after adding the dummy strategies.

###### Proof.

Given $A,B\in\mathbb{Z}^{n\times n}$, define

$\displaystyle A^{\prime}=\left(\begin{array}[]{c|c}A&\bf 1\\\ \hline\cr{\bf
0}&1\end{array}\right),B^{\prime}=\left(\begin{array}[]{c|c}B&{\bf 0}\\\
\hline\cr\bf 1&0\end{array}\right)$

Then $\operatorname{NE}(A,B)=\operatorname{NE}(A^{\prime},B^{\prime})$ follows
(with abuse of notation regarding the equilibrium distributions). ∎

######  Lemma 4.3.

Suppose that $A$ is binary, $\det A\neq 0$ and $A^{-1}\bf 1\geq 0$. Then
$|\det A|\leq|K(A)|\leq n|\det A|$.

###### Proof.

Let $x=A^{-1}\bf 1$. We have $n=\left\langle
Ax,1\right\rangle=\sum_{i,j}A_{i,j}x_{i}$. Because $A$ is binary and
invertible, $\sum_{j}A_{i,j}\in[n]$ for all $i$. Using Cramer’s rule [12],

$\displaystyle x_{j}=\frac{\det(A\stackrel{{\scriptstyle i}}{{\leftarrow}}\bf
1)}{\det A}~{}\Rightarrow~{}\sum_{j}x_{j}=\frac{K(A)}{\det A}\geq 0$

Therefore

$\displaystyle\frac{K(A)}{\det A}\leq n=\sum_{i,j}A_{i,j}x_{i}\leq
n\frac{K(A)}{\det A}$

Hence $|\det A|\leq|K(A)|\leq n|\det A|$. ∎

The proof also implies that under the conditions above (regardless of whether
$A$ is binary), $\det A,K(A)$ have the same sign. It is strengthened as
follows.

######  Lemma 4.4.

Assume the above and in addition that for some $M\geq 0$, $\sum_{j}A_{i,j}\leq
M$ for all $i\in[n]$. Then $|K(A)|\geq\frac{n}{M}|\det A|$.

###### Proof.

The main inequality in the previous proof becomes

$\displaystyle n=\sum_{i,j}A_{i,j}x_{i}\leq M\frac{K(A)}{\det A}$

Hence $|K(A)|\geq\frac{n}{M}|\det A|$. ∎

To demonstrate how $K(A)$ can show up in our context, we have the following:

######  Theorem 4.5.

Let $A,B\in\mathbb{Z}_{2}^{n\times n}$. Suppose that $\det A,\det B\neq 0$ and
that the game admits a fully-mixed NE. Then $C_{1}(A,B)\leq
K(B),C_{2}(A,B)\leq K(A)$.

###### Proof.

Let $x=(B^{T})^{-1}{\bf 1},y=A^{-1}\bf 1$. By the support enumeration
algorithm (see [29], Chapter 3), $x,y\geq\bf 0$ and the unique fully-mixed NE
of the game is $\left(\frac{x}{\left\lVert
x\right\rVert_{1}},\frac{y}{\left\lVert y\right\rVert_{1}}\right)$. As before,
we have

$\displaystyle\left\lVert x\right\rVert_{1}=\sum_{i}x_{i}=\frac{K(B^{T})}{\det
B^{T}}=\frac{K(B)}{\det B}$

($K(B^{T})=K(B)$ by definition). Therefore

$\displaystyle\frac{x_{i}}{\left\lVert
x\right\rVert_{1}}=\frac{\det(B^{T}\stackrel{{\scriptstyle
i}}{{\leftarrow}}\bf 1)}{K(B)}$

Since $B$ has integer entries, the numerator and denominator of the fraction
above are integers, so we get $C_{1}(A,B)\leq C\left(\frac{x}{\left\lVert
x\right\rVert_{1}}\right)\leq K(B)$. An analogous argument shows the second
inequality. ∎

##  5 Worst-Case Bounds

We begin with proving Theorem 1.4.

######  Theorem 5.1 (Restatement of Theorem 1.4).

Let $A,B\in\mathbb{Z}^{n\times n}$. Then

$\displaystyle C_{1}(A,B)\leq\left(\max_{i,j}B_{i,j}\right)^{n}\cdot
2^{O(n\log n)},~{}C_{2}(A,B)\leq\left(\max_{i,j}A_{i,j}\right)^{n}\cdot
2^{O(n\log n)}$

In particular, if $A,B$ have entries which are $poly(n)$, then
$C_{i}(A,B)=2^{O(n\log n)}$.

###### Proof.

Let $(x,y)\in\operatorname{NE}(A,B)$ with supports $I,J$. Let $k=|I|,l=|J|$.

Write $x=\left(\frac{p_{1}}{q},...,\frac{p_{n}}{q}\right)$ where
$p_{i},q\in\mathbb{N}$ and $\gcd(p_{1},...,p_{n})=1$. Consider
$p_{I}:=(p_{i})_{i\in I},B,J$. Then they satisfy the linear equalities and
inequalities

$\displaystyle(B_{I,J})^{T}p_{I}=u\cdot{\bf 1}_{l},~{}~{}~{}(B_{I,[n]\setminus
J})^{T}p_{I}\leq u\cdot{\bf 1}_{n-l},~{}~{}~{}p_{I}\geq{\bf
1}_{k},~{}~{}~{}(p_{I},u)\in\mathbb{N}_{>0}^{k+1}$

In words, these equalities and inequalities mean that conditioned on player 1
playing $x$, the pure strategies in $J$ all yield the maximal utility for
player 2, and that player 1 plays every pure strategy $i\in I$ with positive
probability (see [29], Chapter 3 for further details). We reorganize terms to
get the equivalent problem

$\displaystyle(B_{I,J})^{T}p_{I}-u\cdot{\bf 1}_{l}={\bf
0}_{l},~{}~{}~{}\left(\begin{array}[]{c}u\cdot{\bf 1}_{n-l}-(B_{I,[n]\setminus
J})^{T}p_{I}\\\ p_{I}\end{array}\right)\geq\left(\begin{array}[]{c}{\bf
0}_{n-l}\\\ {\bf
1}_{k}\end{array}\right),~{}~{}~{}(p_{I},u)\in\mathbb{N}_{>0}^{k+1}$

So to minimize $q+u=\sum_{i\in I}p_{i}+u$ where $(p_{I},u)$ is the variable,
von zur Gathen and Sieveking [34] show that there exists a solution
$(p_{I},u)$ where

$\displaystyle\sum_{i\in I}p_{i}+u\leq n(n+1)M$

where $M$ is an upper bound on the absolute values of all subdeterminants of
the matrix

$\displaystyle\left(\begin{array}[]{c|c}\begin{array}[]{c|c}(B_{I,J})^{T}&-{\bf
1}_{l}\end{array}&{\bf 0}_{l}\\\
\hline\cr\left(\begin{array}[]{c}\begin{array}[]{c|c}-(B_{I,[n]\setminus
J})^{T}&{\bf 1}_{n-l}\end{array}\\\ \hline\cr
I_{k+1}\end{array}\right)&\left(\begin{array}[]{c}{\bf 0}_{n-l}\\\
\hline\cr{\bf 1}_{k+1}\end{array}\right)\end{array}\right)$

This is an $n+k+1\times k+2$ matrix, so by Hadamard [18] we can bound
$M\leq\left(\max_{i,j}B_{i,j}\right)^{n}\cdot(2n+1)^{\frac{2n+1}{2}}$ and then
$q=\sum_{i}p_{i}\leq\left(\max_{i,j}B_{i,j}\right)^{n}\cdot 2^{O(n\log n)}$.
Therefore $C_{1}(A,B)\leq q\leq\left(\max_{i,j}B_{i,j}\right)^{n}\cdot
2^{O(n\log n)}$. A similar inequality follows for $C_{2}$. ∎

We now prove the lower bounds in Theorem 1.5 and Theorem 1.6. To obtain the
lower bounds, we note that in all constructions and for all $n\geq 8$, there
is a unique NE and it is fully-mixed. We then derive closed-form expressions
for the unique NE in each construction, and analyze its complexity in terms of
$C$. We begin with the simpler lower bound of $2^{\tilde{\Omega}(n)}$, and
then proceed to the more involved $2^{\Omega(n)}$ lower bound.

It is worth mentioning that Alon and Vũ [1] constructed matrices $B_{n}$ for
every $n$, where the game $(I_{n},B_{n})$ has a unique fully-mixed NE
$(x_{n},U_{n})$ which satisfies $C(x_{n})=2^{\Theta(n\log n)}$. However, these
games also admit many pure NEs, implying that $C_{i}(I_{n},B_{n})=1$. Put
formally,

######  Theorem ([1, Theorem 3.5.1]).

For every $n$ there is a matrix $B_{n}\in\\{0,1\\}^{n\times n}$ such that for
the game $(I_{n},B_{n})$ there exists a fully-mixed NE $(x,y)$ where
$C(x)=2^{\frac{1}{2}n\log n-n(2+o(1))}$, while $C(y)=n$.

###  5.1 $2^{\tilde{\Omega}(\sqrt{n})}$ Lower Bound

For $k\in\mathbb{N}$ let $B^{k}\in\mathbb{Z}_{2}^{k+1\times k+1}$ be the
matrix where $B^{k}_{ij}=1$ if $i\neq j+1\bmod k+1$ and 0 otherwise. For
example,

$\displaystyle B^{5}=\left(\begin{array}[]{cccccc}1&1&1&1&1&0\\\
0&1&1&1&1&1\\\ 1&0&1&1&1&1\\\ 1&1&0&1&1&1\\\ 1&1&1&0&1&1\\\
1&1&1&1&0&1\end{array}\right)$

######  Lemma 5.2.

$\det B^{k}=k$. Let $B^{\prime}$ result from $B^{k}$ by replacing one of its
0-entries with a 1. Then $\det B^{\prime}=1$.

###### Proof.

$B^{k}$ is a $k+1\times k+1$ matrix. Let $\chi_{A}$ be the characteristic
polynomial of a matrix $A$. For the matrix ${\bf 1}_{k+1\times k+1}$, we have
$\chi_{{\bf 1}_{k+1\times k+1}}(x)=(x-k-1)x^{k}$. Therefore

$\displaystyle\det(B^{k})=(-1)^{k}\det({\bf 1}_{k+1\times
k+1}-I_{k+1})=-\det(I_{k+1}-{\bf 1}_{k+1\times k+1})=-\chi_{{\bf 1}_{k+1\times
k+1}}(1)=k$

where the first equality is by applying $k$ row swaps. Let $B^{\prime}$. Apply
the same row swaps that transform $B^{\prime}$ into ${\bf 1}_{k+1\times
k+1}-I_{k+1}$ up to one main-diagonal entry (where the entry is 1). Suppose
that that entry is $(i,i)$. Then by the above, when expanding the determinant
along row $i$,

$\displaystyle\det B^{\prime}=k+(-1)^{k}(-1)^{2i}\det({\bf 1}_{k+1\times
k+1}-I_{k+1})[i|i]\stackrel{{\scriptstyle\text{def}}}{{=}}k+(-1)^{k}\det({\bf
1}_{k\times k}-I_{k})=k-(k-1)=1$

∎

######  Theorem 5.3.

Let $n\in\mathbb{N}$. For $N=\Theta(n^{2}\log n)$ there exist matrices
$A,B\in\mathbb{Z}_{2}^{N\times N}$ such that $A=I_{N}$, and

$\displaystyle C_{1}(A,B)=2^{\Theta(n\log
n)}=2^{\tilde{\Theta}(\sqrt{N})},~{}C_{2}(A,B)=N$ (35)

###### Proof.

For $n$ let $p_{1},...,p_{n}$ be the first $n$ primes. Let $N=\sum_{k\leq
n}(p_{k}+1)+1=\sum_{k}p_{k}+n+1$. By the prime number theorem [3],
$p_{k}=\Theta(k\log k)$, so $N=\Theta(n^{2}\log n)$. Define the matrix
$B^{\prime}=diag(B^{p_{1}},B^{p_{2}},...,B^{p_{n}})\in\mathbb{Z}_{2}^{N-1\times
N-1}$, and then define

$\displaystyle B=\left(\begin{array}[]{c|c}{\bf 0}_{N-1\times 1}&B^{\prime}\\\
\hline\cr 1&{\bf 0}_{1\times N-1}\end{array}\right)\in\mathbb{Z}_{2}^{N\times
N}$ (38)

We first prove that $(A,B)$ has only one NE and it is fully-mixed. Let
$(x,y)\in\operatorname{NE}$ with supports $I,J\subseteq[N]$. Suppose
$I\neq[N]$. Then for some $u$, $x$ satisfies

$\displaystyle\forall j\in J,~{}~{}~{}\sum_{i\in
I}x_{i}B_{ij}=\sum_{i,~{}B_{ij}=1}x_{i}=u$

Here we abuse notation and refer to $B^{p_{k}}$ also as its set of row indices
in $B$. For $i\in B^{p_{k}}$ we also write $i+1\bmod B^{p_{k}}$ to refer to
either $i+1$ if $i<\max B^{p_{k}}$ or $\min B^{p_{k}}$ otherwise. First,
suppose that $k\leq n$ is such that $I\cap
B^{p_{k}}\notin\left\\{\emptyset,B^{p_{k}}\right\\}$. If $|I\cap
B^{p_{k}}|>1$, then linear algebra tells us that $x_{i}=0$ for every $i\in
B^{p_{k}}$, contradicting the assumption on $I$. Otherwise, $I\cap
B^{p_{k}}=\\{i\\}$. Then, $B_{ii}=0$, and because $i>1$ we get
$(x^{T}B)_{i}=0$, while $(x^{T}B)_{i+1\bmod B^{p_{k}}}>0$. Therefore, $i\notin
J$, so because $A=I_{N}$ we get $i\notin I$, a contradiction. Therefore $I\cap
B^{p_{k}}\in\left\\{\emptyset,B^{p_{k}}\right\\}$. Now focus on $i=N$. Suppose
that $i\notin I$, and let $i_{1}=\min I$. By the definition of $B$
(specifically because $B^{\prime}$ is placed off-diagonally), and using the
previous paragraph, it follows that $(x^{T}B)_{j}=0$ for all
$j\in\left\\{1,...,i_{1}-1,i_{1},N\right\\}$, while $(x^{T}B)_{j}>0$ for some
other $j$. Therefore $i_{1}\notin J$, so $i_{1}\notin I$ – a contradiction. In
addition, clearly there holds $I\setminus\\{N\\}\neq\emptyset$. It is left to
show that $B^{p_{k}}\subseteq I$ for all $k$. Suppose that $B^{p_{k}}\cap
I=\emptyset$. Let $i=\max B^{p_{k}}$. Using a similar argument, we get
$y_{i+1}=0$, so $x_{i+1}=0$, but $i+1\in I$, because $N\in I$. Hence $I=[N]$.
By Lemma 4.1, $J=[N]$.

Now we find the fully-mixed NE. Its uniqueness follows by the fact that $\det
I_{n},\det B\neq 0$. Let $(x,y)$ be the NE. For $y$, because $A=I_{N}$ one
immediately gets $y=U_{N}$. For some $u>0$, $x$ needs to satisfy $B^{T}x=\bf
1\cdot u$. Note that $B^{\prime}$ is a block-diagonal matrix, and when
expanding along the first column of $B$,

$\displaystyle\det
B=(-1)^{N-1}\prod_{k=1}^{n}\det(B^{p_{k}})\stackrel{{\scriptstyle\text{\lx@cref{creftype~refnum}{lmm:det
B^k}}}}{{=}}(-1)^{N-1}\prod_{k=1}^{n}p_{k}$

So by Cramer’s rule we get

$\displaystyle\forall i\leq
N~{}~{}~{}x_{i}=u\frac{\det(B^{T}\stackrel{{\scriptstyle i}}{{\leftarrow}}{\bf
1}_{N})}{\det B^{T}}$

Let $k$ such that row $i$ goes through block $B^{p_{k}}$. After replacing the
blocks we get an upper-triangular matrix, where the diagonal contains the
blocks $B^{p_{1}},...,B^{p_{k-1}},B^{p_{k+1}},...,B^{p_{n}}$, and the block
$B^{p_{k}}$ with one of its 0-entries replaced by a 1. Call the last block
$\beta$. So we get

$\displaystyle\det((B\stackrel{{\scriptstyle i}}{{\leftarrow}}{\bf
1}_{N})^{T})$
$\displaystyle=(-1)^{N-1}\cdot((-1)^{(p_{k}+1)\sum_{l<k}(p_{l}+1)}(-1)^{(p_{k}+1)\sum_{l<k}(p_{l}+1)})\det\beta\cdot\prod_{l\neq
k}p_{l}$ $\displaystyle=(-1)^{N-1}\det\beta\cdot\prod_{l\neq
k}p_{l}\stackrel{{\scriptstyle\text{\lx@cref{creftype~refnum}{lmm:det
B^k}}}}{{=}}(-1)^{N-1}\prod_{l\neq k}p_{l}=\frac{\det B}{p_{k}}$

Therefore, $x_{i}=\frac{u}{p_{k}}$. If $i=1$ we define $p_{k}=1$ and the
equality still holds. To normalize, we compute $\left\langle x,{\bf
1}_{N}\right\rangle$:

$\displaystyle\left\langle x,{\bf
1}_{N}\right\rangle=u\left(1+\sum_{k=1}^{n}\frac{p_{k}+1}{p_{k}}\right)=u\left(n+1+\sum_{k=1}^{n}\frac{1}{p_{k}}\right)$

Hence $u=n+1+\sum_{k=1}^{n}\frac{1}{p_{k}}$, and the normalized $x$ becomes
$x_{i}=\frac{1}{p_{k}\left(n+1+\sum_{l=1}^{n}\frac{1}{p_{l}}\right)}$.

Now, observe that
$x_{N}=\frac{\prod_{k}p_{k}}{\left(\prod_{k}p_{k}\right)\left(n+1+\sum_{k=1}^{n}\frac{1}{p_{k}}\right)}$
is $x_{N}$ written as a fraction where the numerator and denominator are
integers. The same holds for every $k$ and the fractions
$x_{i}=\frac{\prod_{l}p_{l}}{p_{k}\prod_{l}p_{l}\left(n+1+\sum_{l=1}^{n}\frac{1}{p_{l}}\right)}$.
Therefore
$C_{1}(A,B)\leq\left(\prod_{k}p_{k}\right)\left(n+1+\sum_{k=1}^{n}\frac{1}{p_{k}}\right)$.
We now claim that this is the reduced form for $x_{N}$, establishing that
$C_{1}(A,B)=\left(\prod_{k}p_{k}\right)\left(n+1+\sum_{k=1}^{n}\frac{1}{p_{k}}\right)$.
If not, then because the fraction is $\leq 1$, it follows that there exists an
$\alpha\in\mathbb{N}$ such that
$\alpha\prod_{k}p_{k}=\left(\prod_{k}p_{k}\right)\left(n+1+\sum_{k}\frac{1}{p_{k}}\right)$,
which means that $n+1+\sum_{k}\frac{1}{p_{k}}\in\mathbb{N}$, so
$\sum_{k}\frac{1}{p_{k}}\in\mathbb{N}$. But this is false: for $n=1$,
$\frac{1}{p_{1}}=\frac{1}{2}\notin\mathbb{N}$. If it was true for $n>1$ then
it would imply that $\frac{1}{p_{n}}+\sum_{k<n}\frac{1}{p_{k}}\in\mathbb{N}$.
Since $p_{n}$ is prime, this means that $p_{n}\mid\prod_{k<n}p_{k}$, which is
a contradiction as they are all distinct primes.

Now we show the asymptotics of $C_{1}(A,B)$. First,
$\log(\prod_{k}p_{k})=\sum_{k}\log p_{k}=\Theta(p_{n})=\Theta(n\log n)$ as
this is the first Chebyshev function [3] , and using the prime number theorem.
Therefore $\prod_{k}p_{k}=2^{\Theta(n\log n)}=2^{\tilde{\Theta}(n)}$. Since
$\sum_{k}\frac{1}{p_{k}}=\Theta(\log\log p_{n})=\Theta(\log\log n)$, we get
$C_{1}(A,B)=2^{\Theta(n\log n)}=2^{\tilde{\Theta}(\sqrt{N})}$. ∎

######  Corollary 5.4 (Restatement of Theorem 1.5, Item 1).

There is a function $f(n)=\tilde{\Theta}(\sqrt{n})$ such that for every $n$
there are $A,B\in\mathbb{Z}_{2}^{n\times n}$ such that $C_{1}(A,B)=2^{f(n)}$
and $C_{2}(A,B)=n$.

###### Proof.

Follows by taking the games above and padding them with dummy strategies as in
Lemma 4.2. ∎

######  Corollary 5.5.

For every $n$, the NE distribution $x$ of player 1 satisfies
$\max_{i,j}\frac{x_{i}}{x_{j}}=\tilde{\Theta}(\sqrt{n})$. Therefore
representing the numerators of $x$ would require $\tilde{\Theta}(n\sqrt{n})$
bits.

###### Proof.

By definition and the prime number theorem, it is
$p_{\tilde{\Theta}(\sqrt{n})}=\tilde{\Theta}(\sqrt{n}\log\sqrt{n})=\tilde{\Theta}(\sqrt{n})$.
This implies that all numerators are at least
$\frac{2^{\tilde{\Theta}(\sqrt{n})}}{n\tilde{\Theta}(\sqrt{n})}$, so they
would all take $\tilde{\Theta}(n\sqrt{n})$ bits. ∎

###  5.2 $2^{\Omega(n)}$ Lower Bound

We first establish constructions and properties. For $z\in\mathbb{C}$, let
$\Re(z),\Im(z)$ be the real part and imaginary part of $z$.

######  Definition 5.6.

Define the linear recurrences $a_{n},b_{n}$ by

$\displaystyle a_{1}=1,a_{2}=1,a_{3}=1,a_{4}=0$ $\displaystyle
b_{1}=0,b_{2}=1,b_{3}=0,b_{4}=1$

and for $n\geq 5$

$\displaystyle a_{n}=a_{n-2}-a_{n-3}+a_{n-4},$ $\displaystyle
b_{n}=b_{n-2}-b_{n-3}+b_{n-4}$

We have the following properties:

######  Lemma 5.7.

For $n\geq 4$, $\operatorname{sign}(b_{n})=(-1)^{n}$. In particular,
$b_{n}\neq 0$ for every $n\geq 5$.

###### Proof.

$\operatorname{sign}(b_{4})=\operatorname{sign}(1)=1$. By induction, for
$n>4$,
$\operatorname{sign}(b_{n})=\operatorname{sign}(b_{n-2}-b_{n-3}+b_{n-4})=\operatorname{sign}(b_{n-2})=(-1)^{n}$
because all 3 signed terms have the same sign (or some are 0 but not all). ∎

######  Lemma 5.8.

For every $n$, $b_{n}+b_{n+1}=a_{n}$.

###### Proof.

It is clear for $n\leq 4$. By induction, for $n\geq 5$,

$\displaystyle
a_{n}=a_{n-2}-a_{n-3}+a_{n-4}=b_{n-2}+b_{n-1}-b_{n-3}-b_{n-2}+b_{n-4}+b_{n-3}=b_{n}+b_{n+1}$

∎

The characteristic polynomial of the recurrence $b_{n}$ is
$x^{4}-x^{2}+x-1=(x-1)(x^{3}+x^{2}+1)$. Let

$\displaystyle\rho$
$\displaystyle=\frac{1}{3}\left(-1-\sqrt[3]{\frac{2}{29-3\sqrt{93}}}-\sqrt[3]{\frac{1}{2}\left(29-3\sqrt{93}\right)}\right)\approx-1.4656,$
(39) $\displaystyle z$
$\displaystyle=\frac{1}{12}\left(-4+\left(1+i\sqrt{3}\right)\sqrt[3]{4\left(29-3\sqrt{93}\right)}+\left(1-i\sqrt{3}\right)\sqrt[3]{4\left(29+3\sqrt{93}\right)}\right)\approx
0.2328-0.7926i$ (40)

be the real root and one of the two complex roots of the polynomial
$x^{3}+x^{2}+1$. The remaining root is $\overline{z}$. We have $|z|\approx
0.826$. Along with the additional root of 1, we get the set of linear
equations in $w_{0},w_{1},w_{2},w_{3}$:

$\displaystyle\begin{cases}w_{0}+w_{1}\rho+w_{2}z+w_{3}\overline{z}=0=b_{1}\\\
w_{0}+w_{1}\rho^{2}+w_{2}z^{2}+w_{3}\overline{z}^{2}=1=b_{2}\\\
w_{0}+w_{1}\rho^{3}+w_{2}z^{3}+w_{3}\overline{z}^{3}=0=b_{3}\\\
w_{0}+w_{1}\rho^{4}+w_{2}z^{4}+w_{3}\overline{z}^{4}=1=b_{4}\\\ \end{cases}$
(41)

From these equations one finds

$\displaystyle w_{0}=\frac{1}{3},~{}w_{1}\approx
0.169,~{}w_{2}\approx-0.251+0.02i,~{}w_{3}=\overline{w_{2}}$ (42)

and this gives the closed-form expression for $b_{n}$:

$\displaystyle
b_{n}=\frac{1}{3}+w_{1}\rho^{n}+w_{2}z^{n}+\overline{w_{2}}\cdot\overline{z}^{n}=\frac{1}{3}+w_{1}\rho^{n}+2\Re(w_{2}z^{n})$
(43)

Note that $|w_{2}|<\frac{1}{3}$. So

$\displaystyle|w_{2}z^{n}+\overline{w_{2}}\cdot\overline{z}^{n}|=|w_{2}z^{n}+\overline{w_{2}z^{n}}|=|2\Re(w_{2}z^{n})|\leq
2|w_{2}z^{n}|<\frac{2}{3}|z|^{n}<|\rho|^{n}$

Therefore

$\displaystyle\lim_{n\to\infty}\frac{b_{n+1}}{b_{n}}=\lim_{n\to\infty}\frac{\frac{1}{3}+w_{1}\rho^{n+1}+2\Re(w_{2}z^{n+1})}{\frac{1}{3}+w_{1}\rho^{n}+2\Re(w_{2}z^{n})}=\frac{w_{1}\rho}{w_{1}}=\rho$

In addition, one can see from the expression for $\frac{b_{n+1}}{b_{n}}$ that
(for $n\geq 5$) (i) its distance to $\rho$ is strictly decreasing; (ii)
$\frac{b_{n+1}}{b_{n}}>\rho$ for $n\in 2\mathbb{N}$ and $<\rho$ otherwise.
Simply put, we get $b_{n}\approx\rho^{n}$. In more precise words:

######  Proposition 5.9.

There exists a strictly increasing sequence $\lambda_{n}<\rho$ and a strictly
decreasing sequence $\mu_{n}>\rho$ such that for every $n\geq 5$,
$-\lambda_{n}b_{n}\leq b_{n+1}\leq-\mu_{n}b_{n}$. Furthermore, those sequences
satisfy $\lim_{n}\lambda_{n}=\lim_{n}\mu_{n}=\rho$.

5.9, $|\rho|>1$ and Lemma 5.8 imply that

######  Proposition 5.10.

For every $n\geq 6$, $a_{n}\neq 0$.

We now show the main property that will allow us to characterize the NEs of
the game that will be constructed:

######  Lemma 5.11.

For every $m<n$, there is no $\alpha\in\mathbb{R}$ such that
$(a_{n},b_{n})=\alpha\cdot(a_{m},b_{m})$, iff
$(m,n)\notin\left\\{(1,3),(4,6),(5,7)\right\\}$.

###### Proof.

Let $6\leq m<n$ and assume equality for contradiction. Then
$a_{m},b_{m},a_{n},b_{n}\neq 0$ so $\alpha\neq 0$. Equivalently we have
$\frac{a_{n}}{a_{m}}=\frac{b_{n}}{b_{m}}$. So

$\displaystyle
a_{n}b_{m}=a_{m}b_{n}\iff(b_{n}+b_{n+1})b_{m}=(b_{m}+b_{m+1})b_{n}\iff
b_{n+1}b_{m}=b_{n}b_{m+1}\iff\frac{b_{n+1}}{b_{n}}=\frac{b_{m+1}}{b_{m}}$

Call the last two ratios $\rho_{n},\rho_{m}$. If $n-m\notin 2\mathbb{N}$ then
either $\rho_{n}<\rho<\rho_{m}$ or $\rho_{m}<\rho<\rho_{n}$. If $n-m\in
2\mathbb{N}$ then either $\rho_{m}<\rho_{n}<\rho$ or $\rho<\rho_{n}<\rho_{m}$.
Both cases follow from 5.9, and both imply a contradiction.

One can verify the correctness of the claim when $m\leq 5$. ∎

We now construct the games that achieve the lower bound. For every $n$ define
$B_{n}\in\\{0,1\\}^{n\times n}$ to have 1s exactly on the main diagonal, on
the diagonal above it, and on the second diagonal below the main one. For
example,

$\displaystyle B_{5}=\left(\begin{array}[]{ccccc}1&1&0&0&0\\\ 0&1&1&0&0\\\
1&0&1&1&0\\\ 0&1&0&1&1\\\ 0&0&1&0&1\end{array}\right)$

Define

$\displaystyle\beta_{n}=\left(\begin{array}[]{c|c}{\bf 0}_{n-1\times
1}&B_{n-1}\\\ \hline\cr 1&{\bf 0}_{1\times
n-1}\end{array}\right)\in\mathbb{Z}_{2}^{n\times n}$

As an example,

$\displaystyle\beta_{11}=\left(\begin{array}[]{cccccccccccccc}0&1&1&0&0&0&0&0&0&0&0\\\
0&0&1&1&0&0&0&0&0&0&0\\\ 0&1&0&1&1&0&0&0&0&0&0\\\ 0&0&1&0&1&1&0&0&0&0&0\\\
0&0&0&1&0&1&1&0&0&0&0\\\ 0&0&0&0&1&0&1&1&0&0&0\\\ 0&0&0&0&0&1&0&1&1&0&0\\\
0&0&0&0&0&0&1&0&1&1&0\\\ 0&0&0&0&0&0&0&1&0&1&1\\\ 0&0&0&0&0&0&0&0&1&0&1\\\
1&0&0&0&0&0&0&0&0&0&0\end{array}\right)$ (55)

######  Lemma 5.12.

$\det B_{1}=1,\det B_{2}=1,\det B_{3}=2$. $\det B_{n}=\det B_{n-1}+\det
B_{n-3}$. Also $\det\beta_{n}=(-1)^{n+1}\det B_{n}$.

###### Proof.

Parts 1 and 3 are immediate. For part 2:

$\displaystyle\det B_{n}$ $\displaystyle=\det B_{n-1}-\det(B_{n}[1|2])=\det
B_{n-1}+\det((B[1|2])[2|1])$ $\displaystyle=\det
B_{n-1}+\det(((B[1|2])[2|1])[1|1])\stackrel{{\scriptstyle\text{def}}}{{=}}\det
B_{n-1}+\det B_{n-3}$

∎

So $\det B_{n}$ is also a linear recurrence. Similarly to before, its
characteristic polynomial is $x^{3}-x^{2}-1$, whose roots are
$-\rho,-z,-\overline{z}$. As a result a similar analysis yields the same
properties for the recurrence $\det B_{n}$, and
$\det\beta_{n}=\Theta(\rho^{n})$. In particular $\beta_{n}$ is invertible for
all sufficiently large $n$.

We now present the two main lemmas, that together yield the $2^{\Omega(n)}$
lower bound.

######  Lemma 5.13.

For every $n\notin\left\\{3,6,7\right\\}$, the game $(I_{n},\beta_{n})$ has a
unique NE and it is fully-mixed.

######  Lemma 5.14.

Let $n\geq 8$ and let $(x,y)$ be the unique NE of $(I_{n},\beta_{n})$. Except
for a subsequence $m_{n}=\omega(n)$, there holds $C(x)=2^{\Theta(n)}$, while
$C(y)=n$.

####  5.2.1 Proof of Lemma 5.13

The lemma follows immediately from the following:

######  Lemma 5.15.

For every $n\geq 1$,

$\displaystyle\left\\{\operatorname{supp}x\mid(x,y)\in\operatorname{NE}(I_{n},\beta_{n})\right\\}$
$\displaystyle=\left\\{[n]\setminus\left\\{i\leq
n\mid\exists\alpha~{}(a_{n+1},b_{n+1})=\alpha\cdot(a_{i},b_{i})\right\\}\right\\},$
$\displaystyle\left\\{\operatorname{supp}y\mid(x,y)\in\operatorname{NE}(I_{n},\beta_{n})\right\\}$
$\displaystyle=\left\\{J\supseteq\operatorname{supp}x\mid(x,y)\in\operatorname{NE}(I_{n},\beta_{n})\right\\}$

###### Proof.

Since in this case, by Lemma 5.11, $|\left\\{[n]\setminus\left\\{i\leq
n\mid\exists\alpha~{}(a_{n+1},b_{n+1})=\alpha\cdot(a_{i},b_{i})\right\\}\right\\}|=1$
for all $n\geq 8$, we assume that $n\geq 10$ and simply show that there is one
NE and it is fully-mixed. The cases $n\leq 9$ can be verified by hand. Let
$(x,y)\in\operatorname{NE}$ with supports $I,J$. Observe that $I\subseteq J$
because $A=I_{n}$ and $x\in\Delta\operatorname{BR}_{1}(y)$. We first show that
$\left\\{1,n-4,n-3,...,n\right\\}\subseteq I$. Let
$i\in\left\\{1,n-4,n-3,...,n\right\\}$, and suppose for contradiction that
$i\notin I$. We refer to Equation 55 to help visualize this.

##### Case $i=1$:

Let $i_{1}=\min I$.

  1. 1.

If $i_{1}=2$, then $3\in I$ (otherwise $2\notin J$). Then,
$(x^{T}\beta_{n})_{2}<(x^{T}\beta_{n})_{4}$, so $2\notin J$, which is a
contradiction.

  2. 2.

If $3\leq i_{1}\leq n-2$, then $i_{1}+1\notin I$ (otherwise $i_{1}\notin J$).

  3. 3.

If $i_{1}=n-1$ then $J\subseteq\left\\{1,n-2,n\right\\}$ – a contradiction.

  4. 4.

If $i_{1}=n$ then $J=\left\\{1\right\\}$ – a contradiction.

##### Case $i=n$:

Then $(x^{T}\beta_{n})_{1}=0$, so $1\notin I$, so it is again a contradiction.

Therefore $1,n\in I\subseteq J$. In order to not contradict that we have
$\left\\{n-2,n-1\right\\}\cap I\neq\emptyset$.

##### Case $i=n-1$:

Then $n-2\in I$. Then $\left\\{n-4,n-3\right\\}\cap I\neq\emptyset$. If
$n-3\in I$ then $(x^{T}\beta_{n})_{n}<(x^{T}\beta_{n})_{n-1}$ and if $n-4\in
I$ then $(x^{T}\beta_{n})_{n}<(x^{T}\beta_{n})_{n-3}$, so $n\notin J$ – a
contradiction.

##### Case $i=n-2$:

Then $n-3\in I$ (otherwise $(x^{T}\beta_{n})_{n-1}=0$ and then $n-1\notin J$
but $n-1\in I$). Then, $(x^{T}\beta_{n})_{n}<(x^{T}\beta_{n})_{n-2}$, so
$n\notin J$ – a contradiction.

##### Case $i=n-3$:

  1. 1.

If $n-2\notin I$ then $n-1\in I$ and this implies that $n-3\in I$ – a
contradiction.

  2. 2.

If $n-1\notin I$ then $n-2\in I$ and this implies that $n-4\in I$, but then
$(x^{T}\beta_{n})_{n}<(x^{T}\beta_{n})_{n-3}$, so $n\notin J$ – a
contradiction.

  3. 3.

If $n-2,n-1\in I$ then $(x^{T}\beta_{n})_{n-1}<(x^{T}\beta_{n})_{n}$ so
$n-1\notin J$ – a contradiction.

##### Case $i=n-4$:

Then by the above, $\left\\{n-3,n-2,n-1,n\right\\}\subseteq I$. With that, and
looking at $(x^{T}\beta_{n})_{n-2,n-1,n}$, we get that
$x_{n-3}=x_{n-2}=x_{n-1}$. Then, in order to have $n-3\in J$, there holds
$n-5\in I$ and $x_{n-5}=x_{n-3}=...=x_{n-1}$. Then, we also get $n-6\notin I$,
for otherwise $(x^{T}\beta_{n})_{n-4}>(x^{T}\beta_{n})_{n}$. Similarly,
$n-5\in I$ implies that $n-7\in I$. Then,
$(x^{T}\beta_{n})_{n-5}=(x^{T}\beta_{n})_{n-3}$, namely $x_{n-7}=2x_{n-5}$.
But then $(x^{T}\beta_{n})_{n-6}\geq
x_{n-5}+x_{n-7}=3x_{n-5}>(x^{T}\beta_{n})_{n}$, in contradiction to $n\in J$.

Now suppose that $J=[n]$. We show that $I=[n]$. $n-4,...,n\in I$, so
$x_{n-4},...,x_{n}>0$ and $n-4,...,n\in J$, so
$(x^{T}\beta_{n})_{n-4}=...=(x^{T}\beta_{n})_{n}$. For every $k$ express each
$x_{n-k}$ as a tuple $(a^{\prime}_{k},b^{\prime}_{k})$ of $x_{n-1},x_{n-4}$,
so that $x_{n-k}=a^{\prime}_{k}x_{n-1}+b^{\prime}_{k}x_{n-4}$. Write
$(a^{\prime}_{k},b^{\prime}_{k})=0$ to mean that
$a^{\prime}_{k}x_{n-1}+b^{\prime}_{k}x_{n-4}=0$. We have

$\displaystyle(x^{T}\beta_{n})_{n}=x_{n-1}+x_{n-2}=x_{n-2}+x_{n-3}=(x^{T}\beta_{n})_{n-1}\Rightarrow
x_{n-1}=x_{n-3}$

Also,

$\displaystyle(x^{T}\beta_{n})_{n}=x_{n-1}+x_{n-2}=x_{n-1}+x_{n-3}+x_{n-4}=(x^{T}\beta_{n})_{n-2}\Rightarrow
x_{n-2}=x_{n-1}+x_{n-4}$

So we get the matching $x_{n-1},...,x_{n-4}=(1,0),(1,1),(1,0),(0,1)$ so
$(a^{\prime}_{k},b^{\prime}_{k})=(a_{k},b_{k})$ for $k\leq 4$. For every
$5\leq k\leq n-1$, because $J=[n]$ we get

$\displaystyle(x^{T}\beta_{n})_{n-k+2}=x_{n-k}+x_{n-k+1}+x_{n-k+3}=x_{n-k+1}+x_{n-k+2}+x_{n-k+4}=(x^{T}\beta_{n})_{n-k+3}$
$\displaystyle\Rightarrow x_{n-k}=x_{n-k+2}-x_{n-k+3}+x_{n-k+4}$

So
$(a^{\prime}_{k},b^{\prime}_{k})=(a^{\prime}_{k-2}-a^{\prime}_{k-3}+a^{\prime}_{k-4},b^{\prime}_{k-2}-b^{\prime}_{k-3}+b^{\prime}_{k-4})$.
Therefore $(a^{\prime}_{k},b^{\prime}_{k})=(a_{k},b_{k})$ for every
$k\in[n-1]$. Then, comparing columns $2,3$ of $\beta_{n}$, we get

$\displaystyle(x^{T}\beta_{n})_{2}=x_{1}+x_{3}=x_{1}+x_{2}+x_{4}=(x^{T}\beta_{n})_{3}$
$\displaystyle\Rightarrow 0=x_{2}-x_{3}+x_{4}$

Or in terms of $a_{k},b_{k}$, we have
$(a_{n-2}-a_{n-3}+a_{n-4},b_{n-2}-b_{n-3}+b_{n-4})\stackrel{{\scriptstyle\text{def}}}{{=}}(a_{n},b_{n})=0$.
Therefore, because $a_{n},b_{n}\neq 0$,
$\frac{x_{n-1}}{x_{n-4}}=\frac{-b_{n}}{a_{n}}$.

Assume for contradiction that $I\neq[n]$. Let $l$ be the minimal $l$ such that
$n-l\notin I$. Let $k<l$. Then

$\displaystyle(x^{T}\beta_{n})_{n-l+2}=x_{n-l}+x_{n-l+1}+x_{n-l+3}=x_{n-l+1}+x_{n-l+2}+x_{n-l+4}=(x^{T}\beta_{n})_{n-l+3}$
$\displaystyle\Rightarrow 0=x_{n-l}=x_{n-l+2}-x_{n-l+3}+x_{n-l+4}$

Using the vector expressions for the above and the recursion equations, we get
$a_{l}x_{n-1}+b_{l}x_{n-4}=0$ so
$\frac{x_{n-1}}{x_{n-4}}=-\frac{b_{l}}{a_{l}}$.

In total, $\frac{b_{n}}{a_{n}}=\frac{b_{l}}{a_{l}}$, in contradiction to Lemma
5.11.

Now suppose for contradiction that $J\subset[n]$ and let $n-l=\min[n]\setminus
J$. If $n-l\in\operatorname{BR}_{2}(x)$, then the argument above can be
repeated to reach a contradiction to Lemma 5.11, so suppose that
$n-l\notin\operatorname{BR}_{2}(x)$. $I\subseteq J$ therefore $x_{n-l}=0$. If
$x_{n-l-1}=0$, then $(x^{T}\beta_{n})_{n-l+1}<(x^{T}\beta_{n})_{n-l+3}$, so
$n-l+1\notin J$ which is a contradiction. Therefore $n-l-1\in I\subseteq J$.
Now, the same argument as above shows that $l\geq 5$ and that for all $k\leq
l+1$, $x_{n-k}=(a_{k},b_{k})$. We have the inequality
$(x^{T}\beta_{n})_{n-l}<(x^{T}\beta_{n})_{n-l+1}=(2,1)$. Hence

$\displaystyle(a_{l+1}+a_{l-1})x_{n-1}+(b_{l+1}+b_{l-1})x_{n-4}+x_{n-l-2}$
$\displaystyle<2x_{n-1}+x_{n-4},$ $\displaystyle a_{l}x_{n-1}+b_{l}x_{n-4}$
$\displaystyle=0$

We show that $(a_{l+1}+a_{l-1}-2)x_{n-1}+(b_{l+1}+b_{l-1}-1)x_{n-4}\geq 0$ in
a contradiction. Using Lemma 5.8, we get

$\displaystyle(b_{l+1}+b_{l+2}+b_{l-1}+b_{l}-2)x_{n-1}+(b_{l+1}+b_{l-1}-1)x_{n-4}$

The equation above gives us $(b_{l}+b_{l+1})x_{n-1}=-b_{l}x_{n-4}$, so using
that and the definition of $b_{l}$ we get

$\displaystyle=(b_{l-1}+b_{l+2}-2)x_{n-1}+(b_{l+3}-1)x_{n-4}$
$\displaystyle=(b_{l-1}+b_{l+2}-2)x_{n-1}-\frac{b_{l}+b_{l+1}}{b_{l}}(b_{l+3}-1)x_{n-1}\geq
0$ $\displaystyle\iff
b_{l-1}+b_{l+2}-2-\frac{b_{l}+b_{l+1}}{b_{l}}(b_{l+3}-1)=b_{l-1}+b_{l+2}-1-b_{l+3}-\frac{b_{l+1}}{b_{l}}(b_{l+3}-1)\geq
0$

Expanding $b_{l+3}$ back yields

$\displaystyle
b_{l-1}+b_{l+2}-1-(b_{l+1}-b_{l}+b_{l-1})-\frac{b_{l+1}}{b_{l}}(b_{l+1}-b_{l}+b_{l-1}-1)$
$\displaystyle=b_{l+2}+b_{l}-\frac{b_{l+1}}{b_{l}}(b_{l+1}+b_{l-1})-1+\frac{b_{l+1}}{b_{l}}\geq
0$ $\displaystyle\iff b_{l+2}+b_{l}-\frac{b_{l+1}}{b_{l}}(b_{l+1}+b_{l-1})\geq
1-\frac{b_{l+1}}{b_{l}}$

Because $l\geq 5$, it is sufficient to show that
$b_{l+2}+b_{l}-\frac{b_{l+1}}{b_{l}}(b_{l+1}+b_{l-1})\geq 3$ for all $l\geq
5$. We deduce this from the following claim.

######  Claim 5.16.

$\lim_{l\to\infty}b_{l}-\frac{b_{l+1}b_{l-1}}{b_{l}}=-\frac{(\rho-1)^{2}}{3\rho}\approx
1.38263$.

###### Proof.

$b_{l}-\frac{b_{l+1}b_{l-1}}{b_{l}}=\frac{b_{l}^{2}-b_{l+1}b_{l-1}}{b_{l}}$.
Let $t_{l}=2\Re(w_{2}z^{l})$, so that $b_{l}=\frac{1}{3}+w_{1}\rho^{n}+t_{l}$.
Using Equation 43,

$\displaystyle b_{l}^{2}$
$\displaystyle=\frac{1}{9}+w_{1}^{2}\rho^{2l}+t_{l}^{2}+\frac{2w_{1}}{3}\rho^{l}+\frac{2}{3}t_{l}+2w_{1}\rho^{l}t_{l},$
$\displaystyle b_{l+1}b_{l-1}$
$\displaystyle=\frac{1}{9}+w_{1}^{2}\rho^{2l}+t_{l+1}t_{l-1}+\frac{w_{1}}{3}(\rho^{l+1}+\rho^{l-1})+\frac{1}{3}(t_{l+1}+t_{l-1})+w_{1}(\rho^{l+1}t_{l-1}+\rho^{l-1}t_{l+1})$

So

$\displaystyle
b_{l}^{2}-b_{l+1}b_{l-1}=t_{l}^{2}-t_{l+1}t_{l-1}-\frac{w_{1}}{3}\rho^{l-1}(\rho-1)^{2}+\frac{1}{3}(2t_{l}-t_{l+1}-t_{l-1})+w_{1}\rho^{l-1}(2\rho
t_{l}-\rho^{2}t_{l-1}-t_{l+1})$

By what we have shown, $|t_{l}|\leq\frac{2}{3}|z|^{l}$, and $|z|<0.9$.
Therefore $t_{l}\to 0$ as $l\to\infty$. Furthermore,

$\displaystyle|w_{1}\rho^{l-1}(2\rho
t_{l}-\rho^{2}t_{l-1}-t_{l+1})|\leq|w_{1}\rho^{l-1}z^{l-1}|(|\rho|+|z|)^{2}=:u|\rho^{l-1}||z^{l-1}|$

Also
$\frac{u|\rho^{l-1}||z^{l-1}|}{|\rho^{l-1}|}=\frac{u\rho^{l-1}|z^{l-1}|}{\rho^{l-1}}\to
0$ when $l\to\infty$. In total, after omitting the negligible terms from the
numerator and denominator, we get

$\displaystyle\lim_{l\to\infty}\frac{b_{l}^{2}-b_{l+1}b_{l-1}}{b_{l}}=\lim_{l\to\infty}\frac{-\frac{w_{1}}{3}\rho^{l-1}(\rho-1)^{2}}{w_{1}\rho^{l}}=-\frac{(\rho-1)^{2}}{3\rho}$

∎

As a result,

$\displaystyle\lim_{l\to\infty}b_{l+2}-\frac{b_{l+1}^{2}}{b_{l}}=\lim_{l\to\infty}\frac{\frac{w_{1}}{3}\rho^{l}(\rho-1)^{2}}{w_{1}\rho^{l}}=\frac{(\rho-1)^{2}}{3}\approx
2.02635$

It can be now easily verified that
$\left(b_{l}-\frac{b_{l+1}b_{l-1}}{b_{l}}\right)+\left(b_{l+2}-\frac{b_{l+1}^{2}}{b_{l}}\right)\geq
3$ for all $l\geq 5$. Therefore we reach a contradiction, hence $J=[n]$,
concluding the proof. ∎

######  Corollary 5.17.

For every $n\neq 3,6,7$, the game $(I_{n},\beta_{n})$ has a unique NE and it
is fully-mixed.

Note that the proof above also tells us how to construct a fully-mixed NE of
$(I_{n},\beta_{n})$: First, $y=U_{n}$. As for $x$, first write
$x^{\prime}_{n-1}=|b_{n}|,x^{\prime}_{n-4}=|a_{n}|$. Then define
$x^{\prime}_{n-k}=a_{k}|b_{n}|+b_{k}|a_{n}|$ for every
$k\in\left\\{2,3,5,6,7,...,n-1\right\\}$. Then define
$x^{\prime}_{n}=2|b_{n}|+|a_{n}|$. Then define
$x=\frac{x^{\prime}}{\left\langle x,{\bf 1}\right\rangle}$. The uniqueness of
the NE is due to $\det\beta_{n},\det I_{n}\neq 0$.

####  5.2.2 Proof of Lemma 5.14

First, more lemmas. Let $(x,y)$ be the fully-mixed NE of $(I_{n},\beta_{n})$.

######  Lemma 5.18.

$|K(\beta_{n})|\geq\frac{n}{3}|\det\beta_{n}|$.

###### Proof.

Follows from Lemma 4.4. ∎

######  Lemma 5.19.

$\rho\notin\mathbb{Q}$.

###### Proof.

$-\rho$ is the real root of the polynomial $x^{3}+x^{2}+1$. The polynomial
evaluated at $2$ is $13$ which is prime, so by Cohn’s irreducibility criterion
[8] the polynomial is irreducible in $\mathbb{Q}[x]$, so
$\rho\notin\mathbb{Q}$. ∎

######  Lemma 5.20.

For all $n\geq 8$, $|\det\beta_{n}|=2|b_{n}|+|a_{n}|$.

###### Proof.

$|\det\beta_{n}|=\det B_{n-1}=\det B_{n-2}+\det B_{n-4}$. So by induction
(with the cases $n\leq 11$ easy to verify),

$\displaystyle\det B_{n-2}+\det
B_{n-4}=2|b_{n-1}|+|a_{n-1}|+2|b_{n-3}|+|a_{n-3}|$

Using Lemma 5.8, and assuming wlog that $b_{n-1}>0$,

$\displaystyle=2b_{n-1}-(b_{n-1}+b_{n})+2b_{n-3}-(b_{n-3}+b_{n-2})=b_{n-1}-b_{n}+b_{n-3}-b_{n-2}=b_{n+1}-b_{n}$
$\displaystyle=a_{n}-2b_{n}=|a_{n}|+2|b_{n}|$

proving the lemma for all $n\geq 8$. ∎

Let $g_{n}=\gcd(a_{n},b_{n})$. By Lemma 5.8,
$g_{n}=\gcd(b_{n}+b_{n+1},b_{n})=\gcd(b_{n},b_{n+1})$.

######  Lemma 5.21.

$C(x)=\frac{|K(\beta_{n})|}{g_{n}}$.

###### Proof.

Assume wlog that $b_{n}>0$. Write
$x=\left(\frac{p_{1}}{q},...,\frac{p_{n}}{q}\right)$ such that
$p_{1},...,p_{n},q\in\mathbb{N}$ and $\mathrm{lcm}(p_{1},...,p_{n})=q$.
Consider the proof of Lemma 5.13. We showed that
$\frac{x_{n-1}}{x_{n-4}}=-\frac{b_{n}}{a_{n}}$, and that
$x_{n-k}=a_{k}x_{n-1}+b_{k}x_{n-4}$. So by picking $b_{n},-a_{n}$ and dividing
by $g_{n}$ we get

$\displaystyle p_{n-1}=\frac{b_{n}}{g_{n}},~{}p_{n-4}=\frac{-a_{n}}{g_{n}}$

Then, applying the equality $x_{n-k}=a_{k}x_{n-1}+b_{k}x_{n-4}$ to the
numerators of the components of $x$, we have

$\displaystyle p_{n-k}=\frac{a_{k}b_{n}-b_{k}a_{n}}{g_{n}}>0$

and $p_{n}=2p_{n-1}+p_{n-4}$ and $q=\sum p_{i}$. Then,
$1\leq\gcd(p_{1},...,p_{n})\leq\gcd(p_{n-1},p_{n-4})=1$, so by definition
$C(x)=q$. Let $p=(p_{i})_{i\in[n]}$. Also, by definition of $\beta_{n}$ and
that $(x,y)\in\operatorname{NE}$ we get for every $j\in[n]$ that
$(p^{T}\beta_{n})_{j}=(p^{T}\beta_{n})_{n}=2p_{n-1}+p_{n-4}$, which by Lemma
5.20 equals $\frac{|\det\beta_{n}|}{g_{n}}$. So,

$\displaystyle\left(\frac{g_{n}}{|\det\beta_{n}|}p\right)^{T}\beta_{n}=\bf 1$

Therefore, by Cramer’s rule,

$\displaystyle\frac{|K(\beta_{n})|}{|\det\beta_{n}|}=\sum_{i}p_{i}=\frac{qg_{n}}{|\det\beta_{n}|}\Rightarrow
C(x)=q=\frac{|K(\beta_{n})|}{g_{n}}$

∎

######  Lemma 5.22.

There exists a $0<\gamma<\rho$ such that $g_{n}\leq\gamma^{n}$ for all
sufficiently large $n$, except for a subsequence $m_{n}=\omega(n)$.

###### Proof.

For convenience, abuse notation and set $b_{n}$ to be $|b_{n}|$ and set $\rho$
to be $|\rho|$ (so that $b_{n},\rho>0$ for $n\geq 3$). Let
$\rho_{n}=\frac{b_{n+1}}{b_{n}}\in\mathbb{Q}$ and
$g_{n}=\gcd(b_{n},b_{n+1})=\gcd(b_{n},\rho_{n}b_{n})$. Asymptotically,
$b_{n}\approx\rho^{n}$, so consider the computation of
$\gcd(\rho^{n},\rho^{n+1})$ using the Euclidean algorithm. The first
iterations yield

$\displaystyle\gcd(\rho^{n},$ $\displaystyle\rho\cdot\rho^{n})$
$\displaystyle\gcd(\rho^{n},$ $\displaystyle(\rho-1)\rho^{n})$
$\displaystyle\gcd((3-2\rho)\rho^{n},$ $\displaystyle(\rho-1)\rho^{n})$
$\displaystyle\gcd((3-2\rho)\rho^{n},$ $\displaystyle(13\rho-19)\rho^{n})$
$\displaystyle\vdots$

As $\rho\notin\mathbb{Q}$, the algorithm will not terminate. Therefore we get
a pair of degree-1 polynomial sequences: $p_{k}=p_{k}^{1}\rho-
p_{k}^{0},q_{k}=q_{k}^{1}\rho-q_{k}^{0}\in\mathbb{Z}[\rho]$ such that the
$k$th iteration of the Euclidean algorithm yields
$\gcd(\rho^{n},\rho\cdot\rho^{n})=\gcd(p_{k}\rho^{n},q_{k}\rho^{n})$. Define
$p_{1}=1,q_{1}=\rho$. Again, as $\rho\notin\mathbb{Q}$, we get $p_{k}q_{k}>0$
for all $k\geq 1$. In particular,

$\displaystyle\forall
k\in\mathbb{N}~{}~{}~{}0<p_{2k-1}=p_{2k}<q_{2k-1},~{}0<q_{2k}=q_{2k+1}<p_{2k}$

Let $M_{k}$ be $p_{k}$ if $k$ is odd, and $q_{k}$ if even.

######  Claim 5.23.

$0<M_{k}<2^{-\frac{k-1}{2}}$.

###### Proof.

The inequality to 0 is clear. Let $k\geq 3$ be odd. We show that
$p_{k}<\frac{1}{2}p_{k-1}$. We have $p_{k}<p_{k-1}$, and
$p_{k}=p_{k-1}-uq_{k-1}$ for the largest integer $u>0$ such that $p_{k}>0$.
Therefore $p_{k}\leq\frac{1}{2}p_{k-1}$. Also, $\rho\notin\mathbb{Q}$ so
$p_{k}<\frac{1}{2}p_{k-1}$. Therefore,
$M_{k}=p_{k}<\frac{1}{2}p_{k-2}=\frac{1}{2}M_{k-2}<...<2^{-\frac{k-1}{2}}M_{1}=2^{-\frac{k-1}{2}}$.
For an even $k$ we similarly get $q_{k}<\frac{1}{2}q_{k-1}$. Then,
$M_{k}=q_{k}<\frac{1}{2}q_{k-2}M_{k-2}<...<2^{-\frac{k-1}{2}}M_{2}<2^{-\frac{k-1}{2}}$.
∎

Now we consider the evaluations $M_{k}(\rho_{n})$. Lemma 5.11 implies that
$\frac{b_{l+1}}{b_{l}}\neq\frac{b_{m+1}}{b_{m}}$ for every $l,m\geq 7$. Since
the root of $M_{k}$ is rational, there is at most one $l\geq 7$ such that
$M_{k}(\rho_{l})=0$, and for all other $l$s $M_{k}(\rho_{l})>0$. So given $n$,
let $K_{M}(7)=1$ and for $n>7$ let

$\displaystyle K_{M}(n)=\begin{cases}\min\left\\{k\mid
M_{k}(\rho_{n})=0\right\\}&\left\\{k\mid
M_{k}(\rho_{n})=0\right\\}\neq\emptyset\\\
\max_{n^{\prime}<n}K_{M}(n^{\prime})+1&else\end{cases}$

Then by definition, $M_{k}(\rho_{n})>0$ for all $k<K_{M}(n)$. Also, $K_{M}$ is
an injective $\left\\{7,...\right\\}\to\mathbb{N}$ function. We use the
following claim:

######  Claim 5.24.

Except on a subsequence $m_{n}=\omega(n)$, $K_{M}(n)=\Omega(n)$.

###### Proof.

Suppose for contradiction that there is a $c>0$ and a subsequence satisfying
$m_{n}\leq cn$ for all $n$ and $K_{M}(m_{n})\leq f(n)=o(n)$. $c\geq 1$ because
$m_{n}\geq n$. Consider the first $\frac{n}{c}$ terms of $K_{M}$. At least $n$
of them will be of the form $K_{M}(m_{l})$, and they satisfy
$\max_{l}K_{M}(m_{l})\leq f\left(\frac{n}{c}\right)$, so because $K_{M}$ is
injective and positive, this means that there are at most
$f\left(\frac{n}{c}\right)$ terms of the form $K_{M}(m_{l})$ in the first
$\frac{n}{c}$ terms of $K_{M}$. But $f\left(\frac{n}{c}\right)<n$ for
sufficiently large $n$, so we get a contradiction. Therefore
$m_{n}=\omega(n)$. ∎

Let $m_{n}$ be the subsequence from the claim, and suppose $K_{M}(n)\geq cn$
for some $c>0$ and for $n\neq m_{l}$. When running the Euclidean algorithm on
$b_{n},b_{n+1}$ (but not optimally, only so as to get the intermediate gcds
$\gcd(p_{i}b_{n},q_{i}b_{n})$), we get for all sufficiently large $n\neq
m_{l}$ that

$\displaystyle
g_{n}=\gcd(b_{n},\rho_{n}b_{n})=\gcd(p_{K_{M}(n)}b_{n},q_{K_{M}(n)}b_{n})\leq
M_{K_{M}(n)}(\rho_{n})b_{n}<2\cdot 2^{-\frac{cn-1}{2}}$

where the last inequality is due to $M_{K_{M}(n)}$’s continuity, and that
$\rho_{n}\to\rho$. The lemma now follows for $\gamma=\sqrt{2}+0.01$. ∎

We can now finish the proof of Lemma 5.14.

###### Proof of Lemma 5.14.

By Lemma 5.18, Lemma 5.21 and Lemma 5.22, for all sufficiently large $n$,
except for the subsequence $m_{n}$ from Lemma 5.22,

$\displaystyle|K(\beta_{n})|\geq
C(x)=\frac{|K(\beta_{n})|}{\gcd(b_{n},b_{n+1})}\geq\frac{\frac{n}{3}(\sqrt{2}+0.02)^{n}}{(\sqrt{2}+0.01)^{n}}$

So $C(x)=2^{\Theta(n)}$ there. For $y$, observe that $y=U_{n}$, so the claim
follows. ∎

######  Corollary 5.25 (Restatement of Theorem 1.6, Item 1).

There is a function $g(n)=\Theta(n)$ such that for every $n$ there are
$A,B\in\mathbb{Z}_{2}^{n\times n}$ such that $C_{1}(A,B)=2^{g(n)}$ and
$C_{2}(A,B)=n$.

###### Proof.

Follows by taking the games above and padding them with dummy strategies as in
Lemma 4.2. ∎

######  Corollary 5.26.

For every $n\geq 8$, the NE distribution $x$ of player 1 satisfies
$\max_{i,j}\frac{x_{i}}{x_{j}}=O(1)$. Therefore representing the numerators of
$x$ would require $\Theta(n^{2})$ bits.

###### Proof.

Let $p_{1},...,p_{n}$ be the numerators of $x$, chosen so that
$p_{n-1}=|b_{n}|,p_{n-4}=|a_{n}|,p_{n}=2p_{n-1}+p_{n-4}$, and for all $k\neq
0,1,4$, $p_{n-k}=a_{k}p_{n-1}+b_{k}p_{n-4}$. Suppose wlog that $b_{n}>0$. Then
by Lemma 5.8

$\displaystyle
p_{n-k}=a_{k}b_{n}-b_{k}a_{n}=(b_{k}+b_{k+1})b_{n}-b_{k}(b_{n}+b_{n+1})=b_{n}b_{k+1}-b_{n+1}b_{k}$

Consider Equation 43. $t_{k}=2\Re(w_{2}z^{k})$, so that
$b_{k}=\frac{1}{3}+w_{1}\rho^{n}+t_{l}$. Then similarly to the proof of Lemma
5.13, we have

$\displaystyle b_{n}b_{k+1}-b_{n+1}b_{k}$
$\displaystyle=t_{n}t_{k+1}-t_{n+1}t_{k}+\frac{w_{1}}{3}(\rho-1)(\rho^{k}-\rho^{n})+\frac{1}{3}(t_{n}+t_{k+1}-t_{n+1}-t_{k})+$
$\displaystyle~{}~{}~{}~{}w_{1}(\rho^{n}t_{k+1}+\rho^{k+1}t_{n}-\rho^{n+1}t_{k}-\rho^{k}t_{n+1})$
$\displaystyle=\frac{w_{1}}{3}(\rho-1)(\rho^{k}-\rho^{n})+\frac{1}{3}(t_{k+1}-t_{k})+w_{1}(\rho^{n}t_{k+1}+\rho^{k+1}t_{n}-\rho^{n+1}t_{k}-\rho^{k}t_{n+1})+o_{n}(1)$

We further have

$\displaystyle\frac{b_{n}b_{k+1}-b_{n+1}b_{k}}{b_{n}}$
$\displaystyle=\frac{\frac{w_{1}}{3}(\rho-1)(\rho^{k}-\rho^{n})+w_{1}(\rho^{n}t_{k+1}-\rho^{n+1}t_{k})}{b_{n}}+o_{n}(1)$
$\displaystyle=\frac{1}{3}(\rho-1)(\rho^{k-n}-1)+t_{k+1}-\rho t_{k}+o_{n}(1)$

So for every $1<k<n$:

$\displaystyle\frac{x_{n-k}}{x_{1}}$
$\displaystyle=\frac{p_{n-k}}{p_{1}}=\frac{\frac{p_{n-k}}{b_{n}}}{\frac{p_{1}}{b_{n}}}=\frac{\frac{1}{3}(\rho-1)(\rho^{k-n}-1)+t_{k+1}-\rho
t_{k}+o_{n}(1)}{\frac{1}{3}(\rho-1)(\rho^{1-n}-1)+t_{2}-\rho t_{1}+o_{n}(1)}$
$\displaystyle\leq\frac{c(\rho-1)(\rho^{k-n}-1)}{(\rho-1)(\rho^{1-n}-1)+t_{2}-\rho
t_{1}}+o_{n}(1)$ $\displaystyle\leq c\left(1-\frac{t_{2}-\rho
t_{1}}{(\rho-1)(\rho^{1-n}-1)+t_{2}-\rho t_{1}}\right)+o_{n}(1)$
$\displaystyle=O(1)$

For some $c=\Theta(1)$, and this is because $t_{k+1}-\rho
t_{k}=O(|z|^{k})=o_{k}(1)$ and $\frac{1}{3}(\rho-1)(\rho^{k-n}-1)=\Theta(1)$.
For $x_{n}$ we have by definition, for some $c^{\prime}=O(1)$:

$\displaystyle x_{n}=x_{1}+x_{3}\leq
c^{\prime}x_{1}\Rightarrow\frac{x_{n}}{x_{1}}\leq c^{\prime}=O(1)$

Hence $\max_{i,j}\frac{x_{i}}{x_{j}}=O(1)$. Therefore, all the numerators are
at least $\frac{2^{\Theta(n)}}{\Theta(n)}$, so they would require in total
$\Theta(n^{2})$ bits. ∎

###  5.3 Constant-Sum Games

Here we prove Theorem 1.5, Item 2 and Theorem 1.6, Item 2. The lower bounds on
the required capability of player 1 remain the same as in the respective Item
1s, although in these constant-sum games, these minimal required capabilities
are now imposed on both players.

######  Definition 5.27.

For $\pi,\tau\in\text{Sym}_{n}$, call a matrix $B$ $(\pi,\tau)$-symmetric if
for all $i\in[n]$, $(B^{T})_{i}=\pi(B_{\tau(i)})$.

######  Lemma 5.28.

Let $y$ and let $x=\pi(y)$. Then $B^{T}x=\tau(By)$.

###### Proof.

Let $i\in[n]$.

$\displaystyle(B^{T}x)_{i}=\sum_{j}B_{j,i}y_{\pi(j)}=\sum_{j}B_{\tau(i),\pi(j)}y_{\pi(j)}=(By)_{\tau(j)}$

so $B^{T}x=\tau(By)$. ∎

A property of zero-sum games mentioned in Avis et al. [5] will also be used.
We state it here in terms of constant-sum games and prove it.

######  Lemma 5.29.

Let $(A,B)$ be a constant-sum game with $A+B={\bf 1}_{n\times n}$, and let
$\pi_{i}(\operatorname{NE}(A,B))$ be the equilibrium strategies of player $i$.
Then
$\operatorname{NE}(A,B)=\pi_{1}(\operatorname{NE}(A,B))\times\pi_{2}(\operatorname{NE}(A,B))$.

###### Proof.

By the minimax theorem, $(x,y)\in\operatorname{NE}$ iff
$x\in\operatorname*{arg\,max}_{s}\min_{t}s^{T}At$ and
$y\in\operatorname*{arg\,max}_{t}\min_{s}s^{T}Bt$. The lemma now follows. ∎

######  Lemma 5.30.

Let $B\in\mathbb{Z}_{2}^{n\times n}$ such that

  1. 1.

it is $(\pi,\tau)$-symmetric,

  2. 2.

the game $(I_{n},B)$ has a unique NE $(\tilde{x},U_{n})$ which is fully-mixed,

  3. 3.

$\det B\neq 0$ and $K(B)\neq\det B$.

Then $({\bf 1}_{n\times n}-B,B)$ has a unique NE which is
$(\tilde{x},\pi^{-1}(\tilde{x}))$.

###### Proof.

First, we show that $(\tilde{x},\pi^{-1}(\tilde{x}))$ is a NE. We have
$B^{T}\tilde{x}={\bf 1}_{n}v$ for some $v>0$. Since $(\tilde{x},U_{n})$ is
fully-mixed and $\det B\neq 0$, we get that $B$ contains no all-1 columns.
Therefore, $v=(B^{T}\tilde{x})_{i}<\left\langle{\bf
1},\tilde{x}\right\rangle=1$. For $\pi^{-1}(\tilde{x})$, we have

$\displaystyle({\bf 1}_{n\times n}-B)\pi^{-1}(\tilde{x})={\bf 1}_{n\times
n}\pi^{-1}(\tilde{x})-B\pi^{-1}(\tilde{x})={\bf
1}_{n}-\tau^{-1}(B^{T}\tilde{x})=(1-v){\bf 1}_{n}$

(by Lemma 5.28). Therefore by the best-response condition [29], it is a NE of
the constant-sum game. To see that it is unique, by the matrix determinant
lemma and the given,

$\displaystyle\det({\bf 1}_{n\times n}-B)=\left(1-{\bf 1}^{T}B^{-1}{\bf
1}\right)\det(-B)=(-1)^{n}\left(1-\frac{K(B)}{\det B}\right)\det B\neq 0$

Now let $(x,y)\in\operatorname{NE}({\bf 1}_{n\times n}-B,B)$ with supports
$I,J$. By Lemma 5.29, $(x,\pi^{-1}(\tilde{x}))\in\operatorname{NE}$. $x$
satisfies

$\displaystyle B^{T}x=v^{\prime}{\bf 1}_{n},~{}~{}~{}\left\langle x,{\bf
1}_{n}\right\rangle=1$

Since $B^{T}$ is invertible, $x=(B^{T})^{-1}v^{\prime}{\bf 1}_{n}$, and
$v^{\prime}$ is such that $\left\langle x,{\bf 1}_{n}\right\rangle=1$. By
invertibility and uniqueness, we get $x=\tilde{x}$. Similarly, we get
$y=\pi^{-1}(\tilde{x})$. Hence $(\tilde{x},\pi^{-1}(\tilde{x}))$ is the unique
NE of the constant-sum game. ∎

We note that in any imitation game $(I_{n},B)$, every NE $(x,y)$ has the
property that $y=U_{\operatorname{supp}y}$. With this lemma we can establish
Item 2 of Theorems 1.5 and 1.6. We begin with Item 2 of Theorem 1.5.

######  Theorem 5.31 (Restatement of Theorem 1.5, Item 2).

There is a function $f(n)=\tilde{\Theta}(\sqrt{n})$ such that for every $n$
there are $A,B\in\mathbb{Z}_{2}^{n\times n}$ such that $A+B={\bf 1}_{n\times
n}$ and $C_{1}(A,B)=C_{2}(A,B)=2^{f(n)}$.

###### Proof.

Let $p_{1},...,p_{n}$ be the first $n$ primes, and let $N,B$ be the integer
and the matrix from the proof of Theorem 5.3. $\sum_{j}B_{i,j}\leq
p_{n}=\tilde{\Theta}(\sqrt{N})$. Therefore, by Lemma 4.4,
$|K(B)|\geq\tilde{\Theta}(\sqrt{N})|\det B|$. Also, $\det
B=(-1)^{N-1}\prod_{k}p_{k}\neq 0$ as was shown in Theorem 5.3. Again, by
Theorem 5.3, $(I_{N},B)$ has a unique NE and it is fully-mixed. Also, by the
construction of $B$, it is $(\pi,\pi)$-symmetric for the cycle
$\pi=(n~{}n-1~{}...~{}1)$. Now we can use Lemma 5.30 to conclude that $({\bf
1}_{N\times N}-B,B)$ has a unique NE $(\tilde{x},\pi^{-1}(\tilde{x})$ and it
is fully-mixed. Furthermore, by Theorem 5.3, there holds

$\displaystyle C_{1}({\bf 1}_{N\times N}-B,B)=C_{2}({\bf 1}_{N\times
N}-B,B)=C(\tilde{x})=C(\pi^{-1}(\tilde{x}))=\left(\prod_{k}p_{k}\right)\left(n+1+\sum_{k=1}^{n}\frac{1}{p_{k}}\right)=2^{\tilde{\Theta}(\sqrt{N})}$

Then, a similar argument to Corollary 5.4 establishes this lower bound for all
positive integers. ∎

######  Theorem 5.32 (Restatement of Theorem 1.6, Item 2).

There is a function $g(n)=\Theta(n)$ such that for every $n$ there are
$A,B\in\mathbb{Z}_{2}^{n\times n}$ such that $A+B={\bf 1}_{n\times n}$ and
$C_{1}(A,B)=C_{2}(A,B)=2^{g(n)}$.

###### Proof.

Let $n\geq 8$ and let $\beta_{n}$. It is $(\pi,\pi)$-symmetric for
$\pi(i)=n-i+1$. By Lemma 5.13, $(I_{n},\beta_{n})$ has a unique NE and it is
fully-mixed. Also, by Lemma 5.12 and Lemma 5.18, $\det\beta_{n}\neq 0$ and
$|K(\beta_{n})|\geq\frac{n}{3}|\det\beta_{n}|$. Therefore, by Lemma 5.30,
$({\bf 1}_{n\times n}-\beta_{n},\beta_{n})$ has a unique NE
$(\tilde{x},\pi^{-1}(\tilde{x}))$ and it is fully-mixed. Furthermore, by Lemma
5.14, there holds

$\displaystyle C_{1}({\bf 1}_{n\times n}-\beta_{n},\beta_{n})=C_{2}({\bf
1}_{n\times
n}-\beta_{n},\beta_{n})=C(\tilde{x})=C(\pi^{-1}(\tilde{x}))=2^{\Theta(n)}$

Then, a similar argument to Corollary 5.25 establishes this lower bound for
all $n$. ∎

## References

  * Alon and Vũ [1997] Noga Alon and Văn H Vũ.  Anti-hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs.  _Journal of Combinatorial Theory, Series A_ , 79(1):133–160, 1997.
  * Anbalagan et al. [2015] Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin, Adrian Vetta, and Hehui Wu.  Large supports are required for well-supported Nash equilibria.  _arXiv preprint arXiv:1504.03602_ , 2015.
  * Apostol [1998] Tom M Apostol.  _Introduction to analytic number theory_.  Springer Science & Business Media, 1998.
  * Arthaud [2023] Farid Arthaud.  Playing repeated games with sublinear randomness.  _arXiv preprint arXiv:2312.13453_ , 2023.
  * Avis et al. [2010] David Avis, Gabriel D Rosenberg, Rahul Savani, and Bernhard Von Stengel.  Enumeration of Nash equilibria for two-player games.  _Economic theory_ , 42:9–37, 2010.
  * Bárány et al. [2007] Imre Bárány, Santosh Vempala, and Adrian Vetta.  Nash equilibria in random games.  _Random Structures & Algorithms_, 31(4):391–405, 2007.
  * Bonifaci et al. [2008] Vincenzo Bonifaci, Ugo Di Iorio, and Luigi Laura.  The complexity of uniform Nash equilibria and related regular subgraph problems.  _Theoretical Computer Science_ , 401(1-3):144–152, 2008.
  * Brillhart et al. [1981] John Brillhart, Michael Filaseta, and Andrew Odlyzko.  On an irreducibility theorem of a. cohn.  _Canadian Journal of Mathematics_ , 33(5):1055–1059, 1981.
  * Bringmann and Larsen [2013] Karl Bringmann and Kasper Green Larsen.  Succinct sampling from discrete distributions.  In _Proceedings of the forty-fifth annual ACM symposium on Theory of Computing_ , pages 775–782, 2013.
  * Bringmann and Panagiotou [2017] Karl Bringmann and Konstantinos Panagiotou.  Efficient sampling methods for discrete distributions.  _Algorithmica_ , 79:484–508, 2017.
  * Budinich and Fortnow [2011] Michele Budinich and Lance Fortnow.  Repeated matching pennies with limited randomness.  In _Proceedings of the 12th ACM conference on Electronic commerce_ , pages 111–118, 2011.
  * Cramer [1750] Gabriel Cramer.  _Introduction à l’analyse des lignes courbes algébriques_.  chez les frères Cramer et C. Philibert, 1750.
  * Daskalakis et al. [2009] Constantinos Daskalakis, Aranyak Mehta, and Christos Papadimitriou.  A note on approximate Nash equilibria.  _Theoretical Computer Science_ , 410(17):1581–1588, 2009.
  * Devroye [1986] Luc Devroye.  _Non-Uniform Random Variate Generation_.  Springer-Verlag, New York, NY, USA, 1986.
  * Feder et al. [2007] Tomas Feder, Hamid Nazerzadeh, and Amin Saberi.  Approximating Nash equilibria using small-support strategies.  In _Proceedings of the 8th ACM Conference on Electronic Commerce_ , pages 352–354, 2007.
  * Gale et al. [1950] David Gale, Harold W Kuhn, and Albert W Tucker.  On symmetric games.  _Contributions to the Theory of Games_ , 1:81–87, 1950\.
  * Goldberg et al. [1968] K Goldberg, AJ Goldman, and M Newman.  The probability of an equilibrium point.  _Journal of Research of the National Bureau of Standards_ , 72(2):93–101, 1968.
  * Hadamard [1893] Jacques Hadamard.  Résolution d’une question relative aux déterminants.  _Bull. des sciences math._ , 2:240–246, 1893.
  * Halpern and Pass [2015] Joseph Y Halpern and Rafael Pass.  Algorithmic rationality: Game theory with costly computation.  _Journal of Economic Theory_ , 156:246–268, 2015.
  * Hubáček et al. [2016] Pavel Hubáček, Moni Naor, and Jonathan Ullman.  When can limited randomness be used in repeated games?  _Theory of Computing Systems_ , 59(4):722–746, 2016.
  * Kakutani [1941] Shizuo Kakutani.  A generalization of Brouwer’s fixed point theorem.  _Duke Mathematical Journal_ , 8(3):457 – 459, 1941.  doi: 10.1215/S0012-7094-41-00838-4.  URL https://doi.org/10.1215/S0012-7094-41-00838-4.
  * Kalyanaraman and Umans [2007] Shankar Kalyanaraman and Christopher Umans.  Algorithms for playing games with limited randomness.  In _European Symposium on Algorithms_ , pages 323–334. Springer, 2007\.
  * Knuth [1976] Donald Knuth.  The complexity of nonuniform random number generation.  _Algorithm and Complexity, New Directions and Results_ , 1976.
  * Lipton et al. [2003] Richard J Lipton, Evangelos Markakis, and Aranyak Mehta.  Playing large games using simple strategies.  In _Proceedings of the 4th ACM Conference on Electronic Commerce_ , pages 36–41, 2003.
  * McLennan and Tourky [2005] Andrew McLennan and Rabee Tourky.  From imitation games to Kakutani.  _Manuscript, available at http://www. econ. umn. edu/mclennan/Papers/papers. html_ , 37:41, 2005.
  * McLennan and Tourky [2010] Andrew McLennan and Rabee Tourky.  Simple complexity from imitation games.  _Games and Economic Behavior_ , 68(2):683–688, 2010.
  * Nash [1951] John Nash.  Non-cooperative games.  _Annals of mathematics_ , pages 286–295, 1951.
  * Neyman and Okada [2000] Abraham Neyman and Daijiro Okada.  Repeated games with bounded entropy.  _Games and Economic Behavior_ , 30(2):228–247, 2000.
  * Roughgarden [2010] Tim Roughgarden.  Algorithmic game theory.  _Communications of the ACM_ , 53(7):78–86, 2010\.
  * Saad et al. [2020] Feras Saad, Cameron Freer, Martin Rinard, and Vikash Mansinghka.  The fast loaded dice roller: A near-optimal exact sampler for discrete probability distributions.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1036–1046. PMLR, 2020.
  * Smith [2002] Warren D Smith.  How to sample from a probability distribution.  Technical report, Technical Report DocNumber17. NEC Research, 2002.
  * Valizadeh and Gohari [2019a] Mehrdad Valizadeh and Amin Gohari.  Playing games with bounded entropy.  _Games and Economic Behavior_ , 115:363–380, 2019a.
  * Valizadeh and Gohari [2019b] Mehrdad Valizadeh and Amin Gohari.  Playing games with bounded entropy: Convergence rate and approximate equilibria.  _arXiv preprint arXiv:1902.03676_ , 2019b.
  * von zur Gathen and Sieveking [1978] Joachim von zur Gathen and Malte Sieveking.  A bound on solutions of linear integer equalities and inequalities.  _Proceedings of the American Mathematical Society_ , 72(1):155–158, 1978.
  * Vose [1991] Michael D Vose.  A linear algorithm for generating random numbers with a given distribution.  _IEEE Transactions on software engineering_ , 17(9):972–975, 1991.
  * Walker [1977] Alastair J Walker.  An efficient method for generating discrete random variables with general distributions.  _ACM Transactions on Mathematical Software (TOMS)_ , 3(3):253–256, 1977.

##  Appendix A Special Cases

###  A.1 $2\times 2$ Games

Let $A,B\in\mathbb{Z}^{2\times 2}$. If $\operatorname{PNE}(A,B)\neq\emptyset$,
then $C_{i}(A,B)=1$. Suppose that $\operatorname{PNE}(A,B)\neq\emptyset$.

Wlog $A_{11}>A_{21}$. This implies that $A_{12}<A_{22}$, and $B_{11}<B_{12}$
and $B_{21}>B_{22}$. By definition, the only equilibria of the game are given
by $p,q\in(0,1)$ that satisfy

$\displaystyle qA_{11}+(1-q)A_{12}=qA_{21}+(1-q)A_{22},$ $\displaystyle
pB_{11}+(1-p)B_{21}=pB_{12}+(1-p)B_{22}$

Solving this yields

$\displaystyle
p=\frac{B_{21}-B_{22}}{B_{12}-B_{11}+B_{21}-B_{22}},~{}q=\frac{A_{22}-A_{12}}{A_{11}-A_{21}+A_{22}-A_{12}}$

after reducing these 2 fractions, using the equality $\gcd(a,a+b)=\gcd(a,b)$,
we get

######  Theorem A.1.

If $\operatorname{PNE}(A,B)=\emptyset$, then

$\displaystyle
C_{1}(A,B)=\frac{B_{12}-B_{11}+B_{21}-B_{22}}{\gcd(B_{12}-B_{11},B_{21}-B_{22})},~{}C_{2}(A,B)=\frac{A_{11}-A_{21}+A_{22}-A_{12}}{\gcd(A_{11}-A_{21},A_{22}-A_{12})}$

###  A.2 Permutation Games

Let $\text{Sym}_{n}$ be the symmetric group of size $n$. Given
$\pi\in\text{Sym}_{n}$, let $P_{\pi}$ be its permutation matrix, so that
$P_{\pi}e_{i}=e_{\pi(i)}$. Then $P_{\pi}^{T}=P_{\pi}$. Write
$\pi=\pi_{1}\cdots\pi_{a}$ and $\tau=\tau_{1}\cdots\tau_{b}$ the permutations
in cycle form. Also write
$\pi^{-1}\tau=(\pi^{-1}\tau)_{1}\cdots(\pi^{-1}\tau)_{d}$. Let
$|(\pi^{-1}\tau)_{k}|$ be the length of the $k$th cycle, and let $J_{k}$ be
the set of indices in that cycle (e.g. $\left\\{1,3,4\right\\}$ for the first
cycle of $(143)(25)$). Let $\pi,\tau\in\text{Sym}_{n}$, and let
$A=P_{\pi},B=P_{\tau}\in\mathbb{Z}_{2}^{n\times n}$. Consider the game
$(A,B)$. We prove the following:

######  Theorem A.2.

$\operatorname{NE}(P_{\pi},P_{\tau})=\left\\{(U_{\pi(J)},U_{J})\mid
D\subseteq[d],~{}J=\bigcup_{k\in D}U_{J_{k}}\right\\}$, and therefore

$C_{1}(A,B)=C_{2}(A,B)=\min_{k\leq d}|(\pi^{-1}\tau)|_{k}$

###### Proof.

Take $(x,y)\in\operatorname{NE}(P_{\pi},P_{\tau})$ with supports $I,J$. Then
$P_{\tau}^{T}x=u{\bf 1}_{J}+s^{1},P_{\pi}y=v{\bf 1}_{I}+s^{2}$ for some
$u,v>0$, where $0\leq s^{1}\leq{\bf 1}_{[n]\setminus J}\cdot u$ and $0\leq
s^{2}\leq{\bf 1}_{[n]\setminus I}\cdot v$. Looking more closely,

$\displaystyle P_{\tau}^{T}x=P_{\tau^{-1}}x=\sum_{i\in
I}x_{i}e_{\tau^{-1}(i)}=u{\bf 1}_{J}+s^{1}$

So because $u>0$ we get $J\subseteq\tau^{-1}(I)$. Similarly,
$I\subseteq\pi(J)$. So $\tau(J)\subseteq I\subseteq\pi(J)$, and these are all
equalities because $\pi,\tau$ are permutations. In particular
$s^{1}=s^{2}={\bf 0}$, so $x=U_{I},y=U_{J}$. Also, $J=\pi^{-1}\tau(J)$, so $J$
is a union of cycles of $\pi^{-1}\tau$, so $J=\bigcup_{k\in D}U_{J_{k}}$ for
some $D\subseteq[d]$. Then, $I=\pi(J)$. On the other hand, given any such $J$
and $I=\pi(J)$, the calculations above verify that
$(U_{\pi(J)},U_{J})\in\operatorname{NE}(P_{\pi},P_{\tau})$. ∎

As a corollary, we also obtain
$\operatorname{NE}(P_{\pi},P_{\tau})=\operatorname{NE}(I_{n},P_{\pi^{-1}\tau})$.