1 Introduction↩︎

In orzech2025nash?, we presented for every \(n\ge4\) an \(n\)-player \(2\)-action game \(G_n\) with payoffs in \(\ios*{0,1,2}\) and a unique Nash equilibrium (NE) \(x^n=(x^n_1,\ldots,x^n_n)\) (\(x^n_i\in[0,1]\) is the probability that player \(i\) plays the first action) where every \(x^n_i\) is irradical, meaning it is algebraic but not closed form expressible by radicals over \(\mathbb{Q}\). There, \([\mathbb{Q}(x^n_i):\mathbb{Q}]\in\ios*{6,26}\) and the Galois group (of the Galois closure of \(\mathbb{Q}(x^n_i)/\mathbb{Q}\)) is (isomorphic to) \(S_6\) or \(S_{26}\).

In this note we present a proof of a stronger result. The proof was developed using AI (see Section 2). Let \({\mathbin{!n}}\) be the derangement number: the number of permutations \(n\to n\) without fixed points. It is known that \({\mathbin{!n}}=\iob*{\frac{n!}{e}}\). We prove the following:

We defer the question of upper bounds to a later version of this note. \(y^n_i\) is irradical for all \(n\ge4\) and \(i\in[n]\) because \(S_{\mathbin{!n}}\) is an unsolvable group for all \(n\ge4\).

As discussed in orzech2025nash?, there are computational implications of this result. To play the NE \(y^n\), each player \(i\) must be able to sample an action from the underlying probability distribution \((y^n_i,1-y^n_i)\). Since \(y^n_i\) is irrational, performing exact sampling from \((y^n_i,1-y^n_i)\) appears to require generating a power series representation of \(y^n_i\) flajolet2011buffon?, mendo2020simulating?. One way to generate the series requires storing and evaluating a polynomial \(f\) that satisfies \(f(y^n_i)=0\). Since \([\mathbb{Q}(y^n_i):\mathbb{Q}]={\mathbin{!n}}\), \(f\) would have \(\deg f\ge{\mathbin{!n}}\) and typically take up \(\Omega({\mathbin{!n}})\) space. Since \(y^n_i\) is irradical, storing and evaluating such an \(f\) appears to be necessary for player \(i\) to play the only NE mixed strategy in the game \(g^*_n\). Irradicality precludes the existence of a closed form representation in radicals for \(y^n_i\), a representation that in general may be more compact compared to the minimal polynomial size (for example \(a=\frac{1}{2}\sqrt{\frac{1}{2}+\sqrt{\frac{1}{2}+\sqrt{\frac{1}{2}}}}\) has the minimal polynomial \(m_a=4096x^8-2048x^6+128x^4+32x^2-7\)) dixon1968solvable?.

Item \(3\) of Proposition 1 implies that the minimal polynomial of each \(y^n_i\) requires \(\Omega({\mathbin{!n}})\) space to store (without instance-specific optimizations), making the task of playing the only NE of \(g^*_n\) computationally intensive for all players.² Without item \(3\), the minimal polynomial may be very easy to store and evaluate: Selmer’s polynomial of degree \({\mathbin{!n}}\), \(t^{\mathbin{!n}}-t-1\), is irreducible and has Galois group \(S_{\mathbin{!n}}\) yet is sparse selmer1956?, osada1987galois?.

2 Use of AI↩︎

We used ChatGPT 5.5 Pro to find this proof as follows. We gave the AI a prompt containing the statement in Proposition 1 and asking it to prove the statement. It output a solution as a proof sketch, containing most of the technical tools and details required for the full proof. Afterward, we used further prompting to get more details about the solution. We verified its correctness and wrote up the full proof presented in this note. Below is a prompt that generated the solution.

prove:

for every n>=4 there is an n-player 2-action game with integer payoffs and a unique NE y=(y_1,...,y_n) (y_i=Pr(i plays first action)) such that:
1. [Q(y_i):Q]=!n the derangement number
2. the galois group of y_i is S_!n
3. the minimal polynomial P_i of y_i has all its !n+1 coefficients nonzero

The generated solution output to the prompt is in Appendix 4 (lightly formatted with links removed). The proof we present is our formalized write-up based on that solution.

3 Definitions↩︎

We refer to roughgarden2010algorithmic?, orzech2025nash? for the full details regarding background on normal form games and NEs and artin2011algebra?, cox1997ideals?, cox1998using? for a full algebra background. An \(n\)-player \(2\)-action game \(G\) is defined by \(n\) payoff functions, \(u_1,\ldots,u_n:\ios*{0,1}^n\to\mathbb{R}\) which are extended to \([0,1]^n\) as \(u_i(x)=\mathbb{E}_{a\sim x}(u_i(a))\). \(G\) has integer payoffs if \(u_i(x_1,\ldots,x_n)\in\mathbb{Z}\) for every \(i\) and \(x_1,\ldots,x_n\in\ios*{0,1}\). A NE is defined in the usual way. Given \(G\) we have \(n\) multi-affine polynomials defined as \(f_i(x_{-i})=u_i(x_{-i},x_i=1)-u_i(x_{-i},x_i=0)\). \(f_i(x_{-i})\) or in short \(f_i(x)\) is the payoff advantage the first action has over the second action for player \(i\) given that the other players play \(x_{-i}\). We have the following useful lemma:

Here, we are interested in fully mixed NEs, in which \(x_i\in(0,1)\) for all \(i\). The set of fully mixed NEs of \(G\) is exactly \(\ios*{x\in(0,1)^n\mid\forall i\in[n]~~f_i(x)=0}\).

3.0.0.1 Games as equation systems:

Define the generic system \(\mathop{\mathrm{\mathcal{S}}}(c,x)\) as follows: there is a coefficient vector \(c=(c_{i,s})_{i\in[n],~s\subseteq[n]\setminus\ios*{i}}\) which is either generic (a vector of symbols) or in \(\mathbb{R}^N\) where \(N=n2^{n-1}\), a variable vector \(x=(x_1,\ldots,x_n)\) that will take values in \(\mathbb{C}^n\) and polynomials \(f_1,\ldots,f_n\in\mathbb{Q}(c)[x]\) of the form \[\begin{align} f_i(c,x)=\sum_{s\subseteq[n]\setminus\ios*{i}}c_{i,s}\prod_{j\in s}x_j. \end{align}\] When \(c\) is generic, we may still set some \(c_{i,s}\) to \(0\). We write \(f_i^c\mathrel{\vcenter{:}}= f_i(c,\cdot)\). Given \(c\), each polynomial \(f_i^c\) has monomial exponents with support \(S_i=\ios*{s\mid c_{i,s}\ne0}\subseteq\ios*{0,1}^{i-1}\times\ios*{0}\times\ios*{0,1}^{n-i}\). The monomial exponent supports \(S_i\) of the generic \(\mathop{\mathrm{\mathcal{S}}}(c,x)\) are \(S_i=\ios*{0,1}^{i-1}\times\ios*{0}\times\ios*{0,1}^{n-i}\) for all \(i\).

Every \(c\) (either generic or real) defines a game \(\mathop{\mathrm{\mathcal{G}}}(c)\) uniquely up to affine transformations, which do not affect the game’s best responses or NEs. In particular if \(c\in\mathbb{Q}^N\) then the payoffs in \(\mathop{\mathrm{\mathcal{G}}}(c)\) can be scaled to be integers. Therefore we sometimes identify games as vectors in \(\mathbb{R}^N\). Furthermore, the set of fully mixed NEs of \(G(c)\) is \(\ios*{x\in(0,1)^n\mid\mathop{\mathrm{\mathcal{S}}}(c,x)=0}\).

3.1 Proof of Proposition 1↩︎

The proof consists of \(4\) steps. In the first, we show that the generic \(\mathop{\mathrm{\mathcal{S}}}\) has \({\mathbin{!n}}\) solutions in \(x\in(\mathbb{C}\setminus\ios*{0})^n\), and the field extension of \(\mathbb{Q}(c)\) by all the coordinates of these \({\mathbin{!n}}\) roots has Galois group \(S_{\mathbin{!n}}\).

Let \(r=\ios*{r^1,\ldots,r^{\mathbin{!n}}}\) be the set of solutions to \(\mathop{\mathrm{\mathcal{S}}}\) where \(r^k=(r^k_1,\ldots,r^k_n)\). We also denote them sometimes by \(r(c)\).

In the second step, we create a simple game \(\mathop{\mathrm{\mathcal{G}}}(c_0)\) with a unique NE \(\iop*{\frac{1}{2},\ldots,\frac{1}{2}}\). Then we find an open neighborhood \(c_0\in U\subseteq\mathbb{R}^N\) such that every \(\mathop{\mathrm{\mathcal{G}}}(c)\) with \(c\in U\) also has a unique NE.

Let \(P_i(t)=\prod_{k=1}^{\mathbin{!n}}(t-r^k_i)\). Then there are polynomials \(b_{k,i}(r^1_i,\ldots,r^{\mathbin{!n}}_i)=b_{k,i}(r(c))\) such that \(P_i=\sum_{k=0}^{\mathbin{!n}}b_{k,i}t^k\). In the third step we show that \(P_i\):

1. is a degree-\({\mathbin{!n}}\) polynomial in \(\mathbb{Q}(c)[t]\) with \(b_{k,i}\ne0\) for all \(k\) (as functions of \(c\)),

2. is the minimal polynomial of \(r^k_i\) for all \(k\),

3. has Galois group \(S_{\mathbin{!n}}\).

Let \(\lambda\in\mathbb{Q}^n\) and consider \(\mathop{\mathrm{\mathcal{S}}}(c,x+\lambda)\). Then there is an invertible function \(\psi_\lambda\) such that \(\mathop{\mathrm{\mathcal{S}}}(c,x+\lambda)=\mathop{\mathrm{\mathcal{S}}}(\psi_\lambda(c),x)\). In particular every \(f^{\psi_\lambda(c)}_i\) is still multi-affine and does not depend on \(x_i\), meaning \(\mathop{\mathrm{\mathcal{G}}}(\psi_\lambda(c))\) is a valid game.

Now we can prove the second and third items.

In the last step we finish the proof by specializing the generic \(c\) in a way that preserves all the properties we proved in the previous steps:

This concludes the proof of Proposition 1.

4 Generated Solution Output↩︎

Let \(D={!n}\), the number of derangements of \(\{1,\dots,n\}\). I will prove existence.

I will use two standard algebraic facts. First, the Bernstein–Kouchnirenko theorem: a generic sparse square system has as many torus roots as the lattice mixed volume of its Newton polytopes. Second, Esterov’s theorem: a reduced irreducible sparse square system has full symmetric monodromy/Galois group. Esterov’s paper states both the Kouchnirenko–Bernstein root count setup and the full symmetric monodromy theorem for reduced irreducible tuples. Hilbert irreducibility is then used to specialize the generic rational-coefficient system to one with rational coefficients while preserving the Galois groups; this is the standard Noether-Hilbert specialization principle.

1. Encoding two-action games by multiaffine equations↩︎

Let \(x_i\in[0,1]\) denote the probability that player \(i\) plays action \(1\). In any two-action game, the expected payoff difference

\[f_i(x_{-i}) = \mathbb{E}[u_i(1,\cdot)]-\mathbb{E}[u_i(0,\cdot)]\]

is a multiaffine polynomial in the variables \(x_j\), \(j\ne i\). Conversely, every such multiaffine polynomial can be realized by a two-action game: set the payoff difference at each pure opponents’ profile equal to the value of the polynomial at the corresponding cube vertex, and interpolate multilinearly.

A profile \(x\) is a Nash equilibrium exactly when, for every \(i\),

\[x_i f_i(x_{-i})\ge 0, \qquad (1-x_i)f_i(x_{-i})\le 0.\]

In particular, if \(x\) is totally mixed, then \(x\) is a Nash equilibrium iff

\[f_1(x)=\cdots=f_n(x)=0.\]

Now define the full two-action support

\[A_i=\{\alpha\in\{0,1\}^n:\alpha_i=0\}.\]

Thus \(f_i\) is a general polynomial supported on \(A_i\), i.e. it contains all squarefree monomials in the variables other than \(x_i\).

2. The mixed volume is the derangement number↩︎

Let \(P_i=\operatorname{conv}(A_i)\). Then

\[P_i=\{x\in\mathbb{R}^n:0\le x_j\le 1\text{ for }j\ne i,\;x_i=0\}.\]

For nonnegative \(\lambda_1,\dots,\lambda_n\),

\[\lambda_1P_1+\cdots+\lambda_nP_n = \prod_{j=1}^n \left[0,\sum_{i\ne j}\lambda_i\right].\]

Therefore its volume is

\[\prod_{j=1}^n\left(\sum_{i\ne j}\lambda_i\right).\]

The coefficient of \(\lambda_1\cdots \lambda_n\) is the number of ways to choose, from the \(j\)-th factor, a \(\lambda_i\) with \(i\ne j\), using every \(i\) exactly once. That is precisely the number of derangements of \(n\) letters. Hence

\[\operatorname{MV}(P_1,\dots,P_n)={!n}=D.\]

So a generic system

\[f_1=\cdots=f_n=0\]

with these supports has \(D\) isolated roots in \((\mathbb{C}^*)^n\).

3. The generic Galois group is \(S_D\), and each coordinate has degree \(D\)↩︎

The tuple \((A_1,\dots,A_n)\) is reduced: the lattice generated by all differences \(A_i-A_i\) contains every basis vector \(e_j\), because \(e_j\in A_i-A_i\) whenever \(i\ne j\).

It is also irreducible. Indeed, if \(I\subset\{1,\dots,n\}\) has \(|I|=m<n\), then:

\[\dim\sum_{i\in I}P_i = \begin{cases} n-1,&m=1,\\ n,&m\ge 2. \end{cases}\]

Since \(n\ge4\), this dimension is always \(>m\). Thus Esterov’s theorem applies, and the generic monodromy group of the \(D\) roots is \(S_D\).

We also need the \(i\)-th coordinate itself to have degree \(D\). For a fixed coordinate \(k\), consider the equivalence relation on the \(D\) generic roots:

\[r\sim s \quad\Longleftrightarrow\quad (x_k\text{ on root }r)=(x_k\text{ on root }s).\]

This relation is invariant under monodromy. Since the monodromy group is \(S_D\), the relation is either discrete or universal. It is not universal: choose constants \(b_{ij}\) with \(i\ne j\), distinct in each column \(j\), and consider

\[h_i(x)=\prod_{j\ne i}(x_j-b_{ij}).\]

The roots of \(h_1=\cdots=h_n=0\) are exactly the points indexed by derangements \(\sigma\), namely

\[x_{\sigma(i)}=b_{i,\sigma(i)}.\]

For each coordinate \(k\), different derangements can have different \(\sigma^{-1}(k)\), and hence different \(x_k\). Therefore the generic relation is not universal, so it is discrete. Thus the generic \(k\)-th coordinate takes \(D\) distinct values.

Therefore, for every \(k\), the coordinate eliminant

\[E_k(T)=\prod_{\text{generic roots }z}(T-z_k)\]

has degree \(D\) and Galois group \(S_D\) over the rational function field of the coefficients.

4. A unique-equilibrium base game↩︎

Now construct a simple base game with a unique equilibrium. Define

\[f_i^0=x_{i+1}-\frac{1}{2}\quad(1\le i<n), \qquad f_n^0=\frac{1}{2}-x_1.\]

At any equilibrium, for \(i<n\),

\[x_{i+1}>\frac{1}{2}\Rightarrow x_i=1, \qquad x_{i+1}<\frac{1}{2}\Rightarrow x_i=0,\]

while for player \(n\),

\[x_1>\frac{1}{2}\Rightarrow x_n=0, \qquad x_1<\frac{1}{2}\Rightarrow x_n=1.\]

If some coordinate is \(>1/2\), these implications propagate around the cycle and force the same coordinate to be \(<1/2\), a contradiction. The same argument rules out a coordinate \(<1/2\). Hence every equilibrium must be

\[x^0=\left(\frac{1}{2},\dots,\frac{1}{2}\right).\]

At \(x^0\), all players are indifferent, so \(x^0\) is indeed an equilibrium. Thus the base game has a unique Nash equilibrium.

Moreover, this property is open. The Jacobian of

\[(f_1^0,\dots,f_n^0)\]

at \(x^0\) is a signed cyclic permutation matrix, hence invertible. By the implicit function theorem, the totally mixed zero near \(x^0\) persists uniquely under small coefficient perturbations. Compactness of \([0,1]^n\), together with the Nash inequalities above, rules out new boundary equilibria for all sufficiently small perturbations. Therefore there is a Euclidean open neighborhood \(V\) of \(f^0\) in coefficient space such that every system in \(V\) defines a game with a unique, totally mixed Nash equilibrium.

5. Specialize to rational coefficients with full Galois group↩︎

The generic coordinate eliminants \(E_k(T)\) have Galois group \(S_D\). By Hilbert irreducibility, in its standard form allowing approximation inside a prescribed real open set, there exists a rational coefficient vector

\[f=(f_1,\dots,f_n)\in V\]

such that, for every \(k\), the specialized eliminant \(E_{k,f}(T)\) remains irreducible of degree \(D\) and has Galois group \(S_D\) over \(\mathbb{Q}\).

Let \(z=(z_1,\dots,z_n)\) be the unique Nash equilibrium of this rational game. Since it is totally mixed, it is one of the \(D\) complex roots of

\[f_1=\cdots=f_n=0.\]

For every \(k\), \(z_k\) is a root of \(E_{k,f}\). Since \(E_{k,f}\) is irreducible of degree \(D\), it is the minimal polynomial of \(z_k\). Hence

\[[\mathbb{Q}(z_k):\mathbb{Q}]=D={!n},\]

and the Galois group of \(z_k\) is \(S_D=S_{!n}\).

6. Make every coefficient of every minimal polynomial nonzero↩︎

Let \(q_k(T)\) be the minimal polynomial of \(z_k\). Choose a rational number \(\varepsilon_k\) arbitrarily small. The minimal polynomial of

\[y_k=z_k+\varepsilon_k\]

is

\[q_k(T-\varepsilon_k).\]

For a fixed nonconstant polynomial \(q_k\), each coefficient of \(q_k(T-\varepsilon)\) is a polynomial function of \(\varepsilon\). The coefficient of \(T^{D-r}\) has highest \(\varepsilon\)-term

\[\binom Dr(-\varepsilon)^r,\]

so it is not identically zero. Therefore only finitely many rational \(\varepsilon\) make any coefficient vanish. Choose each \(\varepsilon_k\) small enough, rational, and outside this finite bad set.

Now define a shifted game by

\[g_i(y_{-i}) = f_i(y_1-\varepsilon_1,\dots,y_{i-1}-\varepsilon_{i-1}, y_{i+1}-\varepsilon_{i+1},\dots,y_n-\varepsilon_n).\]

For sufficiently small \(\varepsilon_k\), the new coefficient vector remains inside \(V\), so the shifted game still has a unique Nash equilibrium. That equilibrium is

\[y=(z_1+\varepsilon_1,\dots,z_n+\varepsilon_n).\]

For every \(k\),

\[[\mathbb{Q}(y_k):\mathbb{Q}]=D={!n},\]

the Galois group is still \(S_D\), and the minimal polynomial

\[P_k(T)=q_k(T-\varepsilon_k)\]

has all \(D+1={!n}+1\) coefficients nonzero.

7. Clear denominators to get integer payoffs↩︎

The shifted polynomials \(g_i\) have rational coefficients. Choose a positive integer \(M\) clearing all denominators of the vertex values \(g_i(v_{-i})\), where \(v_{-i}\in\{0,1\}^{n-1}\).

Define the actual integer-payoff game by

\[u_i(1,v_{-i})=M g_i(v_{-i}), \qquad u_i(0,v_{-i})=0.\]

Then the expected payoff difference for player \(i\) is exactly \(M g_i(y_{-i})\). Multiplication by the positive number \(M\) does not change best responses or Nash equilibria. Thus the resulting game has integer payoffs and the same unique Nash equilibrium \(y\).

Therefore, for every \(n\ge4\), there exists an \(n\)-player two-action integer-payoff game with a unique Nash equilibrium \(y\) such that, for every \(i\),

\[[\mathbb{Q}(y_i):\mathbb{Q}]={!n}, \qquad \operatorname{Gal}(P_i)=S_{!n},\]

and the minimal polynomial \(P_i\) of \(y_i\) has all \({!n}+1\) coefficients nonzero.

---

1. In the proof we will fix \(n\) and omit the \(n\) superscript.↩︎

2. One could ask whether a minimal polynomial with many big coefficients has a multiple which has many zero coefficients. However, Giesbrecht2012? suggest that a sparse multiple can have a much higher degree, and its nonzero coefficients could be even larger.↩︎