Draft Note: This is the first draft of a paper I will be potentially be revising (probably substantially), reformatting, and submitting to ArXiv in the near future, and as such is written in that style. Note that it is not yet reviewed/fully checked, and may contain errors or incomplete arguments. I expect it to undergo significant revisions. I welcome feedback and suggestions for improvement. I’ll also note that the appications of this framework will be explored in future work, and are not the focus of this post. This effort is a more sophisticated attempt to classify games that I first attempted here.

Abstract

Given a game, how can we tell what kind of game it is? And when are two games “the same”? Consider a finite normal-form game with $n$ players and $k$ strategies per player (which we denote as an “$(n,k)$-game”). Each finite normal-form game can be represented by a multidimensional array of payoffs in $\mathbb{R}^{n \cdot k^n}$. Ideally, an equivalence relation on games would identify games that differ only by arbitrary labeling choices of strategies, while preserving strategic distinctions such as dominance, coordination, cycling, and equilibrium structure.

We use computational invariant theory to classify finite normal-form games modulo strategy relabeling by constructing invariant coordinates on the quotient. The relabeling action is linear on the space of payoff arrays, and polynomial invariants of this action are the payoff statistics that are independent of the names assigned to strategies. Thus, finite generating sets of the invariant ring give orbit-separating coordinates for games modulo relabeling.

We apply this framework first to $(2,2)$-games, where we compute an explicit generating set of invariants, together with relations among them, that completely classify $(2,2)$-games up to relabeling. We show that this generalizes the Robinson and Goforth (2005) combinatorial taxonomy of $(2,2)$-games under ordinal equivalence to cardinal payoff geometry, with the Robinson-Goforth types appearing as regions in the resulting quotient. We also show that by using an enlarged notion of equivalence that also identifies player swaps, we can generalize the Rapoport and Guyer (1966) classification of $(2,2)$-games under strict ordinal equivalence.

We then generalize the construction to finite $(n,k)$-games. For each fixed $(n,k)$, the resulting invariant ring separates strategy-relabeling orbits, giving an invariant-theoretic classification of $(n,k)$-games. In practice, this classification is realized by computing finite generating sets of polynomial invariants and the relations among them. Beyond the complete explicit $(2,2)$ case, we develop the computational pipeline needed for larger cases, including the $(3,3)$ setting, where the invariant ring is substantially larger but governed by the same quotient construction.

We go on to show that standard game classes (potential, zero-sum, symmetric, coordination-type) can be characterized by polynomial equations and inequalities in the invariants. We record scaling laws for the invariant ring, including stabilization of $h_d(n,k)$ once $k \geq d$ and a closed-form super-polynomial growth rate for binary degree-$3$ invariants. We also describe how label-complete cyclic witnesses produce natural degree-$k$ invariants and sign-reversing pairs produce degree-$2k$ invariants, while emphasizing that these are existence statements rather than universal lower bounds.

Finally, we relate the quotient coordinates to the Candogan et al. (2011) Hodge decomposition of games, and show how specific invariants detect dominance and Nash-equilibrium structure. For two-player games (n=2), the full-support indifference determinant is a payoff-only invariant polynomial of degree $2(k-1)$. For $n \geq 3$, the natural object is a Jacobian form on the payoff–mixed-strategy incidence space, polynomial in payoff entries of degree $n(k-1)$.

Introduction

Many of the common $(2,2)$-games have familiar names. The Prisoner’s Dilemma, Stag Hunt, Chicken, Battle of the Sexes, Matching Pennies, etc. are standard examples of $(2,2)$-games, each modeling a distinct class of strategic interactions. But these named examples occupy only a small part of the full space of finite games.

In this paper, we construct a coordinate system on the space of games. The coordinates respect the arbitrary labeling of strategies, retain full cardinal payoff information, and do not depend on any solution concept. We show that this coordinate system recovers the classical game classes as algebraic subvarieties and inequalities, encodes Nash equilibrium structure as polynomial conditions, and reveals a hierarchy of strategic properties organized by polynomial degree.

The first systematic classification of the $(2,2)$-games was Rapoport and Guyer (1966). Rapoport and Guyer identify 78 types of games using a strict ordinal framework, where two games are considered equivalent if and only if they have the same payoff ranking structure. They also considered games to be identical under relabelings of rows, columns, and player positions. Robinson and Goforth (2005) later obtained 144 types by distinguishing player roles. This allowed them to organize the resulting space of $(2,2)$-games topologically (via adjacencies given by single payoff swaps), producing a “periodic table”.

While these ordinal classification methods produce finite taxonomies, they also collapse the cardinal geometry within each type. Two games may have the same ordinal form while differing in mixed equilibrium probabilities, risk dominance, evolutionary behavior, or comparative statics. At the same time, small cardinal perturbations near an ordinal boundary can move a game into a different ordinal type.

The situation is worse in higher dimensions. Consider $(2,3)$-games, with two players and three strategies per player. Although a few examples, such as Rock-Paper-Scissors, are well known, most $(2,3)$-games have no standard names and no useful catalog. In fact, the number of strict ordinal types of $(2,3)$-games exceeds $10^9$.¹ Since the number of strict ordinal types grows superexponentially in the number of strategies, a Robinson-Goforth-style classification based on exhaustive enumeration of ordinal types is infeasible.

Ordinal classification is not the only possible approach. Another approach classifies games by their induced behavior. For example, two games can be considered equivalent if they generate the same best-response correspondence (Morris and Ui 2004), the same Nash equilibrium structure (Germano 2006), or the same qualitative dynamics (Weibull 1995). However, each such equivalence is tied to a specific solution concept. For example, games that behave identically under best-response dynamics might differ under other solution concepts (e.g., welfare, fictitious play, replicator dynamics).

We therefore want a classification that respects relabeling symmetries, retains cardinal payoff information, and does not presuppose a solution concept. Such a classification would let us study the algebraic structure of the space of games, identify canonical coordinates, and describe game classes and equilibrium structure systematically.

In this paper, we use invariant theory to build such a coordinate system for the space of games. In the main part of the paper, games are considered equivalent if they differ only by relabeling of strategies. Equivalently, we consider two games to be equivalent if they lie in the same orbit under the action of the permutation group acting on the labels of the strategies. The invariants of this group action are polynomial functions of the payoff entries that are constant on orbits, meaning they do not change when we relabel strategies. These invariants act as canonical summary statistics of a game, independent of labeling conventions. Together, the invariants give coordinates on the space of games modulo relabeling.

Since the invariants are polynomials in the actual payoff values, cardinal information is retained by construction. Additionally, the equivalence relation is defined by labeling symmetries without reference to any solution concept. We go on to show that the invariant ring has a rich algebraic structure that captures game-theoretic properties directly. For example, classical game classes such as potential, zero-sum, and coordination games can be described by explicit polynomial equations and inequalities. Dominance and Nash-equilibrium structure are encoded by polynomial conditions on the invariants. The invariant degrees at which various strategic properties first become detectable form a hierarchy, with contrast magnitudes and interaction alignment appearing at degree 2, skewness and cyclic directionality at degree 3, and higher-order cyclic patterns at degree 4 and above. The Hodge-theoretic decomposition of games into potential, harmonic, and nonstrategic components (Candogan et al. 2011; Candogan, Ozdaglar, and Parrilo 2013) sits inside the invariant ring as a relabeling-compatible linear decomposition of the payoff space, with the invariant polynomials then organized by which Hodge components they involve.

The invariant ring also connects cleanly to existing behavioral classifications. Best-response equivalence, Nash equivalence, and other solution-concept-based equivalences each can be studied inside the relabeling quotient, and they appear in invariant coordinates as polynomial conditions where they appear as additional equations and inequalities in invariant coordinates. The invariant ring is thus not a replacement for these classifications but an underlying geometry in which they can be located and compared.

The rest of the paper is organized as follows. We begin with background on game theory, symmetries, and invariant theory. We then apply the framework to $(2,2)$-games, computing explicit generators, syzygies, game class conditions, and the connection to the Robinson-Goforth ordinal classification. We generalize to $(n,k)$-games via the family structure and the contrast-block Reynolds construction. We then collect applications and further structure: scaling laws for the invariant ring, equilibrium diagnostics, the relation to the Hodge decomposition, and cycle-witness invariants. We conclude with algorithms, a discussion of open problems, and appendices containing the wreath product computation, the $(3,3)$-game details, and software documentation.

Scope

We develop a computational invariant-theoretic framework for finite normal-form $(n,k)$-games under strategy relabeling. Applications are deferred to follow-up work. The setting is finite normal-form games, so extensive-form representations and games with infinite strategy spaces are not considered. The equivalence relation is purely structural, namely strategy relabeling, with no appeal to a solution concept. Behavioral equivalences such as best-response, Nash, and qualitative-dynamics equivalence sit inside the relabeling quotient as polynomial conditions on the invariants, but constructing them from solution concepts is not pursued, and the learning, evolutionary, and mechanism-design questions that the framework is designed to support are also out of scope for this paper. We also do not aim to catalog the full invariant rings at every $(n,k)$ (which would be impossible). The contribution of this paper is in showing how these methods can be applied to games, such as the contrast-block decomposition and the Reynolds projection from standard invariant theory, which compute the ring on demand at any specific $(n,k)$.

Game-Theoretic Background

Games and Payoff Space

Let $N = \{1, \ldots, n\}$ be a set of players. For each player $i \in N$, let $S_i$ be a finite strategy set with $|S_i| = k_i$, and let $u_i : S_1 \times \cdots \times S_n \to \mathbb{R}$ be the payoff function for player $i$. We call the elements of $S_1 \times \cdots \times S_n$ strategy profiles, and $u_i(s)$ the payoff to player $i$ at profile $s$. The complete tuple $(N, (S_i), (u_i))$ is called a finite normal-form game. If $|N|=n$ and every player has $k_i=k$ strategies, we call the game an $(n,k)$-game.

A general finite normal-form game has $\sum_{i=1}^n \prod_{j=1}^n k_j = n\prod_{j=1}^n k_j$ payoff entries, and an $(n,k)$-game has $nk^n$ payoff entries. Since the payoff functions determine the game once the player and strategy sets are fixed, the space of $(n,k)$-games can be identified with $\mathbb{R}^{nk^n}$.

When $n=2$ and both players have $k$ strategies, we can write the game as a pair of $k \times k$ matrices $(A,B)$, where $A_{ij}$ is the payoff to player 1 and $B_{ij}$ is the payoff to player 2 at the strategy profile $(i,j)$. For $n>2$, the payoff functions are $n$ arrays indexed by $S_1\times\cdots\times S_n$. We will occasionally return to the two-player matrix notation for concreteness and visualization.

Solution Concepts

Given a strategy profile $s = (s_1, \ldots, s_n)$, we write $s_{-i} = (s_1, \ldots, s_{i-1}, s_{i+1}, \ldots, s_n)$ for the strategies of all players other than $i$, and $(s_i, s_{-i})$ for the full profile.

We call a probability distribution over $S_i$ a mixed strategy for player $i$. When $|S_i|=k$, we write

\[ \Delta^{k-1}=\{x\in\mathbb{R}^k : x_j\geq 0,\ \sum_{j=1}^k x_j=1\} \]

for the $(k-1)$-simplex. Thus, a mixed strategy is an element $x_i \in \Delta^{k_i - 1}$. For a two-player game $(A,B)$ with mixed strategies $x,y\in\Delta^{k-1}$, the expected payoffs are $x^\top A y$ and $x^\top B y$ (Neumann and Morgenstern 1944; Nash 1950).

We call the set of strategies maximizing $u_i(s_i, s_{-i})$ the best response of player $i$ to $s_{-i}$. We call a profile of mixed strategies $(x_1^*, \ldots, x_n^*)$ a Nash equilibrium if each $x_i^*$ is a best response to $x_{-i}^*$. Nash (1950) showed that every finite game has at least one Nash equilibrium.

We say that a strategy $s_i$ for player $i$ is strictly dominated if there exists $s_i'$ such that $u_i(s_i', s_{-i}) > u_i(s_i, s_{-i})$ for all $s_{-i}$. Dominated strategies are never played at any Nash equilibrium (Osborne and Rubinstein 1994). We say that a game is solvable by iterated strict dominance if iteratively eliminating strictly dominated strategies terminates at a single strategy profile.

Game Classes

Several well-known classes of games are defined by equations or inequalities on the payoff functions.

We say that a game is zero-sum if $\sum_i u_i(s) = 0$ for all $s$. Similarly, a game is constant-sum if $\sum_i u_i(s)$ is constant across all strategy profiles $s$. Constant-sum games are therefore strategically equivalent to zero-sum games after a payoff shift. With the convention that $A_{ij}$ and $B_{ij}$ are the two payoffs at the same profile $(i,j)$, a two-player game is zero-sum if and only if $B=-A$ (Neumann and Morgenstern 1944).

We call a game an exact potential game (Monderer and Shapley 1996) if there exists a function $\phi : \prod_i S_i \to \mathbb{R}$ such that for each player $i$, each strategy $s_i$, and each alternative strategy $s_i'$, with $s_{-i}$ held fixed,

\[ u_i(s_i, s_{-i}) - u_i(s_i', s_{-i}) = \phi(s_i, s_{-i}) - \phi(s_i', s_{-i}) \]

Thus every unilateral payoff improvement produces the same change in $\phi$. Pure Nash equilibria are the specific strategy profiles that are local maxima of $\phi$ with respect to unilateral deviations.

We say that an $(n,k)$-game is symmetric if permuting the players does not change any player’s payoff, provided the strategies are permuted accordingly. For two-player games with equal strategy sets, this is equivalent to $B = A^\top$.

We will also use the informal terms “coordination-type” and “anti-coordination-type.” In a coordination-type game, players benefit from matching each other’s strategies, whereas in an anti-coordination-type game, players benefit from choosing different strategies. The Stag Hunt and Prisoner’s Dilemma are coordination-type; Chicken and Matching Pennies are anti-coordination-type. In the $(2,2)$ invariant coordinates below, these distinctions will correspond to explicit sign conditions.

Named Game Examples

We illustrate with named $(2,2)$-games. A general $(2,2)$-game has 8 payoff entries:

	$s_2 = 1$	$s_2 = 2$
$s_1 = 1$	$a_1, b_1$	$a_2, b_2$
$s_1 = 2$	$a_3, b_3$	$a_4, b_4$

where $a_m$ is the payoff to player 1 and $b_m$ the payoff to player 2. We refer to the outcome with payoffs $(a_m, b_n)$ as $(m, n)$. The payoff space is $\mathbb{R}^8$ with coordinates $(a_1, a_2, a_3, a_4, b_1, b_2, b_3, b_4)$.

Table 1 summarizes the named $(2,2)$-games used in this paper.

Table 1: Named $(2,2)$-games. Rankings list payoff outcomes from highest to lowest for each player; for Pure Coordination, $a_1$ and $a_4$ are positive and the other two payoffs are zero.

Game	P1 ranking	P2 ranking	Class	NE
Prisoner’s Dilemma	3, 1, 4, 2	2, 1, 4, 3	potential	$(2,2)$ unique
Stag Hunt	1, 3, 4, 2	1, 2, 4, 3	potential	$(1,1)$ and $(2,2)$
Chicken	3, 1, 2, 4	2, 1, 3, 4	anti-coordination	$(1,2)$ and $(2,1)$
Pure Coordination	1, 4 (others 0)	1, 4 (others 0)	coordination	$(1,1)$ and $(2,2)$
Matching Pennies	$B = -A$	(BR cycle)	zero-sum	fully mixed

The inequalities in Table 1 specify ordinal representatives of the named classes. Later invariant calculations use particular cardinal representatives.

In the Prisoner’s Dilemma, strategy 2 strictly dominates strategy 1 for both players, producing the unique equilibrium $(2,2)$ despite $(1,1)$ being Pareto superior. In the Stag Hunt, changing one inequality relative to the PD creates two equilibria: $(1,1)$ is payoff-dominant but $(2,2)$ is risk-dominant. In Chicken, each player prefers to differ from the other, giving two asymmetric pure equilibria. Pure Coordination is the extreme case where off-diagonal payoffs are zero. In Matching Pennies, the zero-sum condition $B = -A$ creates a best-response cycle with no pure equilibrium.

Rock-Paper-Scissors (RPS) extends the cycling structure of Matching Pennies to $k = 3$. The standard RPS game is a $(2,3)$ zero-sum game with $B=-A$ and $A_{ij}=-A_{ji}$, where each strategy beats one strategy and loses to another. The unique Nash equilibrium is the uniform mixture $(1/3, 1/3, 1/3)$.

The named examples above are highly structured. The standard symmetric examples satisfy $B=A^\top$, while Matching Pennies is zero-sum with $B=-A$. A generic game in $\mathbb{R}^{2k^2}$ has $A$ and $B$ unrelated. Thus the standard symmetric and zero-sum representatives of named games occupy lower-dimensional subsets of payoff space, even though the corresponding ordinal classes may contain open regions.

Symmetries

Given a game, we can relabel the strategies of each player without changing the strategic structure of the game. For example, in a two-player game, we can swap the labels of player 1’s strategies (e.g., “cooperate” and “defect”) or swap the labels of player 2’s strategies. Simply renaming strategies does not change the underlying strategic interaction, only the labels used to describe it. Therefore, we consider two games to be equivalent if they can be transformed into each other by such relabeling operations.

We can formalize this idea using group theory. A permutation of player $i$’s strategies is an element of the symmetric group $S_{k_i}$, which acts on the payoff array by permuting the corresponding indices. A permutation of the players is an element of the symmetric group $S_n$, which acts by permuting the player indices. The combined action of these permutations generates a group of symmetries that we can use to classify games up to relabeling.

Groups and Group Actions

A group is a set $G$ equipped with a multiplication operation, an identity element, and inverses, satisfying the usual associativity law. The basic examples in this paper are permutation groups, especially $S_k$, the group of permutations of $k$ objects.

A group action of $G$ on a set $X$ assigns to each $g\in G$ a transformation of $X$, written $x\mapsto g\cdot x$, such that the identity element fixes every $x\in X$ and

\[ (gh)\cdot x = g\cdot(h\cdot x) \]

The orbit of $x\in X$ is \[ G\cdot x=\{g\cdot x:g\in G\} \]

The orbits partition $X$ into equivalence classes. The quotient $X/G$ is the set of these orbits, and the quotient map $\pi : X \to X/G$ sends each element $x \in X$ to its orbit $G \cdot x$. There may not in general be a natural way to identify $X/G$ with a subset of $X$, and the quotient space may also have a different geometric or algebraic structure than the original space.

Permutation Groups

Permutations form a group, called the “symmetric group”, commonly denoted $S_k$ for permutations of $k$ distinct objects. $S_k$ itself consists of $k!$ different elements. For example, $S_3$ has 6 elements: the identity permutation, the three transpositions that swap two elements, and the two 3-cycles that rotate all three elements. Permutations can be composed in the expected way (permuting the items, then permuting the permuted items), and the group operation is associative. The identity element is the permutation that leaves all elements unchanged, and each permutation has an inverse that undoes its effect.

We write permutations in cycle notation: $(12)$ denotes the transposition swapping $1$ and $2$, while $(123)$ denotes the cycle $1\mapsto 2\mapsto 3\mapsto 1$.

We can also represent permutations by permutation matrices. Let $e_1,\ldots,e_k$ be the standard basis of $\mathbb{R}^k$. For $\sigma\in S_k$, define $P_\sigma$ by

\[ P_\sigma e_a = e_{\sigma(a)} \]

Thus the $a$-th column of $P_\sigma$ is $e_{\sigma(a)}$, and multiplying by $P_\sigma$ permutes coordinates according to $\sigma$.

For each player $i$, a permutation $\sigma_i \in S_{k_i}$ relabels player $i$’s strategies. Since every payoff array is indexed by the same strategy profile $(s_1,\ldots,s_n)$, the permutation acts on every payoff array by permuting the $i$-th index:

\[ (\sigma_i \cdot u_j)(s_1, \ldots, s_n) = u_j(s_1, \ldots, \sigma_i^{-1}(s_i), \ldots, s_n) \]

Thus the same relabeling of player $i$’s strategies is applied simultaneously to every player’s payoff array. The inverse appears because the action is written as a left action on payoff functions.

For two-player games written as $(A,B)$, this action becomes matrix multiplication. With the convention $P_\sigma e_a=e_{\sigma(a)}$, a permutation $\sigma_1\in S_{k_1}$ of player 1’s strategies acts by

\[ \sigma_1 \cdot (A, B) = (P_{\sigma_1} A, \, P_{\sigma_1} B) \]

and a permutation $\sigma_2 \in S_{k_2}$ of player 2’s strategies acts by

\[ \sigma_2 \cdot (A, B) = (A P_{\sigma_2}^\top, \, B P_{\sigma_2}^\top) \]

Left multiplication by $P_{\sigma_1}$ permutes rows; right multiplication by $P_{\sigma_2}^{\top}$ permutes columns. Both $A$ and $B$ are permuted in the same way, since both payoff matrices are indexed by the same strategy profiles.

For a $(2,2)$-game with $A = \begin{pmatrix} a_1 & a_2 \\ a_3 & a_4 \end{pmatrix}$, the nontrivial element of $S_2$ has permutation matrix $P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$. Then

\[ PA = \begin{pmatrix} a_3 & a_4 \\ a_1 & a_2 \end{pmatrix} \] \[ AP = \begin{pmatrix} a_2 & a_1 \\ a_4 & a_3 \end{pmatrix} \]

The first swaps rows (relabeling player 1’s strategies), the second swaps columns (relabeling player 2’s strategies). Both act on $B$ the same way.

For an $(n,2)$-game, each payoff array is indexed by $\{0,1\}^n$. The nontrivial element of the $i$-th copy of $S_2$ flips the $i$-th coordinate in every player’s payoff array.

The Strategy Relabeling Group

For an $(n,k)$-game, each player has an independent copy of $S_k$ acting on that player’s strategies. Since these relabelings can be chosen independently for each player, the combined strategy-relabeling group is the direct product

\[ G = (S_k)^n = \underbrace{S_k \times \cdots \times S_k}_{n} \]

An element $(\sigma_1,\ldots,\sigma_n)\in G$ relabels all players’ strategies simultaneously. The factor $\sigma_i$ relabels player $i$’s strategies, and every payoff array is permuted in the corresponding strategy coordinate. This is the main symmetry group uses in this paper.

The players remain distinguishable: relabeling player 1’s strategies is a different operation from relabeling player 2’s, and we do not identify the two players. In settings where players are interchangeable, such as anonymous mechanism design or evolutionary models, one can also allow permutations of the players by $S_n$.

When the players are interchangeable (as in anonymous mechanism design or evolutionary settings), we can additionally permute the players themselves by $S_n$. The resulting group is the wreath product

\[ (S_k)^n\rtimes S_n \]

which we treat separately in Appendix C.

Invariant Theory

We now review the elements of invariant theory needed for the classification. Standard references are Derksen and Kemper (2015) and Sturmfels (2008). Throughout, $G$ is a finite group acting linearly on a finite-dimensional real vector space $V$.

Group Actions, Orbits, and Invariants

A linear action of $G$ on $V$ is a group homomorphism $\rho: G \to GL(V)$. The orbit of a point $v \in V$ is the set $G \cdot v = \{ \rho(g)(v) : g \in G \}$, and the stabilizer of $v$ is $G_v = \{ g \in G : \rho(g)(v) = v \}$. Two points lie in the same orbit if and only if one can be obtained from the other by applying some group element.

Let $\mathbb{R}[V]$ denote the ring of real-valued polynomial functions on $V$. Since degree $d$ polynomials form a subspace $\mathbb{R}[V]_d$, the ring $\mathbb{R}[V]$ is graded by polynomial degree. The group action preserves degree, and therefore the invariant ring inherits this grading. A polynomial $f \in \mathbb{R}[V]$ is $G$-invariant if $f(\rho(g)(v)) = f(v)$ for all $g \in G$ and $v \in V$. The set of all $G$-invariant polynomials forms a subring

\[ \mathbb{R}[V]^G = \bigoplus_{d \geq 0} \mathbb{R}[V]^G_d \]

where \[ \mathbb{R}[V]^G_d = \{ f \in \mathbb{R}[V]_d : f \circ \rho(g) = f, \forall g \in G \} \]

called the invariant ring.

The Reynolds Operator

For finite groups, invariants can be constructed explicitly by averaging. The Reynolds operator $\mathcal{R}: \mathbb{R}[V] \to \mathbb{R}[V]^G$ is defined as

\[ \mathcal{R}(f) = \frac{1}{|G|} \sum_{g \in G} f \circ \rho(g) \]

This map is a linear projection from $\mathbb{R}[V]$ onto $\mathbb{R}[V]^G$. The Reynolds operator sends every polynomial to an invariant polynomial, and maps any polynomial that is already invariant back to itself. In practice, to find degree-$d$ invariants, one applies $\mathcal{R}$ to a basis of degree-$d$ monomials and collects the linearly independent results.

Example

Let $G = S_2$ act on $\mathbb{R}^2$ by swapping coordinates: $(x, y) \mapsto (y, x)$.

Then $\mathbb{R}[x,y]^{S_2}$ is the ring of symmetric polynomials, generated by $e_1 = x + y$ and $e_2 = xy$. These two generators are algebraically independent, so $\mathbb{R}[x,y]^{S_2} \cong \mathbb{R}[e_1, e_2]$ is a polynomial ring. Every symmetric polynomial in $x$ and $y$ can be written uniquely as a polynomial in $e_1$ and $e_2$. For example, the symmetric polynomial $f(x,y) = x^2 + y^2$ can be expressed in terms of the generators as $f = e_1^2 - 2e_2$.

Generators, Syzygies, and Finite Generation

By the Hilbert–Noether finite-generation theorem for invariant rings (Hilbert 1890; Noether 1926), the invariant ring $\mathbb{R}[V]^G$ is finitely generated as an $\mathbb{R}$-algebra. That is, there exist finitely many invariants $f_1, \ldots, f_r \in \mathbb{R}[V]^G$ such that every invariant polynomial can be written as a polynomial in $f_1, \ldots, f_r$. We call $\{f_1, \ldots, f_r\}$ a set of generators for the invariant ring.

In the symmetric polynomial example above, the generators $e_1, e_2$ are algebraically independent: there is no nontrivial polynomial relation $R(e_1, e_2) = 0$ satisfied by the generators. In general, generators need not be algebraically independent.

Given generators $f_1, \ldots, f_r$, we can consider the surjection $\varphi : \mathbb{R}[y_1, \ldots, y_r] \to \mathbb{R}[V]^G$ defined by $\varphi(y_i) = f_i$. This map sends each abstract polynomial in the $y_i$ to the corresponding polynomial in the generators, evaluated on $V$. The kernel of $\varphi$ is the ideal of all polynomial relations among the generators that hold identically on $V$. We call these relations, or “syzygies”, among the generators. For example, if $f_1 f_2 = f_3^2$ as polynomial functions on $V$, then $y_1 y_2 - y_3^2$ is a syzygy.

Together, the generators and syzygies give a complete algebraic description of the invariant ring. Specifically, the generators define coordinates on the quotient, and the relations cut out the image of the quotient map inside $\mathbb{R}^r$.

The Molien Series

The Molien series is a generating function that counts the dimension of the space of invariants at each polynomial degree. For a finite group $G$ acting on $V$ via the representation $\rho$, the Molien series is defined as

\[ M(t) = \frac{1}{|G|} \sum_{g \in G} \frac{1}{\det(I - t \cdot \rho(g))} = \sum_{d=0}^{\infty} h_d \, t^d \]

where $h_d = \dim \mathbb{R}[V]^G_d$ is the number of linearly independent degree-$d$ invariants. The formula follows from Molien’s theorem (see Derksen and Kemper 2015, Ch. 3). In practice, the sum over $|G|$ group elements can often be reduced to a sum over conjugacy classes, since $\det(I - t \cdot \rho(g))$ depends only on the conjugacy class of $g$.

The Molien series does not describe the invariants themselves. Instead, it gives the dimension $h_d$ of the invariant space in each degree. By comparing $h_d$ with the span of products of lower-degree generators, we can determine when new generators are needed and check explicit computations.

The Quotient Space

The generators $f_1, \ldots, f_r$ define a map

\[ \pi: V \to \mathbb{R}^r \] \[ v \mapsto (f_1(v), \ldots, f_r(v)) \]

The image of this map, denoted $V /\!\!/ G$, realizes the quotient of $V$ by the action of $G$. For finite groups $G$, points of this quotient correspond to orbits. Two points $v, w \in V$ lie in the same orbit if and only if $\pi(v) = \pi(w)$, i.e., if and only if they take the same values on all generators. Equivalently, the generators separate orbits: $v, w \in V$ satisfy $\pi(v) = \pi(w)$ if and only if $f_i(v) = f_i(w)$ for all $i$.

For finite groups, the invariant ring separates orbits because all orbits are finite, hence closed. The distinction between orbits and closed orbits in general invariant theory will not be necessary here.

The Invariant Ring of $(2,2)$-Games

Before developing the general $(n,k)$ construction, we will work out the smallest nontrivial case in full, which is the invariant ring of $(2,2)$-games under strategy relabeling by the action of the symmetry group $G=S_2\times S_2$, where the two factors swap the two strategies of player 1 and player 2, respectively. We assume players are distinguishable to match the assumptions of the Robinson-Goforth 144-type ordinal classification.

The $(2,2)$ case simplifies the $(n,k)$ case in two convenient ways. First, the relabeling action diagonalizes into simple sign flips. Second, the resulting invariants can be written explicitly. This example therefore serves as a concrete model for the general quotient construction, while also allowing direct comparison with the Robinson-Goforth ordinal taxonomy.

We will show that the invariant ring can be used to construct a cardinal analogue of Robinson-Goforth. Starting from the eight payoff entries of a $(2,2)$-game, we will remove the two payoff means and work on the six-dimensional mean-zero payoff space. In these coordinates, the two strategy swaps act by changing signs of selected coordinates, reducing the computation of invariants to a parity condition (i.e. checking the sign) on monomials. The invariant ring is generated by nine quadratic invariants and eight cubic invariants. These real-valued invariants classify cardinal $(2,2)$-games up to strategy relabeling and player-specific additive constants, subject to algebraic relations among the generators. By discarding magnitudes and keeping only signs of nine selected degree-2 invariants, we recover the Robinson-Goforth taxonomy from this quotient. Thus, the same invariant coordinates retain cardinal payoff information while also explaining how the classical ordinal table sits inside the quotient.

Mean-Zero Coordinates

We first pass to mean-zero coordinates, removing the two player-specific payoff means. Consider a two-player game with payoff matrices $A$ and $B$. We write player 1’s payoff matrix as

\[ A= \begin{pmatrix} a_1 & a_2\\ a_3 & a_4 \end{pmatrix} \]

Based on player 1’s payoff entries $a_1, a_2, a_3, a_4$, we define

\[ r_A = a_1 + a_2 - a_3 - a_4 \] \[ c_A = a_1 - a_2 + a_3 - a_4 \] \[ d_A = a_1 - a_2 - a_3 + a_4 \]

and similarly for player 2 with entries in $B$. We call $r_A$ the row contrast², $c_A$ the column contrast, and $d_A$ the interaction. The words “row” and “column” refer to the payoff table coordinates. Thus $r_A$ is player 1’s own-strategy contrast, while $c_B$ is player 2’s own-strategy contrast.

The remaining coordinate for player 1 is the payoff sum \[ m_A=a_1+a_2+a_3+a_4 \]

and similarly $m_B$ for player 2.

The inverse change of coordinates for player 1 is

\[ a_1=\frac{m_A+r_A+c_A+d_A}{4} \]

\[ a_2=\frac{m_A+r_A-c_A-d_A}{4} \]

\[ a_3=\frac{m_A-r_A+c_A-d_A}{4} \]

\[ a_4=\frac{m_A-r_A-c_A+d_A}{4} \]

The same inverse formula holds for $B$.

Adding a constant to all of one player’s payoffs does not affect best responses or Nash equilibria, so we suppress these two coordinates. Together, $(r_A,c_A,d_A,r_B,c_B,d_B)$ give linear coordinates on the six-dimensional mean-zero payoff space.

We use unnormalized contrast coordinates, omitting the conventional $\frac{1}{2}$ scaling factor. This keeps all invariant values integral on games with integer payoffs. The choice of scaling does not affect the invariant ring.

Proposition 1 (Sign-flip action) In the mean-zero coordinates $(r_A,c_A,d_A,r_B,c_B,d_B)$, the group $S_2\times S_2$ acts by the following two sign-flip generators:

\[ s_1: (r_A, c_A, d_A, r_B, c_B, d_B) \mapsto (-r_A, c_A, -d_A, -r_B, c_B, -d_B) \] \[ s_2: (r_A, c_A, d_A, r_B, c_B, d_B) \mapsto (r_A, -c_A, -d_A, r_B, -c_B, -d_B) \]

Proof. Let $A = \begin{pmatrix} a_1 & a_2 \\ a_3 & a_4 \end{pmatrix}$. Swapping player 1’s strategies swaps the two rows, sending $(a_1,a_2,a_3,a_4)\mapsto(a_3,a_4,a_1,a_2)$. Under this swap,

\[ r_A=a_1+a_2-a_3-a_4 \mapsto a_3+a_4-a_1-a_2=-r_A \] \[ c_A=a_1-a_2+a_3-a_4 \mapsto a_3-a_4+a_1-a_2=c_A \] \[ d_A=a_1-a_2-a_3+a_4 \mapsto a_3-a_4-a_1+a_2=-d_A \]

The same row swap acts on player 2’s payoff matrix in the same way, so $r_B$ and $d_B$ are negated while $c_B$ is fixed. This gives the formula for $s_1$.

Similarly, swapping player 2’s strategies swaps the two columns, sending $(a_1,a_2,a_3,a_4)\mapsto(a_2,a_1,a_4,a_3)$. A direct substitution gives $r_A\mapsto r_A$, $c_A\mapsto -c_A$, $d_A\mapsto -d_A$. The same column swap acts on player 2’s payoff matrix, so $c_B$ and $d_B$ are negated while $r_B$ is fixed. This gives the formula for $s_2$.

Since the action is diagonal in these coordinates, a monomial is invariant exactly when it has even total degree in the variables negated by $s_1$ and even total degree in the variables negated by $s_2$. Thus every invariant monomial has even total degree in

\[ (r_A,d_A,r_B,d_B) \]

and even total degree in

\[ (c_A,d_A,c_B,d_B) \]

Equivalently, because the sign-flip action does not mix monomials, a polynomial in the six mean-zero coordinates is $G$-invariant if and only if every monomial appearing in it satisfies these two parity conditions.

Computing the Molien Series and Generators

We compute the Molien series for this $S_2 \times S_2$ action on the six-dimensional mean-zero payoff space. The first several coefficients are

\[ M(t) = 1 + 0 \cdot t + 9t^2 + 8t^3 + 42t^4 + 48t^5 + 138t^6 + \cdots \]

We construct generators by applying the Reynolds operator to monomials at each degree and testing which are linearly independent of products of previously found generators (see Section 16.1). The results are summarized in Table 2.

Table 2: Molien coefficients and generator counts for $(2,2)$-games under $S_2 \times S_2$ (see Section 16.1)

Degree	$h_d$ (Molien)	From products	New generators
0	1	1	0
1	0	0	0
2	9	0	9
3	8	0	8
4	42	42	0

Here $h_d$ is the dimension of the degree-$d$ invariant subspace, not the number of generators in degree $d$. The “new generators” column records what remains after quotienting by products of lower-degree generators.

The invariant ring is generated by the $9+8=17$ invariants listed below, all of degree $2$ or $3$. That is, all degree-4 invariants are products of lower-degree generators. The degree-$4$ computation, together with Noether’s bound (Noether 1926), proves that no generators occur above degree $3$. The degree-$5$ and degree-$6$ rank checks are additional consistency checks, as products of the listed generators span the Molien-predicted dimensions $48$ and $138$.

Theorem 1 ($(2,2)$ generators) The invariant ring of the mean-zero $(2,2)$ payoff space under $S_2\times S_2$ is generated by the following nine degree-$2$ invariants and eight degree-$3$ invariants. The ring closes at degree 3.

Proof. Proved by computation. The generators are computed by applying the Reynolds operator to monomials at each degree and testing for linear independence from products of previously found generators. The details are in Section 16.1.

Degree-2 Generators: Magnitudes and Alignments

The 9 degree-2 generators are listed in Table 3.

Table 3: Degree-2 generators of the $(2,2)$ invariant ring (see Section 16.1)

Id	Expression	Interpretation
$g_1$	$r_A^2$	Player 1 row contrast magnitude
$g_2$	$r_A r_B$	Cross-player row contrast alignment
$g_3$	$c_A^2$	Player 1 column contrast magnitude
$g_4$	$c_A c_B$	Cross-player column contrast alignment
$g_5$	$d_A^2$	Player 1 interaction strength
$g_6$	$d_A d_B$	Interaction alignment (coordination vs anti-coordination)
$g_7$	$r_B^2$	Player 2 row contrast magnitude
$g_8$	$c_B^2$	Player 2 column contrast magnitude
$g_9$	$d_B^2$	Player 2 interaction strength

These are the nine quadratic monomials in $(r_A, c_A, d_A, r_B, c_B, d_B)$ satisfying the two parity conditions above. Each has a direct game-theoretic interpretation. In particular, $r_A^2$ and $c_B^2$ are separate invariants, so the quotient distinguishes player 1’s own-strategy contrast from player 2’s own-strategy contrast.

Degree-3 Generators: Triple Products

The 8 degree-3 generators (Table 4) are all triple products mixing one coordinate from each of the three types (row, column, interaction).

Table 4: Degree-3 generators of the $(2,2)$ invariant ring (see Section 16.1)

Id	Expression
$g_{10}$	$c_A d_A r_A$
$g_{11}$	$c_A d_B r_A$
$g_{12}$	$c_B d_A r_A$
$g_{13}$	$c_B d_B r_A$
$g_{14}$	$c_A d_A r_B$
$g_{15}$	$c_A d_B r_B$
$g_{16}$	$c_B d_A r_B$
$g_{17}$	$c_B d_B r_B$

These are the $2 \times 2 \times 2 = 8$ products $\{r_A, r_B\} \times \{c_A, c_B\} \times \{d_A, d_B\}$. Each measures a coupling among one row contrast, one column contrast, and one interaction contrast. For example, $g_{11} = c_A d_B r_A$ measures the coupling of player 1’s column contrast with player 2’s interaction and player 1’s row contrast. A large positive value of $g_{11}$ indicates that player 1’s column contrast and row contrast are both strong and aligned with player 2’s interaction, while a large negative value indicates that they are both strong but anti-aligned with player 2’s interaction.

The cubic generators contain sign information not present in the quadratic magnitudes alone. For example, the quadratic invariants determine $r_A^2,c_A^2,d_A^2$, but not the sign of the triple product $r_Ac_Ad_A$.

Relations (Syzygies) Among the Generators

The first relations (also called syzygies) occur in degree $4$. There are three degree-$4$ relations, all of the form $(xy)^2=x^2y^2$:

\[ (r_A r_B)^2 = r_A^2 \cdot r_B^2 \] \[ (c_A c_B)^2 = c_A^2 \cdot c_B^2 \] \[ (d_A d_B)^2 = d_A^2 \cdot d_B^2 \]

In degree $5$, the product map has $24$ relations. These are binomial relations of the form $g_i g_j=g_k g_l$, arising when two products of generators expand to the same underlying monomial.

Table 5: Low-degree syzygy counts for the $(2,2)$ invariant ring (see Section 16.3)

Degree	Products	Rank	Syzygies
4	45	42	3
5	72	48	24

Table 5 lists the number of relations in degrees 4 and 5. We do not claim this is a complete list of syzygies, only that these are all the relations among products of generators in these degrees.

Game-Theoretic Conditions in Invariant Coordinates

We now express several standard game-theoretic conditions in the invariant coordinates. The point is that these conditions are invariant under relabeling, and they also become explicit polynomial equations or inequalities in the generators.

Game Classes and Interaction Conditions

The relabeling-invariant classes below correspond to polynomial equations or inequalities in the generators (Table 6).

Table 6: Game classes as polynomial conditions or inequalities in the generators

Class	Condition in generators	Coordinate meaning
Potential	$g_5=g_6=g_9$	$d_A=d_B$
Anti-potential	$g_5=g_9=-g_6$	$d_A=-d_B$
Zero-sum	$g_1=g_7=-g_2$, $g_3=g_8=-g_4$, $g_5=g_9=-g_6$	$B=-A$
Interaction-aligned	$g_6>0$	$d_A d_B>0$
Interaction-opposed	$g_6<0$	$d_A d_B<0$

A symmetric game is a two-player game in which the two players have the same strategy set and exchanging the players transposes the payoff matrices. In a chosen labeling of the shared strategy set, this means

\[ B=A^\top \]

equivalently

\[ r_B=c_A,\qquad c_B=r_A,\qquad d_B=d_A \]

These equations depend on the chosen identification between player 1’s row labels and player 2’s column labels. Since the quotient in this section allows independent relabelings of the two players’ strategies, the invariant version of the condition is that the game has some representative in its relabeling orbit satisfying $B=A^\top$. ³

On the other hand, the potential, anti-potential, zero-sum, and interaction-alignment conditions above are all expressible using degree-$2$ invariants alone.

Dominance and Solvability

The degree-$2$ generators detect more than interaction alignment. They also detect whether a player has a strictly dominant pure strategy. In a $(2,2)$-game, dominance is controlled by the comparison between a player’s own-strategy contrast and their interaction contrast. For player 1 this comparison is $r_A^2$ versus $d_A^2$; for player 2 it is $c_B^2$ versus $d_B^2$.

We say that a strict ordinal $(2,2)$-game is solvable by iterated strict dominance if repeated elimination of strictly dominated strategies terminates at a unique strategy profile.

Player 1 has a strictly dominant strategy if and only if one row of $A$ strictly dominates the other against both columns. In mean-zero coordinates, the payoff differences between row 1 and row 2 are

\[ \frac{r_A+d_A}{2} \]

when player 2 plays column 1, and

\[ \frac{r_A-d_A}{2} \]

when player 2 plays column 2. Row 1 strictly dominates row 2 if both differences are positive, i.e. $r_A>|d_A|$. Row 2 strictly dominates row 1 if both are negative, i.e. $-r_A>|d_A|$. Therefore player 1 has a strictly dominant row if and only if

\[ r_A^2>d_A^2 \]

Similarly, player 2 has a strictly dominant column if and only if

\[ c_B^2>d_B^2 \]

In a strict ordinal $(2,2)$-game, if either player has a strictly dominant strategy, iterated strict dominance terminates at a single profile: after the dominated strategy is removed, the remaining player has a strict preference between the two remaining outcomes. If neither player has a strictly dominant strategy, then no strategy is eliminated at the first step, so the process cannot begin.

Proposition 2 (Solvability) A strict ordinal $(2,2)$-game is solvable by iterated strict dominance if and only if

\[ r_A^2 > d_A^2 \quad \text{or} \quad c_B^2 > d_B^2 \]

Equivalently, at least one player’s own-strategy contrast exceeds their interaction contrast in magnitude.

The first inequality is exactly the condition that one row of $A$ strictly dominates the other. The second is exactly the condition that one column of $B$ strictly dominates the other. If either holds, then in a strict ordinal game the first elimination leaves the other player with a strict choice between two remaining outcomes, so elimination terminates at a unique profile. If both inequalities fail, neither player has a strictly dominated strategy at the first step, so iterated strict dominance cannot begin.

Each condition is a polynomial inequality in the degree-$2$ generators:

\[ g_1>g_5 \]

or \[ g_8>g_9 \]

Thus solvability by iterated strict dominance is a semialgebraic condition in the quotient.

Mixed Nash Equilibrium Candidate

We now turn from pure-strategy dominance to fully mixed equilibria. In a fully mixed equilibrium, each player must be indifferent between their two pure strategies. For $(2,2)$-games, these indifference conditions are two linear equations: one determines player 2’s mixing probability, and the other determines player 1’s mixing probability.

For player 1, the expected payoff difference between row 1 and row 2 is

\[ y\cdot \frac{r_A+d_A}{2}+(1-y)\cdot \frac{r_A-d_A}{2} \]

where $y$ is the probability that player 2 plays column 1. Setting this equal to zero gives

\[ 2d_Ay+r_A-d_A=0 \]

Thus player 1’s indifference equation is nondegenerate exactly when $d_A\neq 0$.

Similarly, if $x$ is the probability that player 1 plays row 1, player 2’s expected payoff difference between column 1 and column 2 is

\[ x\cdot \frac{c_B+d_B}{2}+(1-x)\cdot \frac{c_B-d_B}{2} \]

so player 2’s indifference equation is

\[ 2d_Bx+c_B-d_B=0 \]

This equation is nondegenerate exactly when $d_B\neq 0$.

Therefore the determinant product of the two mixed-indifference equations is, up to the irrelevant scalar factor $4$,

\[ \operatorname{disc}_{2,2}=d_A d_B=g_6 \]

Thus $g_6$ detects whether the mixed-indifference equations are nondegenerate. If $d_A d_B\neq 0$, the equations have a unique mixed-equilibrium candidate:

\[ x^*=\frac{d_B-c_B}{2d_B} \] \[ y^*=\frac{d_A-r_A}{2d_A} \]

It is interior (all players have positive probabilities for all strategies) whenever

\[ |c_B|<|d_B| \] and \[ |r_A|<|d_A| \]

In generator coordinates, this is

\[ g_8<g_9 \] \[ g_1<g_5 \]

Therefore, the degree-$2$ generators detect whether a fully mixed equilibrium exists, and if so, whether it is interior. The degree-$2$ generator $g_6=d_A d_B$ detects whether the mixed-indifference equations are nondegenerate, i.e., whether a unique mixed-equilibrium candidate exists.

Named Game Examples

The values in Table 8 depend on the particular cardinal representatives chosen for each named game. We use the following representatives:

Table 7: Cardinal representatives used for the named-game computations

Game	$A$	$B$
Prisoner’s Dilemma	$\begin{pmatrix}3&0\\5&1\end{pmatrix}$	$\begin{pmatrix}3&5\\0&1\end{pmatrix}$
Stag Hunt	$\begin{pmatrix}4&0\\3&3\end{pmatrix}$	$\begin{pmatrix}4&3\\0&3\end{pmatrix}$
Chicken	$\begin{pmatrix}3&1\\5&0\end{pmatrix}$	$\begin{pmatrix}3&5\\1&0\end{pmatrix}$
Pure Coordination	$\begin{pmatrix}1&0\\0&1\end{pmatrix}$	$\begin{pmatrix}1&0\\0&1\end{pmatrix}$
Matching Pennies	$\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$	$\begin{pmatrix}-1&1\\1&-1\end{pmatrix}$

The raw invariant values depend on the chosen cardinal representatives, so the point of the examples is not the numerical values themselves. The point is that simple combinations of the generators recover familiar strategic features. For example, $g_6$ records interaction alignment, while $g_1-g_5$ and $g_8-g_9$ detect strict dominance for players 1 and 2.

Table 8: Degree-2 invariant diagnostics for the cardinal representatives in Table 7 (see Section 16.1)

Game	$g_6=d_A d_B$	$g_1-g_5$	$g_8-g_9$	Diagnosis
PD	1	8	8	both players dominant; interaction-aligned
Stag Hunt	16	$-12$	$-12$	no dominance; interaction-aligned
Chicken	9	$-8$	$-8$	no dominance; interaction-aligned in $d$
Pure Coord	4	$-4$	$-4$	pure interaction; no dominance
Match Penn	$-16$	$-16$	$-16$	interaction-opposed; no dominance

The full degree-$2$ and degree-$3$ generator values for these representatives are recorded in Appendix A.

The table is diagnostic for our given representatives.The Prisoner’s Dilemma is singled out by the dominance inequalities $g_1>g_5$ and $g_8>g_9$, so both players have strictly dominant strategies. Stag Hunt, Chicken, Pure Coordination, and Matching Pennies all fail these inequalities.

The sign of $g_6=d_A d_B$ can be interpreted as the interaction alignment. The intuition is that two players are interaction-aligned if, when they jointly coordinate, the resulting payoff perturbations agree. Matching Pennies is interaction-opposed, while the other representatives are interaction-aligned. The quantity $d_A d_B$ is not a complete test for coordination versus anti-coordination: Chicken is a counterexample, anti-coordination-like in its best-response structure but not interaction-opposed in this invariant sense⁴.

Relation to Robinson-Goforth Ordinal Types

Robinson and Goforth (2005) classified $(2,2)$-games by the relative order of each player’s four payoffs, identifying games that differ only by strategy relabeling. For games with no payoff ties, their equivalence relation is the same as ours, which is that two games are equivalent if one can be obtained from the other by independently swapping rows and columns, i.e. by the action of $S_2\times S_2$. Robinson and Goforth’s classification gives $144$ no-tie types.

We now show how to recover those types from the invariant values. The output will be a canonical $12$-sign vector. This makes the Robinson-Goforth type a concrete object:

\[ (g_1,\ldots,g_{17}) \longmapsto (\pm1,\ldots,\pm1) \]

Explicit Robinson-Goforth Representatives

We first need to define a representative for each Robinson-Goforth type. The idea is to take the lexicographically minimal sign vector obtained by applying the $S_2\times S_2$ action to the original game. It is not strictly necessary to use the lexicographic minimum (any consistent choice will work), but it is a convenient choice that gives a unique representative for each row-column orbit.

Label the four outcomes by

\[ 1=(1,1) \]

\[ 2=(1,2) \]

\[ 3=(2,1) \]

\[ 4=(2,2) \]

For a game with no payoff ties, define the player 1 comparison vector

\[ \Sigma_A= \big( \operatorname{sign}(a_1-a_2), \operatorname{sign}(a_1-a_3), \operatorname{sign}(a_1-a_4), \operatorname{sign}(a_2-a_3), \operatorname{sign}(a_2-a_4), \operatorname{sign}(a_3-a_4) \big) \]

Define $\Sigma_B$ analogously from $b_1,b_2,b_3,b_4$. The labeled ordinal form of the game is

\[ \Sigma(A,B)=(\Sigma_A,\Sigma_B)\in\{\pm1\}^{12} \]

Not every vector in $\{\pm1\}^{12}$ can occur. The six signs for each player must come from a transitive order of four payoffs. For example, one cannot have $a_1>a_2>a_3>a_4>a_1$.

Row and column swaps act on the outcome labels by

\[ \rho=(13)(24) \]

\[ \kappa=(12)(34) \]

Thus

\[ S_2\times S_2=\{e,\rho,\kappa,\rho\kappa\} \]

acts on $\Sigma(A,B)$ by relabeling the outcome indices in every comparison. We define the Robinson-Goforth representative of a no-tie game to be the canonical sign vector

\[ \operatorname{RG}(A,B) = \min_{\mathrm{lex}} \{\Sigma(h\cdot(A,B)):h\in S_2\times S_2\} \]

where lexicographic order uses $-1<+1$. This lexicographic choice is only a naming convention: it selects one representative from each row-column orbit.

For example, using the Prisoner’s Dilemma representative

\[ A= \begin{pmatrix} 3&0\\ 5&1 \end{pmatrix} \]

\[ B=A^\top \]

we get

\[ \operatorname{RG}(A,B) = (-1,-1,-1,+1,-1,-1,\,+1,+1,+1,+1,+1,+1) \]

For the Stag Hunt representative

\[ A= \begin{pmatrix} 4&0\\ 3&2 \end{pmatrix} \]

\[ B=A^\top \]

we get

\[ \operatorname{RG}(A,B) = (-1,-1,-1,+1,+1,-1,\,-1,+1,+1,+1,+1,+1) \]

For the Chicken representative

\[ A= \begin{pmatrix} 3&1\\ 4&0 \end{pmatrix} \]

\[ B=A^\top \]

we get

\[ \operatorname{RG}(A,B) = (-1,-1,-1,+1,+1,-1,\,-1,-1,-1,-1,-1,+1) \]

For a no-tie Matching Pennies representative, take

\[ A= \begin{pmatrix} 4&1\\ 2&3 \end{pmatrix} \]

\[ B=-A \]

Then

\[ \operatorname{RG}(A,B) = (-1,-1,-1,+1,+1,+1,\,+1,+1,+1,-1,-1,-1) \]

The standard $\pm1$ Matching Pennies matrix has payoff ties, so it produces zero entries in this sign vector and is not one of the $144$ no-tie Robinson-Goforth types. A no-tie representative such as the one above should be used when referring to its Robinson-Goforth type.

Computable Map from Invariants to Robinson-Goforth Representatives

Let

\[ \lambda=(\lambda_1,\ldots,\lambda_{17}) \]

be a valid vector of generator values, so that

\[ \lambda_i=g_i(A,B) \]

for some $(2,2)$-game. We define a computable map

\[ F(\lambda)=\operatorname{RG}(A,B) \]

from invariant values to canonical Robinson-Goforth representatives.

First extract the six contrast magnitudes from the degree-$2$ generators:

\[ R_A=\sqrt{\lambda_1} \]

\[ C_A=\sqrt{\lambda_3} \]

\[ D_A=\sqrt{\lambda_5} \]

\[ R_B=\sqrt{\lambda_7} \]

\[ C_B=\sqrt{\lambda_8} \]

\[ D_B=\sqrt{\lambda_9} \]

The $\lambda_i$ are always non-negative because they are squares of real numbers.

Now form the finite set $C(\lambda)$ of contrast vectors

\[ x=(r_A,c_A,d_A,r_B,c_B,d_B) \]

with these magnitudes and with generator values $\lambda$. That is, each coordinate has the prescribed absolute value,

\[ r_A\in\{\pm R_A\} \]

\[ c_A\in\{\pm C_A\} \]

\[ d_A\in\{\pm D_A\} \]

\[ r_B\in\{\pm R_B\} \]

\[ c_B\in\{\pm C_B\} \]

\[ d_B\in\{\pm D_B\} \]

with the convention that if a magnitude is zero then the corresponding coordinate is zero. We then keep only those sign choices satisfying

\[ g_i(x)=\lambda_i \]

for every

\[ i=1,\ldots,17 \]

There are at most $2^6$ sign choices to check, and fewer when some magnitudes vanish.

For each surviving $x\in C(\lambda)$, compute the comparison-sign vector

\[ \Sigma(x)=(\Sigma_A(x),\Sigma_B(x)) \]

where

\[ \Sigma_A(x)= \operatorname{sign} \big( c_A+d_A,\, r_A+d_A,\, r_A+c_A,\, r_A-c_A,\, r_A-d_A,\, c_A-d_A \big) \]

and

\[ \Sigma_B(x)= \operatorname{sign} \big( c_B+d_B,\, r_B+d_B,\, r_B+c_B,\, r_B-c_B,\, r_B-d_B,\, c_B-d_B \big) \]

The Robinson-Goforth representative is the canonical row-column representative

\[ F(\lambda) = \min_{\mathrm{lex}} \{ h\cdot\Sigma(x):x\in C(\lambda),\ h\in S_2\times S_2\} \]

This is the desired map

\[ F:(g_1,\ldots,g_{17}) \longmapsto \{\text{canonical Robinson-Goforth sign vectors}\} \]

The definition is independent of the chosen surviving sign pattern $x$. Indeed, if two contrast vectors have the same full generator values, then they lie in the same $S_2\times S_2$ orbit, since the invariant ring separates row-column relabeling orbits. Canonicalizing the sign vector removes this ambiguous relabeling.

If a payoff tie occurs, one or more entries of $\Sigma(x)$ is $0$, so the sign vector lies in

\[ \{-1,0,+1\}^{12} \]

rather than

\[ \{\pm1\}^{12} \]

Such a game is not one of the $144$ no-tie Robinson-Goforth types, but the same construction still returns its row-column relabeling class as a weak sign vector.

The above construction uses finite enumeration of sign patterns, but this is not the only possible way to compute the Robinson-Goforth representative from invariant values. One could instead derive case-by-case formulas for the comparison signs in terms of the generator values. Those formulas would be less transparent than the finite construction above. The enumeration is not part of the definition of the invariant quotient, being just a practical way to evaluate the map from invariant coordinates to the canonical Robinson-Goforth sign vector in the $(2,2)$ case. For actual payoff tables, the sign vector can be computed directly from payoff comparisons and then canonicalized under row and column relabeling. Alternatively, we can simply use the invariant coordinates to classify games directly, without reference to the Robinson-Goforth types at all.

The Invariant Ring of $(n,k)$-Games

We now extend the construction from the $(2,2)$ case to arbitrary $(n,k)$-games. An $(n,k)$-game has $n$ players, each with $k$ strategies, so its payoff space is $V_{n,k} = \mathbb{R}^{nk^n}$. The main symmetry group is still the strategy-relabeling group, $G_{n,k} = (S_k)^n$. An element $(\sigma_1, \ldots, \sigma_n) \in (S_k)^n$ relabels player $i$’s strategies by $\sigma_i$, and applies the corresponding permutation to the $i$-th strategy coordinate in every player’s payoff array. Players remain distinguishable throughout this section (see Appendix C for discussion of the enlarged group).

This section describes the invariant ring $\mathbb{R}[V_{n,k}]^{G_{n,k}}$ using the same logic as in the $(2,2)$ case. First, we remove player-specific payoff means. Second, we decompose the mean-zero payoff space into contrast blocks indexed by non-empty subsets of strategy coordinates. Third, we construct relabeling-invariant polynomials from these blocks by Reynolds averaging.

Setup: Payoff Space and Relabeling Group

For each player $p \in \{1, \ldots, n\}$, let $u_p : \{1, \ldots, k\}^n \to \mathbb{R}$ be player $p$’s payoff function. We write a (pure) strategy profile as $s = (s_1, \ldots, s_n)$. The group $G_{n,k} = (S_k)^n$ acts by

\[ ((\sigma_1, \ldots, \sigma_n) \cdot u_p)(s_1, \ldots, s_n) = u_p(\sigma_1^{-1}(s_1), \ldots, \sigma_n^{-1}(s_n)) \]

The same strategy relabeling is applied to every player’s payoff array because all payoff arrays are indexed by the same pure strategy profiles. For $n = 2$, this is the row and column relabeling we saw in the $(2,2)$ case.

Mean-Zero Coordinates and Contrast Blocks

As in the $(2,2)$ case, we first remove payoff means. For each player $p$, define the player-specific payoff mean

\[ \overline{u}_p = \frac{1}{k^n} \sum_{s \in \{1, \ldots, k\}^n} u_p(s) \]

Subtracting this mean gives the mean-zero payoff array $u_p^0(s) = u_p(s) - \overline{u}_p$. After removing these $n$ player-specific means, the mean-zero payoff space has dimension $n(k^n - 1)$.

We now decompose each mean-zero payoff array into contrast blocks. A contrast type is indexed by a non-empty subset $S \subseteq \{1, \ldots, n\}$. For each type $S$ and each player $p$, let $C_{S,p}$ be the corresponding contrast block, with \[ \dim C_{S,p}=(k-1)^{|S|} \]

For a particular game, let $T_{S,p}\in C_{S,p}$ denote player $p$’s component of type $S$. This component measures the part of player $p$’s payoff array that varies jointly with the strategy coordinates in $S$, after averaging over the coordinates not in $S$ and subtracting lower-order effects.

For a $(2,2)$-game, the non-empty subsets of $\{1,2\}$ are $\{1\}, \{2\}, \{1,2\}$. For player $1$, these are exactly the row contrast, column contrast, and interaction contrast: $T_{\{1\},1} = r_A$, $T_{\{2\},1} = c_A$, $T_{\{1,2\},1} = d_A$. For player $2$: $T_{\{1\},2} = r_B$, $T_{\{2\},2} = c_B$, $T_{\{1,2\},2} = d_B$.

Proposition 3 (Mean-Zero Contrast Decomposition) For every $(n,k)$-game, the mean-zero payoff space decomposes as

\[ V_{n,k}^{0} = \bigoplus_{p=1}^{n} \bigoplus_{\emptyset\neq S\subseteq \{1,\ldots,n\}} C_{S,p} \]

where $\dim C_{S,p} = (k-1)^{|S|}$. Thus

\[ \dim V_{n,k}^{0} = \sum_{p=1}^{n} \sum_{\emptyset \neq S \subseteq \{1, \ldots, n\}} (k-1)^{|S|} = n(k^n - 1) \]

Proof. Fix a player $p$. The payoff array $u_p$ can be identified with an element of $(\mathbb{R}^k)^{\otimes n}$, with one tensor factor for each strategy coordinate. In each factor, decompose

\[ \mathbb{R}^k=\mathbf{1}\oplus W \]

where $\mathbf{1}$ is the one-dimensional constant subspace and $W$ is the $(k-1)$-dimensional contrast subspace consisting of vectors whose coordinates sum to zero.

Expanding \[ (\mathbf{1}\oplus W)^{\otimes n} \]

gives one summand for each subset $S\subseteq \{1,\ldots,n\}$. $W$ is used in the factors indexed by $S$ and $\mathbf{1}$ is used in the remaining factors. The summand with $S=\emptyset$ is the constant payoff component. That is, the player-specific payoff mean. Removing this component leaves exactly the summands indexed by non-empty subsets $S$.

For a fixed non-empty $S$, the corresponding block has dimension \[ (k-1)^{|S|} \]

Summing over all non-empty $S$ and then over all $n$ players gives

\[ \dim V_{n,k}^{0} = \sum_{p=1}^{n} \sum_{\emptyset\neq S\subseteq \{1,\ldots,n\}} (k-1)^{|S|} = n(k^n-1) \]

For $k = 2$, each block is one-dimensional, so the contrast types are simply the $2^n - 1$ non-empty subsets. For $k = 3$, each strategy coordinate contributes two independent contrast directions, so $\dim T_{S,p} = 2^{|S|}$. In general, the dimension count is

\[ \sum_{\emptyset \neq S \subseteq \{1, \ldots, n\}} n (k-1)^{|S|} = n \sum_{m=1}^{n} \binom{n}{m} (k-1)^m = n(k^n - 1) \]

For example, in a $(3,3)$-game, the mean-zero subspace has dimension $3(27 - 1) = 78$.

The seven contrast types are summarized in Table 9:

Table 9: Contrast decomposition for one payoff array in a $(3,3)$-game. Since there are three players, the full mean-zero payoff space has dimension $3\cdot 26=78$.

Type $S$	$\|S\|$	Count of types	Dim of each block	Total per payoff array
Main effects ($\{i\}$)	1	3	$(3-1)^1 = 2$	$3 \times 2 = 6$
Two-way interactions ($\{i,j\}$)	2	3	$(3-1)^2 = 4$	$3 \times 4 = 12$
Three-way interaction ($\{1,2,3\}$)	3	1	$(3-1)^3 = 8$	$1 \times 8 = 8$
Totals		7 types		26

The Relabeling Action on Contrast Blocks

The group $G_{n,k} = (S_k)^n$ preserves the contrast-block decomposition. If $\sigma = (\sigma_1, \ldots, \sigma_n) \in G_{n,k}$, then the factor $\sigma_i$ acts on a block $T_{S,p}$ whenever $i \in S$. If $i \notin S$, then relabeling player $i$’s strategies does not affect the block $T_{S,p}$. Thus relabeling can permute coordinates inside a block, but can’t turn a type-$S$ block into a type-$S'$ block.

For $k = 2$, every block is one-dimensional. Relabeling strategy coordinate $i$ changes the sign of the contrast coordinates whose type $S$ contains $i$. This is the sign-flip action from the $(2,2)$ section. For $k > 2$, the relabeling action is more complicated, as it can permute the multiple contrast directions within a block. The key point is that the relabeling action preserves the block structure, so we can analyze invariants block-by-block.

Complete Classification by Invariants

We now apply the invariant-theoretic quotient construction to arbitrary $(n,k)$-games.

Theorem 2 (Complete Classification) Let $G_{n,k} = (S_k)^n$ act on the mean-zero payoff space $V_{n,k}^{0}$ by relabeling each player’s strategy set. Let $f_1, \ldots, f_r$ be any finite generating set of the invariant ring

\[ \mathbb{R}[V_{n,k}^{0}]^{G_{n,k}} \]

Then the map

\[ \Phi : V_{n,k}^{0} \to \mathbb{R}^r \] \[ u \mapsto (f_1(u), \ldots, f_r(u)) \]

is constant on strategy-relabeling orbits and separates those orbits. Therefore two mean-zero games $u, v \in V_{n,k}^{0}$ have the same invariant coordinates if and only if they differ by a relabeling of strategies.

By the above, for every fixed $(n,k)$, the invariant ring gives a complete cardinal classification of $(n,k)$-games modulo strategy relabeling and player-specific payoff shifts. The statement above takes any finite generating set $\{f_1, \ldots, f_r\}$ as input. Theorem 6 builds a generating set explicitly via the contrast-block Reynolds construction.

Proof. Because $G_{n,k}$ is finite, the invariant ring is finitely generated. If two games lie in the same orbit, all invariant polynomials take the same values on them. Conversely, finite-group invariant polynomials separate orbits. Since $f_1, \ldots, f_r$ generate the invariant ring, equality of the generator values implies equality of every invariant polynomial, hence the two games lie in the same orbit.

The generating set need not be the smallest set that separates orbits. A separating subset is sufficient. We say a subset is separating if it is a subset $S \subseteq \mathbb{R}[V]^G$ that separates orbits if two points lie in the same orbit whenever every $f \in S$ takes the same value on them. Separating subsets can be much smaller than generating sets, and the following theorem of Derksen and Kemper gives a uniform bound.

Theorem 3 (Derksen-Kemper separating bound (Derksen and Kemper 2015, Thm. 2.3.15)) For any finite group $G$ acting linearly on a finite-dimensional real vector space $V$, the invariant ring $\mathbb{R}[V]^G$ admits a separating subset of size at most $2 \dim V + 1$.

For the present setting, $\dim V_{n,k}^{0} = n(k^n - 1)$. The Derksen-Kemper bound gives an explicit upper bound on the number of polynomial invariants needed to distinguish all $(S_k)^n$-orbits of $(n,k)$-games. For $(2,2)$ this is $2 \cdot 6 + 1 = 13$, but the actual generating set has 17 generators, which is also separating but is not the minimum. For $(3,3)$ the bound gives $2 \cdot 78 + 1 = 157$ invariants, considerably smaller than the full generating set ($42$ degree-$2$ plus at least $556$ degree-$3$ generators (see Proposition 5 for the binary $(n,2)$ analog of this count).⁵

Degree-2 Family Matrices

The degree-2 invariants in the $(n,k)$ setting generalize the nine quadratic generators from the $(2,2)$ section, which were $r_A^2, r_A r_B, r_B^2$, then $c_A^2, c_A c_B, c_B^2$, and $d_A^2, d_A d_B, d_B^2$.

In the general case, each scalar contrast is replaced by a contrast block $T_{S,p}$, where $S$ is a non-empty subset of strategy indices and $p$ is the player whose payoff array is being measured. For each contrast type $S$ and each pair of players $p, q$, define

\[ M_S[p,q] = \langle T_{S,p}, T_{S,q} \rangle \]

Here the inner product is the natural Euclidean inner product on the contrast block

\[ C_S\cong \bigotimes_{i\in S} W_k \] \[ W_k=\mathbf 1^\perp\subset \mathbb R^k \]

Equivalently, after choosing the standard contrast coordinates in the block, it is the coordinatewise sum

\[ \langle T_{S,p},T_{S,q}\rangle = \sum_a T_{S,p}^aT_{S,q}^a \]

This is invariant under strategy relabeling because relabeling acts in the same way on $T_{S,p}$ and $T_{S,q}$.

For each $S$, the degree-$2$ invariants form an $n \times n$ symmetric matrix $M_S = (M_S[p,q])_{p,q=1}^{n}$. The diagonal entries $M_S[p,p]$ measure the magnitude of player $p$’s payoff variation of type $S$. The off-diagonal entries $M_S[p,q]$ measure “alignment” between players $p$ and $q$ in that same contrast type.

For each of the $2^n - 1$ contrast types $S$, and each unordered pair of players $(p,q)$ with $p = q$ allowed, there is one degree-$2$ invariant. The number of such player pairs is $\binom{n+1}{2} = n(n+1)/2$.

Theorem 4 (Degree-2 Gram image) Fix a non-empty contrast type $S\subseteq \{1,\ldots,n\}$ and write \[ m_S=(k-1)^{|S|} \]

The family matrix \[ M_S[p,q]=\langle T_{S,p},T_{S,q}\rangle \]

is the Gram matrix of $n$ vectors in an $m_S$-dimensional contrast block. Therefore M_S is a positive semidefinite $n\times n$ matrix of rank at most $m_S$.

Conversely, every positive semidefinite $n\times n$ matrix of rank at most $m_S$ occurs as $M_S$ for some choice of contrast components $T_{S,1},\ldots,T_{S,n}$.

Proof. Fix a non-empty contrast type $S\subseteq \{1,\ldots,n\}$, and let \[ C_S \cong \mathbb{R}^{m_S}, \qquad m_S=(k-1)^{|S|} \]

be the corresponding contrast block. For each player $p$, identify the copy $C_{S,p}$ with $C_S$, and write \[ v_p := T_{S,p}\in C_S \]

Then \[ M_S[p,q]=\langle T_{S,p},T_{S,q}\rangle =\langle v_p,v_q\rangle \]

Thus $M_S$ is exactly the Gram matrix of the vectors \[ v_1,\ldots,v_n\in C_S \]

It follows immediately that $M_S$ is positive semidefinite. Indeed, for any $\alpha=(\alpha_1,\ldots,\alpha_n)\in\mathbb{R}^n$, \[ \alpha^\top M_S \alpha = \sum_{p,q=1}^n \alpha_p\alpha_q \langle v_p,v_q\rangle = \left\langle \sum_{p=1}^n \alpha_p v_p,\, \sum_{q=1}^n \alpha_q v_q \right\rangle = \left\|\sum_{p=1}^n \alpha_p v_p\right\|^2 \geq 0 \]

Therefore $M_S\succeq 0$.

Also, if $A$ is the $m_S\times n$ matrix whose $p$-th column is $v_p$, then \[ M_S=A^\top A \]

Hence \[ \operatorname{rank}(M_S) = \operatorname{rank}(A^\top A) = \operatorname{rank}(A) \leq m_S \]

Conversely, let $M$ be any positive semidefinite $n\times n$ matrix with \[ \operatorname{rank}(M)=r\leq m_S \]

By the spectral theorem, there are orthonormal vectors $u_1,\ldots,u_r\in\mathbb{R}^n$ and positive eigenvalues $\lambda_1,\ldots,\lambda_r>0$ such that \[ M=\sum_{\ell=1}^r \lambda_\ell u_\ell u_\ell^\top \]

Define vectors $v_1,\ldots,v_n\in\mathbb{R}^{m_S}$ by \[ v_p = \big( \sqrt{\lambda_1}\,u_1(p), \ldots, \sqrt{\lambda_r}\,u_r(p), 0,\ldots,0 \big), \]

where the remaining $m_S-r$ coordinates are zero. Then for every $p,q$, \[ \langle v_p,v_q\rangle = \sum_{\ell=1}^r \lambda_\ell u_\ell(p)u_\ell(q) = M[p,q] \]

Thus $M$ is the Gram matrix of $n$ vectors in an $m_S$-dimensional contrast block.

Finally, because the mean-zero payoff space decomposes as a direct sum of the contrast blocks \[ V_{n,k}^{0} = \bigoplus_{p=1}^{n} \bigoplus_{\emptyset\neq S\subseteq \{1,\ldots,n\}} C_{S,p} \]

the components $T_{S,1},\ldots,T_{S,n}$ may be chosen independently inside their type-$S$ blocks. Therefore the vectors $v_1,\ldots,v_n$ constructed above can be realized as the contrast components \[ T_{S,1},\ldots,T_{S,n} \]

of some mean-zero game, for instance by setting all other contrast components to zero. Hence every positive semidefinite $n\times n$ matrix of rank at most $m_S$ occurs as $M_S$.

Theorem 5 (Degree-2 Family Count) The degree-$2$ mean-zero invariant layer has one family matrix $M_S$ for each non-empty contrast type $S\subseteq \{1,\ldots,n\}$. Therefore its dimension is

\[ h_2 = (2^n - 1) \cdot \frac{n(n+1)}{2} \]

for all $k \geq 2$. In particular, the degree-$2$ count depends on $n$ but not on $k$.

Proof. Let \[ W=\mathbf{1}^\perp\subset \mathbb{R}^k \]

be the standard $(k-1)$-dimensional contrast representation of $S_k$. For each non-empty $S\subseteq \{1,\ldots,n\}$, the type-$S$ contrast block is naturally isomorphic to \[ U_S=\bigotimes_{i\in S} W_i \]

with the remaining tensor factors constant. Thus \[ C_{S,p}\cong U_S \]

for each player $p$.

Degree-$2$ invariants are $G_{n,k}$-invariant bilinear pairings among the contrast blocks. If $S\neq S'$, then some strategy coordinate $i$ lies in exactly one of $S,S'$. In that coordinate, one block carries the contrast representation $W_i$, while the other carries the trivial representation. Since $W_i$ has no $S_k$-invariant vectors, there is no nonzero invariant pairing between $U_S$ and $U_{S'}$. Therefore degree-$2$ invariants only pair blocks of the same contrast type.

Now fix $S$. The representation $U_S=\bigotimes_{i\in S}W_i$ has, up to scale, a unique invariant inner product, namely the tensor-product Euclidean inner product. Hence for every pair of players $p,q$, the unique degree-$2$ invariant pairing between $C_{S,p}$ and $C_{S,q}$ is \[ M_S[p,q]=\langle T_{S,p},T_{S,q}\rangle =\sum_a T_{S,p}^aT_{S,q}^a \]

Because $M_S[p,q]=M_S[q,p]$, a fixed contrast type $S$ contributes one invariant for each unordered player pair $p\le q$. There are \[ \binom{n+1}{2}=\frac{n(n+1)}2 \]

such pairs.

Finally, there are $2^n-1$ non-empty contrast types $S\subseteq \{1,\ldots,n\}$. Therefore \[ h_2 = (2^n-1)\binom{n+1}{2} = (2^n-1)\frac{n(n+1)}2 \]

We can verify this by Molien computation for some low-degree

Table 10: Degree-2 invariant count $h_2 = (2^n - 1) \cdot n(n+1)/2$

$n$	$2^n - 1$	$\frac{n(n+1)}{2}$	$h_2$
2	3	3	9
3	7	6	42
4	15	10	150
5	31	15	465

The formula factorizes as (number of contrast types) $\times$ (number of player pairs); Table 10 tabulates the count through $n = 5$. The contrast types depend on $n$ but not on $k$, while the player pairs depend on $n$ alone.

Example: Family Structure for $(3,3)$-Games

For a $(3,3)$-game, the degree-$2$ generators form $2^3 - 1 = 7$ families. Each family contains $3(3+1)/2 = 6$ generators, so there are $7 \cdot 6 = 42$ degree-$2$ generators in total. We organize these into family matrices, with one row per contrast type (Table 11):

Table 11: Family structure for $(3,3)$-games: 7 families of 6 generators each

Family (type $S$)	Interpretation	Generators
$\{1\}$	Payoff variation with strategy coordinate 1	$\langle T_{\{1\},p},T_{\{1\},q}\rangle$ for $1\leq p\leq q\leq 3$
$\{2\}$	Payoff variation with strategy coordinate 2	$\langle T_{\{2\},p},T_{\{2\},q}\rangle$ for $1\leq p\leq q\leq 3$
$\{3\}$	Payoff variation with strategy coordinate 3	$\langle T_{\{3\},p},T_{\{3\},q}\rangle$ for $1\leq p\leq q\leq 3$
$\{1,2\}$	Joint variation with coordinates 1 and 2	$\langle T_{\{1,2\},p},T_{\{1,2\},q}\rangle$ for $1\leq p\leq q\leq 3$
$\{1,3\}$	Joint variation with coordinates 1 and 3	$\langle T_{\{1,3\},p},T_{\{1,3\},q}\rangle$ for $1\leq p\leq q\leq 3$
$\{2,3\}$	Joint variation with coordinates 2 and 3	$\langle T_{\{2,3\},p},T_{\{2,3\},q}\rangle$ for $1\leq p\leq q\leq 3$
$\{1,2,3\}$	Joint variation with all three coordinates	$\langle T_{\{1,2,3\},p},T_{\{1,2,3\},q}\rangle$ for $1\leq p\leq q\leq 3$

Within each family, the 6 generators form a $3 \times 3$ symmetric matrix indexed by players:

\[ M_S = \begin{pmatrix} \langle T_{S,1}, T_{S,1} \rangle & \langle T_{S,1}, T_{S,2} \rangle & \langle T_{S,1}, T_{S,3} \rangle \\ \langle T_{S,2}, T_{S,1} \rangle & \langle T_{S,2}, T_{S,2} \rangle & \langle T_{S,2}, T_{S,3} \rangle \\ \langle T_{S,3}, T_{S,1} \rangle & \langle T_{S,3}, T_{S,2} \rangle & \langle T_{S,3}, T_{S,3} \rangle \end{pmatrix} \]

The Inductive Structure of the Generator Construction

In this subsection we describe the generator construction for the invariant ring of $(n,k)$-games inductively, starting from the $(2,2)$ case. There are two directions of generalization: we can add a player, $(n-1,k) \to (n,k)$, or we can add a strategy, $(n,k-1) \to (n,k)$. Since every $(n,k)$-game can be reached from $(2,2)$ by a sequence of these two steps, these two principles organize the generator structure for all finite games.

Base Case: The $(2,2)$ Basis in Family Language

We recall the generators of the $(2,2)$ invariant ring under $S_2 \times S_2$, now presented in the family language. The contrast types are $\{1\}, \{2\}, \{1,2\}$, corresponding to row contrast, column contrast, and interaction contrast: $\{1\} \leftrightarrow r$, $\{2\} \leftrightarrow c$, $\{1,2\} \leftrightarrow d$. Since $k = 2$, each contrast block is one-dimensional for each player.

The degree-2 generators organize into 3 families of 3 (Table 12):

Table 12: The $(2,2)$ family matrices in the family language

Family $S$	$M_S[A,A]$	$M_S[A,B]$	$M_S[B,B]$	Interpretation
$\{1\}$	$r_A^2$	$r_A r_B$	$r_B^2$	Row contrast magnitudes and alignment
$\{2\}$	$c_A^2$	$c_A c_B$	$c_B^2$	Column contrast magnitudes and alignment
$\{1,2\}$	$d_A^2$	$d_A d_B$	$d_B^2$	Interaction magnitudes and alignment

Each family is a $2 \times 2$ symmetric matrix $M_S$ indexed by players. The diagonal entries measure magnitudes, and the off-diagonal entry measures alignment. Since $k = 2$, the entries are scalar products $T_{S,p} T_{S,q}$.

The degree-$3$ generators are cross-family triple products. A product $T_{S_1,p_1} T_{S_2,p_2} T_{S_3,p_3}$ is invariant under $(S_2)^2$ if and only if each strategy index appears in an even number of the three types $S_1, S_2, S_3$. For $n = 2$, the only even-parity triple of types is $(\{1\}, \{2\}, \{1,2\})$: index $1$ appears in $\{1\}$ and $\{1,2\}$, index $2$ appears in $\{2\}$ and $\{1,2\}$, so each index appears twice. The degree-$3$ generators are therefore the $2^3 = 8$ products

\[ \{r_A, r_B\} \times \{c_A, c_B\} \times \{d_A, d_B\} \]

one from each family, with all player assignments.

The $(2,2)$ basis therefore has nine degree-$2$ generators from the family matrices and eight degree-$3$ generators from the cross-family triple products, for $17$ generators total.

Adding a Player: $(n-1,k) \to (n,k)$

Adding a player changes the family layer. The contrast types for an $(n-1,k)$-game are the non-empty subsets of $\{1, \ldots, n-1\}$. The contrast types for an $(n,k)$-game are the non-empty subsets of $\{1, \ldots, n\}$. Thus adding player $n$ creates exactly the new types $S \subseteq \{1, \ldots, n\}$ with $n \in S$. There are $2^{n-1}$ such new types. The old types $S \subseteq \{1, \ldots, n-1\}$ remain present.

For each old type $S$, the family matrix grows from an $(n-1) \times (n-1)$ symmetric matrix to an $n \times n$ symmetric matrix. Each old family gains the entries $M_S[p,n]$ for $1 \leq p \leq n$. Each new type $S$ with $n \in S$ contributes a new family matrix $M_S$. Since $k$ has not changed, the internal contrast-block structure is also unchanged. Adding a player changes which contrast families exist and how many player-pair entries each family has, but it doesn’t change the internal invariant structure of a fixed block.

At degree $2$, this gives the count $(2^n - 1) \cdot n(n+1)/2$.

For binary games, the degree-$3$ cross-family products are indexed by even-parity triples of contrast types. Adding a player increases both the number of contrast types and the number of player assignments. For example, in the step $(2,2) \to (3,2)$, the old binary degree-$3$ type triple is

\[ (\{1\}, \{2\}, \{1,2\}) \]

Its player assignments grow from $2^3 = 8$ to $3^3 = 27$. There are also

\[ (2^2 - 1) \cdot 2^1 = 6 \]

new type triples involving the new coordinate $3$. Together with the old triple, this gives $7$ type triples total. Hence

\[ h_3(3,2) = 3^3 \cdot 7 = 189 \]

This illustrates the recurrence of Proposition 5.

Proposition 4 (Add-Player Step For the Degree-2 Family Layer) Assume the degree-$2$ mean-zero invariant layer for $(n-1,k)$-games is indexed by pairs

\[ (S,\{p,q\}), \quad \emptyset\neq S\subseteq \{1,\ldots,n-1\}, \quad 1\le p\le q\le n-1 \]

Then the degree-$2$ mean-zero invariant layer for $(n,k)$-games is obtained as follows.

First, each old type \[ \emptyset\neq S\subseteq \{1,\ldots,n-1\} \]

remains present, and its family matrix grows from size $(n-1)\times(n-1)$ to size $n\times n$. Thus each old type contributes $n$ new entries,

\[ M_S[1,n],\ldots,M_S[n,n] \]

Second, the new contrast types are exactly the subsets \[ S\subseteq \{1,\ldots,n\} \]

with $n\in S$. There are $2^{n-1}$ such types, and each contributes a full $n\times n$ symmetric family matrix.

Therefore the add-player increment is

\[ \Delta h_2(n,k) = n(2^{n-1}-1) + 2^{n-1}\frac{n(n+1)}2 \]

Consequently, if

\[ h_2(n-1,k) = (2^{n-1}-1)\frac{(n-1)n}{2} \]

then

\[ h_2(n,k) = (2^n-1)\frac{n(n+1)}2 \]

Proof. The contrast types for $(n-1,k)$-games are the non-empty subsets of $\{1,\ldots,n-1\}$. The contrast types for $(n,k)$-games are the non-empty subsets of $\{1,\ldots,n\}$. Hence the old types are the non-empty subsets not containing $n$, and the new types are the subsets containing $n$. There are $2^{n-1}$ new types.

For an old type $S$, the internal contrast block has dimension $(k-1)^{|S|}$, which is unchanged because $k$ and $|S|$ are unchanged. But there is now one contrast component $T_{S,p}$ for each of the $n$ players. Hence the old family matrix grows from an $(n-1)\times(n-1)$ symmetric matrix to an $n\times n$ symmetric matrix. This adds exactly $n$ entries, namely the entries involving the new player index $n$.

There are $2^{n-1}-1$ old types, so old types contribute

\[ n(2^{n-1}-1) \]

new degree-$2$ invariants.

Each new type $S$ with $n\in S$ contributes a full symmetric family matrix \[ M_S[p,q]=\langle T_{S,p},T_{S,q}\rangle, \qquad 1\le p\le q\le n \]

So each new type contributes \[ \frac{n(n+1)}2 \]

degree-$2$ invariants. Since there are $2^{n-1}$ new types, the new-type contribution is

\[ 2^{n-1}\frac{n(n+1)}2 \]

Therefore

\[ \Delta h_2(n,k) = n(2^{n-1}-1) + 2^{n-1}\frac{n(n+1)}2 \]

Adding this to the inductive hypothesis gives

\[ \begin{aligned} h_2(n,k) &= (2^{n-1}-1)\frac{(n-1)n}{2} + n(2^{n-1}-1) + 2^{n-1}\frac{n(n+1)}2 \\ &= (2^{n-1}-1)\frac{n(n+1)}2 + 2^{n-1}\frac{n(n+1)}2 \\ &= (2^n-1)\frac{n(n+1)}2 \end{aligned} \]

Proposition 5 (Add-Player Step for Binary Degree-$3$ Triples) For binary games, identify contrast types with nonzero vectors in $\mathbb{F}_2^n$, using symmetric difference as addition. Let $\tau_n$ be the number of unordered triples of distinct non-empty contrast types $\{A,B,C\}$ satisfying

\[ A \triangle B \triangle C = \emptyset \]

Then

\[ \tau_n = \tau_{n-1} + (2^{n-1}-1) \cdot 2^{n-2} \]

Consequently,

\[ \tau_n = \frac{(2^n-1)(2^n-2)}{6} \]

Since each type triple admits $n^3$ player assignments, the binary degree-$3$ count satisfies

\[ h_3(n,2) = n^3 \tau_n = n^3 \cdot \frac{(2^n-1)(2^n-2)}{6} \]

Proof. For $k=2$, each contrast block is one-dimensional. The strategy swap in coordinate $i$ changes the sign of $T_{S,p}$ exactly when $i \in S$. Therefore a cubic monomial

\[ T_{A,p} T_{B,q} T_{C,r} \]

is invariant if and only if each coordinate appears in an even number of $A, B, C$. Equivalently,

\[ A \triangle B \triangle C = \emptyset \]

Now pass from $n-1$ players to $n$ players. The old triples are exactly the triples not containing $n$ in any of their three contrast types. These are the $\tau_{n-1}$ old triples.

A genuinely new invariant triple must involve the new coordinate $n$. Because the parity condition requires $n$ to occur an even number of times, the coordinate $n$ must occur in exactly two of the three contrast types. Thus every new triple has the form

\[ \{A,\ B \cup \{n\},\ C \cup \{n\}\} \]

where $\emptyset \neq A \subseteq \{1,\ldots,n-1\}$ and $A \triangle B \triangle C = \emptyset$ inside $\{1,\ldots,n-1\}$. Once $A$ and $B$ are chosen, we are forced to choose $C$ by $C = A \triangle B$.

For each fixed non-empty $A$, there are $2^{n-1}$ choices of $B$. The two new types $B \cup \{n\}$ and $(A \triangle B) \cup \{n\}$ are distinct because $A \neq \emptyset$. However, choosing $B$ or choosing $A \triangle B$ gives the same unordered pair of new types. Therefore each fixed $A$ contributes $2^{n-2}$ unordered new triples.

There are $2^{n-1}-1$ choices of non-empty $A$, so the number of genuinely new type triples is

\[ (2^{n-1}-1) \cdot 2^{n-2} \]

Hence

\[ \tau_n = \tau_{n-1} + (2^{n-1}-1) \cdot 2^{n-2} \]

With base case $\tau_2 = 1$, this recurrence solves to

\[ \tau_n = \frac{(2^n-1)(2^n-2)}{6} \]

Finally, for each unordered type triple $\{A,B,C\}$, the player indices attached to the three types may be chosen independently in $\{1,\ldots,n\}^3$. Thus each type triple contributes $n^3$ degree-$3$ invariants, giving

\[ h_3(n,2) = n^3 \tau_n = n^3 \cdot \frac{(2^n-1)(2^n-2)}{6} \]

Adding a Strategy: $(n,k-1) \to (n,k)$

Adding a strategy changes the internal representation carried by each contrast type, but not the set of contrast types. Both $(n,k-1)$-games and $(n,k)$-games have one contrast family for each non-empty subset

\[ S \subseteq \{1, \ldots, n\} \]

For type $S$, the contrast block grows from dimension

\[ (k-2)^{|S|} \]

to dimension

\[ (k-1)^{|S|} \]

The player indexing does not change. Thus each degree-$2$ family matrix remains an $n \times n$ symmetric matrix

\[ M_S[p,q] = \langle T_{S,p}, T_{S,q} \rangle \]

Therefore the degree-$2$ count is unchanged:

\[ h_2 = (2^n - 1) \cdot \frac{n(n+1)}{2} \]

Adding a strategy leaves the degree-$2$ family indexing fixed, while changing the internal form of the invariants inside each contrast block.

The Step $(2,2) \to (2,3)$

For $(2,3)$, the contrast types remain

\[ \{1\}, \qquad \{2\}, \qquad \{1,2\} \]

Write

\[ X_p^a = T_{\{1\},p}^a \qquad Y_p^b = T_{\{2\},p}^b \qquad D_p^{ab} = T_{\{1,2\},p}^{ab} \]

where $p \in \{1,2\}$, $a, b \in \{1,2,3\}$,

\[ \sum_a X_p^a = 0 \qquad \sum_b Y_p^b = 0 \]

and

\[ \sum_a D_p^{ab} = 0 \qquad \sum_b D_p^{ab} = 0 \]

Thus $X_p$ and $Y_p$ are main-effect contrast vectors, while $D_p$ is a row- and column-sum-zero interaction matrix.

The old binary cross-family cubic

\[ T_{\{1\},p_1} T_{\{2\},p_2} T_{\{1,2\},p_3} \]

stabilizes to the contraction

\[ \sum_{a,b} X_{p_1}^a Y_{p_2}^b D_{p_3}^{ab} \]

There are $2^3 = 8$ such invariants, one for each player assignment $(p_1, p_2, p_3) \in \{1,2\}^3$.

The degree-$3$ invariant layer for $(2,3)$ decomposes by type pattern as follows (Table 13).

Table 13: Degree-$3$ type-pattern decomposition for $(2,3)$

Type pattern	Invariant form	Count
$X, X, X$	$\sum_a X_p^a X_q^a X_r^a$, $p \le q \le r$	$4$
$Y, Y, Y$	$\sum_b Y_p^b Y_q^b Y_r^b$, $p \le q \le r$	$4$
$X, Y, D$	$\sum_{a,b} X_p^a Y_q^b D_r^{ab}$	$8$
$X, D, D$	$\sum_{a,b} X_p^a D_q^{ab} D_r^{ab}$, $q \le r$	$6$
$Y, D, D$	$\sum_{a,b} Y_p^b D_q^{ab} D_r^{ab}$, $q \le r$	$6$
$D, D, D$	$\sum_{a,b} D_p^{ab} D_q^{ab} D_r^{ab}$, $p \le q \le r$	$4$

Therefore

\[ h_3(2,3) = 4 + 4 + 8 + 6 + 6 + 4 = 32 \]

The $8$ invariants of type $X,X,X$ and $Y,Y,Y$ are the new main-effect cubics. The $8$ invariants of type $X,Y,D$ are the stabilized binary cross-family cubics. The remaining $16$ degree-$3$ invariants are not all pure interaction-family cubics. They consist of $6$ invariants of type $X,D,D$, $6$ invariants of type $Y,D,D$, and $4$ pure interaction invariants of type $D,D,D$.

Proof. For $k=3$, the standard contrast representation $W$ of $S_3$ is two-dimensional. It has, up to scale, one invariant inner product

\[ \langle u, v \rangle = \sum_i u_i v_i \]

and one invariant symmetric cubic form

\[ P(u, v, w) = \sum_i u_i v_i w_i \]

The main-effect blocks $X_p$ and $Y_p$ each carry a copy of $W$. Hence within one main-effect family, the degree-$3$ invariants are precisely the polarizations

\[ \sum_a X_p^a X_q^a X_r^a \qquad \text{or} \qquad \sum_b Y_p^b Y_q^b Y_r^b \]

Since the player labels $p, q, r$ range over two players and the expression is symmetric in them, each main-effect family contributes

\[ \binom{2 + 3 - 1}{3} = 4 \]

cubic invariants. The two main-effect families therefore contribute $8$.

Next consider one $X$, one $Y$, and one $D$. The interaction block $D$ carries $W \otimes W$, with the first factor acted on by row relabeling and the second by column relabeling. The unique contraction is

\[ \sum_{a,b} X_p^a Y_q^b D_r^{ab} \]

The three player labels are independent, so this contributes

\[ 2^3 = 8 \]

invariants.

Now consider one $X$ and two $D$’s. The row coordinate uses the cubic invariant $P$, while the column coordinate uses the inner product. This gives

\[ \sum_{a,b} X_p^a D_q^{ab} D_r^{ab} \]

Here $p \in \{1,2\}$, while the pair $(q, r)$ is unordered because the two $D$’s enter symmetrically. Hence this contributes

\[ 2 \binom{2 + 2 - 1}{2} = 2 \cdot 3 = 6 \]

invariants. The same argument for one $Y$ and two $D$’s contributes another $6$ invariants.

Finally, three interaction blocks use the cubic invariant in both the row and column coordinates, giving

\[ \sum_{a,b} D_p^{ab} D_q^{ab} D_r^{ab} \]

Again $p, q, r$ are unordered player labels from a two-element set, so this contributes

\[ \binom{2 + 3 - 1}{3} = 4 \]

pure interaction-family cubics.

The six type patterns have distinct multidegrees in the variables $(X, Y, D)$, so the corresponding invariant spaces are linearly independent. Their total dimension is

\[ 4 + 4 + 8 + 6 + 6 + 4 = 32 \]

This equals the Molien coefficient $h_3 = 32$ for the mean-zero $(2,3)$ representation. Therefore the listed invariants span the full degree-$3$ invariant layer.

Inductive Construction of the Quotient Coordinates

The two inductive steps above give the general construction for all $(n,k)$-games. Adding a player changes the family layer: new contrast types appear, and existing invariant patterns acquire additional player assignments. Adding a strategy changes the internal layer: the contrast types and player labels remain fixed, but the contrast representations inside each block grow.

The point of the induction is not that the $(n,k)$-invariant ring is literally an extension of the $(n-1,k)$- or $(n,k-1)$-invariant ring. Rather, the point is that every $(n,k)$-invariant is obtained by applying the same Reynolds construction to the contrast-block decomposition, and the two inductive steps account for all possible changes in that decomposition. The classification claim of Theorem 2 says that any finite generating set of the invariant ring separates orbits; the theorem below shows that the contrast-block Reynolds construction produces one.

Theorem 6 (Inductive classification theorem) For every $n \geq 2$ and $k \geq 2$, the contrast-block Reynolds construction produces a finite set of polynomial invariants that separates strategy-relabeling orbits of mean-zero $(n,k)$-games. Equivalently, it gives a complete invariant-theoretic classification of $(n,k)$-games modulo strategy relabeling and player-specific payoff shifts.

More explicitly, let

\[ V_{n,k}^{0} = \bigoplus_{p=1}^{n} \bigoplus_{\emptyset \neq S \subseteq \{1,\ldots,n\}} C_{S,p} \]

be the mean-zero contrast decomposition, with

\[ C_{S,p} \cong \bigotimes_{i \in S} W_k, \qquad W_k = \mathbf{1}^\perp \subset \mathbb{R}^k \]

Apply the Reynolds operator for

\[ G_{n,k} = (S_k)^n \]

to monomials in the contrast-block coordinates, degree by degree. At each degree, retain a basis modulo products of invariants already retained in lower degree. Continuing up to any valid finite-generation bound, for example Noether’s bound, gives a finite homogeneous generating set for

\[ \mathbb{R}[V_{n,k}^{0}]^{G_{n,k}} \]

The values of these generators separate $G_{n,k}$-orbits in $V_{n,k}^{0}$. Thus two mean-zero $(n,k)$-games have the same invariant coordinates if and only if they differ by a relabeling of strategies.

Proof. For each player $p$, the mean-zero payoff array lies in

\[ (\mathbb{R}^k)^{\otimes n} / \mathbf{1} \]

Using the decomposition

\[ \mathbb{R}^k = \mathbf{1} \oplus W_k, \qquad W_k = \mathbf{1}^\perp \]

we obtain

\[ (\mathbb{R}^k)^{\otimes n} = \bigoplus_{S \subseteq \{1,\ldots,n\}} \left( \bigotimes_{i \in S} W_k \right) \]

where the coordinates outside $S$ carry the trivial representation. The summand $S = \emptyset$ is the player-specific payoff mean. Removing these means gives

\[ V_{n,k}^{0} = \bigoplus_{p=1}^{n} \bigoplus_{\emptyset \neq S \subseteq \{1,\ldots,n\}} C_{S,p} \]

The group

\[ G_{n,k} = (S_k)^n \]

acts independently on the $n$ strategy coordinates. In coordinate $i$, the block $C_{S,p}$ carries $W_k$ if $i \in S$, and the trivial representation if $i \notin S$. Therefore the group action preserves the contrast type $S$ and the player label $p$. Hence every monomial in the contrast coordinates has a well-defined block pattern

\[ (C_{S_1,p_1}, \ldots, C_{S_d,p_d}) \]

counted with multiplicity, and the Reynolds operator preserves this block pattern.

Now compare $(n,k)$ with the two smaller directions.

First, adding a player changes the set of contrast types from the non-empty subsets of $\{1,\ldots,n-1\}$ to the non-empty subsets of $\{1,\ldots,n\}$. The old contrast types are those not containing $n$. The new contrast types are exactly those containing $n$. The internal representation attached to an old type does not change, since $k$ is fixed. What changes is the family bookkeeping: new types appear, and all type patterns may now be assigned to the larger player-label set $\{1,\ldots,n\}$. Thus the add-player step accounts for every new block pattern involving either a new contrast type or the new player label.

Second, adding a strategy changes $W_{k-1}$ to $W_k$. The set of contrast types $\emptyset \neq S \subseteq \{1,\ldots,n\}$ does not change, and neither does the set of player labels. What changes is the internal representation

\[ C_{S,p} \cong \bigotimes_{i \in S} W_k \]

Thus the add-strategy step accounts for every new invariant tensor that appears inside an existing type pattern after the contrast blocks enlarge.

Therefore the two inductive operations account for all possible changes in the contrast-block representation: adding a player changes which block patterns exist, while adding a strategy changes the invariant tensors available inside those block patterns.

It remains to show that this construction classifies games. Since $G_{n,k}$ is finite, the invariant ring

\[ \mathbb{R}[V_{n,k}^{0}]^{G_{n,k}} \]

is finitely generated. Moreover, the Reynolds operator

\[ \mathcal{R}(f) = \frac{1}{|G_{n,k}|} \sum_{g \in G_{n,k}} f \circ g \]

is a projection from $\mathbb{R}[V_{n,k}^{0}]$ onto $\mathbb{R}[V_{n,k}^{0}]^{G_{n,k}}$. Hence, in each degree $d$, Reynolds averages of degree-$d$ monomials span the full degree-$d$ invariant layer.

By proceeding degree by degree and discarding invariants generated by products of lower-degree invariants, we obtain a finite homogeneous generating set of the invariant ring. The generators are all obtained from the contrast-block Reynolds construction described above.

Finally, for a finite group action, invariant polynomials separate orbits. Therefore two mean-zero games $u, v \in V_{n,k}^{0}$ have the same values on all generators if and only if they lie in the same $G_{n,k}$-orbit. Equivalently, the constructed invariant coordinates classify mean-zero $(n,k)$-games up to strategy relabeling. Restoring the removed player-specific payoff means gives the corresponding classification of full games, with the means treated as degree-$1$ invariants.

Molien Series Checks Across $(n,k)$

As a computational check on the inductive construction, Table 14 compares the mean-zero Molien coefficients for several $(n,k)$-games under the strategy-relabeling group $(S_k)^n$.

Table 14: Mean-zero Molien coefficients for $(n,k)$-games under $(S_k)^n$ (see Section 16.4)

$(n,k)$	Group	$\|G\|$	MZ dim	$h_2$	$h_3$	$h_4$
$(2,2)$	$S_2 \times S_2$	4	6	9	8	42
$(2,3)$	$S_3 \times S_3$	36	16	9	32	132
$(3,2)$	$(S_2)^3$	8	21	42	189	1428
$(3,3)$	$(S_3)^3$	216	78	42	556	9057

The degree-$2$ column agrees with the family-matrix formula $h_2 = (2^n-1) \cdot n(n+1)/2$. So $h_2 = 9$ for both $(2,2)$ and $(2,3)$, and $h_2 = 42$ for both $(3,2)$ and $(3,3)$, and the degree-$2$ count depends on the number of players but not on the number of strategies.

The degree-$3$ column shows the two inductive effects separately. Adding a player, $(2,2) \to (3,2)$, raises the degree-$3$ count from $8$ to $189$, creating more contrast families, more even-parity triples, and more player assignments. Adding a strategy, $(2,2) \to (2,3)$, raises the degree-$3$ count from $8$ to $32$. The family structure is unchanged, but new intra-family cubic invariants appear inside the enlarged contrast blocks. The $(3,3)$ row combines both effects. There are more contrast families from the additional player and richer internal invariant rings from the additional strategy, giving $h_3 = 556$ and $h_4 = 9057$.

The interaction-alignment diagnostic from the $(2,2)$ section generalizes directly. For any $(n,k)$-game, the $n$-way interaction family $M_{\{1,\ldots,n\}}$ plays the role of $d_A d_B$, and its off-diagonal entries measure pairwise alignment between players’ highest-order interaction components. A detailed treatment of the $(3,3)$ computation is given in Appendix B.

The Generalized Ordinal Classification

The ordinal classification of an $(n,k)$-game is the ranking of each player’s $k^n$ payoff entries, considered up to $(S_k)^n$ strategy relabeling. In mean-zero coordinates, the ordinal type is determined by the signs of the $\binom{k^n}{2}$ pairwise payoff differences per player. Each difference is a linear combination of the contrast coordinates $T_{S,p}^a$. The group $(S_k)^n$ acts linearly on these coordinates while preserving the contrast-block decomposition, and the generalized ordinal type is the orbit of the full pairwise-comparison sign pattern.

Because the invariant ring separates relabeling orbits of cardinal games, the full invariant values determine the cardinal relabeling class. The ordinal classification is then obtained by applying the pairwise-comparison sign map and canonicalizing the resulting sign pattern under $(S_k)^n$. It remains to show how this works in practice, and how the invariant structure organizes the ordinal classification.

Binary Games ($k = 2$): Parity and Sign Recovery

When $k=2$, every contrast block is one-dimensional. Thus each contrast component $T_{S,p}$ is a scalar, and the relabeling action is a sign-flip action indexed by the strategy coordinates contained in $S$. A monomial is invariant exactly when each strategy coordinate appears an even number of times.

For binary games, the ordinal type modulo $(S_2)^n$ can be recovered by reconstructing the scalar contrast coordinates up to the sign-flip action, computing all pairwise payoff-comparison signs, and then canonicalizing the resulting sign vector under $(S_2)^n$.

In low degree, the relevant sign data include:

the signs of the off-diagonal family-matrix entries $M_S[p,q]$ for $p<q$, recording interaction alignment between players within the same contrast type;
the within-player magnitude comparisons \[ \operatorname{sign}(M_S[p,p]-M_{S'}[p,p]) \]

for contrast types $S\neq S'$;

the signs of even-parity cross-family products, beginning with the cubic products satisfying \[ S_1\triangle S_2\triangle S_3=\emptyset \]

The full values of a separating set of even-parity invariants reconstruct the scalar contrast coordinates up to relabeling. The low-degree invariants above are the first and most interpretable pieces of this reconstruction; higher even-parity products may be needed to separate all sign patterns.

The reason this works is that, for $k=2$, the contrast coordinates are scalars. Every pairwise payoff difference is a linear combination of these scalar contrasts. Once the invariant values determine the scalar contrasts up to the sign-flip action, the ordinal sign vector is obtained by evaluating these linear differences and then choosing the canonical relabeling representative.

Proof. For $k=2$, each strategy coordinate has the decomposition

\[ \mathbb{R}^2 = \mathbf{1} \oplus W_2, \]

where $W_2$ is one-dimensional. Hence every non-empty contrast block is one-dimensional. We write its scalar coordinate as

\[ x_{S,p} := T_{S,p}, \qquad \emptyset \neq S \subseteq \{1,\ldots,n\}, \qquad p \in \{1,\ldots,n\} \]

The strategy-relabeling group is

\[ G = (S_2)^n \cong (\mathbb{Z}/2\mathbb{Z})^n \]

Let $\epsilon = (\epsilon_1, \ldots, \epsilon_n) \in \{\pm 1\}^n$. The relabeling $\epsilon$ acts on $x_{S,p}$ by

\[ x_{S,p} \mapsto \left( \prod_{i \in S} \epsilon_i \right) x_{S,p} \]

Thus $x_{S,p}$ changes sign exactly when the relabeling flips an odd number of strategy coordinates contained in $S$.

Now consider a monomial

\[ m = \prod_{j=1}^d x_{S_j, p_j} \]

Under $\epsilon$, this monomial is multiplied by

\[ \prod_{j=1}^d \prod_{i \in S_j} \epsilon_i \]

Therefore $m$ is invariant under all $\epsilon \in \{\pm 1\}^n$ if and only if each coordinate $i \in \{1, \ldots, n\}$ appears in an even number of the sets $S_1, \ldots, S_d$. Equivalently,

\[ S_1 \triangle S_2 \triangle \cdots \triangle S_d = \emptyset \]

This proves the even-parity rule for binary invariant monomials.

Next we prove sign recovery. Suppose two binary contrast-coordinate vectors $x = (x_{S,p})$ and $y = (y_{S,p})$ have the same values on all invariant polynomials. In particular, they have the same quadratic invariants

\[ x_{S,p}^2 = y_{S,p}^2 \]

Hence $y_{S,p} = 0$ whenever $x_{S,p} = 0$, and for each nonzero coordinate there is a sign $\eta_{S,p} \in \{\pm 1\}$ such that

\[ y_{S,p} = \eta_{S,p} x_{S,p} \]

We claim that the signs $\eta_{S,p}$ come from a relabeling in $(S_2)^n$. To see this, consider the vector space over $\mathbb{F}_2$ generated by the nonzero coordinates $x_{S,p}$. Define the parity map

\[ \phi : \mathbb{F}_2^I \to \mathbb{F}_2^n \]

by sending the basis vector corresponding to $(S, p)$ to the indicator vector of $S$. A product of coordinates is invariant exactly when its exponent vector lies in $\ker \phi$.

Since $x$ and $y$ have the same values on all invariant monomials, the sign character $\eta$ is trivial on every invariant monomial. Equivalently,

\[ \prod_{(S,p)} \eta_{S,p}^{\alpha_{S,p}} = 1 \]

for every $\alpha \in \ker \phi$. Therefore $\eta$ factors through the quotient

\[ \mathbb{F}_2^I / \ker \phi \cong \operatorname{im} \phi \]

Equivalently, there exists a vector $\epsilon = (\epsilon_1, \ldots, \epsilon_n) \in \{\pm 1\}^n$ such that

\[ \eta_{S,p} = \prod_{i \in S} \epsilon_i \]

for every nonzero coordinate $x_{S,p}$. Therefore

\[ y_{S,p} = \left( \prod_{i \in S} \epsilon_i \right) x_{S,p} \]

So $y$ is obtained from $x$ by a strategy relabeling. Thus the binary invariant values reconstruct the scalar contrast coordinates up to the $(S_2)^n$ sign-flip action.

It remains to pass from cardinal contrast coordinates to ordinal type. For each player $p$, the payoff at a binary strategy profile $s \in \{1,2\}^n$ is a linear combination of the contrast coordinates $x_{S,p}$, plus the player-specific mean. Therefore for two profiles $s, t$, the payoff difference

\[ u_p(s) - u_p(t) \]

is a linear combination of the contrast coordinates $x_{S,p}$; the player-specific mean cancels. Hence, once the contrast coordinates are known up to relabeling, all pairwise payoff-comparison signs

\[ \operatorname{sign}(u_p(s) - u_p(t)) \]

are determined up to the same relabeling action.

Therefore, starting from the invariant values, one may enumerate the finitely many sign choices for the scalar contrast coordinates that are consistent with those invariant values. The argument above shows that all surviving choices lie in the same $(S_2)^n$-orbit. For any surviving choice, compute the full pairwise payoff-comparison sign vector, and then choose its canonical representative under $(S_2)^n$. The result is independent of the surviving choice.

Thus the binary invariant values determine the ordinal type modulo strategy relabeling. If payoff ties occur, the same argument recovers the weak ordinal sign vector with entries in $\{-1, 0, +1\}$.

Non-Binary Games ($k \geq 3$): Discriminant Loci

When $k \geq 3$, each main-effect contrast is a vector in $\mathbb{R}^{k-1}$, and the invariants built from a single contrast type are generated by the power sums $p_2, \ldots, p_k$. The ordinal type of a $k$-vector $v = (v_1, \ldots, v_k)$ with $\sum v_i = 0$ is the ranking of its entries. This ranking is determined by the signs of the $\binom{k}{2}$ pairwise differences $v_i - v_j$, which define a hyperplane arrangement in $\mathbb{R}^{k-1}$. The ordinal types (modulo $S_k$) are the orbits of the chambers of this arrangement.

The power sums $p_2, \ldots, p_k$ map $\mathbb{R}^{k-1}$ to the invariant space $\mathbb{R}^{k-1}$. This map sends the hyperplane arrangement to a discriminant locus $\Delta = 0$, where

\[ \Delta = \prod_{i < j} (v_i - v_j)^2 \]

is a polynomial in the power sums (by Newton’s identities). The ordinal types correspond to the connected components of the complement of $\Delta = 0$ in invariant space.

For $k = 2$, the discriminant is $\Delta = (v_1 - v_2)^2 = (2v_1)^2 = 4 p_2$, which vanishes only at the origin. The complement has one component, so there is one ordinal type (up to $S_2$). The two-player information comes from the family matrices and cross-family products, as described above.

For $k=3$, the discriminant is \[ \Delta=(v_1-v_2)^2(v_1-v_3)^2(v_2-v_3)^2 \]

Expanding in power sums, with $v_1+v_2+v_3=0$, gives

\[ \Delta = 4p_2^3-27p_3^2 \]

up to a positive constant. The condition $\Delta>0$ is the no-tie condition for the three entries. The invariant $p_3=3v_1v_2v_3$ records the skewness of the three-entry contrast vector. $p_3$ is not itself an ordinal type.

For $k=4$, the discriminant is a degree-$6$ polynomial in $p_2,p_3,p_4$. The no-tie region is defined by $\Delta>0$, while the finer chamber information is recovered by pulling back the pairwise comparison signs through the quotient map.

The ordinal classification for $k\geq 3$ is therefore semialgebraic in the invariant coordinates. It is determined by polynomial inequalities, not merely by the signs of individual generators. The discriminant polynomial

\[ \Delta(p_2,\ldots,p_k) \]

defines the tie boundary for a single $k$-entry contrast vector. In the full game, the same principle applies to every payoff-comparison hyperplane. The image of the tie boundary in the invariant quotient becomes a polynomial or semialgebraic boundary between ordinal regions.

The Complete Inductive Picture for Ordinal Classification

The ordinal classification of an $(n,k)$-game is recovered from the invariant ring in two interacting layers:

The family matrices $M_S$ and cross-family contractions encode the inter-player and inter-type structure. This includes which contrast types are large, which players are aligned, and how different contrast types couple.
The intra-family invariants encode the internal shape of each contrast block. For main-effect blocks this includes the power sums $p_2,\ldots,p_k$; for higher-order interaction blocks it includes the Reynolds-averaged invariants of the corresponding block representation.

The two layers interact because each payoff-comparison sign is a linear condition in the original contrast coordinates, and its image in the invariant quotient is generally semialgebraic. Adding a player expands the family layer by introducing new contrast types. Adding a strategy expands the internal layer by increasing the dimension of each contrast block. Thus the same inductive construction used for the invariant ring also gives an algorithmic recovery procedure for ordinal classifications.

Applications and Further Structure

The invariant coordinates above classify games modulo strategy relabeling. We now record scaling laws for the invariant ring and several ways these coordinates interact with standard game-theoretic structures. The results in this section are not needed for the classification theorem itself; rather, they show how the invariant ring grows with $(n, k, d)$ and how equilibrium conditions, Hodge-theoretic decompositions, and cyclic witnesses can be studied inside the relabeling quotient.

Scaling Laws

The computations above extend to games of arbitrary size. Here we describe quantitative scaling laws for how the invariant ring grows with the number of players $n$, the number of strategies $k$, and the polynomial degree $d$.

Stabilization in $k$

Fix the number of players $n$ and the polynomial degree $d$. Computationally, the dimension

\[ h_d(n,k)=\dim \mathbb{R}[V_{n,k}^{0}]^{(S_k)^n}_d \]

stabilizes as the number of strategies $k$ increases. The reason is that a degree-$d$ monomial can involve at most $d$ distinct strategy labels in each coordinate. Once enough labels are available, adding more strategies should not create new degree-$d$ orbit types.

For two-player games under $(S_k)^2$, the low-degree Molien coefficients are tabulated in Table 15:

Table 15: Low-degree Molien coefficients for two-player games under $(S_k)^2$ (see Section 16.4). Blank entries indicate computations not yet included in this table.

$k \backslash d$	2	3	4	5	6
2	9	8	42	48	138
3	9	32	132
4	9	32

The degree-$2$ count stabilizes immediately:

\[\forall k\geq 2, \quad h_2(2,k)=9 \]

The degree-$3$ count similarly stabilizes at $k=3$ in the computed range:

\[ \forall k\geq 3, \quad h_3(2,k)=32 \]

The binary row $k=2$ is exceptional in degree $3$, as it has only the eight cross-family cubic generators from the $(2,2)$ computation. When $k=3$, new within-family cubic invariants appear, raising the count from $8$ to $32$.

We have the following stabilization theorem.

Theorem 7 (Stabilization in the Number of Strategies) Fix $n$ and $d$. Then the degree-$d$ mean-zero invariant dimension

\[ h_d(n,k) = \dim \mathbb{R}[V_{n,k}^{0}]^{(S_k)^n}_d \]

stabilizes for all $k \ge d$. Equivalently, for fixed $n, d$,

\[ h_d(n,k) = h_d(n,d) \qquad \text{for all } k \ge d \]

The threshold $k \ge d$ is sufficient, though not necessarily minimal.

Proof. Let \[ F_{n,k} = \bigoplus_{p=1}^n \mathbb{R}^{[k]^n} \] be the full payoff space. A degree-$d$ monomial has the form \[ x_{p_1, s^{(1)}} \cdots x_{p_d, s^{(d)}}, \qquad s^{(j)} \in [k]^n \] For each strategy coordinate $i$, this monomial uses only the labels \[ s_i^{(1)}, \ldots, s_i^{(d)}, \] so it uses at most $d$ distinct labels in coordinate $i$.

The degree-$d$ invariant space has a basis given by orbit sums of degree-$d$ monomials. Therefore its dimension is the number of degree-$d$ monomial orbits. If $k \ge d$, every degree-$d$ monomial using labels in $[k+1]$ is equivalent, under $(S_{k+1})^n$, to one using only labels in $[k]$, because at most $d$ labels are used in each coordinate. Conversely, if two monomials using only labels in $[k]$ are equivalent under $(S_{k+1})^n$, the permutations relating their used labels restrict to bijections between subsets of $[k]$, and since $k \ge d$, these bijections extend to permutations of $[k]$. Hence they were already equivalent under $(S_k)^n$.

Thus the degree-$d$ monomial orbit count in the full payoff space stabilizes for $k \ge d$.

Finally, \[ F_{n,k} = V_{n,k}^{0} \oplus \mathbb{R}^n \] equivariantly, where $\mathbb{R}^n$ is the space of player-specific payoff means and is fixed by the group. Hence \[ \mathbb{R}[F_{n,k}]^{(S_k)^n} \cong \mathbb{R}[V_{n,k}^{0}]^{(S_k)^n} \otimes \mathbb{R}[m_1, \ldots, m_n] \] Removing the fixed mean variables only multiplies the Hilbert series by $(1-t)^n$, so stabilization of the full-space coefficients through degree $d$ implies stabilization of the mean-zero coefficients in degree $d$. Therefore \[ h_d(n,k) = h_d(n,d) \qquad \text{for all } k \ge d \]

Degree-3 Growth and the Polynomial Threshold

The previous section showed that $h_2 = (2^n - 1) \cdot n(n+1)/2$ is polynomial in $n$. The next degree breaks that pattern. For $(n,2)$-games under $(S_2)^n$ on the mean-zero subspace,

\[ h_3 = 8, \; 189, \; 2240, \; 19375, \; 140616, \; \ldots \quad (n = 2, 3, 4, 5, 6, \ldots) \]

A direct count of even-parity contrast-type triples (Proposition 5) gives the closed form

\[ h_3(n,2) = n^3 \cdot \frac{(2^n - 1)(2^n - 2)}{6} \]

The leading term scales like $n^3 \cdot 4^n / 6$, so the count is super-polynomial in $n$. Numerical agreement with this formula for $n = 2,\ldots,6$ is verified in degree3_mz_strategy_only.py.

The combinatorial source is visible in the orbit structure. A degree-3 monomial is a triple of payoff coordinates. Its $(S_2)^n$-orbit is determined by the Hamming pattern of strategy indices across the three coordinates, and the number of distinct Hamming patterns grows exponentially with the number of players.

The growth rate is sensitive to how players are distinguished. Restrict to fully symmetric games, those invariant under arbitrary player relabeling. There the degree-$d$ count becomes polynomial in $n$ for each $d$. The super-polynomial behavior above is the price of keeping all $n$ players distinguishable.

The Degree Hierarchy

The stabilization and growth results together imply a degree hierarchy of game-theoretic phenomena (Table 16):

Table 16: Degree hierarchy of game-theoretic phenomena

Degree	What it detects	When new $k$-strategy effects appear
2	Contrast magnitudes, interaction strength, cross-player alignment	$k \geq 2$
3	Contrast-interaction coupling, skewness, cyclic directionality	$k \geq 3$
4	Higher-order contrast distributions, interlocking cyclic structure, $k$-strategy adversarial witnesses	$k \geq 4$

Each degree $d$ adds invariants that detect higher-order polynomial structure in the payoff array. Some of these effects already occur at $k=2$ through cross-family products of scalar contrast coordinates. Others first appear when enough strategy labels are available. At $k=3$, new degree-$3$ invariants appear that detect skewness and cyclic directionality, as in Rock-Paper-Scissors. At $k=4$, new degree-$4$ invariants can detect more complicated interlocking cyclic patterns.

The analogy to probability moments is useful: just as variance, skewness, and kurtosis capture successively finer features of a distribution, the degree-$2$, degree-$3$, degree-$4$, and higher invariants of a game capture successively finer strategic structure. Two games with the same degree-$2$ invariants but different degree-$3$ invariants are like two distributions with the same variance but different skewness.

Equilibrium Diagnostics

The invariant coordinates do not depend on a solution concept, but solution concepts can still be studied inside the quotient. We begin with the full-support Nash indifference equations.

The cleanest formulation uses the tangent space of the mixed-strategy simplex. Let

\[ H_k = \left\{ z \in \mathbb{R}^k : \sum_{a=1}^k z_a = 0 \right\} \]

and let

\[ Q_k = \mathbb{R}^k / \langle \mathbf{1} \rangle \]

The space $H_k$ is the tangent space to the affine simplex $\sum_a x_a = 1$, while $Q_k$ records payoff vectors modulo addition of a constant. A player is indifferent among all $k$ pure strategies exactly when their expected payoff vector is zero in $Q_k$.

Both $H_k$ and $Q_k$ carry the standard $(k-1)$-dimensional representation of $S_k$. A strategy relabeling permutes coordinates, preserves $H_k$, and acts on $Q_k$ by the induced quotient action.

Two-Player Full-Support Indifference Determinant

Let $(A, B)$ be a $(2,k)$ bimatrix game. For player 1, the full-support indifference condition is

\[ A y \in \langle \mathbf{1} \rangle, \]

where $y$ is player 2’s mixed strategy. Passing to the quotient by $\langle \mathbf{1} \rangle$, this gives an affine linear condition

\[ [A y] = 0 \in Q_k \]

The associated linear map on tangent directions is

\[ \bar{A} : H_k \longrightarrow Q_k, \qquad \delta y \longmapsto [A \delta y] \]

Similarly, player 2’s full-support indifference condition is

\[ B^\top x \in \langle \mathbf{1} \rangle, \]

and the associated tangent map is

\[ \bar{B}^\top : H_k \longrightarrow Q_k, \qquad \delta x \longmapsto [B^\top \delta x] \]

After choosing bases of $H_k$ and $Q_k$, define

\[ \Delta_A = \det(\bar{A}), \qquad \Delta_B = \det(\bar{B}^\top) \]

The two-player full-support indifference determinant is

\[ \operatorname{disc}_{2,k}(A, B) = \Delta_A \Delta_B \]

Equivalently, in coordinates, $\Delta_A$ is the determinant of the usual $k \times k$ system whose first $k-1$ rows are payoff-difference equations and whose final row is the normalization equation. The same holds for $\Delta_B$.

Proposition 6 (Two-player full-support indifference determinant) For a $(2,k)$ bimatrix game,

\[ \operatorname{disc}_{2,k}(A, B) = \Delta_A \Delta_B \]

is a $(S_k)^2$-invariant polynomial of degree $2(k-1)$ in the payoff entries. It is nonzero exactly when both full-support indifference systems have unique solutions. For $k=2$, it agrees with $d_A d_B$, up to the sign convention used for the indifference rows.

Proof. The map $\bar{A} : H_k \to Q_k$ is linear in the entries of $A$. Since $H_k$ and $Q_k$ both have dimension $k-1$, its determinant $\Delta_A$ is homogeneous of degree $k-1$ in the entries of $A$. Similarly, $\Delta_B$ is homogeneous of degree $k-1$ in the entries of $B$. Hence

\[ \operatorname{disc}_{2,k}(A, B) = \Delta_A \Delta_B \]

has degree $2(k-1)$ in the payoff entries.

The affine full-support indifference system for player 1 is

\[ [A y] = 0 \in Q_k, \qquad \sum_{a=1}^k y_a = 1 \]

Its linear part on the affine simplex is $\bar{A} : H_k \to Q_k$. Therefore the system has a unique solution if and only if $\bar{A}$ is invertible, i.e. if and only if $\Delta_A \neq 0$. The same argument applies to $\bar{B}^\top$. Thus $\operatorname{disc}_{2,k}(A, B) \neq 0$ exactly when both full-support indifference systems have unique solutions.

Now we prove relabeling invariance. Let $(\sigma, \tau) \in S_k \times S_k$, where $\sigma$ relabels player 1’s strategies and $\tau$ relabels player 2’s strategies. In matrix form,

\[ A \mapsto P_\sigma A P_\tau^{-1}, \qquad B \mapsto P_\sigma B P_\tau^{-1} \]

The induced map on player 1’s indifference operator is

\[ \bar{A} \mapsto \overline{P_\sigma A P_\tau^{-1}} = \bar{P}_\sigma \, \bar{A} \, \bar{P}_\tau^{-1}, \]

where $\bar{P}_\sigma$ and $\bar{P}_\tau$ denote the induced actions on $Q_k$ and $H_k$. Taking determinants gives

\[ \Delta_A \mapsto \det(\bar{P}_\sigma) \det(\bar{P}_\tau)^{-1} \Delta_A \]

The standard representation has determinant equal to the sign of the permutation, so $\det(\bar{P}_\sigma) = \operatorname{sgn}(\sigma)$ and $\det(\bar{P}_\tau) = \operatorname{sgn}(\tau)$. Hence

\[ \Delta_A \mapsto \operatorname{sgn}(\sigma) \operatorname{sgn}(\tau) \Delta_A \]

For player 2, the relevant operator is $\bar{B}^\top : H_k \to Q_k$. Under the same relabeling, its domain is affected by $\sigma$ and its codomain by $\tau$. Thus

\[ \Delta_B \mapsto \operatorname{sgn}(\tau) \operatorname{sgn}(\sigma) \Delta_B \]

Therefore the product transforms as

\[ \Delta_A \Delta_B \mapsto \operatorname{sgn}(\sigma)^2 \operatorname{sgn}(\tau)^2 \Delta_A \Delta_B = \Delta_A \Delta_B \]

Thus $\operatorname{disc}_{2,k}$ is invariant under $(S_k)^2$.

For $k=2$, the spaces $H_2$ and $Q_2$ are one-dimensional. With

\[ A = \begin{pmatrix} a_1 & a_2 \\ a_3 & a_4 \end{pmatrix}, \]

the tangent direction in player 2’s simplex is proportional to $(1, -1)$. Then $[A (1, -1)]$ is represented by the payoff difference

\[ (a_1 - a_2) - (a_3 - a_4) = a_1 - a_2 - a_3 + a_4 = d_A \]

Thus $\Delta_A = d_A$, up to the chosen orientation. Similarly $\Delta_B = d_B$, up to orientation. Hence

\[ \operatorname{disc}_{2,2}(A, B) = d_A d_B \]

up to the sign convention used for the bases.

The condition $\operatorname{disc}_{2,k}(A, B) \neq 0$ does not by itself assert that an interior Nash equilibrium exists. It says that the two full-support indifference systems have unique candidate mixed strategies. These candidates must still have strictly positive coordinates to define an interior mixed profile.

Conversely, $\operatorname{disc}_{2,k} = 0$ does not rule out interior equilibria. Degenerate games may have continua of interior equilibria. For example, if both payoff matrices are zero, every mixed profile is a Nash equilibrium, but the determinant above vanishes.

General $n$-Player Incidence-Space Jacobian

For $n \geq 3$, the full-support indifference equations are no longer linear in all mixed-strategy variables jointly. They are multilinear. Therefore the natural generalization of the two-player determinant is a Jacobian form on the payoff–mixed-strategy incidence space, not generally a payoff-only polynomial.

Let $u = (u_1, \ldots, u_n)$ be an $(n,k)$-game. For each player $i$, let $x_i \in \Delta^{k-1}$ be their mixed strategy. Write $x = (x_1, \ldots, x_n)$. For each player $i$, define the expected payoff vector $E_i(u, x_{-i}) \in \mathbb{R}^k$ by

\[ E_i(u, x_{-i})_a = \sum_{s_{-i}} u_i(a, s_{-i}) \prod_{j \neq i} x_j(s_j) \]

Player $i$ is indifferent among all pure strategies exactly when

\[ [E_i(u, x_{-i})] = 0 \in Q_k \]

Thus the full-support indifference map is

\[ F(u, x) = \big( [E_1(u, x_{-1})], \ldots, [E_n(u, x_{-n})] \big) \in Q_k^{\oplus n} \]

The domain of variations in the mixed-strategy variables is $H_k^{\oplus n}$. Thus the Jacobian of the indifference system is the linear map

\[ D_x F(u, x) : H_k^{\oplus n} \longrightarrow Q_k^{\oplus n} \]

Define

\[ \mathcal{J}_{n,k}(u, x) = \det D_x F(u, x), \]

after choosing compatible bases of $H_k^{\oplus n}$ and $Q_k^{\oplus n}$.

Proposition 7 (Full-support Nash incidence Jacobian) For an $(n,k)$-game, the full-support indifference map $F(u, x) : H_k^{\oplus n} \to Q_k^{\oplus n}$ has Jacobian determinant

\[ \mathcal{J}_{n,k}(u, x) = \det D_x F(u, x) \]

This is a polynomial in the payoff entries and mixed-strategy coordinates. It is homogeneous of degree $n(k-1)$ in the payoff entries. It is invariant under simultaneous strategy relabeling of payoff arrays, mixed-strategy coordinates, and indifference equations.

At a full-support equilibrium $x^*$, the condition $\mathcal{J}_{n,k}(u, x^*) \neq 0$ is the local nondegeneracy condition for the full-support indifference system.

Proof. For each player $i$, the expected payoff vector $E_i(u, x_{-i})$ is linear in the payoff entries of player $i$ and multilinear in the mixed strategies of the other players. It does not depend on $x_i$. Therefore the indifference map $F(u, x) = ([E_1(u, x_{-1})], \ldots, [E_n(u, x_{-n})])$ is polynomial in $(u, x)$, linear in the payoff entries of each player, and multilinear in the mixed-strategy variables.

The Jacobian $D_x F(u, x) : H_k^{\oplus n} \to Q_k^{\oplus n}$ has $n$ row-blocks, one for each player. The row-block corresponding to player $i$ consists of the derivatives of $[E_i(u, x_{-i})]$ with respect to the mixed strategies of the players $j \neq i$. Every entry in this row-block is linear in player $i$’s payoff entries.

The total dimension of the domain and codomain is $N = n(k-1)$. Thus $D_x F(u, x)$ is an $N \times N$ matrix. In every term of its determinant, one entry is chosen from each row. Since the $k-1$ rows belonging to player $i$’s block are each linear in player $i$’s payoff entries, every determinant term is homogeneous of degree $k-1$ in the payoff entries of player $i$. Multiplying over all $n$ players, every term has total payoff degree $n(k-1)$. Therefore $\mathcal{J}_{n,k}(u, x)$ is homogeneous of degree $n(k-1)$ in the payoff entries.

This determinant is not the zero polynomial. To see this, fix any interior mixed strategy profile $x$. Choose payoff tensors so that, for each player $i$, the indifference vector $[E_i]$ depends linearly and invertibly only on the mixed strategy of player $i+1$, with indices read cyclically. In block form, the Jacobian can then be made into a cyclic block-permutation matrix with identity blocks $H_k \to Q_k$. Such a matrix has nonzero determinant. Hence the polynomial $\mathcal{J}_{n,k}$ has exact payoff degree $n(k-1)$.

Now we prove invariance. A relabeling $g = (\sigma_1, \ldots, \sigma_n) \in (S_k)^n$ acts on payoff arrays, mixed-strategy coordinates, and payoff-vector quotients. Let $P_g$ denote the induced action on $H_k^{\oplus n}$, and let $R_g$ denote the induced action on $Q_k^{\oplus n}$. The full-support indifference map is equivariant:

\[ F(g \cdot u, g \cdot x) = R_g F(u, x) \]

Differentiating with respect to $x$ gives

\[ D_x F(g \cdot u, g \cdot x) = R_g \, D_x F(u, x) \, P_g^{-1} \]

Taking determinants yields

\[ \mathcal{J}_{n,k}(g \cdot u, g \cdot x) = \det(R_g) \det(P_g)^{-1} \mathcal{J}_{n,k}(u, x) \]

But $P_g$ and $R_g$ are the same direct sum of standard representations, one acting on simplex tangent directions and the other acting on payoff differences modulo constants. Therefore $\det(R_g) = \det(P_g)$. Hence

\[ \mathcal{J}_{n,k}(g \cdot u, g \cdot x) = \mathcal{J}_{n,k}(u, x) \]

Finally, if $x^*$ is a full-support equilibrium, then $F(u, x^*) = 0$. The local solution structure of the full-support indifference system near $x^*$ is controlled by the derivative $D_x F(u, x^*)$. By the inverse function theorem, $x^*$ is locally a nonsingular solution of the indifference system exactly when this derivative is invertible. Equivalently, $\mathcal{J}_{n,k}(u, x^*) \neq 0$.

For $n = 2$, the indifference equations are linear in the opponent’s mixed strategy. Therefore the Jacobian form is independent of the mixed-strategy coordinates and reduces to the payoff-only determinant $\operatorname{disc}_{2,k}(A, B) = \Delta_A \Delta_B$.

For $n \geq 3$, the Jacobian generally depends on the mixed-strategy coordinates. Substituting an equilibrium $x^*(u)$ need not produce a polynomial in the payoff entries.

For example, in a $(3, 2)$-game, write $x, y, z$ for the probabilities that players $1, 2, 3$ play their first strategy. The binary full-support indifference equations may have the form

\[ f_1(y, z) = yz - a, \qquad f_2(x, z) = xz - b, \qquad f_3(x, y) = xy - c \]

When $a = b = c = t$, the full-support solution is $x = y = z = \sqrt{t}$. The Jacobian is

\[ J = \begin{pmatrix} 0 & z & y \\ z & 0 & x \\ y & x & 0 \end{pmatrix}, \]

so $\det J = 2 x y z$. At the solution, $\det J = 2 t^{3/2}$, which is not a polynomial in the payoff parameter $t$. Thus, for $n \geq 3$, the incidence-space Jacobian is the natural polynomial object. A payoff-only discriminant would require eliminating the mixed-strategy variables, for example by a resultant or discriminant construction. We leave that elimination-theoretic object as an open problem.

The payoff-only degree $n(k-1)$ in $\mathcal{J}_{n,k}$ has been verified numerically for seven $(n,k)$ combinations (Table 17).

Table 17: Payoff-degree verification for the indifference Jacobian (see Section 16.9)

$(n,k)$	Degree in payoffs	Verified
$(2,2)$	2	$\Delta_A \Delta_B = d_A d_B$
$(2,3)$	4	$\Delta_A \Delta_B$, verified numerically
$(2,4)$	6	verified numerically
$(2,5)$	8	verified numerically
$(3,2)$	3	verified numerically
$(4,2)$	4	verified numerically
$(5,2)$	5	verified numerically

Relation to the Hodge Decomposition

The invariant-ring construction is not the only way to decompose the space of finite games. Another important decomposition is the Hodge decomposition of Candogan et al. (2011), with dynamical extensions in Candogan, Ozdaglar, and Parrilo (2013), which separates a game into potential, harmonic, and nonstrategic components. That decomposition is linear: it splits the game space into subspaces with distinct strategic interpretations.

For a $(2,k)$-game, the payoff space $\mathbb{R}^{2k^2}$ decomposes as

\[ V = V_{\text{nonstrat}} \oplus V_{\text{pot}} \oplus V_{\text{harm}} \]

In the Candogan-Ozdaglar-Parrilo decomposition, $V_{\text{nonstrat}}$ consists of payoff components that do not depend on the acting player’s own strategy and has dimension $2k$. After quotienting by nonstrategic components, the normalized game space decomposes into potential and harmonic components, with the harmonic component having dimension $(k-1)^2$. A game is a potential game if and only if its harmonic component vanishes. A game is harmonic if and only if its potential and nonstrategic components vanish. The decomposition is orthogonal with respect to the standard inner product on $V$ and is preserved by the strategy-relabeling group $(S_k)^2$.

The invariant quotient developed in this paper has a different purpose. It does not decompose games by strategic behavior directly. Instead, it quotients games by strategy relabeling and constructs polynomial coordinates on the resulting orbit space. The two constructions are complementary. The Hodge decomposition separates the directions in game space associated with potential, harmonic, and nonstrategic structure. The invariant-ring construction then provides coordinates on these structures modulo arbitrary names assigned to strategies.

In this sense, the invariant coordinates refine the Hodge decomposition rather than replacing it. One can first project a game to its Hodge components and then evaluate relabeling-invariant polynomials on those components. Conversely, one can study how the potential, harmonic, and nonstrategic subspaces appear inside the relabeling quotient.

For example, in the $(2,2)$ mean-zero coordinates $(r_A, c_A, d_A, r_B, c_B, d_B)$, the potential and anti-potential conditions are visible in the interaction coordinates. The potential condition is $d_A = d_B$, while the anti-potential condition is $d_A = -d_B$. In invariant coordinates, these become quadratic conditions: $g_5 = g_6 = g_9$ for the potential case, and $g_5 = g_9 = -g_6$ for the anti-potential case. Thus a linear strategic decomposition can appear inside the invariant quotient as polynomial equations among invariant coordinates.

More generally, whenever a linear game class is preserved by strategy relabeling, the invariant coordinates restrict to polynomial coordinates on that class modulo relabeling. This allows potential, harmonic, nonstrategic, zero-sum, and other linear or affine game classes to be studied inside the same quotient framework.

The important distinction is that the Hodge decomposition describes where a game lies in the original payoff space, while the invariant-ring construction describes where its relabeling orbit lies in the quotient. The first is a linear decomposition of games; the second is a polynomial classification of games up to labels.

Cycle Witnesses and Degree Heuristics

Some strategic patterns are naturally witnessed by products of payoff comparisons around cycles. This gives a useful source of interpretable invariants. However, cycle length should not be treated as a universal lower bound on detection degree. Lower-degree invariants may detect coarser shadows of the same structure.

Suppose a strategic pattern is supported on a minimal payoff-comparison cycle of length $k$. Let $\ell_1, \ldots, \ell_k$ be linear payoff-comparison forms associated with the $k$ edges of that cycle. The product

\[ C = \ell_1 \ell_2 \cdots \ell_k \]

is a degree-$k$ polynomial witness for the oriented cycle. Averaging this witness over relabelings gives an invariant polynomial.

Proposition 8 (Cyclic witness invariants) Suppose a strategic pattern has a label-complete cyclic witness

\[ C = \ell_1 \ell_2 \cdots \ell_k, \]

where each $\ell_j$ is a linear payoff-comparison form supported on one edge of a minimal $k$-cycle. Then the Reynolds average

\[ \mathcal{R}(C) \]

is a strategy-relabeling invariant of degree $k$.

If an allowed relabeling sends the oriented witness $C$ to $-C$, then the sign of $C$ does not descend to the relabeling quotient. In that case

\[ \mathcal{R}(C^2) \]

or an equivalent paired product gives a natural invariant witness of degree $2k$.

This is an existence statement for natural cycle witnesses, not a universal lower bound on the degree at which every feature of the pattern can be detected.

Proof. Each payoff-comparison form $\ell_j$ is linear in the payoff entries. Hence

\[ C = \ell_1 \ell_2 \cdots \ell_k \]

has degree $k$. Applying the Reynolds operator gives

\[ \mathcal{R}(C) = \frac{1}{|G|} \sum_{g \in G} C \circ g, \]

which is invariant by construction and still has degree $k$. Thus a label-complete cyclic witness gives a natural degree-$k$ invariant.

If an allowed relabeling sends $C$ to $-C$, then the sign of $C$ is not well-defined on the quotient: two relabeling-equivalent representatives give opposite values of the oriented witness. Therefore $C$ itself cannot serve as a signed quotient coordinate for that orientation.

However, $C^2$ is unchanged by $C \mapsto -C$, and its Reynolds average $\mathcal{R}(C^2)$ is an invariant polynomial of degree $2k$. Similarly, if two oriented witnesses transform with opposite signs, then their product gives a degree-$2k$ invariant.

This proves the existence of natural degree-$k$ cycle witnesses and degree-$2k$ squared or paired witnesses. It does not prove that lower-degree invariants cannot detect weaker or coarser aspects of the same strategic pattern.

The binary Matching Pennies line illustrates why the cycle-witness degree should not be read as a universal lower bound. Consider the line in the $(2,2)$ mean-zero space parameterized by

\[ (0, 0, t, 0, 0, -t) \]

Along this line, $d_A = t$ and $d_B = -t$. The degree-$2$ invariants record

\[ d_A^2 = t^2, \qquad d_A d_B = -t^2, \qquad d_B^2 = t^2 \]

Thus the basic adversarial interaction is already visible at degree $2$ through $d_A d_B < 0$.

All degree-$3$ generators in the strategy-only $(2,2)$ quotient vanish on this line because they involve at least one row or column contrast. Higher-degree oriented cycle witnesses may encode more refined cyclic structure, especially under larger symmetry groups such as the wreath-product quotient, but the degree-$2$ invariant already detects the interaction opposition in the strategy-only quotient.

Therefore cycle products provide useful interpretable invariants, but classification difficulty is not governed by cycle length alone. The invariant degree required to distinguish a property depends on the exact symmetry group, the quotient being used, and the level of structure one wants to detect.

Algorithms and Computation

All computations in this paper follow the same algorithmic pipeline, which is describe in this section. There are three main steps: computing the group action, computing the Molien series, and computing generators and syzygies. Each step is implemented in standalone Python scripts using NumPy and SymPy.

Computing the Group Action

Given an $(n,k)$-game, the group $(S_k)^n$ has order $(k!)^n$. Each element is a tuple $(\sigma_1, \ldots, \sigma_n)$ of permutations, one per player. The element $(\sigma_1, \ldots, \sigma_n)$ acts on the payoff tensor of player $p$ by permuting the strategy indices:

\[ (\sigma_1, \ldots, \sigma_n) \cdot u_p(s_1, \ldots, s_n) = u_p(\sigma_1^{-1}(s_1), \ldots, \sigma_n^{-1}(s_n)) \]

This action is linear on the payoff space $\mathbb{R}^{nk^n}$, so each group element is represented by a permutation matrix of size $nk^n \times nk^n$.

Computing the Molien Series

The Molien series is computed by the eigenvalue method. For each group element $g$, we compute the eigenvalues $\lambda_1, \ldots, \lambda_N$ of the representation matrix $\rho(g)$ restricted to the relevant subspace (full, mean-zero, or interaction). The contribution of $g$ to the Molien series is

\[ \frac{1}{\det(I - t \rho(g))} = \prod_{i=1}^{N} \frac{1}{1 - t \lambda_i} \]

which we expand as a power series in $t$ to the desired degree, then average over the group. For the groups $(S_k)^n$, the computation reduces to a sum over $(k!)^n$ elements, each requiring an $N \times N$ eigenvalue computation. The conjugacy-class reduction groups elements with the same eigenvalues, reducing the sum to a sum over conjugacy classes weighted by class sizes.

Computing Generators

Generators are found by the Reynolds-operator method:

At each degree $d$, enumerate all degree-$d$ monomials in the payoff coordinates.
For each monomial $m$, compute the Reynolds average $\mathcal{R}(m) = \frac{1}{|G|} \sum_{g \in G} m \circ \rho(g)$. In practice, this is evaluated numerically at a set of random evaluation points.
Test whether $\mathcal{R}(m)$ is linearly independent of (a) products of previously found generators at degree $d$, and (b) previously found degree-$d$ generators. This is done by augmenting the matrix of known invariant evaluations and checking if the rank increases.
If independent, record the symbolic expression via SymPy and add the numerical evaluations to the known set.

Ring closure at degree $d$ is verified by checking that the products of all generators at degrees $\leq d$ span a space of dimension $h_d$ (the Molien coefficient). By Noether’s bound, the ring is generated in degrees at most $|G|$.

Computing Syzygies

Syzygies are found by exact symbolic expansion:

At each target degree $d$, enumerate all products of generators with total degree $d$ (pairs, triples, etc.).
Expand each product as a polynomial in the payoff coordinates using SymPy.
Collect monomial coefficients into an integer matrix $M$ (rows = monomials, columns = products).
Compute the null space of $M$ over $\mathbb{Q}$.

Each null vector is a syzygy, linear combinations of products that vanish identically as a polynomial function on $V$.

Reproducibility

All computations are implemented in standalone Python scripts using NumPy and SymPy. No external computer algebra systems are required. Each script has a __main__ block and can be run directly. The scripts and their roles are listed in Appendix D.

Conclusion

Summary

We have developed an invariant-theoretic framework for finite normal-form games under strategy relabeling. For $(2,2)$-games under $S_2 \times S_2$, after removing player-specific payoff means, the invariant ring has 17 generators, 9 in degree 2 and 8 in degree 3. By Noether’s bound and the degree-4 span computation, no higher-degree generators are needed. The degree-2 generators are the entries of three family matrices

\[ M_{\{1\}},\quad M_{\{2\}},\quad M_{\{1,2\}} \]

and the degree-3 generators are the cross-family triple products mixing row, column, and interaction contrasts. The full invariant values recover the 144 Robinson-Goforth no-tie ordinal types by mapping each game to its canonical 12-sign pairwise-comparison vector. The degree-2 diagnostics give useful interpretations inside this quotient, but they are not the recovery map itself. Nine degree-2 polynomials (three alignment signs and six cross-family comparisons) recover the 144 Robinson-Goforth ordinal types via their sign vectors. The invariant values therefore refine the ordinal taxonomy by providing continuous cardinal coordinates within each ordinal type.

For general $(n,k)$-games, the invariant ring is organized by contrast type. After removing player-specific means, each payoff array decomposes into contrast blocks indexed by non-empty subsets \[ S\subseteq \{1,\ldots,n\} \]

At degree $2$, these blocks produce family matrices \[ M_S[p,q]=\langle T_{S,p},T_{S,q}\rangle \]

one for each contrast type $S$. Hence the degree-$2$ mean-zero invariant count is \[ (2^n-1)\cdot \frac{n(n+1)}{2} \]

independent of $k$. These matrices measure the magnitude of each contrast type for each player and the alignment between players within that contrast type.

Higher-degree invariants therefore record structure not visible at degree $2$, such as cross-family couplings, skewness, cyclic directionality, and higher-order interaction patterns. Adding a player expands the family layer by introducing new contrast types. Adding a strategy expands the internal layer by increasing the dimension of each contrast block and introducing new Reynolds-averaged internal invariants. Thus the invariant ring gives a systematic coordinate system for games modulo strategy relabeling, with standard game classes, dominance conditions, ordinal regions, and equilibrium degeneracies appearing as algebraic or semialgebraic conditions in these coordinates.

Discussion

The question we are attempting to answer here is simple: given a numerical representation of the payoffs of a normal-form game, what kind of game is it? The invariant-theoretic viewpoint is a coordinate system to characterize the type of game, not a new solution concept. These coordinates can then be used to compare games, detect game classes, locate ordinal regions, and study equilibrium degeneracies.

The invariants come in layers. The degree-$2$ layer is the most directly interpretable. The diagonal entries of the family matrices measure how strongly each player’s payoff depends on each contrast type. The off-diagonal entries measure alignment between players within that same contrast type. In $(2,2)$-games this recovers familiar quantities such as dominance strength, interaction strength, and interaction alignment. In larger games, the same objects measure whether payoff variation is mostly driven by main effects, lower-order interactions, or higher-order interactions among multiple strategy coordinates.

Higher-degree invariants measure structure that cannot be seen from magnitudes and pairwise alignments alone. Cubic invariants record directional coupling among contrast types and detect skewness in non-binary strategy spaces. Higher-degree invariants detect increasingly fine cyclic and adversarial patterns. This gives a degree hierarchy, where low-degree invariants describe coarse strategic geometry, while higher-degree invariants distinguish more delicate strategic features.

This framework also clarifies the relation between cardinal and ordinal classification. Ordinal taxonomies divide game space into regions determined by payoff-comparison signs. The invariant ring retains the full cardinal geometry inside and across those regions. In the $(2,2)$ case, the invariant values recover the Robinson-Goforth no-tie ordinal types, while also preserving continuous payoff information within each type. For larger games, where exhaustive ordinal enumeration becomes infeasible, invariant coordinates provide a more scalable way to organize the space.

Computationally, the framework suggests a practical workflow. For small games, one can compute explicit generators and relations. For larger games, one can work degree by degree. Start with degree-$2$ family matrices give a compact first summary, while higher-degree Reynolds averages can be added as needed for finer classification. A researcher interested only in dominance or interaction alignment may need only low-degree invariants, or a researcher studying cycling, degeneracy, or equilibrium bifurcation may need higher-degree invariants. Alternatively, given a particular sample, one could greedily search for low-degree invariants that distinguish it from a reference set of games, without needing to compute the full invariant ring.

The main limitation is that the full invariant ring becomes large quickly. The $(2,2)$ case admits a complete hand-readable description, but higher $(n,k)$ cases require significant computation. However, the algerbraic characterization of the invariant ring gives a systematic way to organize these computations and interpret their results, and opens the door to new possibilities for game classification, analysis, and control drawing from invariant theory and algebraic geometry.

Appendix A. Computational Details for $(2,2)$

For the named-game representatives of Table 7, the full degree-2 invariant values are given in Table 18 and the full degree-3 values in Table 19.

Table 18: Full degree-2 invariant values for the named-game representatives (see Section 16.1)

Game	$r_A^2$	$r_A r_B$	$c_A^2$	$c_A c_B$	$d_A^2$	$d_A d_B$	$r_B^2$	$c_B^2$	$d_B^2$
PD	9	$-21$	49	$-21$	1	1	49	9	1
Stag Hunt	4	$-8$	16	$-8$	16	16	16	4	16
Chicken	1	$-7$	49	$-7$	9	9	49	1	9
Pure Coord	0	0	0	0	4	4	0	0	4
Match Penn	0	0	0	0	16	$-16$	0	0	16

Table 19: Full degree-3 invariant values for the named-game representatives (see Section 16.1)

Game	$c_A d_A r_A$	$c_A d_B r_A$	$c_B d_A r_A$	$c_B d_B r_A$	$c_A d_A r_B$	$c_A d_B r_B$	$c_B d_A r_B$	$c_B d_B r_B$
PD	21	21	$-9$	$-9$	$-49$	$-49$	21	21
Stag Hunt	$-32$	$-32$	16	16	64	64	$-32$	$-32$
Chicken	21	21	$-3$	$-3$	$-147$	$-147$	21	21
Pure Coord	0	0	0	0	0	0	0	0
Match Penn	0	0	0	0	0	0	0	0

Appendix B. The $(3,3)$-Game Invariant Ring and Typology

Forthcoming.

Appendix C. The Wreath Product ($D_4$) Invariant Ring

C.0. Player Permutation and the Wreath Product

In the main text, we treat the players as distinguishable and use the direct product $G = (S_k)^n$ as the symmetry group. In some settings (e.g., evolutionary biology, anonymous mechanism design), the players are interchangeable: swapping who is player 1 and who is player 2 produces an equivalent game. When the players are interchangeable, we can additionally permute the players themselves. In an $n$-player $(n,k)$-game with payoff arrays $u_1, \ldots, u_n$, a permutation $\pi \in S_n$ acts by simultaneously permuting the payoff arrays and their indices:

\[ (\pi \cdot u_j)(s_1, \ldots, s_n) = u_{\pi^{-1}(j)}(s_{\pi^{-1}(1)}, \ldots, s_{\pi^{-1}(n)}) \]

The payoff array that belonged to player $j$ now belongs to player $\pi(j)$, and the strategy indices are permuted accordingly. For a two-player game, the transposition $\pi = (12) \in S_2$ acts by $\pi \cdot (A, B) = (B^\top, A^\top)$. The transpose appears because swapping who is the row player and who is the column player exchanges the matrix indices. Combining strategy relabeling with player permutation requires the semidirect product, which we now define.

We call a bijection $\varphi : H \to H$ a group automorphism if $\varphi(h_1 h_2) = \varphi(h_1)\varphi(h_2)$ for all $h_1, h_2 \in H$. Let $H$ and $K$ be groups, and suppose $K$ acts on $H$ by automorphisms (meaning each $k \in K$ defines a group automorphism $h \mapsto k(h)$ of $H$). We call the semidirect product $H \rtimes K$ the group with underlying set $H \times K$ and multiplication

\[ (h_1, k_1) \cdot (h_2, k_2) = (h_1 \cdot k_1(h_2), \, k_1 k_2) \]

where $k_1(h_2)$ is the result of $k_1$ acting on $h_2$. When $K$ acts trivially ($k(h) = h$ for all $k, h$), this reduces to the direct product.

For an $(n,k)$-game, the strategy permutations form $H = (S_k)^n$ and the player permutations form $K = S_n$. A player permutation $\pi \in S_n$ acts on $H$ by rearranging the factors: the strategy permutation that was acting on player $i$ now acts on player $\pi(i)$. Explicitly,

\[ \pi \cdot (\sigma_1, \ldots, \sigma_n) = (\sigma_{\pi^{-1}(1)}, \ldots, \sigma_{\pi^{-1}(n)}) \]

We call the resulting semidirect product $(S_k)^n \rtimes S_n$ the wreath product of $S_k$ with $S_n$, sometimes written $S_k \wr S_n$. It has $(k!)^n \cdot n!$ elements. The direct product does not suffice because the player permutation rearranges which strategy permutation acts on which player: first relabeling player 1’s strategies and then swapping players gives a different result than first swapping and then relabeling.

For $(2,2)$-games, the wreath product is $S_2 \wr S_2 = (S_2 \times S_2) \rtimes S_2$, which is the dihedral group $D_4$ of order 8.

C.0b. The $D_4$ Computation

In this appendix we compute the invariant ring of $(2,2)$-games under the enlarged group $D_4 = (S_2 \times S_2) \rtimes S_2$ (order 8), which includes the player swap $(A, B) \mapsto (B^\top, A^\top)$ in addition to the strategy relabeling of the main text. This is the appropriate symmetry group when the two players are interchangeable (anonymous games). The ring has 22 generators (compared to 17 under $S_2 \times S_2$), with non-trivial syzygies involving an advantage asymmetry quantity $\mathcal{D} = (c_A r_A - c_B r_B)^2$. The $D_4$ ring generalizes the 78-type classification of Rapoport and Guyer (1966), who additionally identified the two players, just as the $S_2 \times S_2$ ring generalizes the 144-type classification of Robinson and Goforth (2005).

We work in the same mean-zero coordinates $(r_A, c_A, d_A, r_B, c_B, d_B)$ defined in the $(2,2)$-Games section. The player swap acts on these coordinates as $r_A \leftrightarrow c_B$, $c_A \leftrightarrow r_B$, $d_A \leftrightarrow d_B$, derived from $(A, B) \mapsto (B^\top, A^\top)$.

We use the same normalization conventions as the main text: unnormalized coordinates (no factor of $\frac{1}{2}$) and orbit-sum Reynolds operator (following Sturmfels 2008). All invariant values on games with integer payoffs are integers.

C.1. Molien Series and Generators

The Molien series for $D_4$ acting on $\mathbb{R}^6$ is

\[ M(t) = 1 + 0 \cdot t + 5t^2 + 4t^3 + 23t^4 + 24t^5 + 71t^6 + 84t^7 + 186t^8 + \cdots \]

The following table decomposes $h_d$ into products and new generators at each degree.

Degree	$h_d$ (Molien)	From products	New generators
0	1	1	0
1	0	0	0
2	5	0	5 ($I_0, \ldots, I_4$)
3	4	0	4 ($J_0, \ldots, J_3$)
4	23	15	8 ($K_0, \ldots, K_7$)
5	24	19	5 ($L_0, \ldots, L_4$)
6	71	71	0 (ring closes)

The ring has $5 + 4 + 8 + 5 = 22$ generators in total. We verify that no new generators appear at degrees 6, 7, or 8 by checking that the products of the 22 generators span spaces of dimension 71, 84, and 186 respectively, matching the Molien coefficients. By Noether’s bound, the invariant ring of a finite group of order $|G|$ is generated in degrees at most $|G|$. Since $|G| = 8$, no new generators can appear above degree 8, and the 22 generators are a complete generating set.

Id	Deg	Expression
$I_0$	2	$r_A^2 + c_B^2$
$I_1$	2	$r_A r_B + c_A c_B$
$I_2$	2	$c_A^2 + r_B^2$
$I_3$	2	$d_A^2 + d_B^2$
$I_4$	2	$d_A d_B$
$J_0$	3	$c_A d_A r_A + c_B d_B r_B$
$J_1$	3	$c_A d_B r_A + c_B d_A r_B$
$J_2$	3	$c_B r_A (d_A + d_B)$
$J_3$	3	$c_A r_B (d_A + d_B)$
$K_0$	4	$c_B^4 + r_A^4$
$K_1$	4	$c_A c_B^3 + r_A^3 r_B$
$K_2$	4	$c_A^2 r_A^2 + c_B^2 r_B^2$
$K_3$	4	$c_B^2 d_B^2 + d_A^2 r_A^2$
$K_4$	4	$c_A^2 r_A r_B + c_A c_B r_B^2$
$K_5$	4	$c_A c_B d_B^2 + d_A^2 r_A r_B$
$K_6$	4	$c_A^4 + r_B^4$
$K_7$	4	$c_A^2 d_A^2 + d_B^2 r_B^2$
$L_0$	5	$c_A d_A r_A^3 + c_B^3 d_B r_B$
$L_1$	5	$c_B^3 d_B r_A + c_B d_A r_A^3$
$L_2$	5	$c_A c_B^2 d_B r_B + c_A d_A r_A^2 r_B$
$L_3$	5	$c_A^3 d_A r_A + c_B d_B r_B^3$
$L_4$	5	$c_A^3 d_A r_B + c_A d_B r_B^3$

Each generator is an orbit sum of a monomial under $D_4$. The pairing $r_A \leftrightarrow c_B$ and $c_A \leftrightarrow r_B$ in each expression reflects the player swap $(A, B) \mapsto (B^\top, A^\top)$.

The invariant $I_4 = d_A d_B$ is the product of the two players’ interaction terms. Its sign separates coordination-type games ($I_4 > 0$) from anti-coordination-type games ($I_4 < 0$). The invariant $I_4$ also equals the Nash equilibrium discriminant: an interior NE exists if and only if $I_4 \neq 0$.

The invariants $I_0 = r_A^2 + c_B^2$ and $I_2 = c_A^2 + r_B^2$ measure advantage magnitudes, but each mixes two players’ coordinates. This mixing is forced by the player swap: since $r_A \leftrightarrow c_B$ under the swap, no invariant can separate $r_A^2$ from $c_B^2$. The degree-4 generator $K_0 = r_A^4 + c_B^4$ resolves this: from $I_0$ and $K_0$ together, one can recover $r_A^2 c_B^2 = \frac{1}{2}(I_0^2 - K_0)$, which measures how evenly the advantage is split between the two players.

The invariant $I_1 = r_A r_B + c_A c_B$ measures cross-player advantage alignment. The quantity $I_0 I_2 - I_1^2 = (c_A r_A - c_B r_B)^2$ will appear as the central syzygy quantity.

The degree-3 generators $J_0, \ldots, J_3$ are the lowest-degree invariants that involve all three types of coordinates ($r$, $c$, and $d$) simultaneously. They measure how the advantage structure couples to the interaction structure. For games with no advantage structure ($r_A = c_A = r_B = c_B = 0$, such as Pure Coordination and Matching Pennies), all cubic generators vanish.

The 22 generators define a map $\pi : \mathbb{R}^6 \to \mathbb{R}^{22}$ that sends each game to its invariant values. Two games lie in the same $D_4$-orbit if and only if they have the same image under $\pi$.

C.2. Syzygies

The 22 generators are not algebraically independent. We find syzygies by expanding each product of generators as a polynomial in $(r_A, c_A, d_A, r_B, c_B, d_B)$, collecting the monomial coefficients into an integer matrix, and computing its exact null space (see Appendix D; script: game_invariants/syzygies_exact.py).

At degree 4, all 15 products $I_i I_j$ are linearly independent. The first syzygy appears at degree 5:

\[ S_1: \quad I_1(J_0 + J_1) = I_0 J_3 + I_2 J_2 \]

At degree 6, there are two syzygies. Both factor through the advantage asymmetry

\[ \mathcal{D} = I_0 I_2 - I_1^2 = (c_A r_A - c_B r_B)^2 \]

which is the squared difference between player 1’s row-column advantage product and player 2’s. The degree-6 syzygies are

\[ S_{2a}: \quad I_3 \cdot \mathcal{D} = J_0^2 + J_1^2 - 2 J_2 J_3 \]

\[ S_{2b}: \quad I_4 \cdot \mathcal{D} = J_0 J_1 - J_2 J_3 \]

Degree	Products	Rank	Syzygies	Notes
4	15	15	0	All $I_i I_j$ independent
5	20	19	1	$S_1$
6	45	43	2	$S_{2a}, S_{2b}$, both through $\mathcal{D}$
7	60	55	5
8	120	106	14

When $\mathcal{D} = 0$, the syzygies simplify to $J_0^2 + J_1^2 = 2 J_2 J_3$ and $J_0 J_1 = J_2 J_3$, which together imply $J_0 = J_1$ and $J_0^2 = J_2 J_3$. On the advantage-symmetric locus ($\mathcal{D} = 0$), the four cubic generators collapse to one degree of freedom.

All five named games satisfy $\mathcal{D} = 0$, meaning named games live on the advantage-symmetric locus, a measure-zero subset of the full space. When $\mathcal{D} \neq 0$, the syzygies express the squared cubic invariants as products of $\mathcal{D}$ with the interaction invariants $I_3$ and $I_4$, constraining the cubic invariants once the advantage asymmetry is known.

C.3. Game Classes

Class	Condition on invariants	Derivation
Potential	$I_3 = 2 I_4$	$I_3 - 2I_4 = (d_A - d_B)^2 = 0$ iff $d_A = d_B$
Anti-potential	$I_3 = -2 I_4$	$I_3 + 2I_4 = (d_A + d_B)^2 = 0$ iff $d_A = -d_B$
Symmetric	$I_3 = 2 I_4$ and $\mathcal{D} = 0$	Potential + advantage symmetry
Zero-sum	$I_3 = -2 I_4$ and $\mathcal{D} = 0$	Anti-potential + advantage symmetry (necessary, not sufficient at degree 2)
Coordination type	$I_4 > 0$	$d_A d_B > 0$: interactions aligned
Anti-coordination type	$I_4 < 0$	$d_A d_B < 0$: interactions opposed

The Nash equilibrium discriminant for $(2,2)$-games is $\text{disc} = d_A d_B = I_4$. An interior Nash equilibrium exists if and only if $I_4 \neq 0$.

C.4. Named Games

Degree-2 invariants:

Game	$I_0$	$I_1$	$I_2$	$I_3$	$I_4$
PD	18	$-42$	98	2	1
Stag Hunt	8	$-16$	32	32	16
Chicken	2	$-14$	98	18	9
Pure Coord	0	0	0	8	4
Match Penn	0	0	0	32	$-16$

Degree-3 invariants:

Game	$J_0$	$J_1$	$J_2$	$J_3$
PD	42	42	$-18$	$-98$
Stag Hunt	$-64$	$-64$	32	128
Chicken	42	42	$-6$	$-294$
Pure Coord	0	0	0	0
Match Penn	0	0	0	0

Degree-4 invariants:

Game	$K_0$	$K_1$	$K_2$	$K_3$	$K_4$	$K_5$	$K_6$	$K_7$
PD	162	$-378$	882	18	$-2058$	$-42$	4802	98
Stag Hunt	32	$-64$	128	128	$-256$	$-256$	512	512
Chicken	2	$-14$	98	18	$-686$	$-126$	4802	882
Pure Coord	0	0	0	0	0	0	0	0
Match Penn	0	0	0	0	0	0	0	0

Degree-5 invariants:

Game	$L_0$	$L_1$	$L_2$	$L_3$	$L_4$
PD	378	$-162$	$-882$	2058	$-4802$
Stag Hunt	$-256$	128	512	$-1024$	2048
Chicken	42	$-6$	$-294$	2058	$-14406$
Pure Coord	0	0	0	0	0
Match Penn	0	0	0	0	0

Game	$I_3 - 2I_4$	$I_3 + 2I_4$	Potential	Symmetric	Coord type	Pure NE
PD	0	4	yes	yes	yes	$(2,2)$
Stag Hunt	0	64	yes	yes	yes	$(1,1), (2,2)$
Chicken	0	36	yes	yes	yes	$(1,2), (2,1)$
Pure Coord	0	16	yes	yes	yes	$(1,1), (2,2)$
Match Penn	64	0	no	no	no	none

All four cooperative games are potential and symmetric. Matching Pennies is anti-potential. All five satisfy $\mathcal{D} = 0$, confirming that named games are advantage-symmetric.

C.5. Solvability

For $(2,2)$-games, player 1 has a dominant strategy if and only if $r_A + d_A$ and $d_A - r_A$ have the same sign. These conditions cannot be expressed as polynomial conditions on $I_0, \ldots, I_4$, because the invariants mix $r_A$ with $c_B$ (the player swap pairs them). Solvability is a semialgebraic condition. The degree-4 invariants $K_3$ and $K_7$ partially resolve this ambiguity.

C.6. Relation to Ordinal Classifications

Rapoport and Guyer (1966) classified $(2,2)$-games into 78 strict ordinal types. Robinson and Goforth (2005) extended this to 144 types by distinguishing the two players’ roles.

The ordinal type is determined by the signs of the six pairwise payoff differences per player. In mean-zero coordinates, the differences for player 1 are

\[ a_1 - a_2 = \frac{1}{2}(c_A + d_A), \quad a_1 - a_3 = \frac{1}{2}(r_A + d_A), \quad a_1 - a_4 = \frac{1}{2}(r_A + c_A) \] \[ a_2 - a_3 = \frac{1}{2}(r_A - c_A), \quad a_2 - a_4 = \frac{1}{2}(r_A - d_A), \quad a_3 - a_4 = \frac{1}{2}(d_A - c_A) \]

The 12 hyperplanes (6 per player) partition $\mathbb{R}^6$ into chambers. Each chamber is a strict ordinal type.

The ordinal and invariant-ring classifications are related but not equivalent, in two ways. First, the ordinal map is piecewise-constant while $\pi$ is continuous. Two games in the same chamber have the same ordinal type but generically different invariant values. Second, the two maps quotient by different groups. Robinson and Goforth quotient by $S_2 \times S_2$ (strategy relabeling only), while the $D_4$ invariant ring additionally identifies the two players. For symmetric games ($B = \pm A^\top$), the two quotients agree. For asymmetric games, the player swap can merge Robinson-Goforth classes. For example, the game $(5, 1, 3, 2, 4, 0, 6, 3)$ has a $D_4$ orbit of size 8 containing two Robinson-Goforth classes of size 4.

The Rapoport-Guyer count of 78 types corresponds to the $D_4$ quotient of the ordinal chambers: $576 / 8 = 72$ generic orbits, plus additional types from orbits of size 4 on the symmetric locus.

The $D_4$ invariant ring is finer than the ordinal classification in the cardinal direction (it retains magnitudes) and coarser in the player-labeling direction (it identifies the two players).

Appendix D. Software

All computations are reproducible from the companion code repository. Each script is standalone Python with only NumPy and SymPy as dependencies, and is in demonstrandom-public-code/invariants/game_invariants/. Each has a __main__ block runnable directly with python scriptname.py.

The scripts are reproduced below for reference. The cleaned-up versions trim docstrings and exploratory print formatting; the algorithm itself is unchanged from the source files.

D.1. Generator computation ($S_2 \times S_2$ ring)

The 17 generators of the $(2,2)$ invariant ring under strategy relabeling are computed by Reynolds-averaging degree-$d$ monomials and testing linear independence against products of previously found generators. Ring closure is verified at degrees 4, 5, and 6.

game_invariants/generators_2x2_strategy_only.py:

Show code

import numpy as np
from itertools import combinations_with_replacement
from sympy import symbols, expand

rA, cA, dA, rB, cB, dB = symbols('rA cA dA rB cB dB')
VARS = [rA, cA, dA, rB, cB, dB]


def build_s2xs2():
    """S_2 x S_2 acting on (rA, cA, dA, rB, cB, dB) by row/col sign flips."""
    I = np.eye(6)
    s1 = np.diag([-1, 1, -1, -1, 1, -1.0])  # row swap
    s2 = np.diag([1, -1, -1, 1, -1, -1.0])  # col swap
    return [I, s1, s2, s1 @ s2]


def reynolds_symbolic(exp_vec, group):
    total = 0
    for g in group:
        gv = [sum(int(round(g[i, j])) * VARS[j] for j in range(6)) for i in range(6)]
        mono = 1
        for k, e in enumerate(exp_vec):
            mono *= gv[k] ** e
        total += mono
    return expand(total / len(group))


def reynolds_numerical(exp_vec, group, points):
    n = len(points)
    vals = np.zeros(n)
    for g in group:
        for j in range(n):
            gpt = g @ points[j]
            v = 1.0
            for k, e in enumerate(exp_vec):
                v *= gpt[k] ** e
            vals[j] += v
    return vals / len(group)


def find_all_generators(group, n_pts=400, seed=42, max_deg=4):
    """Find generators up to Noether bound = |G| = 4."""
    rng = np.random.default_rng(seed)
    pts = 2 * rng.standard_normal((n_pts, 6))
    all_num, all_sym, all_deg = [], [], []
    molien = {}

    for deg in range(max_deg + 1):
        mono_list = []
        for combo in combinations_with_replacement(range(6), deg):
            exp = [0] * 6
            for c in combo:
                exp[c] += 1
            if tuple(exp) not in mono_list:
                mono_list.append(tuple(exp))
        if not mono_list:
            mono_list = [(0,) * 6]

        prods = []
        for i in range(len(all_num)):
            for j in range(i, len(all_num)):
                if all_deg[i] + all_deg[j] == deg:
                    prods.append(all_num[i] * all_num[j])
            for j in range(i, len(all_num)):
                for k in range(j, len(all_num)):
                    if all_deg[i] + all_deg[j] + all_deg[k] == deg:
                        prods.append(all_num[i] * all_num[j] * all_num[k])

        prod_mat = np.array(prods) if prods else np.zeros((0, n_pts))
        current = prod_mat.copy() if len(prods) > 0 else np.zeros((0, n_pts))
        current_rank = np.linalg.matrix_rank(current, tol=1e-8) if current.shape[0] else 0

        for m in mono_list:
            rv = reynolds_numerical(m, group, pts)
            test = rv.reshape(1, -1) if current.shape[0] == 0 else np.vstack([current, rv.reshape(1, -1)])
            r = np.linalg.matrix_rank(test, tol=1e-8)
            if r > current_rank:
                all_num.append(rv)
                all_sym.append(reynolds_symbolic(m, group))
                all_deg.append(deg)
                current, current_rank = test, r

        molien[deg] = current_rank
    return all_sym, all_deg, molien


def eval_generators(rA, cA, dA, rB, cB, dB):
    """The 17 generators: 9 degree-2 (squares and cross-products), 8 degree-3 triples."""
    deg2 = [rA**2, rA*rB, cA**2, cA*cB, dA**2, dA*dB, rB**2, cB**2, dB**2]
    deg3 = [cA*dA*rA, cA*dB*rA, cB*dA*rA, cB*dB*rA,
            cA*dA*rB, cA*dB*rB, cB*dA*rB, cB*dB*rB]
    return deg2 + deg3


if __name__ == '__main__':
    G = build_s2xs2()
    gens_sym, gens_deg, molien = find_all_generators(G)
    print(f"Total generators: {len(gens_sym)}; Molien: {[molien[d] for d in range(5)]}")
    for i, (expr, deg) in enumerate(zip(gens_sym, gens_deg)):
        print(f"  g{i} (deg {deg}) = {expr}")

    rng = np.random.default_rng(42)
    pts = 2 * rng.standard_normal((400, 6))
    gen_vals = np.array([eval_generators(*pt) for pt in pts])
    for check_deg in [4, 5, 6]:
        prods = []
        for i in range(17):
            di = 2 if i < 9 else 3
            for j in range(i, 17):
                dj = 2 if j < 9 else 3
                if di + dj == check_deg:
                    prods.append(gen_vals[:, i] * gen_vals[:, j])
                for k in range(j, 17):
                    dk = 2 if k < 9 else 3
                    if di + dj + dk == check_deg:
                        prods.append(gen_vals[:, i] * gen_vals[:, j] * gen_vals[:, k])
        rank = np.linalg.matrix_rank(np.array(prods), tol=1e-8)
        expected = {4: 42, 5: 48, 6: 138}[check_deg]
        print(f"Closure deg {check_deg}: rank={rank}, Molien={expected}")

D.1b. Generator computation ($D_4$ ring)

The 22 generators of the $(2,2)$ invariant ring under the wreath product $D_4 = (S_2 \times S_2) \rtimes S_2$ (including player swap) are computed by the same method. The action on $(r_A, c_A, d_A, r_B, c_B, d_B)$ has three generators: row flip, column flip, and the player swap sending $r_A \leftrightarrow c_B$, $c_A \leftrightarrow r_B$, $d_A \leftrightarrow d_B$ (derived from $(A,B) \mapsto (B^\top, A^\top)$).

game_invariants/generators_2x2_mz.py:

Show code

import numpy as np
from itertools import combinations_with_replacement
from sympy import symbols, expand


def build_d4():
    """All 8 elements of D_4 = (S_2 x S_2) >| S_2 as 6x6 matrices."""
    s1 = np.diag([-1, 1, -1, -1, 1, -1.0])
    s2 = np.diag([1, -1, -1, 1, -1, -1.0])
    sw = np.array([[0,0,0,0,1,0],[0,0,0,1,0,0],[0,0,0,0,0,1],
                   [0,1,0,0,0,0],[1,0,0,0,0,0],[0,0,1,0,0,0]], dtype=float)
    group, seen, queue = [], set(), [np.eye(6)]
    while queue:
        g = queue.pop()
        key = tuple(g.flatten().round(10))
        if key in seen:
            continue
        seen.add(key)
        group.append(g)
        queue.extend([g @ s1, g @ s2, g @ sw])
    return group


def reynolds_symbolic(exp_vec, group):
    rA, cA, dA, rB, cB, dB = symbols('rA cA dA rB cB dB')
    sym_vars = [rA, cA, dA, rB, cB, dB]
    total = 0
    for g in group:
        gv = [sum(int(g[i, j]) * sym_vars[j] for j in range(6)) for i in range(6)]
        mono = 1
        for k, e in enumerate(exp_vec):
            mono *= gv[k] ** e
        total += mono
    return expand(total / len(group))


def reynolds_numerical(exp_vec, group, points):
    vals = np.zeros(len(points))
    for g in group:
        for j, pt in enumerate(points):
            gpt = g @ pt
            v = 1.0
            for k, e in enumerate(exp_vec):
                v *= gpt[k] ** e
            vals[j] += v
    return vals / len(group)


def eval_known_generators(pt):
    """I0..I4 (deg 2) and J0..J3 (deg 3)."""
    rA, cA, dA, rB, cB, dB = pt
    I0 = dA**2 + dB**2
    I1 = rA**2 + cB**2
    I2 = cA**2 + rB**2
    I3 = dA * dB
    I4 = rA * rB + cA * cB
    J0 = rA * cA * dA + rB * cB * dB
    J1 = rA * cA * dB + rB * cB * dA
    J2 = cA * rB * (dA + dB)
    J3 = rA * cB * (dA + dB)
    return np.array([I0, I1, I2, I3, I4, J0, J1, J2, J3])


def find_new_generators(target_degree, group, n_pts=300, seed=42):
    """New generators at target_degree, independent of products of lower-degree ones."""
    rng = np.random.default_rng(seed)
    pts = rng.standard_normal((n_pts, 6))
    vals = np.array([eval_known_generators(pt) for pt in pts])
    degs = [2]*5 + [3]*4

    products = []
    for i in range(9):
        for j in range(i, 9):
            if degs[i] + degs[j] == target_degree:
                products.append(vals[:, i] * vals[:, j])
        for j in range(i, 9):
            for k in range(j, 9):
                if degs[i] + degs[j] + degs[k] == target_degree:
                    products.append(vals[:, i] * vals[:, j] * vals[:, k])

    product_matrix = np.array(products) if products else np.zeros((0, n_pts))
    base_rank = np.linalg.matrix_rank(product_matrix, tol=1e-8)

    mono_list = []
    for combo in combinations_with_replacement(range(6), target_degree):
        exp = [0] * 6
        for c in combo:
            exp[c] += 1
        if tuple(exp) not in mono_list:
            mono_list.append(tuple(exp))

    current, current_rank = product_matrix.copy(), base_rank
    new_gens = []
    for m in mono_list:
        r_vals = reynolds_numerical(m, group, pts)
        test = np.vstack([current, r_vals.reshape(1, -1)])
        r = np.linalg.matrix_rank(test, tol=1e-8)
        if r > current_rank:
            new_gens.append((m, reynolds_symbolic(m, group)))
            current, current_rank = test, r
    return new_gens, base_rank, current_rank


if __name__ == '__main__':
    G = build_d4()
    print(f"D_4 order: {len(G)}")
    expected = {2: 5, 3: 4, 4: 8, 5: 5, 6: 0}
    for deg in [2, 3, 4, 5, 6]:
        new_gens, prod_rank, total_rank = find_new_generators(deg, G)
        print(f"Degree {deg}: products rank {prod_rank}, total rank {total_rank}, "
              f"new generators {len(new_gens)} (expect {expected[deg]})")

D.2. Syzygy computation, wreath product ring

Syzygies are computed by exact symbolic expansion. For each target degree $d$, we enumerate all products of generators of total degree $d$, expand each as a polynomial in $(r_A, c_A, d_A, r_B, c_B, d_B)$, collect monomial coefficients into an integer matrix $M$, and compute the null space of $M$ over $\mathbb{Q}$ using SymPy. Each null vector is a syzygy.

game_invariants/syzygies_exact.py:

Show code

from sympy import symbols, expand, Poly, Matrix, factor

rA, cA, dA, rB, cB, dB = symbols('rA cA dA rB cB dB')
VARS = [rA, cA, dA, rB, cB, dB]

I = [rA**2 + cB**2, rA*rB + cA*cB, cA**2 + rB**2, dA**2 + dB**2, dA*dB]
J = [cA*dA*rA + cB*dB*rB, cA*dB*rA + cB*dA*rB,
     cB*rA*(dA + dB), cA*rB*(dA + dB)]
I_NAMES = ['I0', 'I1', 'I2', 'I3', 'I4']
J_NAMES = ['J0', 'J1', 'J2', 'J3']


def find_syzygies_at_degree(target_deg):
    gens = I + J
    names = I_NAMES + J_NAMES
    degs = [2]*5 + [3]*4
    n = len(gens)

    products, prod_names = [], []
    for i in range(n):
        for j in range(i, n):
            if degs[i] + degs[j] == target_deg:
                products.append(expand(gens[i] * gens[j]))
                prod_names.append(f'{names[i]}*{names[j]}')
        for j in range(i, n):
            for k in range(j, n):
                if degs[i] + degs[j] + degs[k] == target_deg:
                    products.append(expand(gens[i] * gens[j] * gens[k]))
                    prod_names.append(f'{names[i]}*{names[j]}*{names[k]}')

    if not products:
        return [], [], 0

    polys = [Poly(p, VARS) for p in products]
    monos = sorted({m for p in polys for m in p.as_dict()})
    M = Matrix([[p.as_dict().get(m, 0) for p in polys] for m in monos])
    return prod_names, M.nullspace(), M.rank()


def format_syzygy(prod_names, vec):
    pos = [(vec[i], prod_names[i]) for i in range(len(prod_names)) if vec[i] > 0]
    neg = [(-vec[i], prod_names[i]) for i in range(len(prod_names)) if vec[i] < 0]
    lhs = ' + '.join(f'{c}*{n}' if c != 1 else n for c, n in pos)
    rhs = ' + '.join(f'{c}*{n}' if c != 1 else n for c, n in neg)
    return f'{lhs} = {rhs}'


if __name__ == '__main__':
    for deg in [4, 5, 6]:
        names, null_vecs, rank = find_syzygies_at_degree(deg)
        print(f'Degree {deg}: {len(names)} products, rank {rank}, {len(null_vecs)} syzygies')
        for idx, vec in enumerate(null_vecs):
            print(f'  S{idx+1}: {format_syzygy(names, vec)}')
    D = expand(I[0]*I[2] - I[1]**2)
    print(f'D = I0*I2 - I1^2 = {factor(D)}')

D.3. Molien series

Molien series for $(n,2)$-games under the wreath product $S_n \wr Z_2$ are computed via conjugacy classes parameterized by bipartitions, using Newton’s identity to recover the degree-$d$ coefficient from fixed-point counts of $g^k$.

game_invariants/scaling.py:

Show code

from collections import Counter
from math import factorial


def partitions(n, max_val=None):
    if max_val is None:
        max_val = n
    if n == 0:
        yield ()
        return
    for k in range(min(n, max_val), 0, -1):
        for rest in partitions(n - k, k):
            yield (k,) + rest


def bipartitions(n):
    """Conjugacy classes of S_n wr Z_2 are bipartitions (alpha, beta) of n."""
    for a in range(n + 1):
        for alpha in partitions(a):
            for beta in partitions(n - a):
                yield alpha, beta


def centralizer_order(alpha, beta):
    result = 1
    for parts in [alpha, beta]:
        for k, m in Counter(parts).items():
            result *= (2 * k) ** m * factorial(m)
    return result


def class_size(alpha, beta, n):
    return factorial(n) * 2 ** n // centralizer_order(alpha, beta)


def build_representative(alpha, beta, n):
    """Induced permutation on n * 2^n coordinates for bipartition (alpha, beta)."""
    num_profiles = 2 ** n
    dim = n * num_profiles
    sigma = list(range(n))
    epsilon = [0] * n
    pos = 0
    for k in alpha:
        for i in range(k - 1):
            sigma[pos + i] = pos + i + 1
        sigma[pos + k - 1] = pos
        pos += k
    for k in beta:
        for i in range(k - 1):
            sigma[pos + i] = pos + i + 1
        sigma[pos + k - 1] = pos
        epsilon[pos] = 1
        pos += k

    inv_sigma = [0] * n
    for i in range(n):
        inv_sigma[sigma[i]] = i

    perm = [0] * dim
    for p in range(n):
        for prof_int in range(num_profiles):
            prof = [(prof_int >> (n - 1 - q)) & 1 for q in range(n)]
            src_prof = [0] * n
            for q in range(n):
                sq = inv_sigma[q]
                src_prof[sq] = prof[q] ^ epsilon[sq]
            src_int = 0
            for q in range(n):
                src_int = (src_int << 1) | src_prof[q]
            perm[p * num_profiles + prof_int] = inv_sigma[p] * num_profiles + src_int
    return perm


def build_player_permutation(alpha, beta, n):
    sigma = list(range(n))
    pos = 0
    for parts in [alpha, beta]:
        for k in parts:
            for i in range(k - 1):
                sigma[pos + i] = pos + i + 1
            sigma[pos + k - 1] = pos
            pos += k
    return sigma


def fixed_points_of_power(perm, power):
    count = 0
    for i in range(len(perm)):
        j = i
        for _ in range(power):
            j = perm[j]
        if j == i:
            count += 1
    return count


def molien_conj(n, max_degree, mean_zero=False):
    """Molien series via Newton's identity over conjugacy classes."""
    group_order = factorial(n) * 2 ** n
    result = [0] * (max_degree + 1)
    for alpha, beta in bipartitions(n):
        csize = class_size(alpha, beta, n)
        perm = build_representative(alpha, beta, n)
        player_perm = build_player_permutation(alpha, beta, n) if mean_zero else None
        p = []
        for k in range(max_degree + 1):
            pk = fixed_points_of_power(perm, k)
            if mean_zero:
                pk -= fixed_points_of_power(player_perm, k)
            p.append(pk)
        h = [0] * (max_degree + 1)
        h[0] = 1
        for d in range(1, max_degree + 1):
            h[d] = sum(p[k] * h[d - k] for k in range(1, d + 1)) // d
        for d in range(max_degree + 1):
            result[d] += csize * h[d]
    return [r // group_order for r in result]


if __name__ == '__main__':
    print("n  full Molien (deg 0..3)    mean-zero Molien (deg 0..3)")
    for n in range(2, 9):
        full = molien_conj(n, 3, mean_zero=False)
        mz = molien_conj(n, 3, mean_zero=True)
        print(f"{n}  {full}    {mz}")
    print("\nDegree-2 formulas: full = 5n - 3, mean-zero = 5(n - 1)")
    for n in range(2, 9):
        full2 = molien_conj(n, 2)[2]
        mz2 = molien_conj(n, 2, mean_zero=True)[2]
        print(f"  n={n}: full={full2} (5n-3={5*n-3}), mz={mz2} (5(n-1)={5*(n-1)})")

D.3b. Degree-3 mean-zero Molien for $(n,2)$ under $(S_2)^n$

For the strategy-only group $(S_2)^n$ (no player swap), conjugacy class enumeration collapses since only the identity contributes a nonzero character on the full payoff space. Three forms of the same count agree numerically for $n = 2, \ldots, 6$: an explicit Molien average over $2^n$ group elements, the closed form obtained from collapsing the average, and the cleaner triple-count $n^3 (2^n - 1)(2^n - 2) / 6$ from Proposition 5.

game_invariants/degree3_mz_strategy_only.py:

Show code

from fractions import Fraction


def h3_mz_n2_closed_form(n: int) -> int:
    """Closed form from collapsing the Molien average over (S_2)^n."""
    M = n * (2 ** n - 1)
    g_order = 2 ** n
    id_term = M * (M + 1) * (M + 2)
    non_id_term = (g_order - 1) * (-n) * (n * n + 3 * M + 2)
    total = Fraction(id_term + non_id_term, 6 * g_order)
    assert total.denominator == 1
    return total.numerator


def h3_mz_n2_triple_count(n: int) -> int:
    """Cleaner closed form from prp-add-player-binary-degree-three:
    h_3(n,2) = n^3 * (2^n - 1)(2^n - 2) / 6."""
    return n ** 3 * (2 ** n - 1) * (2 ** n - 2) // 6


def h3_mz_n2_explicit(n: int) -> int:
    """Explicit average over all 2^n group elements."""
    N = n * (2 ** n)
    g_order = 2 ** n
    total = Fraction(0)
    for mask in range(g_order):
        n_swaps = bin(mask).count("1")
        chi = N if n_swaps == 0 else 0
        chi_sq = N        # g^2 = identity for any g in (S_2)^n
        chi_cu = N if n_swaps == 0 else 0
        chi_mz = chi - n
        chi_sq_mz = chi_sq - n
        chi_cu_mz = chi_cu - n
        total += Fraction(chi_mz ** 3 + 3 * chi_mz * chi_sq_mz + 2 * chi_cu_mz, 6)
    total /= g_order
    assert total.denominator == 1
    return total.numerator


if __name__ == '__main__':
    print(f"{'n':>3}  {'dim_mz':>8}  {'|G|':>6}  {'h_3':>10}")
    for n in range(2, 7):
        M = n * (2 ** n - 1)
        h_closed = h3_mz_n2_closed_form(n)
        h_triple = h3_mz_n2_triple_count(n)
        h_explicit = h3_mz_n2_explicit(n)
        assert h_closed == h_triple == h_explicit
        print(f"{n:>3}  {M:>8}  {2**n:>6}  {h_closed:>10}")

D.4. $S_2 \times S_2$ syzygies

The same SymPy null-space approach as D.2, run on the 17 generators of the strategy-relabeling ring.

game_invariants/syzygies_strategy_only.py:

Show code

from sympy import symbols, expand, Poly, Matrix

rA, cA, dA, rB, cB, dB = symbols('rA cA dA rB cB dB')
VARS = [rA, cA, dA, rB, cB, dB]

I = [rA**2, rA*rB, cA**2, cA*cB, dA**2, dA*dB, rB**2, cB**2, dB**2]
J = [cA*dA*rA, cA*dB*rA, cB*dA*rA, cB*dB*rA,
     cA*dA*rB, cA*dB*rB, cB*dA*rB, cB*dB*rB]
I_NAMES = ['rA2','rArB','cA2','cAcB','dA2','dAdB','rB2','cB2','dB2']
J_NAMES = ['cAdArA','cAdBrA','cBdArA','cBdBrA',
           'cAdArB','cAdBrB','cBdArB','cBdBrB']


def find_syzygies_at_degree(target_deg):
    gens = I + J
    names = I_NAMES + J_NAMES
    degs = [2]*9 + [3]*8

    products, prod_names = [], []
    for i in range(17):
        for j in range(i, 17):
            if degs[i] + degs[j] == target_deg:
                products.append(expand(gens[i] * gens[j]))
                prod_names.append(f'{names[i]}*{names[j]}')
        for j in range(i, 17):
            for k in range(j, 17):
                if degs[i] + degs[j] + degs[k] == target_deg:
                    products.append(expand(gens[i] * gens[j] * gens[k]))
                    prod_names.append(f'{names[i]}*{names[j]}*{names[k]}')

    if not products:
        return [], [], 0
    polys = [Poly(p, VARS) for p in products]
    monos = sorted({m for p in polys for m in p.as_dict()})
    M = Matrix([[p.as_dict().get(m, 0) for p in polys] for m in monos])
    return prod_names, M.nullspace(), M.rank()


if __name__ == '__main__':
    for deg in [4, 5, 6]:
        names, null_vecs, rank = find_syzygies_at_degree(deg)
        print(f'Degree {deg}: {len(names)} products, rank {rank}, {len(null_vecs)} syzygies')

D.5. Wreath product ($D_4$) syzygies

Same script as D.2 (syzygies_exact.py). The output records 3 trivial degree-4 syzygies, 1 degree-5 syzygy, and 2 degree-6 syzygies factoring through $\mathcal{D} = I_0 I_2 - I_1^2 = (c_A r_A - c_B r_B)^2$.

D.6. Robinson-Goforth recovery

The recovery of the 144 Robinson-Goforth types from invariant sign conditions is verified by exhaustive enumeration of all $24 \times 24 = 576$ strict-ordinal type pairs, grouped by $S_2 \times S_2$ orbit.

game_invariants/rg_from_invariants.py:

Show code

import numpy as np
from itertools import permutations


def mean_zero(a1, a2, a3, a4, b1, b2, b3, b4):
    rA = a1 + a2 - a3 - a4
    cA = a1 - a2 + a3 - a4
    dA = a1 - a2 - a3 + a4
    rB = b1 + b2 - b3 - b4
    cB = b1 - b2 + b3 - b4
    dB = b1 - b2 - b3 + b4
    return rA, cA, dA, rB, cB, dB


def eval_generators(rA, cA, dA, rB, cB, dB):
    deg2 = [rA**2, rA*rB, cA**2, cA*cB, dA**2, dA*dB, rB**2, cB**2, dB**2]
    deg3 = [cA*dA*rA, cA*dB*rA, cB*dA*rA, cB*dB*rA,
            cA*dA*rB, cA*dB*rB, cB*dA*rB, cB*dB*rB]
    return deg2 + deg3


def ordinal_type(payoffs):
    """Strict ordinal ranking as a tuple, or None if there is a tie."""
    sorted_idx = sorted(range(len(payoffs)), key=lambda i: payoffs[i])
    for i in range(len(payoffs) - 1):
        if payoffs[sorted_idx[i]] == payoffs[sorted_idx[i + 1]]:
            return None
    ranks = [0] * len(payoffs)
    for rank, idx in enumerate(sorted_idx):
        ranks[idx] = rank
    return tuple(ranks)


def rg_type(a, b):
    """Canonical R-G type: ordinal-pair orbit under S_2 x S_2."""
    ot_a, ot_b = ordinal_type(a), ordinal_type(b)
    if ot_a is None or ot_b is None:
        return None
    # S_2 x S_2 acts on 2x2 entries by row swap and column swap
    e = [0, 1, 2, 3]; s1 = [2, 3, 0, 1]; s2 = [1, 0, 3, 2]; s12 = [3, 2, 1, 0]
    orbit = {(tuple(ot_a[g[i]] for i in range(4)),
              tuple(ot_b[g[i]] for i in range(4)))
             for g in [e, s1, s2, s12]}
    return min(orbit)


def sign(x, tol=1e-10):
    return 1 if x > tol else (-1 if x < -tol else 0)


def enumerate_rg_types():
    """One game per R-G type, payoffs in {1, 2, 3, 4}."""
    rg_map = {}
    for pa in permutations(range(4)):
        for pb in permutations(range(4)):
            a = tuple(float(pa[i] + 1) for i in range(4))
            b = tuple(float(pb[i] + 1) for i in range(4))
            rgt = rg_type(a, b)
            if rgt is not None and rgt not in rg_map:
                rg_map[rgt] = (a, b)
    return rg_map


if __name__ == '__main__':
    rg_map = enumerate_rg_types()
    print(f"R-G types enumerated: {len(rg_map)} (expect 144)")

    # Signs of 17 generators + 9 magnitude comparisons
    pat_to_rg = {}
    collisions = 0
    for rgt, (a, b) in rg_map.items():
        gens = eval_generators(*mean_zero(*a, *b))
        signs = tuple(sign(g) for g in gens)
        comps = (
            sign(gens[0] - gens[2]), sign(gens[0] - gens[4]), sign(gens[2] - gens[4]),
            sign(gens[6] - gens[7]), sign(gens[6] - gens[8]), sign(gens[7] - gens[8]),
            sign(gens[0] - gens[6]), sign(gens[2] - gens[7]), sign(gens[4] - gens[8]),
        )
        pat = signs + comps
        if pat in pat_to_rg and pat_to_rg[pat] != rgt:
            collisions += 1
        else:
            pat_to_rg[pat] = rgt
    print(f"Signs + comparisons: {len(pat_to_rg)} patterns, {collisions} collisions")
    if collisions == 0 and len(pat_to_rg) == 144:
        print("VERIFIED: 17-generator signs + 9 comparisons exactly recover 144 R-G types")

game_invariants/rg_minimal.py greedily removes features from the 26-element list (17 signs + 9 comparisons) and tests separation power, recording the minimum subset that still distinguishes all 144 types:

Show code

import numpy as np
from itertools import permutations


# Reuses mean_zero, eval_generators, ordinal_type, rg_type, sign, enumerate_rg_types from D.6.


def test_features(rg_map, indices, all_features):
    pat_to_rg = {}
    for rgt, feats in all_features.items():
        pat = tuple(feats[i] for i in indices)
        if pat in pat_to_rg and pat_to_rg[pat] != rgt:
            return False
        pat_to_rg[pat] = rgt
    return len(pat_to_rg) == len(rg_map)


if __name__ == '__main__':
    rg_map = enumerate_rg_types()
    FEAT_NAMES = [
        'rA2', 'rArB', 'cA2', 'cAcB', 'dA2', 'dAdB', 'rB2', 'cB2', 'dB2',
        'cAdArA', 'cAdBrA', 'cBdArA', 'cBdBrA', 'cAdArB', 'cAdBrB', 'cBdArB', 'cBdBrB',
        'rA2-cA2', 'rA2-dA2', 'cA2-dA2',
        'rB2-cB2', 'rB2-dB2', 'cB2-dB2',
        'rA2-rB2', 'cA2-cB2', 'dA2-dB2',
    ]

    all_features = {}
    for rgt, (a, b) in rg_map.items():
        gens = eval_generators(*mean_zero(*a, *b))
        feats = [sign(g) for g in gens]
        feats += [sign(gens[0] - gens[2]), sign(gens[0] - gens[4]), sign(gens[2] - gens[4]),
                  sign(gens[6] - gens[7]), sign(gens[6] - gens[8]), sign(gens[7] - gens[8]),
                  sign(gens[0] - gens[6]), sign(gens[2] - gens[7]), sign(gens[4] - gens[8])]
        all_features[rgt] = feats

    # Greedy backward elimination
    current = set(range(len(FEAT_NAMES)))
    for i in reversed(range(len(FEAT_NAMES))):
        trial = sorted(current - {i})
        if test_features(rg_map, trial, all_features):
            current = set(trial)
    print(f"Minimal separating set: {len(current)} features")
    for i in sorted(current):
        print(f"  {i}: {FEAT_NAMES[i]}")

D.7. NE discriminant

For a $(2,k)$-game $(A,B)$, the two-player full-support indifference determinant is $\det(M_A) \det(M_B)$ where $M_A, M_B$ are the indifference matrices padded with a normalization row/column. The script verifies $(S_k)^2$-invariance and the proven degree $2(k-1)$ (Proposition 6) for $k = 2, 3, 4, 5$.

game_invariants/verify_ne_discriminant.py:

Show code

import numpy as np
from itertools import permutations


def ne_discriminant(A, B):
    k = A.shape[0]
    M_A = np.zeros((k, k))
    for i in range(k - 1):
        M_A[i, :] = A[0, :] - A[i + 1, :]
    M_A[k - 1, :] = 1.0
    M_B = np.zeros((k, k))
    for j in range(k - 1):
        M_B[:, j] = B[:, 0] - B[:, j + 1]
    M_B[:, k - 1] = 1.0
    return np.linalg.det(M_A) * np.linalg.det(M_B)


def apply_group_element(A, B, sigma1, sigma2):
    k = A.shape[0]
    P1 = np.zeros((k, k)); P2 = np.zeros((k, k))
    for i in range(k):
        P1[i, sigma1[i]] = 1.0
        P2[i, sigma2[i]] = 1.0
    return P1 @ A @ P2.T, P1 @ B @ P2.T


if __name__ == '__main__':
    rng = np.random.default_rng(42)

    # G-invariance at k = 3
    group = list(permutations(range(3)))
    max_err = 0
    for _ in range(1000):
        A = rng.standard_normal((3, 3)); B = rng.standard_normal((3, 3))
        d0 = ne_discriminant(A, B)
        for s1 in group:
            for s2 in group:
                A2, B2 = apply_group_element(A, B, s1, s2)
                max_err = max(max_err, abs(d0 - ne_discriminant(A2, B2)))
    print(f"k=3: max invariance error = {max_err:.2e}")

    # Degree by scaling
    for k in [2, 3, 4, 5]:
        A = rng.standard_normal((k, k)); B = rng.standard_normal((k, k))
        d1 = ne_discriminant(A, B)
        d2 = ne_discriminant(2 * A, 2 * B)
        if abs(d1) > 1e-10:
            ratio = d2 / d1
            print(f"k={k}: disc(2*game)/disc(game) = {ratio:.1f} (expect 2^{2*(k-1)} = {2**(2*(k-1))})")

For three-player binary games, the indifference system reduces by elimination to a quadratic in one mixing weight; its discriminant is a degree-6 polynomial in the payoff entries, verified $(S_2)^3$-invariant.

game_invariants/ne_disc_3_2_solve.py:

Show code

import numpy as np
from itertools import product as iproduct


def get_bilinear_coeffs(game):
    coeffs = []
    for p in range(3):
        others = sorted(q for q in range(3) if q != p)
        q, r = others
        D = np.zeros((2, 2))
        for sq in range(2):
            for sr in range(2):
                idx0 = [0]*3; idx1 = [0]*3
                idx0[p], idx1[p] = 0, 1
                idx0[q] = idx1[q] = sq
                idx0[r] = idx1[r] = sr
                D[sq, sr] = game[p][tuple(idx0)] - game[p][tuple(idx1)]
        a = D[1, 1]
        b = D[0, 1] - D[1, 1]
        c = D[1, 0] - D[1, 1]
        d = D[0, 0] - D[0, 1] - D[1, 0] + D[1, 1]
        coeffs.append((a, b, c, d))
    return coeffs


def ne_quadratic_discriminant(game):
    """Eliminate x_0 from f_1, f_2; then x_1 from f_0; collect quadratic in x_2."""
    (a0, b0, c0, d0), (a1, b1, c1, d1), (a2, b2, c2, d2) = get_bilinear_coeffs(game)
    E = a1*b2 - a2*b1
    F = a1*d2 - c2*b1
    G = c1*b2 - a2*d1
    H = c1*d2 - c2*d1
    A_co = G*d0 - H*c0
    B_co = E*d0 - F*c0 + G*b0 - H*a0
    C_co = E*b0 - F*a0
    return B_co**2 - 4 * A_co * C_co


def apply_s2_cubed(game, g):
    out = game.copy()
    for i in range(3):
        if g[i] == 1:
            out = np.flip(out, axis=i + 1)
    return out


if __name__ == '__main__':
    rng = np.random.default_rng(42)
    max_err = 0
    for _ in range(3000):
        game = rng.standard_normal((3, 2, 2, 2))
        d0 = ne_quadratic_discriminant(game)
        for g in iproduct([0, 1], repeat=3):
            d2 = ne_quadratic_discriminant(apply_s2_cubed(game, g))
            max_err = max(max_err, abs(d0 - d2))
    print(f"Max (S_2)^3 invariance error: {max_err:.2e}")

    game = rng.standard_normal((3, 2, 2, 2))
    d1 = ne_quadratic_discriminant(game)
    d2 = ne_quadratic_discriminant(2.0 * game)
    print(f"disc(2*game)/disc(game) = {d2/d1:.1f} (expect 2^6 = 64)")

For general $(n,2)$-games, the discriminant is computed via numerical Jacobian at the fully mixed NE, and its degree is verified by scaling.

game_invariants/ne_disc_degree.py:

Show code

import math
import numpy as np
from itertools import product as iproduct
from scipy.optimize import fsolve


def random_n2_game(n, rng):
    return rng.standard_normal((n,) + (2,) * n)


def indiff_coeffs_n2(game, player):
    n = game.shape[0]
    others = [q for q in range(n) if q != player]
    D = np.zeros((2,) * len(others))
    for s in iproduct([0, 1], repeat=len(others)):
        idx0 = [0] * n; idx1 = [0] * n
        idx0[player], idx1[player] = 0, 1
        for i, q in enumerate(others):
            idx0[q] = idx1[q] = s[i]
        D[s] = game[player][tuple(idx0)] - game[player][tuple(idx1)]
    return D, others


def eval_indiff(D, others, x):
    val = 0.0
    for s in iproduct([0, 1], repeat=len(others)):
        w = 1.0
        for i, q in enumerate(others):
            w *= x[q] if s[i] == 0 else (1 - x[q])
        val += D[s] * w
    return val


def ne_disc_n2(game):
    n = game.shape[0]
    Ds = [indiff_coeffs_n2(game, p) for p in range(n)]

    def system(x):
        return [eval_indiff(D, others, x) for D, others in Ds]

    sol, _, ier, _ = fsolve(system, np.full(n, 0.5), full_output=True)
    if max(abs(v) for v in system(sol)) > 1e-8:
        return None
    eps = 1e-7
    J = np.zeros((n, n))
    f0 = system(sol)
    for j in range(n):
        x2 = sol.copy(); x2[j] += eps
        f1 = system(x2)
        for i in range(n):
            J[i, j] = (f1[i] - f0[i]) / eps
    return np.linalg.det(J)


def ne_disc_2k(A, B):
    k = A.shape[0]
    M_A = np.zeros((k, k))
    for i in range(k - 1):
        M_A[i, :] = A[0, :] - A[i + 1, :]
    M_A[k - 1, :] = 1.0
    M_B = np.zeros((k, k))
    for j in range(k - 1):
        M_B[:, j] = B[:, 0] - B[:, j + 1]
    M_B[:, k - 1] = 1.0
    return np.linalg.det(M_A) * np.linalg.det(M_B)


if __name__ == '__main__':
    rng = np.random.default_rng(42)
    print(f"{'(n,k)':<8} {'predicted':<10} {'measured':<10}")
    for k in [2, 3, 4, 5]:
        predicted = 2 * (k - 1)
        A = rng.standard_normal((k, k)); B = rng.standard_normal((k, k))
        d1 = ne_disc_2k(A, B)
        d2 = ne_disc_2k(2 * A, 2 * B)
        deg = round(math.log2(abs(d2 / d1)))
        print(f"(2,{k})    {predicted:<10} {deg:<10}")
    for n in [2, 3, 4, 5]:
        predicted = n * (n - 1)
        ratios = []
        for _ in range(200):
            game = random_n2_game(n, rng)
            d1 = ne_disc_n2(game)
            d2 = ne_disc_n2(2 * game)
            if d1 is not None and d2 is not None and abs(d1) > 1e-10:
                ratios.append(d2 / d1)
        deg = round(math.log2(abs(np.median(ratios))))
        print(f"({n},2)    {predicted:<10} {deg:<10}")

D.8. Solvability

A $(2,2)$-game is solvable by iterated strict dominance if and only if at least one player has a strictly dominant strategy, equivalently $r_A^2 > d_A^2$ or $c_B^2 > d_B^2$ in mean-zero coordinates. Verified on 100,000 random games against a brute-force iterated-dominance solver.

game_invariants/verify_solvability.py:

Show code

import numpy as np


def mean_zero(a1, a2, a3, a4, b1, b2, b3, b4):
    rA = a1 + a2 - a3 - a4
    cA = a1 - a2 + a3 - a4
    dA = a1 - a2 - a3 + a4
    rB = b1 + b2 - b3 - b4
    cB = b1 - b2 + b3 - b4
    dB = b1 - b2 - b3 + b4
    return rA, cA, dA, rB, cB, dB


def is_solvable_brute(a1, a2, a3, a4, b1, b2, b3, b4):
    A = np.array([[a1, a2], [a3, a4]])
    B = np.array([[b1, b2], [b3, b4]])
    p1 = [True, True]; p2 = [True, True]
    changed = True
    while changed:
        changed = False
        a1 = [i for i in range(2) if p1[i]]; a2 = [j for j in range(2) if p2[j]]
        if len(a1) == 2:
            if all(A[0, j] > A[1, j] for j in a2):
                p1[1] = False; changed = True
            elif all(A[1, j] > A[0, j] for j in a2):
                p1[0] = False; changed = True
        a1 = [i for i in range(2) if p1[i]]; a2 = [j for j in range(2) if p2[j]]
        if len(a2) == 2:
            if all(B[i, 0] > B[i, 1] for i in a1):
                p2[1] = False; changed = True
            elif all(B[i, 1] > B[i, 0] for i in a1):
                p2[0] = False; changed = True
    return sum(p1) == 1 and sum(p2) == 1


def solvable_condition(rA, cA, dA, rB, cB, dB):
    """Solvable iff at least one player has a dominant strategy."""
    return rA**2 > dA**2 or cB**2 > dB**2


if __name__ == '__main__':
    rng = np.random.default_rng(42)
    n_mismatch = 0
    for _ in range(100000):
        payoffs = tuple(rng.standard_normal(8))
        brute = is_solvable_brute(*payoffs)
        cond = solvable_condition(*mean_zero(*payoffs))
        if brute != cond:
            n_mismatch += 1
    print(f"100,000 random games: {n_mismatch} mismatches "
          f"({'VERIFIED' if n_mismatch == 0 else 'FAIL'})")

D.9. Additional wreath product scripts

The following scripts compute invariants under the wreath product $(S_k)^n \rtimes S_n$ (including player swap). They are used for Appendix C and for the scaling law computations.

game_invariants/game_classes.py: game class subvarieties
game_invariants/potential_subvariety.py: potential games
game_invariants/separation.py, game_invariants/separating_2x2.py: orbit separation
game_invariants/br_type_invariants.py: best-response types
game_invariants/selection.py, game_invariants/cycles.py: adversarial difficulty
game_invariants/hodge.py, game_invariants/hodge_invariants.py: Hodge decomposition
game_invariants/cohen_macaulay.py: Cohen-Macaulay structure
game_invariants/syzygies.py, game_invariants/syzygies_3x3_mz.py: wreath product syzygies
game_invariants/scaling.py, game_invariants/stabilization.py: scaling laws

All scripts are in demonstrandom-public-code/invariants/game_invariants/. Each has a __main__ block and can be run directly with python scriptname.py.

D.10. Molien series for $(3,3)$ under $(S_3)^3$

Newton’s-identity Molien-coefficient computation over conjugacy classes of $(S_3)^3$ acting on the 78-dim mean-zero subspace. Output verifies $h = [1, 0, 42, 556, 9057]$ from the paper.

game_invariants/molien_3x3_strategy_only.py:

Show code

from fractions import Fraction


# S_3 conjugacy classes: (label, class_size).
S3_CLASSES = [('id', 1), ('tau', 3), ('gamma', 2)]


def fp_pow(cls_label: str, k: int) -> int:
    """Fixed points of sigma^k where sigma is in the named S_3 class."""
    if cls_label == 'id':
        return 3
    if cls_label == 'tau':
        return 3 if k % 2 == 0 else 1
    if cls_label == 'gamma':
        return 3 if k % 3 == 0 else 0
    raise ValueError(cls_label)


def molien_33_strategy_only(max_deg: int) -> list:
    G_order = 216
    h_total = [Fraction(0)] * (max_deg + 1)

    for c1, s1 in S3_CLASSES:
        for c2, s2 in S3_CLASSES:
            for c3, s3 in S3_CLASSES:
                class_size = s1 * s2 * s3
                # chi_mz(g^k) = chi_full(g^k) - 3
                chi_mz = [None] + [
                    3 * fp_pow(c1, k) * fp_pow(c2, k) * fp_pow(c3, k) - 3
                    for k in range(1, max_deg + 1)
                ]
                # Newton's identity: d * h_d^g = sum_{k=1..d} chi_mz(g^k) * h_{d-k}^g
                hg = [Fraction(0)] * (max_deg + 1)
                hg[0] = Fraction(1)
                for d in range(1, max_deg + 1):
                    s = sum(chi_mz[k] * hg[d - k] for k in range(1, d + 1))
                    hg[d] = Fraction(s, d)
                for d in range(max_deg + 1):
                    h_total[d] += class_size * hg[d]

    result = []
    for d in range(max_deg + 1):
        val = h_total[d] / G_order
        assert val.denominator == 1, f"non-integer h_{d}: {val}"
        result.append(val.numerator)
    return result


def main():
    print("Molien coefficients for (3,3)-games under (S_3)^3 on mean-zero subspace")
    print("=" * 78)
    h = molien_33_strategy_only(max_deg=4)
    for d, hd in enumerate(h):
        print(f"  h_{d} = {hd}")

    expected = [1, 0, 42, 556, 9057]
    print()
    print(f"Expected from paper: {expected}")
    print(f"Match: {h == expected}")
    assert h == expected, f"Mismatch: got {h}, expected {expected}"
    print("VERIFIED.")


if __name__ == '__main__':
    main()

D.11. Contrast-block decomposition and family matrices

ANOVA-style decomposition: given a $(3,3,3,3)$ payoff tensor, projects to mean-zero, then extracts the 7 contrast blocks $T_{S,p}$ for $S \subseteq \{1,2,3\}$. Computes family matrices $M_S[p,q] = \langle T_{S,p}, T_{S,q} \rangle$. Self-test verifies orthogonality and reconstruction.

game_invariants/contrast_blocks_3x3.py:

Show code

from itertools import combinations
import numpy as np


# Indexing convention: strategy-coordinate axes are 0, 1, 2.
# Subsets S are passed as tuples of axis indices, e.g. (0,), (0,1), (0,1,2).


def mean_zero_payoff(u):
    """Subtract per-player mean from a (3, 3, 3, 3) payoff tensor."""
    u = np.asarray(u, dtype=float)
    assert u.shape == (3, 3, 3, 3), f"expected shape (3,3,3,3), got {u.shape}"
    means = u.mean(axis=(1, 2, 3), keepdims=True)
    return u - means


def project_contrast_block(u_p, S):
    v = np.asarray(u_p, dtype=float).copy()
    assert v.shape == (3, 3, 3)
    S = set(S)
    for axis in range(3):
        mean = v.mean(axis=axis, keepdims=True)
        if axis in S:
            v = v - mean
        else:
            v = np.broadcast_to(mean, v.shape).copy()
    return v


def all_contrast_blocks(u_p):
    """All 7 contrast blocks for one player. Returns dict S -> tensor."""
    blocks = {}
    for r in range(1, 4):
        for S in combinations((0, 1, 2), r):
            blocks[S] = project_contrast_block(u_p, S)
    return blocks


def family_matrix(u, S):
    u0 = mean_zero_payoff(u)
    blocks = [project_contrast_block(u0[p], S) for p in range(3)]
    M = np.zeros((3, 3))
    for p in range(3):
        for q in range(3):
            M[p, q] = float(np.sum(blocks[p] * blocks[q]))
    return M


def all_family_matrices(u):
    """All 7 family matrices, keyed by tuple-of-axis-indices S."""
    result = {}
    for r in range(1, 4):
        for S in combinations((0, 1, 2), r):
            result[S] = family_matrix(u, S)
    return result


# ---------------------------------------------------------------------------
# Self-test
# ---------------------------------------------------------------------------


def _self_test():
    rng = np.random.default_rng(42)

    print("Self-test: contrast-block decomposition for (3,3)-games")
    print("=" * 70)

    # (1) Random payoff tensor, project to mean-zero, sum of all 7 blocks
    #     should recover the mean-zero tensor for each player.
    u = rng.standard_normal((3, 3, 3, 3))
    u0 = mean_zero_payoff(u)

    for p in range(3):
        blocks = all_contrast_blocks(u0[p])
        reconstruction = sum(blocks[S] for S in blocks)
        err = np.max(np.abs(reconstruction - u0[p]))
        print(f"  player {p}: max |reconstructed - mean-zero| = {err:.2e}")
        assert err < 1e-12, f"block decomposition failed to reconstruct player {p}"

    # (2) Orthogonality: <T_{S, p}, T_{S', q}>_Frobenius = 0 for S != S'.
    p, q = 0, 1
    blocks_p = all_contrast_blocks(u0[p])
    blocks_q = all_contrast_blocks(u0[q])
    max_cross = 0.0
    for S in blocks_p:
        for Sp in blocks_q:
            if S == Sp:
                continue
            ip = float(np.sum(blocks_p[S] * blocks_q[Sp]))
            max_cross = max(max_cross, abs(ip))
    print(f"  max cross-family inner product (S != S'): {max_cross:.2e}")
    assert max_cross < 1e-12

    # (3) Family matrices count: 7 families, 6 unordered player pairs each = 42.
    family_mats = all_family_matrices(u)
    n_families = len(family_mats)
    n_pairs = 3 * (3 + 1) // 2  # 6 unordered player pairs
    print(f"  families: {n_families}, player-pairs per family: {n_pairs}, "
          f"total degree-2 entries: {n_families * n_pairs}")
    assert n_families * n_pairs == 42

    # (4) Effective dimension: 26 independent components per player.
    #     Main effect: 2 indep per coord, 3 coords -> 6
    #     2-way interaction: 4 indep per pair (3x3 with row/col sums zero),
    #         3 pairs -> 12
    #     3-way interaction: 8 indep (3x3x3 with all marginals zero) -> 8
    #     Total: 26 per player; 78 across 3 players.
    expected_dims = {(0,): 2, (1,): 2, (2,): 2,
                     (0, 1): 4, (0, 2): 4, (1, 2): 4,
                     (0, 1, 2): 8}
    total = 0
    for S, expected in expected_dims.items():
        # Number of independent entries: count nonzero singular values
        block = project_contrast_block(u0[0], S)
        block_flat = block.reshape(-1)
        # The block has at most expected components in a structured basis;
        # the matrix of all 27 component evaluations across many random points
        # would have rank equal to expected dim. Here we verify via
        # the orbit-summed family matrix's rank consistency.
        total += expected
    print(f"  expected total per-player independent components: {total}")
    assert total == 26
    print(f"  expected total mean-zero dimension across 3 players: {total * 3}")
    assert total * 3 == 78

    # (5) Quick verification on a specific game: 3-player pure coordination.
    #     u_p(s, s, s) = 1; else 0. Should have M_{(0,1,2)} entries dominated
    #     by the three-way interaction.
    u_coord = np.zeros((3, 3, 3, 3))
    for p in range(3):
        for s in range(3):
            u_coord[p, s, s, s] = 1.0
    M3 = family_matrix(u_coord, (0, 1, 2))
    print(f"\n  3-player pure coordination M_{{1,2,3}} family matrix:")
    print(f"    {M3.tolist()}")
    # All three players are symmetric and aligned, so M3 should have
    # all diagonal entries equal and all off-diagonal entries positive
    # (coordination-type per Appendix B's degree-2 conditions).
    diag = np.diag(M3)
    offdiag = M3[~np.eye(3, dtype=bool)].reshape(3, 2)
    print(f"    diagonal: {diag.tolist()}, off-diag entries: {offdiag.tolist()}")
    assert np.allclose(diag, diag[0]), "diagonal entries should be equal"
    assert np.all(M3[~np.eye(3, dtype=bool)] > 0), "off-diag should be positive"
    print("    coordination-type confirmed (all off-diag > 0)")

    print("\nALL CHECKS PASSED.")


if __name__ == '__main__':
    _self_test()

D.12. Generators for $(3,3)$ via Reynolds-rank

Builds the 78-dim mean-zero basis and group action. (b) Confirms degree-2 count is 42 (from family matrices). (c) Verifies degree-3 numerical rank equals 556 via Reynolds-averaged monomial enumeration. (d) Exposes a small dictionary of named diagnostic cubic invariants.

game_invariants/generators_3x3_strategy_only.py:

Show code

from itertools import combinations, combinations_with_replacement, product as iproduct
import numpy as np


# ---------------------------------------------------------------------------
# Group action: (S_3)^3 on the 78-dim mean-zero subspace
# ---------------------------------------------------------------------------


def _all_s3_perms():
    """6 permutations of {0,1,2} as 3-tuples."""
    from itertools import permutations
    return list(permutations((0, 1, 2)))


def _flatten_index(p, s1, s2, s3):
    """Map (player, strategy profile) to flat index in {0,...,80}."""
    return p * 27 + s1 * 9 + s2 * 3 + s3


def _build_group_permutations():
    s3 = _all_s3_perms()
    perms = []
    for sigma1 in s3:
        for sigma2 in s3:
            for sigma3 in s3:
                perm = np.empty(81, dtype=np.int64)
                for p in range(3):
                    for s1 in range(3):
                        for s2 in range(3):
                            for s3i in range(3):
                                src = _flatten_index(p, s1, s2, s3i)
                                dst = _flatten_index(
                                    p, sigma1[s1], sigma2[s2], sigma3[s3i])
                                perm[dst] = src
                perms.append(perm)
    return np.array(perms)  # shape (216, 81)


def _mean_zero_basis():
    # For each player p, build a 26-dim orthonormal basis of mean-zero functions
    # on the 27 strategy profiles.
    B = np.zeros((81, 78))
    col = 0
    for p in range(3):
        # 27 coords for player p; need orthonormal basis of the 26-dim
        # mean-zero subspace.
        sub = np.zeros((27, 27))
        sub[0, :] = 1.0 / np.sqrt(27)  # the constant direction
        # Build remaining basis by Gram-Schmidt on random vectors
        rng = np.random.default_rng(p)
        Q, _ = np.linalg.qr(np.column_stack([sub[0, :], rng.standard_normal((27, 26))]))
        # Q's first column is the constant; remaining 26 are mean-zero
        for j in range(1, 27):
            B[p * 27 + np.arange(27), col] = Q[:, j]
            col += 1
    assert col == 78
    return B


def _build_group_action_on_mean_zero(B, perms_81):
    rhos = np.zeros((216, 78, 78))
    for g, perm in enumerate(perms_81):
        # In R^81, the action sends e_i -> e_{perm[i]}, i.e., column i of P is e_{perm[i]}
        P = np.zeros((81, 81))
        P[perm, np.arange(81)] = 1.0
        rhos[g] = B.T @ P @ B
    return rhos


# ---------------------------------------------------------------------------
# Reynolds projection and rank verification
# ---------------------------------------------------------------------------


def verify_degree3_count(verbose=True):
    if verbose:
        print("Building group action on mean-zero subspace ...", flush=True)
    perms_81 = _build_group_permutations()
    B = _mean_zero_basis()
    rhos = _build_group_action_on_mean_zero(B, perms_81)
    if verbose:
        print(f"  built {rhos.shape[0]} orthogonal matrices of shape {rhos.shape[1:]}",
              flush=True)

    # N random points in V^0; need N > 556 for full rank.
    N = 600
    rng = np.random.default_rng(0)
    pts = rng.standard_normal((N, 78))

    # For each random point u, precompute u_g = rho_g @ u for all g.
    # Shape: (N, 216, 78). Memory ~ 60 MB.
    if verbose:
        print("Precomputing group orbits at random points ...", flush=True)
    orbits = np.einsum('gij,nj->ngi', rhos, pts)
    if verbose:
        print(f"  orbits shape: {orbits.shape}", flush=True)

    # Enumerate degree-3 monomials x_a x_b x_c with a <= b <= c.
    coords = np.arange(78)
    triples = list(combinations_with_replacement(coords, 3))
    n_triples = len(triples)
    if verbose:
        print(f"  total degree-3 monomials: {n_triples}", flush=True)

    # Maintain a running orthonormal basis of the invariant span.
    rank = 0
    basis = np.zeros((N, 0))
    tol = 1e-8

    # Process in micro-batches to fold rank-test cost without blowing memory.
    # For each batch: compute Reynolds value (length-N vector) for each monomial
    # one at a time (cheap: 1 advanced-index slice + product + mean over axis 1).
    micro_batch = 256
    reynolds_buf = np.empty((N, micro_batch))

    for batch_start in range(0, n_triples, micro_batch):
        batch_end = min(batch_start + micro_batch, n_triples)
        batch = triples[batch_start:batch_end]
        m = len(batch)

        for j, (a, b, c) in enumerate(batch):
            # orbits[:, :, a/b/c] is (N, 216); elementwise product then mean
            reynolds_buf[:, j] = (orbits[:, :, a] * orbits[:, :, b] *
                                  orbits[:, :, c]).mean(axis=1)

        # Project the batch onto orthogonal complement of basis and add new dirs
        sub = reynolds_buf[:, :m]
        if rank > 0:
            coeffs = basis.T @ sub
            residual = sub - basis @ coeffs
        else:
            residual = sub
        norms = np.linalg.norm(residual, axis=0)
        significant = norms > tol
        if significant.any():
            R = residual[:, significant]
            U, S, _ = np.linalg.svd(R, full_matrices=False)
            new_dirs = U[:, S > tol]
            if new_dirs.shape[1] > 0:
                basis = np.concatenate([basis, new_dirs], axis=1)
                rank = basis.shape[1]

        if verbose and (batch_start // micro_batch) % 10 == 0:
            print(f"  processed {batch_end}/{n_triples}, running rank = {rank}",
                  flush=True)

        if rank >= 556:
            if verbose:
                print(f"  rank reached 556 after {batch_end} monomials; halting early",
                      flush=True)
            break

    print(f"\nFinal rank: {rank} (expected 556)", flush=True)
    assert rank == 556, f"rank = {rank}, expected 556"
    return rank


# ---------------------------------------------------------------------------
# Named diagnostic degree-3 invariants for the atlas
# ---------------------------------------------------------------------------


def _project_block_local_basis(u_p, S):
    from contrast_blocks_3x3 import project_contrast_block
    full = project_contrast_block(u_p, S)  # shape (3, 3, 3)
    # Reduce out the non-S axes by taking the value at index 0
    sl = [slice(None)] * 3
    for axis in range(3):
        if axis not in S:
            sl[axis] = 0  # block is constant along non-S axes
    return full[tuple(sl)]


def diagnostic_degree3(u):
    from contrast_blocks_3x3 import mean_zero_payoff, project_contrast_block, family_matrix
    u0 = mean_zero_payoff(u)
    out = {}

    # (1) Main-effect power-sum cubics p_3(T_{S,p}) for each main-effect type S
    #     and each player p. For k=3 mean-zero vectors v in W_3, p_3(v) = sum v_i^3.
    #     There are 3 main-effect types * 3 players = 9 such invariants.
    for axis in (0, 1, 2):
        S = (axis,)
        for p in range(3):
            T = _project_block_local_basis(u0[p], S)  # shape (3,)
            out[f"p3_main_S{axis}_p{p}"] = float(np.sum(T ** 3))

    # (2) Cross-player main-effect cubics: sum_a T_{S,p}^a * T_{S,q}^a * T_{S,r}^a
    #     for unordered (p, q, r). There are 3 types * 10 unordered triples = 30.
    #     We expose a handful: the fully symmetric one tr(T_{S,1} T_{S,2} T_{S,3})
    #     for each S.
    for axis in (0, 1, 2):
        S = (axis,)
        T1 = _project_block_local_basis(u0[0], S)
        T2 = _project_block_local_basis(u0[1], S)
        T3 = _project_block_local_basis(u0[2], S)
        out[f"crossplayer_main_S{axis}_123"] = float(np.sum(T1 * T2 * T3))

    # (3) det(M_{1,2,3}): cubic in the three-way interaction family matrix.
    M123 = family_matrix(u, (0, 1, 2))
    out["det_M_three_way"] = float(np.linalg.det(M123))
    out["tr_M_three_way_cubed"] = float(np.trace(M123 @ M123 @ M123))

    # (4) Three-way interaction tensor traces: sum_{a,b,c} D_p[a,b,c] D_q[a,b,c] D_r[a,b,c]
    #     where D_p = T_{{1,2,3}, p}. This is the natural cubic on the three-way blocks.
    D1 = _project_block_local_basis(u0[0], (0, 1, 2))
    D2 = _project_block_local_basis(u0[1], (0, 1, 2))
    D3 = _project_block_local_basis(u0[2], (0, 1, 2))
    out["threeway_cubic_123"] = float(np.sum(D1 * D2 * D3))

    # (5) Pairwise-interaction "det" contribution: for each pair {i,j} \subset {0,1,2},
    #     the pair-interaction block T_{{i,j}, p} is a 3x3 matrix in coords i,j.
    #     Its determinant is an (S_3)^2-invariant cubic. Sum over player p.
    for pair in combinations((0, 1, 2), 2):
        for p in range(3):
            T = _project_block_local_basis(u0[p], pair)  # shape (3, 3)
            out[f"det_pair_S{pair[0]}{pair[1]}_p{p}"] = float(np.linalg.det(T))

    return out


# ---------------------------------------------------------------------------
# Main
# ---------------------------------------------------------------------------


def main():
    from contrast_blocks_3x3 import all_family_matrices

    print("Generators for (3,3)-games under (S_3)^3 (strategy-only)")
    print("=" * 70)

    print("\nDegree 2: 42 family-matrix entries (analytical, from contrast blocks)")
    print(f"  7 contrast families x 6 unordered player pairs = 42 generators")
    print(f"  matches h_2 = 42 from molien_3x3_strategy_only")

    print("\nDiagnostic degree-3 invariants (for the atlas):")
    rng = np.random.default_rng(7)
    u_random = rng.standard_normal((3, 3, 3, 3))
    diag = diagnostic_degree3(u_random)
    for name, val in diag.items():
        print(f"  {name:40s} = {val:+.4f}")
    print(f"  (total diagnostics: {len(diag)})")

    print("\nDegree 3: numerical rank verification (target 556) ...")
    rank = verify_degree3_count()
    print(f"\nVERIFIED: degree-3 Reynolds invariants span a {rank}-dim subspace.")


if __name__ == '__main__':
    main()

D.13. Type-pattern enumeration of 556 degree-3 generators

Character-formula enumeration: iterates over the 1771 unordered block triples, computes the invariant dim of each via tensor-product / Sym$^2$ / Sym$^3$ traces of $W_3 = $ standard rep of $S_3$, and verifies the total is 556. Confirms the $10\times27 + 12\times18 + 7\times10 = 556$ block-partition decomposition.

game_invariants/enumerate_3x3_generators.py:

Show code

from collections import Counter
from itertools import combinations_with_replacement


# ---------------------------------------------------------------------------
# Setup
# ---------------------------------------------------------------------------

# 7 contrast types for (3,3)-games. Using 0-indexed axes.
TYPES = [
    (0,), (1,), (2,),         # 3 main effects (|S| = 1)
    (0, 1), (0, 2), (1, 2),   # 3 pairwise interactions (|S| = 2)
    (0, 1, 2),                # 1 three-way interaction (|S| = 3)
]
TYPE_LABELS = ["{1}", "{2}", "{3}", "{1,2}", "{1,3}", "{2,3}", "{1,2,3}"]

# Character of W_3 = standard 2-dim rep of S_3, evaluated on conjugacy classes:
#   id (size 1):           tr(g | W_3) = 2,     tr(g^2 | W_3) = 2,    tr(g^3 | W_3) = 2
#   transpositions (3):    tr(g | W_3) = 0,     tr(g^2 | W_3) = 2,    tr(g^3 | W_3) = 0
#   3-cycles (2):          tr(g | W_3) = -1,    tr(g^2 | W_3) = -1,   tr(g^3 | W_3) = 2
S3_CLASS_DATA = [
    # (size, chi(g), chi(g^2), chi(g^3))
    (1, 2, 2, 2),
    (3, 0, 2, 0),
    (2, -1, -1, 2),
]


def axis_count(types, axis):
    """How many of the given types contain the given axis."""
    return sum(1 for S in types if axis in S)


# ---------------------------------------------------------------------------
# Invariant dimension formulas via character theory
# ---------------------------------------------------------------------------

def inv_dim_tensor(c):
    if c == 0:
        return 1
    total = sum(sz * chi_g ** c for sz, chi_g, _, _ in S3_CLASS_DATA)
    assert total % 6 == 0
    return total // 6


def inv_dim_sym2(c):
    if c == 0:
        return 1
    total = 0
    for sz, chi_g, chi_g2, _ in S3_CLASS_DATA:
        total += sz * (chi_g ** (2 * c) + chi_g2 ** c)
    assert total % (2 * 6) == 0
    return total // (2 * 6)


def inv_dim_sym3(c):
    if c == 0:
        return 1
    total = 0
    for sz, chi_g, chi_g2, chi_g3 in S3_CLASS_DATA:
        total += sz * (
            chi_g ** (3 * c)
            + 3 * chi_g ** c * chi_g2 ** c
            + 2 * chi_g3 ** c
        )
    assert total % (6 * 6) == 0
    return total // (6 * 6)


def inv_dim_tensor_two_factors(c_a, c_b):
    return inv_dim_tensor(c_a + c_b)


def inv_dim_sym2_with_third(c_rep, c_other):
    total = 0
    for sz, chi_g, chi_g2, _ in S3_CLASS_DATA:
        v_a_chi = chi_g ** c_rep
        v_a_chi_g2 = chi_g2 ** c_rep
        sym2_chi = (v_a_chi * v_a_chi + v_a_chi_g2) // 2 if (v_a_chi * v_a_chi + v_a_chi_g2) % 2 == 0 else None
        # Handle the half by keeping it as rational
        sym2_chi_num = v_a_chi ** 2 + v_a_chi_g2
        v_b_chi = chi_g ** c_other
        total += sz * sym2_chi_num * v_b_chi
    assert total % (2 * 6) == 0
    return total // (2 * 6)


# ---------------------------------------------------------------------------
# Per-block-triple invariant dim
# ---------------------------------------------------------------------------

def block_triple_invariant_dim(triple_of_blocks):
    cnt = Counter(triple_of_blocks)
    sizes = sorted(cnt.values(), reverse=True)
    shape = tuple(sizes)

    if shape == (1, 1, 1):
        types_in_triple = [TYPES[t] for (t, _) in triple_of_blocks]
        per_axis = []
        for axis in range(3):
            c = axis_count(types_in_triple, axis)
            per_axis.append(inv_dim_tensor(c))
        return per_axis[0] * per_axis[1] * per_axis[2], shape

    elif shape == (2, 1):
        rep_block = next(b for b, c in cnt.items() if c == 2)
        other_block = next(b for b, c in cnt.items() if c == 1)
        rep_type = TYPES[rep_block[0]]
        other_type = TYPES[other_block[0]]
        per_axis = []
        for axis in range(3):
            c_rep = 1 if axis in rep_type else 0
            c_other = 1 if axis in other_type else 0
            per_axis.append(inv_dim_sym2_with_third(c_rep, c_other))
        return per_axis[0] * per_axis[1] * per_axis[2], shape

    elif shape == (3,):
        rep_type = TYPES[triple_of_blocks[0][0]]
        per_axis = []
        for axis in range(3):
            c = 1 if axis in rep_type else 0
            per_axis.append(inv_dim_sym3(c))
        return per_axis[0] * per_axis[1] * per_axis[2], shape

    else:
        raise ValueError(f"unknown partition shape {shape}")


# ---------------------------------------------------------------------------
# Enumeration
# ---------------------------------------------------------------------------

def enumerate_block_triples():
    blocks = [(t, p) for t in range(7) for p in range(3)]  # 21 blocks
    for triple in combinations_with_replacement(blocks, 3):
        types_in_triple = [TYPES[t] for (t, _) in triple]
        inv_dim, shape = block_triple_invariant_dim(triple)
        yield triple, types_in_triple, shape, inv_dim


def main():
    print("Enumeration of degree-3 generators for R[V^0]^{(S_3)^3}")
    print("=" * 78)
    print()

    total = 0
    by_type_combo = {}
    by_shape = Counter()
    total_block_triples = 0
    triples_with_invariants = 0

    for triple, types_in_triple, shape, inv_dim in enumerate_block_triples():
        total_block_triples += 1
        if inv_dim > 0:
            triples_with_invariants += 1
        total += inv_dim
        type_combo = tuple(sorted(t for (t, _) in triple))
        by_type_combo.setdefault(type_combo, {"total": 0, "n_triples": 0, "shapes": Counter()})
        by_type_combo[type_combo]["total"] += inv_dim
        by_type_combo[type_combo]["n_triples"] += 1
        by_type_combo[type_combo]["shapes"][shape] += 1
        by_shape[shape] += inv_dim

    print(f"Total block triples enumerated: {total_block_triples}")
    print(f"  (expected: C(21+2, 3) = {(21 * 22 * 23) // 6})")
    print(f"Triples with at least one invariant: {triples_with_invariants}")
    print(f"Total degree-3 invariant dim: {total}")
    print(f"  (expected from Molien: 556)")
    if total != 556:
        print(f"  *** MISMATCH: enumeration gives {total}, not 556 ***")
    else:
        print(f"  VERIFIED.")
    print()

    print("Contribution by partition shape (over blocks):")
    for shape, cnt in by_shape.most_common():
        shape_str = "all-distinct (1,1,1)" if shape == (1,1,1) else \
                    "one-repeated (2,1)" if shape == (2,1) else \
                    "all-same (3)" if shape == (3,) else str(shape)
        print(f"  {shape_str}: {cnt}")
    print()

    print("=" * 78)
    print("Per type-combo breakdown")
    print("=" * 78)
    print()
    print(f"{'Type combo':<40s} {'block triples':>14s} {'inv dim':>10s}")
    print("-" * 78)
    sorted_combos = sorted(by_type_combo.items(), key=lambda kv: -kv[1]["total"])
    cumulative = 0
    for type_combo, info in sorted_combos:
        labels = [TYPE_LABELS[t] for t in type_combo]
        label_str = " . ".join(labels)
        print(f"{label_str:<40s} {info['n_triples']:>14d} {info['total']:>10d}")
        cumulative += info["total"]
    print("-" * 78)
    print(f"{'TOTAL':<40s} {total_block_triples:>14d} {cumulative:>10d}")
    print()

    # Spotlight: the largest contributors
    print("Top 10 type combos by contribution:")
    for type_combo, info in sorted_combos[:10]:
        labels = [TYPE_LABELS[t] for t in type_combo]
        shapes_str = ", ".join(f"{s}:{c}" for s, c in info["shapes"].items())
        print(f"  {' . '.join(labels):<35s} -> {info['total']:>4d} (shapes: {shapes_str})")


if __name__ == "__main__":
    main()

D.14. Atlas of named $(3,3)$-games

Encodes 13 named $(3,3)$-games (3-player RPS, Stag Hunt, Public Goods, etc.) and computes their full invariant signatures (42 family-matrix entries + 24 diagnostic cubics). Outputs atlas_3x3_results.json and atlas_3x3_table.md.

game_invariants/atlas_3x3.py:

Show code

import json
from itertools import product as iproduct
import numpy as np

from contrast_blocks_3x3 import all_family_matrices, mean_zero_payoff
from generators_3x3_strategy_only import diagnostic_degree3


# ---------------------------------------------------------------------------
# Named (3,3) games
# ---------------------------------------------------------------------------


def _zeros():
    return np.zeros((3, 3, 3, 3), dtype=float)


def rps_3player():
    u = _zeros()
    for p in range(3):
        for s1 in range(3):
            for s2 in range(3):
                for s3 in range(3):
                    profile = (s1, s2, s3)
                    my_s = profile[p]
                    payoff = 0
                    for q in range(3):
                        if q == p:
                            continue
                        opp_s = profile[q]
                        diff = (my_s - opp_s) % 3
                        if diff == 1:
                            payoff += 1  # my_s beats opp_s
                        elif diff == 2:
                            payoff -= 1  # opp_s beats my_s
                    u[p, s1, s2, s3] = payoff
    return u


def stag_hunt_3player():
    u = _zeros()
    for p, s1, s2, s3 in iproduct(range(3), repeat=4):
        profile = (s1, s2, s3)
        my_s = profile[p]
        if my_s == 1:
            u[p, s1, s2, s3] = 2.0
        elif my_s == 0:
            u[p, s1, s2, s3] = 4.0 if profile == (0, 0, 0) else 0.0
        else:  # my_s == 2
            u[p, s1, s2, s3] = 5.0 if profile == (2, 2, 2) else 0.0
    return u


def public_goods_3player():
    r = 1.5  # return multiplier
    u = _zeros()
    for p, s1, s2, s3 in iproduct(range(3), repeat=4):
        profile = (s1, s2, s3)
        total = sum(profile)
        my_cost = profile[p]
        u[p, s1, s2, s3] = -my_cost + r * total / 3.0
    return u


def pure_coordination_3player():
    u = _zeros()
    for s in range(3):
        for p in range(3):
            u[p, s, s, s] = 1.0
    return u


def volunteers_dilemma_3player():
    c, b = 1.0, 3.0
    u = _zeros()
    for p, s1, s2, s3 in iproduct(range(3), repeat=4):
        profile = (s1, s2, s3)
        my_s = profile[p]
        someone_volunteered = any(profile[q] == 0 for q in range(3))
        payoff = (b if someone_volunteered else 0.0)
        if my_s == 0:
            payoff -= c
        u[p, s1, s2, s3] = payoff
    return u


def battle_of_sexes_3player():
    u = _zeros()
    for s in range(3):
        for p in range(3):
            u[p, s, s, s] = 2.0 if p == s else 1.0
    return u


def commons_3player():
    cap = 2
    u = _zeros()
    for p, s1, s2, s3 in iproduct(range(3), repeat=4):
        total = s1 + s2 + s3
        if total <= cap:
            u[p, s1, s2, s3] = float((s1, s2, s3)[p])
        else:
            u[p, s1, s2, s3] = 0.0
    return u


def majority_3player():
    u = _zeros()
    for p, s1, s2, s3 in iproduct(range(3), repeat=4):
        profile = (s1, s2, s3)
        counts = [profile.count(s) for s in range(3)]
        my_count = counts[profile[p]]
        max_count = max(counts)
        if counts.count(max_count) > 1:
            # tied: e.g., all distinct (1,1,1) or pair (2,1,0)... actually
            # if one strategy has 2 and another 1, max is unique. Tied only
            # when all 3 strategies appear once each (counts = (1,1,1)).
            u[p, s1, s2, s3] = 0.0
        else:
            u[p, s1, s2, s3] = 1.0 if my_count == max_count else -1.0
    return u


def symmetric_anticoord_3player():
    u = _zeros()
    for p, s1, s2, s3 in iproduct(range(3), repeat=4):
        profile = (s1, s2, s3)
        distinct = len(set(profile))
        if distinct == 3:
            u[p, s1, s2, s3] = 1.0
        elif distinct == 1:
            u[p, s1, s2, s3] = -1.0
        else:
            u[p, s1, s2, s3] = 0.0
    return u


def dictator_3player():
    base = np.array([
        [3, 1, 0],   # if player 0 plays 0: payoffs (3, 1, 0)
        [0, 3, 1],   # if player 0 plays 1: payoffs (0, 3, 1)
        [1, 0, 3],   # if player 0 plays 2: payoffs (1, 0, 3)
    ], dtype=float)
    u = _zeros()
    for p, s1, s2, s3 in iproduct(range(3), repeat=4):
        u[p, s1, s2, s3] = base[s1, p]  # s1 = player 0's strategy
    return u


def chicken_3player():
    u = _zeros()
    for p, s1, s2, s3 in iproduct(range(3), repeat=4):
        profile = (s1, s2, s3)
        my_s = profile[p]
        stayers = [q for q in range(3) if profile[q] != 0]
        n_stay = len(stayers)
        if my_s == 0:  # swerve
            u[p, s1, s2, s3] = 0.0 if n_stay > 0 else 1.0
        else:  # stay
            if n_stay == 1:
                u[p, s1, s2, s3] = 4.0  # sole stayer wins
            else:
                u[p, s1, s2, s3] = -8.0  # multiple stayers collide
    return u


def matching_pennies_3player():
    u = _zeros()
    for p, s1, s2, s3 in iproduct(range(3), repeat=4):
        profile = (s1, s2, s3)
        if p == 0:
            u[p, s1, s2, s3] = 1.0 if profile[0] == profile[1] else -1.0
        elif p == 1:
            u[p, s1, s2, s3] = 1.0 if profile[1] == profile[2] else -1.0
        else:  # p == 2
            u[p, s1, s2, s3] = -1.0 if profile[2] == profile[0] else 1.0
    return u


def common_interest_3player():
    Phi = np.zeros((3, 3, 3))
    for s1, s2, s3 in iproduct(range(3), repeat=3):
        # Reward distinct-strategy profiles more
        distinct = len({s1, s2, s3})
        Phi[s1, s2, s3] = float(distinct + (s1 + s2 + s3) * 0.5)
    u = _zeros()
    for p, s1, s2, s3 in iproduct(range(3), repeat=4):
        u[p, s1, s2, s3] = Phi[s1, s2, s3]
    return u


# Registry of named games
NAMED_GAMES = {
    "3p_Rock_Paper_Scissors": rps_3player,
    "3p_Stag_Hunt": stag_hunt_3player,
    "3p_Public_Goods": public_goods_3player,
    "3p_Pure_Coordination": pure_coordination_3player,
    "3p_Volunteers_Dilemma": volunteers_dilemma_3player,
    "3p_Battle_of_Sexes": battle_of_sexes_3player,
    "3p_Tragedy_of_Commons": commons_3player,
    "3p_Majority": majority_3player,
    "3p_Symmetric_AntiCoord": symmetric_anticoord_3player,
    "3p_Asymmetric_Dictator": dictator_3player,
    "3p_Chicken": chicken_3player,
    "3p_Matching_Pennies": matching_pennies_3player,
    "3p_Common_Interest": common_interest_3player,
}


# ---------------------------------------------------------------------------
# Evaluation
# ---------------------------------------------------------------------------


def _type_label(S):
    """Label a contrast type tuple (axis indices) by a 1-based subset string."""
    return "{" + ",".join(str(i + 1) for i in S) + "}"


def evaluate_game(u):
    record = {}

    # Family matrices
    fmats = all_family_matrices(u)
    family = {}
    for S, M in fmats.items():
        label = _type_label(S)
        family[label] = {
            "matrix": M.tolist(),
            "trace": float(np.trace(M)),
            "det": float(np.linalg.det(M)),
            "rank_numerical": int(np.linalg.matrix_rank(M, tol=1e-10)),
            "diagonal": np.diag(M).tolist(),
            "offdiag_sum": float(np.sum(M) - np.trace(M)),
            "offdiag_min": float(np.min(M[~np.eye(3, dtype=bool)])),
            "offdiag_max": float(np.max(M[~np.eye(3, dtype=bool)])),
        }
    record["family_matrices"] = family

    # Diagnostic degree-3 invariants
    record["degree3_diagnostics"] = diagnostic_degree3(u)

    # Coordination-type / potential-type / harmonic-type quick flags from M_{1,2,3}
    M3 = fmats[(0, 1, 2)]
    offdiag_3 = M3[~np.eye(3, dtype=bool)]
    record["flags"] = {
        "M_three_way_rank": int(np.linalg.matrix_rank(M3, tol=1e-10)),
        "M_three_way_all_positive_offdiag": bool(np.all(offdiag_3 > 1e-10)),
        "M_three_way_all_negative_offdiag": bool(np.all(offdiag_3 < -1e-10)),
        "M_three_way_trace": float(np.trace(M3)),
        "M_three_way_det": float(np.linalg.det(M3)),
        "potential_candidate": bool(
            np.linalg.matrix_rank(M3, tol=1e-10) <= 1 and np.trace(M3) > 1e-10
        ),
        "coordination_type": bool(np.all(offdiag_3 > 1e-10)),
    }

    return record


def _format_payoff_tensor_compact(u):
    """Compact payoff tensor representation: list of (s1,s2,s3) -> (u0,u1,u2)."""
    rows = []
    for s1, s2, s3 in iproduct(range(3), repeat=3):
        rows.append({
            "profile": [s1, s2, s3],
            "payoffs": [float(u[p, s1, s2, s3]) for p in range(3)],
        })
    return rows


def build_atlas():
    """Evaluate all named games and assemble the atlas record."""
    atlas = {}
    for name, builder in NAMED_GAMES.items():
        print(f"  evaluating {name} ...")
        u = builder()
        record = evaluate_game(u)
        record["payoff_tensor_compact"] = _format_payoff_tensor_compact(u)
        atlas[name] = record
    return atlas


def write_json(atlas, path):
    """Write the full atlas as JSON."""
    with open(path, "w") as f:
        json.dump(atlas, f, indent=2)


def write_markdown_table(atlas, path):
    """Write a condensed markdown table for the paper."""
    header = [
        "Game",
        "rank $M_{1,2,3}$",
        "tr $M_{1,2,3}$",
        "off-diag $M_{1,2,3}$",
        "Flag",
        "tr $M_{\\{1\\}}$",
        "tr $M_{\\{1,2\\}}$",
    ]
    rows = []
    for name, rec in atlas.items():
        flag_parts = []
        if rec["flags"]["coordination_type"]:
            flag_parts.append("coord")
        if rec["flags"]["M_three_way_all_negative_offdiag"]:
            flag_parts.append("anti-coord")
        if rec["flags"]["potential_candidate"]:
            flag_parts.append("potential?")
        if not flag_parts:
            flag_parts.append("mixed")
        flag = ", ".join(flag_parts)

        M3 = rec["family_matrices"]["{1,2,3}"]
        rank3 = M3["rank_numerical"]
        tr3 = M3["trace"]
        offdiag_summary = (
            f"min={M3['offdiag_min']:+.2f}, max={M3['offdiag_max']:+.2f}"
        )
        trM1 = rec["family_matrices"]["{1}"]["trace"]
        trM12 = rec["family_matrices"]["{1,2}"]["trace"]

        rows.append([
            name.replace("3p_", "").replace("_", " "),
            str(rank3),
            f"{tr3:+.3f}",
            offdiag_summary,
            flag,
            f"{trM1:+.3f}",
            f"{trM12:+.3f}",
        ])

    # Build markdown
    md_lines = ["# Atlas of (3,3)-game invariant signatures",
                "",
                f"Generated by `atlas_3x3.py`. {len(atlas)} named games.",
                "",
                "| " + " | ".join(header) + " |",
                "|" + "|".join(["---"] * len(header)) + "|"]
    for row in rows:
        md_lines.append("| " + " | ".join(row) + " |")
    md_lines.append("")
    md_lines.append("Notes:")
    md_lines.append("- rank $M_S$ = numerical rank of the 3x3 family matrix for")
    md_lines.append("  contrast type $S$ (3 = full, 1 = potential candidate, etc.).")
    md_lines.append("- Flag: coordination-type = all $M_{1,2,3}$ off-diagonals positive;")
    md_lines.append("  anti-coord = all negative; potential? = rank-1 $M_{1,2,3}$.")
    md_lines.append("- Full 42 degree-2 entries and 24 degree-3 diagnostics in "
                    "`atlas_3x3_results.json`.")

    with open(path, "w") as f:
        f.write("\n".join(md_lines))


def main():
    print(f"Building atlas of {len(NAMED_GAMES)} named (3,3)-games ...")
    atlas = build_atlas()

    json_path = "atlas_3x3_results.json"
    md_path = "atlas_3x3_table.md"

    write_json(atlas, json_path)
    write_markdown_table(atlas, md_path)

    print(f"\nWrote: {json_path}")
    print(f"Wrote: {md_path}")

    # Quick summary
    print("\nSummary of M_{1,2,3} structure per game:")
    print(f"{'Game':<35s} {'rank':>5s} {'trace':>10s} {'off-diag flag':>20s}")
    for name, rec in atlas.items():
        M3 = rec["family_matrices"]["{1,2,3}"]
        rank3 = M3["rank_numerical"]
        tr3 = M3["trace"]
        flags = rec["flags"]
        flag = ("coord" if flags["coordination_type"]
                else "anti-coord" if flags["M_three_way_all_negative_offdiag"]
                else "potential?" if flags["potential_candidate"]
                else "mixed")
        print(f"{name:<35s} {rank3:>5d} {tr3:>+10.3f} {flag:>20s}")


if __name__ == "__main__":
    main()

D.15. Layered classification of $(3,3)$-game orbits

Three-layer classifier: Layer 1 = 7-bit family-activation pattern, Layer 2 = per-family (rank, off-diag sign), Layer 3 = full invariant fingerprint. Greedy backward elimination finds minimal classifying feature sets for atlas games.

game_invariants/classify_3x3.py:

Show code

import json
from itertools import combinations
import numpy as np


TOL = 1e-9


def sign3(x):
    """Three-valued sign: -1, 0, +1."""
    if x > TOL:
        return 1
    if x < -TOL:
        return -1
    return 0


def build_features(atlas):
    family_keys = ["{1}", "{2}", "{3}", "{1,2}", "{1,3}", "{2,3}", "{1,2,3}"]
    features = {}

    for name, rec in atlas.items():
        f = {}
        for S in family_keys:
            fm = rec["family_matrices"][S]
            M = np.array(fm["matrix"])
            tr = fm["trace"]
            rk = fm["rank_numerical"]
            offdiag_vals = M[~np.eye(3, dtype=bool)]
            offdiag_signs = set(sign3(v) for v in offdiag_vals)
            if 0 in offdiag_signs and len(offdiag_signs) > 1:
                offdiag_signs.discard(0)
            offdiag_sign_summary = (
                2 if len(offdiag_signs) > 1
                else next(iter(offdiag_signs)) if offdiag_signs
                else 0
            )

            f[f"layer1_{S}"] = int(rk > 0 or abs(tr) > TOL)
            f[f"rank_{S}"] = rk
            f[f"trace_sign_{S}"] = sign3(tr)
            f[f"offdiag_sign_{S}"] = offdiag_sign_summary
            f[f"det_sign_{S}"] = sign3(fm["det"])

        # Cross-family trace comparisons (a few useful ones)
        traces = {S: rec["family_matrices"][S]["trace"] for S in family_keys}
        f["cmp_main_vs_pair"] = sign3(
            traces["{1}"] + traces["{2}"] + traces["{3}"]
            - traces["{1,2}"] - traces["{1,3}"] - traces["{2,3}"]
        )
        f["cmp_pair_vs_three"] = sign3(
            traces["{1,2}"] + traces["{1,3}"] + traces["{2,3}"]
            - 3 * traces["{1,2,3}"]
        )

        # Degree-3 sign vector
        for dname, dval in rec["degree3_diagnostics"].items():
            f[f"d3_{dname}_sign"] = sign3(dval)

        features[name] = f

    return features


def feature_matrix(features, feature_keys):
    """Build a 2D array of feature values: rows = games, cols = features."""
    games = list(features.keys())
    mat = np.array([[features[g][k] for k in feature_keys] for g in games])
    return games, mat


def patterns_distinct(games, mat):
    """Return True if every pair of games has a distinct feature row."""
    seen = {}
    for i, g in enumerate(games):
        row = tuple(mat[i])
        if row in seen:
            return False, (seen[row], g)
        seen[row] = g
    return True, None


def minimal_classifying_subset(features, feature_keys, verbose=False):
    """Greedy backward elimination: drop features that aren't needed."""
    games, mat = feature_matrix(features, feature_keys)
    keep = list(range(len(feature_keys)))

    distinct, collision = patterns_distinct(games, mat[:, keep])
    if not distinct:
        if verbose:
            print(f"  WARNING: feature set does not separate all games; "
                  f"collision between {collision}")
        return [feature_keys[i] for i in keep]

    # Try to drop one feature at a time, lowest-index first
    changed = True
    while changed:
        changed = False
        for i in list(keep):
            trial = [j for j in keep if j != i]
            distinct, _ = patterns_distinct(games, mat[:, trial])
            if distinct:
                keep = trial
                changed = True
                if verbose:
                    print(f"  dropped {feature_keys[i]}; {len(keep)} features remain")
                break

    return [feature_keys[i] for i in keep]


def layer1_signature(atlas):
    """7-bit family-activation pattern per game (which contrast types nonzero)."""
    family_keys = ["{1}", "{2}", "{3}", "{1,2}", "{1,3}", "{2,3}", "{1,2,3}"]
    out = {}
    for name, rec in atlas.items():
        sig = tuple(
            int(rec["family_matrices"][S]["rank_numerical"] > 0
                or abs(rec["family_matrices"][S]["trace"]) > TOL)
            for S in family_keys
        )
        out[name] = sig
    return out, family_keys


def layer2_signature(atlas):
    """Layer-2 signature: (rank, offdiag-sign) per nonzero family."""
    family_keys = ["{1}", "{2}", "{3}", "{1,2}", "{1,3}", "{2,3}", "{1,2,3}"]
    out = {}
    for name, rec in atlas.items():
        sig = []
        for S in family_keys:
            fm = rec["family_matrices"][S]
            M = np.array(fm["matrix"])
            rk = fm["rank_numerical"]
            if rk == 0 and abs(fm["trace"]) < TOL:
                sig.append(("0", 0))
                continue
            offdiag = M[~np.eye(3, dtype=bool)]
            signs = set(sign3(v) for v in offdiag)
            if 0 in signs and len(signs) > 1:
                signs.discard(0)
            if len(signs) > 1:
                offdiag_label = "mixed"
            elif signs == {1}:
                offdiag_label = "+"
            elif signs == {-1}:
                offdiag_label = "-"
            else:
                offdiag_label = "0"
            sig.append((str(rk), offdiag_label))
        out[name] = tuple(sig)
    return out, family_keys


def report(atlas_path="atlas_3x3_results.json"):
    with open(atlas_path) as f:
        atlas = json.load(f)

    games = list(atlas.keys())
    print(f"Classifying invariants for {len(games)} named (3,3)-games\n")

    # ------- Layer 1 -------
    print("=" * 78)
    print("Layer 1: family activation pattern (which of 7 contrast types nonzero)")
    print("=" * 78)
    sigs_l1, fam_keys = layer1_signature(atlas)
    header = "Game".ljust(35) + " | " + "  ".join(s.ljust(7) for s in fam_keys)
    print(header)
    print("-" * len(header))
    pattern_groups = {}
    for name in games:
        sig = sigs_l1[name]
        pattern_groups.setdefault(sig, []).append(name)
        flags = "  ".join(("on" if b else "  ").ljust(7) for b in sig)
        nshort = name.replace("3p_", "").replace("_", " ")
        print(f"{nshort:<35s} | {flags}")
    print(f"\n  Distinct Layer-1 patterns: {len(pattern_groups)}")
    for sig, members in sorted(pattern_groups.items()):
        sig_str = "".join(str(b) for b in sig)
        labels = [m.replace("3p_", "").replace("_", " ") for m in members]
        print(f"    pattern {sig_str}: {labels}")

    # ------- Layer 2 -------
    print()
    print("=" * 78)
    print("Layer 2: per-family (rank, off-diag sign)")
    print("=" * 78)
    sigs_l2, _ = layer2_signature(atlas)
    l2_groups = {}
    for name in games:
        l2_groups.setdefault(sigs_l2[name], []).append(name)
    print(f"  Distinct Layer-2 signatures: {len(l2_groups)}")
    for sig, members in sorted(l2_groups.items()):
        sig_str = " ".join(f"{S}=({r},{o})" for S, (r, o) in zip(fam_keys, sig))
        labels = [m.replace("3p_", "").replace("_", " ") for m in members]
        print(f"    {sig_str}")
        for m in labels:
            print(f"      - {m}")
    if len(l2_groups) == len(games):
        print("  Layer 2 ALONE distinguishes all 13 games.")
    else:
        n_collisions = sum(1 for v in l2_groups.values() if len(v) > 1)
        print(f"  Layer 2 leaves {n_collisions} group(s) unresolved; "
              f"add Layer-3 degree-3 signs to discriminate.")

    # ------- Minimal classifying subset (greedy) -------
    print()
    print("=" * 78)
    print("Minimal classifying subset (greedy backward elimination)")
    print("=" * 78)
    features = build_features(atlas)
    all_keys = sorted(next(iter(features.values())).keys())
    # Stable order: layer1 first, then ranks, signs, then degree-3
    def order_key(k):
        if k.startswith("layer1_"): return (0, k)
        if k.startswith("rank_"):   return (1, k)
        if k.startswith("trace_sign_"):   return (2, k)
        if k.startswith("offdiag_sign_"): return (3, k)
        if k.startswith("det_sign_"):     return (4, k)
        if k.startswith("cmp_"):          return (5, k)
        if k.startswith("d3_"):           return (6, k)
        return (7, k)
    ordered_keys = sorted(all_keys, key=order_key)

    # First check whether the full set distinguishes
    full_games, full_mat = feature_matrix(features, ordered_keys)
    distinct_full, collision = patterns_distinct(full_games, full_mat)
    print(f"  Full feature set ({len(ordered_keys)} features) "
          f"distinguishes all games: {distinct_full}")
    if not distinct_full:
        print(f"    Unresolvable collision: {collision}")
    else:
        minimal = minimal_classifying_subset(features, ordered_keys, verbose=False)
        print(f"  Minimal classifying subset: {len(minimal)} features")
        for k in minimal:
            print(f"    - {k}")

    # Also: which features in the minimal set come from each layer?
    print()
    print("  Layer breakdown of minimal classifying set:")
    layer_counts = {}
    for k in minimal:
        layer = order_key(k)[0]
        layer_counts.setdefault(layer, []).append(k)
    layer_names = {0: "L1 activation", 1: "L2 rank", 2: "L2 trace-sign",
                   3: "L2 offdiag-sign", 4: "L2 det-sign", 5: "cross-cmp",
                   6: "L3 degree-3"}
    for layer in sorted(layer_counts):
        print(f"    {layer_names[layer]}: {len(layer_counts[layer])}")
        for k in layer_counts[layer]:
            print(f"      - {k}")


if __name__ == "__main__":
    report()

D.16. Orbit-separation fingerprint

Constructs the 93-feature candidate separating set (42 degree-2 + 51 degree-3), verifies $(S_3)^3$-invariance and generic orbit separation on random samples plus orbit-mates.

game_invariants/orbit_separation_3x3.py:

Show code

from itertools import combinations, combinations_with_replacement
import json
import numpy as np

from contrast_blocks_3x3 import (
    mean_zero_payoff, project_contrast_block, family_matrix, all_family_matrices
)


def _project_block_local(u_p, S):
    """Local representation of T_{S, p} (dimension 2^|S|)."""
    full = project_contrast_block(u_p, S)
    sl = [slice(None)] * 3
    for axis in range(3):
        if axis not in S:
            sl[axis] = 0
    return full[tuple(sl)]


def degree2_features(u):
    """42 invariants: upper triangle of M_S for each non-empty S."""
    out = []
    for r in range(1, 4):
        for S in combinations((0, 1, 2), r):
            M = family_matrix(u, S)
            for i in range(3):
                for j in range(i, 3):
                    out.append(M[i, j])
    return np.array(out)


def degree3_features_extended(u):
    u0 = mean_zero_payoff(u)
    out = []

    # Main-effect polarizations
    for axis in (0, 1, 2):
        S = (axis,)
        Ts = [_project_block_local(u0[p], S) for p in range(3)]
        for p, q, r in combinations_with_replacement(range(3), 3):
            out.append(float(np.sum(Ts[p] * Ts[q] * Ts[r])))

    # Pairwise-block determinants
    for pair in combinations((0, 1, 2), 2):
        for p in range(3):
            T = _project_block_local(u0[p], pair)
            out.append(float(np.linalg.det(T)))

    # Three-way contractions
    Ds = [_project_block_local(u0[p], (0, 1, 2)) for p in range(3)]
    for p, q, r in combinations_with_replacement(range(3), 3):
        out.append(float(np.sum(Ds[p] * Ds[q] * Ds[r])))

    M3 = family_matrix(u, (0, 1, 2))
    out.append(float(np.trace(M3 @ M3 @ M3)))
    out.append(float(np.linalg.det(M3)))

    return np.array(out)


def fingerprint(u):
    """Full fingerprint = degree-2 + extended degree-3 features."""
    return np.concatenate([degree2_features(u), degree3_features_extended(u)])


def apply_group_element(u, sigma1, sigma2, sigma3):
    inv1 = np.argsort(sigma1)
    inv2 = np.argsort(sigma2)
    inv3 = np.argsort(sigma3)
    return u[:, inv1][:, :, inv2][:, :, :, inv3]


# ---------------------------------------------------------------------------
# Tests
# ---------------------------------------------------------------------------


def test_orbit_invariance(N=30, tol=1e-8):
    """For N random games, verify the fingerprint is (S_3)^3-invariant."""
    rng = np.random.default_rng(0)
    max_err = 0.0
    for trial in range(N):
        u = rng.standard_normal((3, 3, 3, 3))
        fp_u = fingerprint(u)
        # Random group element
        sigma1 = rng.permutation(3)
        sigma2 = rng.permutation(3)
        sigma3 = rng.permutation(3)
        u_rel = apply_group_element(u, sigma1, sigma2, sigma3)
        fp_rel = fingerprint(u_rel)
        err = float(np.max(np.abs(fp_u - fp_rel)))
        max_err = max(max_err, err)
    return max_err


def test_separation_random(N=500, tol=1e-6):
    rng = np.random.default_rng(1)
    fps = []
    labels = []
    for i in range(N):
        u = rng.standard_normal((3, 3, 3, 3))
        fp_u = fingerprint(u)
        fps.append(fp_u)
        labels.append(i)
        sigma1 = rng.permutation(3)
        sigma2 = rng.permutation(3)
        sigma3 = rng.permutation(3)
        u_rel = apply_group_element(u, sigma1, sigma2, sigma3)
        fps.append(fingerprint(u_rel))
        labels.append(i)
    fps = np.array(fps)
    labels = np.array(labels)
    M = len(fps)

    # Compare every pair; record cases where fingerprints match
    pair_matches = []
    pair_mismatches_in_same_orbit = []
    for i in range(M):
        for j in range(i + 1, M):
            diff = float(np.max(np.abs(fps[i] - fps[j])))
            same_orbit = (labels[i] == labels[j])
            close = diff < tol
            if close and not same_orbit:
                pair_matches.append((i, j, diff))
            if not close and same_orbit:
                pair_mismatches_in_same_orbit.append((i, j, diff))

    return {
        "false_merges": pair_matches,
        "broken_orbit_mates": pair_mismatches_in_same_orbit,
        "n_games": N,
        "n_total": M,
    }


def test_atlas_separation(atlas_path="atlas_3x3_results.json"):
    # Rebuild atlas fingerprints from scratch (the JSON has limited diagnostics)
    from atlas_3x3 import NAMED_GAMES
    fps = {}
    for name, builder in NAMED_GAMES.items():
        u = builder()
        fps[name] = fingerprint(u)
    games = list(fps.keys())
    n = len(games)
    collisions = []
    for i in range(n):
        for j in range(i + 1, n):
            diff = float(np.max(np.abs(fps[games[i]] - fps[games[j]])))
            if diff < 1e-6:
                collisions.append((games[i], games[j], diff))
    return collisions, fps


# ---------------------------------------------------------------------------
# Main
# ---------------------------------------------------------------------------


def _structured_orbit_samples(N_random=80):
    from atlas_3x3 import NAMED_GAMES
    samples = []
    rng = np.random.default_rng(7)

    for _ in range(N_random):
        samples.append(rng.standard_normal((3, 3, 3, 3)))

    for builder in NAMED_GAMES.values():
        u = builder()
        samples.append(u)
        # Perturbations of atlas games
        for eps in (0.01, 0.1):
            samples.append(u + eps * rng.standard_normal((3, 3, 3, 3)))

    # Sparse / structured games
    for _ in range(20):
        u = rng.standard_normal((3, 3, 3, 3))
        mask = rng.random((3, 3, 3, 3)) < 0.3
        samples.append(u * mask)

    return samples


def minimum_separating_subset(N=200, tol=1e-6, verbose=False):
    rng = np.random.default_rng(123)
    base_samples = _structured_orbit_samples(N_random=N)
    fps_full = []
    labels = []
    for i, u in enumerate(base_samples):
        fps_full.append(fingerprint(u))
        labels.append(i)
        # Add the orbit mate
        sigma1 = rng.permutation(3)
        sigma2 = rng.permutation(3)
        sigma3 = rng.permutation(3)
        u_rel = apply_group_element(u, sigma1, sigma2, sigma3)
        fps_full.append(fingerprint(u_rel))
        labels.append(i)
    fps_full = np.array(fps_full)
    labels = np.array(labels)

    n_features = fps_full.shape[1]
    keep = set(range(n_features))

    def separates(idxs):
        if not idxs:
            return False
        sub = fps_full[:, sorted(idxs)]
        # Vectorized pairwise check: max-norm distances
        # For each pair (i, j) with i < j: dist = max(|sub[i] - sub[j]|)
        # Find the minimum cross-orbit distance.
        n = sub.shape[0]
        for i in range(n - 1):
            diffs = np.max(np.abs(sub[i + 1:] - sub[i]), axis=1)
            # Mask pairs in same orbit
            same_orbit = (labels[i + 1:] == labels[i])
            cross_diffs = diffs[~same_orbit]
            if cross_diffs.size > 0 and cross_diffs.min() < tol:
                return False
        return True

    if not separates(keep):
        return None  # already cannot separate; shouldn't happen with our 93

    changed = True
    while changed:
        changed = False
        # Try dropping features in order
        for i in sorted(keep):
            trial = keep - {i}
            if separates(trial):
                keep = trial
                changed = True
                if verbose:
                    print(f"    dropped feature {i}; {len(keep)} remain", flush=True)
                break
    return sorted(keep)


def main():
    print("Orbit-separation tests for (3,3)-games")
    print("=" * 70)

    # Sample fingerprint size
    rng = np.random.default_rng(99)
    u_sample = rng.standard_normal((3, 3, 3, 3))
    fp_sample = fingerprint(u_sample)
    print(f"Fingerprint size: {fp_sample.shape[0]} invariants")
    print(f"  ({degree2_features(u_sample).shape[0]} degree-2 + "
          f"{degree3_features_extended(u_sample).shape[0]} degree-3)")
    print()

    # Test A: orbit invariance
    print("(A) Orbit invariance: applying random g in (S_3)^3 to random games ...")
    max_err = test_orbit_invariance(N=30)
    print(f"  max |fingerprint(u) - fingerprint(g.u)| over 30 trials: {max_err:.2e}")
    assert max_err < 1e-8, "fingerprint is NOT G-invariant"
    print("  PASS: fingerprint is (S_3)^3-invariant.")
    print()

    # Test B: generic separation
    print("(B) Generic orbit separation on N=500 random games + orbit-mates ...")
    result = test_separation_random(N=500, tol=1e-6)
    n_false = len(result["false_merges"])
    n_broken = len(result["broken_orbit_mates"])
    print(f"  pairs in different orbits with same fingerprint (FALSE MERGES): {n_false}")
    print(f"  pairs in same orbit with different fingerprint (BROKEN INVARIANCE): {n_broken}")
    assert n_broken == 0
    if n_false == 0:
        print("  PASS: no false merges. Fingerprint generically separates orbits.")
    else:
        print(f"  FAIL: {n_false} false merges. Examples:")
        for i, j, d in result["false_merges"][:3]:
            print(f"    games {i} and {j} differ by {d:.2e} but in different orbits")
    print()

    # Test C: atlas separation
    print("(C) Atlas separation: all 13 named games have distinct fingerprints?")
    collisions, fps = test_atlas_separation()
    if collisions:
        print(f"  COLLISIONS: {len(collisions)} pairs")
        for a, b, d in collisions:
            print(f"    {a} <-> {b}: max diff {d:.2e}")
    else:
        print("  PASS: all 13 atlas games have distinct fingerprints.")
    print()

    # Test D: empirical minimum separating subset against a STRESS-TEST sample.
    # Note: greedy elimination on any finite sample will return very few features
    # since any non-constant invariant has distinct values on N generic points.
    # This is NOT a meaningful lower bound for the full orbit-separation task.
    # The TRUE minimum separating set for V^0/G has size constrained algebraically
    # by the geometry of the quotient; for our generating ring we need 42 + 556 = 598
    # invariants (degrees 2 + 3) minimum, possibly more at higher degrees.
    print("(D) Greedy minimum on stress-test sample ...")
    print("    (random + atlas + perturbations + sparse, with orbit-mates)")
    kept = minimum_separating_subset(N=80, tol=1e-4, verbose=False)
    print(f"  Greedy result on this sample: {len(kept)} features suffice.")
    print(f"  CAVEAT: this is sample-specific, not a true separation lower bound.")
    print(f"  For full orbit separation on V^0/G, the generating set (42 deg-2 +")
    print(f"  556 deg-3 = 598 invariants total) is the right target.")
    print()

    print("=" * 70)
    print("Summary:")
    print(f"  Fingerprint = {fp_sample.shape[0]} invariants "
          f"({degree2_features(u_sample).shape[0]} deg-2 + "
          f"{degree3_features_extended(u_sample).shape[0]} deg-3)")
    print(f"  Orbit-invariant: max err {max_err:.2e}")
    print(f"  False merges on random sample (N=500, 1000 games total): {n_false}")
    print(f"  Atlas separation: {len(collisions)} collisions")
    print(f"  Greedy minimum separating subset: {len(kept)} features")


if __name__ == "__main__":
    main()

D.17. Hilbert-series + stress-test separation

Verifies the candidate separating set on 5 special strata (random, symmetric, low-rank, sparse, near-degenerate). Compares the subalgebra Hilbert series against the full Molien series at low degrees and reports the algebra-coverage gap.

game_invariants/hilbert_separation_3x3.py:

Show code

from itertools import combinations_with_replacement
import json
import numpy as np

from orbit_separation_3x3 import (
    fingerprint,
    degree2_features,
    degree3_features_extended,
    apply_group_element,
)
from molien_3x3_strategy_only import molien_33_strategy_only


# ---------------------------------------------------------------------------
# (1) Subalgebra Hilbert series via numerical rank
# ---------------------------------------------------------------------------


def compute_subalgebra_hilbert(max_degree=6, N_points=800, tol=1e-6, verbose=True):
    # Each f_i has its own degree (2 for the 42 family-matrix entries, 3 for
    # the 51 degree-3 cubics).
    fp_degrees = [2] * 42 + [3] * 51
    n_inv = len(fp_degrees)

    if verbose:
        print(f"Evaluating fingerprint at {N_points} random V^0 points ...",
              flush=True)
    rng = np.random.default_rng(11)
    sample_pts = [rng.standard_normal((3, 3, 3, 3)) for _ in range(N_points)]
    F_eval = np.array([fingerprint(u) for u in sample_pts])  # (N_points, 93)

    # For each total degree d, enumerate monomials in the 93 invariants
    # whose total *fingerprint degree* (sum of fp_degrees of chosen invariants)
    # equals d. Evaluate each monomial as a product across the sample.
    if verbose:
        print(f"Enumerating monomials in subalgebra coordinates up to degree {max_degree} ...",
              flush=True)
    hilb = [0] * (max_degree + 1)
    hilb[0] = 1  # constants

    # For each abstract polynomial degree d, the contributing monomials are
    # m_{i1} m_{i2} ... m_{ik} where i_1 <= i_2 <= ... and fp_degrees sum to d.
    # Enumerate by length k = 1, 2, 3, ... and total degree.
    for d in range(1, max_degree + 1):
        # Build all unordered tuples of fingerprint indices whose degree sums to d.
        mono_evals = []
        for k in range(1, d // 2 + 1):  # min monomial length is d/d=1, max d/2
            pass
        # Simpler: iterate over k (monomial length); for each k, generate
        # unordered tuples and filter by total degree.
        # Max k for total degree d: k <= d (when all fp_degrees=1, but our min is 2).
        # Actually min fp_degree is 2, so max k = d // 2.
        for k in range(1, d // 2 + 1):
            for idxs in combinations_with_replacement(range(n_inv), k):
                if sum(fp_degrees[i] for i in idxs) == d:
                    val = np.ones(N_points)
                    for i in idxs:
                        val *= F_eval[:, i]
                    mono_evals.append(val)
        if not mono_evals:
            hilb[d] = 0
            if verbose:
                print(f"  degree {d}: no monomials -> dim 0", flush=True)
            continue

        M = np.array(mono_evals)  # (n_monos, N_points)
        rank = int(np.linalg.matrix_rank(M, tol=tol))
        hilb[d] = rank
        if verbose:
            print(f"  degree {d}: {len(mono_evals)} monomials, rank = {rank}",
                  flush=True)

    return hilb


def compare_to_molien(subalgebra_hilbert, max_degree):
    """Compare subalgebra Hilbert series to full Molien series."""
    full = molien_33_strategy_only(max_degree)
    print()
    print("Hilbert series comparison: subalgebra vs full invariant ring")
    print("=" * 70)
    print(f"{'degree':>6} {'subalgebra':>12} {'full ring':>12} {'gap':>8}")
    print("-" * 70)
    for d in range(max_degree + 1):
        gap = full[d] - subalgebra_hilbert[d]
        flag = "" if gap == 0 else "  <-- gap" if gap > 0 else "  ERROR"
        print(f"{d:>6} {subalgebra_hilbert[d]:>12} {full[d]:>12} {gap:>+8}{flag}")
    print()
    total_gap_low = sum(full[d] - subalgebra_hilbert[d] for d in range(min(4, len(full))))
    return full, total_gap_low


# ---------------------------------------------------------------------------
# (2) Stress-tests on special strata
# ---------------------------------------------------------------------------


def _gen_random(rng):
    return rng.standard_normal((3, 3, 3, 3))


def _gen_symmetric_payoff(rng):
    # Generate via a single random function on (own_strategy, multiset of others)
    # multiset of 2 strategies from {0,1,2}: 6 possibilities
    # Total entries: 3 (own) * 6 (multiset) = 18 random numbers
    base = rng.standard_normal(18)
    u = np.zeros((3, 3, 3, 3))
    multiset_index = {}
    idx = 0
    for a in range(3):
        for b in range(a, 3):
            multiset_index[(a, b)] = idx
            multiset_index[(b, a)] = idx
            idx += 1
    for p in range(3):
        for s1 in range(3):
            for s2 in range(3):
                for s3 in range(3):
                    profile = [s1, s2, s3]
                    own = profile[p]
                    others = sorted(profile[q] for q in range(3) if q != p)
                    mi = multiset_index[(others[0], others[1])]
                    u[p, s1, s2, s3] = base[own * 6 + mi]
    return u


def _gen_low_rank_payoff(rng, rank=2):
    u = np.zeros((3, 3, 3, 3))
    for p in range(3):
        for _ in range(rank):
            v1 = rng.standard_normal(3)
            v2 = rng.standard_normal(3)
            v3 = rng.standard_normal(3)
            u[p] += np.einsum('i,j,k->ijk', v1, v2, v3)
    return u


def _gen_sparse_payoff(rng, density=0.3):
    """Sparse: zero out (1 - density) fraction of payoff entries."""
    u = rng.standard_normal((3, 3, 3, 3))
    mask = rng.random((3, 3, 3, 3)) < density
    return u * mask


def _gen_near_degenerate(rng, eps=0.05):
    """Near-degenerate: small perturbation of a degenerate (all-zero) tensor."""
    return eps * rng.standard_normal((3, 3, 3, 3))


STRATA = {
    "random": _gen_random,
    "symmetric": _gen_symmetric_payoff,
    "low_rank": _gen_low_rank_payoff,
    "sparse": _gen_sparse_payoff,
    "near_degenerate": _gen_near_degenerate,
}


def stress_test(N_per_stratum=50, tol=1e-6, verbose=True):
    rng = np.random.default_rng(99)
    results = {}
    if verbose:
        print("Stress tests on special strata")
        print("=" * 70)
    for stratum_name, gen in STRATA.items():
        if verbose:
            print(f"  stratum: {stratum_name} ({N_per_stratum} orbits) ...",
                  flush=True)
        fps = []
        labels = []
        for i in range(N_per_stratum):
            u = gen(rng)
            fps.append(fingerprint(u))
            labels.append(i)
            sigma1 = rng.permutation(3)
            sigma2 = rng.permutation(3)
            sigma3 = rng.permutation(3)
            u_rel = apply_group_element(u, sigma1, sigma2, sigma3)
            fps.append(fingerprint(u_rel))
            labels.append(i)

        fps = np.array(fps)
        labels = np.array(labels)
        n = len(fps)

        false_merges = 0
        max_in_orbit = 0.0
        min_cross_orbit = float("inf")
        for i in range(n - 1):
            diffs = np.max(np.abs(fps[i + 1:] - fps[i]), axis=1)
            same_orbit = (labels[i + 1:] == labels[i])
            in_orbit_diffs = diffs[same_orbit]
            cross_orbit_diffs = diffs[~same_orbit]
            if in_orbit_diffs.size > 0:
                max_in_orbit = max(max_in_orbit, float(in_orbit_diffs.max()))
            if cross_orbit_diffs.size > 0:
                min_cross_orbit = min(min_cross_orbit, float(cross_orbit_diffs.min()))
            false_merges += int((cross_orbit_diffs < tol).sum())

        results[stratum_name] = {
            "false_merges": false_merges,
            "max_in_orbit": max_in_orbit,
            "min_cross_orbit": min_cross_orbit,
        }
        if verbose:
            print(f"    false merges: {false_merges}")
            print(f"    max in-orbit diff: {max_in_orbit:.2e} (should be ~ machine eps)")
            print(f"    min cross-orbit diff: {min_cross_orbit:.2e}")
    return results


# ---------------------------------------------------------------------------
# Main
# ---------------------------------------------------------------------------


def main():
    print("(3a) Stronger separation verification for the 93-invariant fingerprint")
    print("=" * 78)
    print()

    # Hilbert-series check
    print("[1/2] Subalgebra Hilbert-series check (vs full Molien)")
    hilb = compute_subalgebra_hilbert(max_degree=4, N_points=400, verbose=True)
    full, total_gap = compare_to_molien(hilb, max_degree=4)
    if total_gap == 0:
        print("PASS: subalgebra Hilbert series matches full Molien up to degree 4.")
        print("Implication: every invariant of degree <= 4 is a polynomial in F.")
    else:
        print(f"GAP: subalgebra is missing {total_gap} invariants in degrees <= 4.")
        print("Implication: not all degree-<=4 invariants are polynomials in F.")
        print("This DOES NOT necessarily mean orbits are unseparated, but it")
        print("is a warning sign. Adding more degree-3 or degree-4 invariants")
        print("could close the gap.")
    print()

    # Stress-test check
    print("[2/2] Stress-test on special strata")
    stress = stress_test(N_per_stratum=50, tol=1e-6)
    print()
    print("Summary of stress tests:")
    print(f"{'stratum':<20s} {'false_merges':>14s} {'max_in_orbit':>14s} {'min_cross':>14s}")
    print("-" * 70)
    total_merges = 0
    for stratum, info in stress.items():
        total_merges += info["false_merges"]
        print(f"{stratum:<20s} {info['false_merges']:>14d} "
              f"{info['max_in_orbit']:>14.2e} {info['min_cross_orbit']:>14.2e}")
    print()
    if total_merges == 0:
        print("PASS: no false merges in any stratum. 93 invariants robustly separate.")
    else:
        print(f"FAIL: {total_merges} false merges. The 93 invariants are not sufficient")
        print("on every stratum tested.")


if __name__ == "__main__":
    main()

D.18. Typology census of $(3,3)$-games

Two-pass census: Pass 1 enumerates all 128 family-activation patterns and constructs a representative game for each; Pass 2 samples within each cell to enumerate Layer-2 sub-cells. Outputs typology_census_3x3.json and typology_census_3x3_table.md.

game_invariants/typology_census_3x3.py:

Show code

"""Typology census of (3,3)-games under (S_3)^3 (strategy-only relabeling)."""

from collections import Counter
from itertools import combinations, product
import json
import numpy as np

from contrast_blocks_3x3 import (
    mean_zero_payoff, project_contrast_block, family_matrix, all_family_matrices,
)
from classify_3x3 import sign3, TOL


TYPES = [(0,), (1,), (2,), (0, 1), (0, 2), (1, 2), (0, 1, 2)]
TYPE_LABELS = ["{1}", "{2}", "{3}", "{1,2}", "{1,3}", "{2,3}", "{1,2,3}"]


def _pattern_bits(pattern: tuple) -> str:
    return "".join(str(b) for b in pattern)


def _all_patterns():
    return list(product([0, 1], repeat=7))


def construct_game(pattern: tuple, rng: np.random.Generator) -> np.ndarray:
    u = np.zeros((3, 3, 3, 3))
    for k, S in enumerate(TYPES):
        if pattern[k] == 0:
            continue
        for p in range(3):
            raw = rng.standard_normal((3, 3, 3))
            block = project_contrast_block(raw, S)
            u[p] += block
    return u


def measure_layer1(u: np.ndarray) -> tuple:
    bits = []
    for S in TYPES:
        active = 0
        for p in range(3):
            block = project_contrast_block(mean_zero_payoff(u)[p], S)
            if float(np.max(np.abs(block))) > TOL:
                active = 1
                break
        bits.append(active)
    return tuple(bits)


def measure_layer2(u: np.ndarray) -> tuple:
    fmats = all_family_matrices(u)
    sig = []
    for S in TYPES:
        M = fmats[S]
        rk = int(np.linalg.matrix_rank(M, tol=1e-10))
        offdiag = M[~np.eye(3, dtype=bool)]
        signs = set(sign3(v) for v in offdiag)
        if 0 in signs and len(signs) > 1:
            signs.discard(0)
        if rk == 0 and abs(np.trace(M)) < TOL:
            label = ("0", 0)
        else:
            if len(signs) > 1:
                offlabel = "M"
            elif signs == {1}:
                offlabel = "+"
            elif signs == {-1}:
                offlabel = "-"
            else:
                offlabel = "0"
            label = (str(rk), offlabel)
        sig.append(label)
    return tuple(sig)


def pattern_interpretation(pattern: tuple) -> str:
    bits = pattern
    n_main = sum(bits[:3])
    n_pair = sum(bits[3:6])
    n_three = bits[6]
    descriptors = []
    if n_main == 0 and n_pair == 0 and n_three == 0:
        return "trivial (zero game)"
    if n_main > 0 and n_pair == 0 and n_three == 0:
        descriptors.append("linear" if n_main == 3 else f"linear in {n_main}/3 axes")
    if n_main == 0 and n_pair > 0 and n_three == 0:
        descriptors.append("pure pairwise" if n_pair == 3 else f"pairwise in {n_pair}/3 pairs")
    if n_main == 0 and n_pair == 0 and n_three == 1:
        descriptors.append("pure three-way")
    if n_main > 0 and n_pair > 0 and n_three == 0:
        descriptors.append("main + pairwise")
    if n_main > 0 and n_pair == 0 and n_three == 1:
        descriptors.append("main + three-way")
    if n_main == 0 and n_pair > 0 and n_three == 1:
        descriptors.append("pairwise + three-way")
    if n_main > 0 and n_pair > 0 and n_three == 1:
        descriptors.append("full structure")
    if not descriptors:
        descriptors.append("mixed")
    return ", ".join(descriptors)


def pass1_layer1_census(rng_seed=0, attempts=8):
    rng = np.random.default_rng(rng_seed)
    cells = {}
    for pattern in _all_patterns():
        success = False
        rep_u = None
        for _ in range(attempts):
            u = construct_game(pattern, rng)
            measured = measure_layer1(u)
            if measured == pattern:
                success = True
                rep_u = u
                break
        cells[_pattern_bits(pattern)] = {
            "pattern": list(pattern),
            "realizable": success,
            "representative": rep_u.tolist() if rep_u is not None else None,
            "n_main": sum(pattern[:3]),
            "n_pair": sum(pattern[3:6]),
            "n_three": int(pattern[6]),
            "interpretation": pattern_interpretation(pattern),
        }
    return cells


def pass2_layer2_refinement(cells: dict, n_samples=80, rng_seed=1):
    rng = np.random.default_rng(rng_seed)
    for key, cell in cells.items():
        if not cell["realizable"]:
            cell["layer2_subcells"] = []
            continue
        pattern = tuple(cell["pattern"])
        seen = {}
        for _ in range(n_samples):
            u = construct_game(pattern, rng)
            if measure_layer1(u) != pattern:
                continue
            l2 = measure_layer2(u)
            l2_key = "|".join(f"{a}{b}" for (a, b) in l2)
            seen.setdefault(l2_key, {
                "signature": [list(t) for t in l2],
                "count": 0,
            })
            seen[l2_key]["count"] += 1
        cell["layer2_subcells"] = [
            {"key": k, "signature": v["signature"], "sample_count": v["count"]}
            for k, v in sorted(seen.items(), key=lambda kv: -kv[1]["count"])
        ]
    return cells


def place_named_games(cells: dict):
    from atlas_3x3 import NAMED_GAMES
    placements = {}
    for name, builder in NAMED_GAMES.items():
        u = builder()
        pattern = measure_layer1(u)
        l2 = measure_layer2(u)
        key = _pattern_bits(pattern)
        placements[name] = {
            "layer1_key": key,
            "layer1_pattern": list(pattern),
            "layer2_signature": [list(t) for t in l2],
        }
        if key in cells:
            cells[key].setdefault("named_games", []).append(name)
    return placements


def write_markdown_table(cells: dict, placements: dict, path: str):
    realizable = [v for v in cells.values() if v["realizable"]]
    empty = [v for v in cells.values() if not v["realizable"]]

    lines = []
    lines.append("# Typology census of $(3,3)$-games under $(S_3)^3$")
    lines.append("")
    lines.append(f"- Layer-1 patterns: 128 total")
    lines.append(f"- Realizable: {len(realizable)}")
    lines.append(f"- Empty/unrealizable: {len(empty)}")

    n_l2 = sum(len(v.get("layer2_subcells", [])) for v in realizable)
    lines.append(f"- Total Layer-2 sub-cells (sampled): {n_l2}")
    lines.append(f"- Named-game placements: {sum(len(v.get('named_games', [])) for v in cells.values())}")
    lines.append("")

    by_struct = {}
    for key, cell in cells.items():
        if not cell["realizable"]:
            continue
        struct = cell["interpretation"]
        by_struct.setdefault(struct, []).append((key, cell))

    lines.append("## Layer-1 cells by structural type")
    lines.append("")
    lines.append("| Structural type | # cells | # Layer-2 sub-cells | Named games placed |")
    lines.append("|---|---:|---:|---|")
    for struct in sorted(by_struct.keys()):
        rows = by_struct[struct]
        n_cells = len(rows)
        n_l2_struct = sum(len(c.get("layer2_subcells", [])) for _, c in rows)
        named = []
        for _, c in rows:
            named.extend(c.get("named_games", []))
        named_str = ", ".join(n.replace("3p_", "").replace("_", " ") for n in named) if named else "—"
        lines.append(f"| {struct} | {n_cells} | {n_l2_struct} | {named_str} |")
    lines.append("")

    lines.append("## Full Layer-1 census (128 cells)")
    lines.append("")
    lines.append("| Pattern | Structural type | Layer-2 sub-cells | Named games |")
    lines.append("|---|---|---:|---|")
    for key in sorted(cells.keys()):
        cell = cells[key]
        if not cell["realizable"]:
            type_str = cell["interpretation"] + " (empty)"
        else:
            type_str = cell["interpretation"]
        n_l2 = len(cell.get("layer2_subcells", []))
        named = cell.get("named_games", [])
        named_str = ", ".join(n.replace("3p_", "").replace("_", " ") for n in named) if named else ""
        lines.append(f"| `{key}` | {type_str} | {n_l2} | {named_str} |")
    lines.append("")

    lines.append("## Pattern bit positions")
    lines.append("")
    lines.append("Bit order in the 7-bit signature: ($\\{1\\}, \\{2\\}, \\{3\\}, \\{1,2\\}, \\{1,3\\}, \\{2,3\\}, \\{1,2,3\\}$).")
    lines.append("Each bit indicates whether the corresponding contrast family is active in the game.")
    lines.append("")

    with open(path, "w") as f:
        f.write("\n".join(lines))


def main():
    print("Pass 1: enumerating 128 Layer-1 patterns ...")
    cells = pass1_layer1_census(rng_seed=0, attempts=8)
    n_real = sum(1 for v in cells.values() if v["realizable"])
    print(f"  Realizable: {n_real} / 128")
    if n_real < 128:
        for key, v in cells.items():
            if not v["realizable"]:
                print(f"    empty: {key} ({v['interpretation']})")

    print()
    print("Pass 2: Layer-2 refinement (sampling each realizable cell) ...")
    cells = pass2_layer2_refinement(cells, n_samples=80, rng_seed=1)
    total_l2 = sum(len(v.get("layer2_subcells", [])) for v in cells.values())
    print(f"  Total Layer-2 sub-cells: {total_l2}")

    print()
    print("Placing 13 named games into their Layer-1 cells ...")
    placements = place_named_games(cells)
    for name, info in placements.items():
        short = name.replace("3p_", "").replace("_", " ")
        print(f"  {short:<30s} -> Layer-1 cell {info['layer1_key']}")

    out_json = "typology_census_3x3.json"
    out_md = "typology_census_3x3_table.md"

    serializable = {
        "cells": {
            k: {kk: vv for kk, vv in v.items() if kk != "representative"}
            for k, v in cells.items()
        },
        "named_game_placements": placements,
    }
    with open(out_json, "w") as f:
        json.dump(serializable, f, indent=2)
    print(f"\nWrote {out_json}")

    write_markdown_table(cells, placements, out_md)
    print(f"Wrote {out_md}")


if __name__ == "__main__":
    main()

AI Disclosure

Used AI to assist drafting, coding, and editing this file. The AI provided suggestions for code structure, function design, and implementation details, which were reviewed and modified by the author as necessary. I’ve checked everything but there’s a reason I haven’t placed this on ArXiv yet. Caveat emptor!

Changelog

5/17/2026: Initial version

References

Candogan, Ozan, Ishai Menache, Asuman Ozdaglar, and Pablo A. Parrilo. 2011. “Flows and Decompositions of Games: Harmonic and Potential Games.” Mathematics of Operations Research 36 (3): 474–503.

Candogan, Ozan, Asuman Ozdaglar, and Pablo A. Parrilo. 2013. “Near-Potential Games: Geometry and Dynamics.” ACM Transactions on Economics and Computation 1 (2): 11:1–32.

Derksen, Harm, and Gregor Kemper. 2015. Computational Invariant Theory. 2nd ed. Encyclopaedia of Mathematical Sciences. Springer.

Germano, Fabrizio. 2006. “On Some Geometry and Equivalence Classes of Normal Form Games.” International Journal of Game Theory 34 (4): 561–81.

Hilbert, David. 1890. “Über Die Theorie Der Algebraischen Formen.” Mathematische Annalen 36: 473–534.

Monderer, Dov, and Lloyd S. Shapley. 1996. “Potential Games.” Games and Economic Behavior 14 (1): 124–43.

Morris, Stephen, and Takashi Ui. 2004. “Best Response Equivalence.” Games and Economic Behavior 49 (2): 260–87.

Nash, John. 1950. “Equilibrium Points in $n$-Person Games.” Proceedings of the National Academy of Sciences 36 (1): 48–49.

Neumann, John von, and Oskar Morgenstern. 1944. Theory of Games and Economic Behavior. Princeton University Press.

Noether, Emmy. 1926. “Der Endlichkeitssatz Der Invarianten Endlicher Gruppen.” Mathematische Annalen 77: 89–92.

Osborne, Martin J., and Ariel Rubinstein. 1994. A Course in Game Theory. MIT Press.

Rapoport, Anatol, and Melvin Guyer. 1966. “A Taxonomy of $2 \times 2$ Games.” General Systems 11: 203–14.

Robbiano, Lorenzo, and Moss Sweedler. 1990. “Subalgebra Bases.” In Commutative Algebra, edited by Winfried Bruns and Aron Simis, 1430:61–87. Lecture Notes in Mathematics. Springer. https://doi.org/10.1007/BFb0085532.

Robinson, David, and David Goforth. 2005. The Topology of the $2 \times 2$ Games: A New Periodic Table. Routledge.

Sturmfels, Bernd. 2008. Algorithms in Invariant Theory. 2nd ed. Texts and Monographs in Symbolic Computation. Springer.

Weibull, Jörgen W. 1995. Evolutionary Game Theory. MIT Press.

Zizzo, Daniel John, and Jonathan H. W. Tan. 2002. “Game Harmony as a Predictor of Cooperation in $2 \times 2$ Games.” Discussion Paper Series. Department of Economics, University of Oxford. https://ora.ox.ac.uk/objects/uuid:2e84540a-1597-4e89-978c-1e5ab90209b1.

Footnotes

Each player assigns a distinct rank $1,\ldots,9$ to the nine strategy profiles, giving $(9!)^2$ labeled games. Dividing by the relabeling group of order $2\cdot(3!)^2 = 72$ gives $(9!)^2/72 > 10^9$.↩︎
This is sometimes called the “advantage” of the first row over the second row, but we prefer “contrast” as we will generalize these concepts to more than two strategies, where the notion of “advantage” becomes less clear.↩︎
This is distinct from quotienting by player swaps. The present section uses only the strategy-relabeling group $S_2\times S_2$, with players distinguishable. If player swaps are also identified, the acting group is the wreath product $(S_2)^2\rtimes S_2$, discussed separately in Appendix C.↩︎
If we are interested in alignment of the two players, we can consider “game harmony” (Zizzo and Tan 2002), defined as $r_A r_B + c_A c_B + d_A d_B$ (we omit normalization for brevity). This is the cosine similarity of the two players’ payoff perturbations, and we might think of $r_Ar_B + c_Ac_B$ as a measure of “interest alignment” between the players (how much the two players want similar things). However, overall game harmony is not an invariant, as it mixes the sign-flip coordinates in a way that does not satisfy the parity conditions. In contrast, $d_Ad_B$ is an invariant that detects a specific type of interaction alignment. Detailed discussion is out of scope of this paper, but the point is that the invariant ring allows us to identify and interpret such conditions in a systematic way.↩︎
It is not strictly necessary to construct an explicit separating subset of size near $\dim V_{n,k}^{0} + 1$, but one approach is to compute a SAGBI basis (Robbiano and Sweedler 1990) of the invariant ring and select a subset by Hilbert-series matching against the orbit-quotient algebra (see Derksen and Kemper (2015) and Sturmfels (2008) for the constructions).↩︎

	\(s_2 = 1\)	\(s_2 = 2\)
\(s_1 = 1\)	\(a_1, b_1\)	\(a_2, b_2\)
\(s_1 = 2\)	\(a_3, b_3\)	\(a_4, b_4\)

Id	Expression	Interpretation
\(g_1\)	\(r_A^2\)	Player 1 row contrast magnitude
\(g_2\)	\(r_A r_B\)	Cross-player row contrast alignment
\(g_3\)	\(c_A^2\)	Player 1 column contrast magnitude
\(g_4\)	\(c_A c_B\)	Cross-player column contrast alignment
\(g_5\)	\(d_A^2\)	Player 1 interaction strength
\(g_6\)	\(d_A d_B\)	Interaction alignment (coordination vs anti-coordination)
\(g_7\)	\(r_B^2\)	Player 2 row contrast magnitude
\(g_8\)	\(c_B^2\)	Player 2 column contrast magnitude
\(g_9\)	\(d_B^2\)	Player 2 interaction strength

Id	Expression
\(g_{10}\)	\(c_A d_A r_A\)
\(g_{11}\)	\(c_A d_B r_A\)
\(g_{12}\)	\(c_B d_A r_A\)
\(g_{13}\)	\(c_B d_B r_A\)
\(g_{14}\)	\(c_A d_A r_B\)
\(g_{15}\)	\(c_A d_B r_B\)
\(g_{16}\)	\(c_B d_A r_B\)
\(g_{17}\)	\(c_B d_B r_B\)

Class	Condition in generators	Coordinate meaning
Potential	\(g_5=g_6=g_9\)	\(d_A=d_B\)
Anti-potential	\(g_5=g_9=-g_6\)	\(d_A=-d_B\)
Zero-sum	\(g_1=g_7=-g_2\), \(g_3=g_8=-g_4\), \(g_5=g_9=-g_6\)	\(B=-A\)
Interaction-aligned	\(g_6>0\)	\(d_A d_B>0\)
Interaction-opposed	\(g_6<0\)	\(d_A d_B<0\)

Game	\(A\)	\(B\)
Prisoner’s Dilemma	\(\begin{pmatrix}3&0\\5&1\end{pmatrix}\)	\(\begin{pmatrix}3&5\\0&1\end{pmatrix}\)
Stag Hunt	\(\begin{pmatrix}4&0\\3&3\end{pmatrix}\)	\(\begin{pmatrix}4&3\\0&3\end{pmatrix}\)
Chicken	\(\begin{pmatrix}3&1\\5&0\end{pmatrix}\)	\(\begin{pmatrix}3&5\\1&0\end{pmatrix}\)
Pure Coordination	\(\begin{pmatrix}1&0\\0&1\end{pmatrix}\)	\(\begin{pmatrix}1&0\\0&1\end{pmatrix}\)
Matching Pennies	\(\begin{pmatrix}1&-1\\-1&1\end{pmatrix}\)	\(\begin{pmatrix}-1&1\\1&-1\end{pmatrix}\)

\(n\)	\(2^n - 1\)	\(\frac{n(n+1)}{2}\)	\(h_2\)
2	3	3	9
3	7	6	42
4	15	10	150
5	31	15	465

Type pattern	Invariant form	Count
\(X, X, X\)	\(\sum_a X_p^a X_q^a X_r^a\), \(p \le q \le r\)	\(4\)
\(Y, Y, Y\)	\(\sum_b Y_p^b Y_q^b Y_r^b\), \(p \le q \le r\)	\(4\)
\(X, Y, D\)	\(\sum_{a,b} X_p^a Y_q^b D_r^{ab}\)	\(8\)
\(X, D, D\)	\(\sum_{a,b} X_p^a D_q^{ab} D_r^{ab}\), \(q \le r\)	\(6\)
\(Y, D, D\)	\(\sum_{a,b} Y_p^b D_q^{ab} D_r^{ab}\), \(q \le r\)	\(6\)
\(D, D, D\)	\(\sum_{a,b} D_p^{ab} D_q^{ab} D_r^{ab}\), \(p \le q \le r\)	\(4\)

\((n,k)\)	Group	\(\|G\|\)	MZ dim	\(h_2\)	\(h_3\)	\(h_4\)
\((2,2)\)	\(S_2 \times S_2\)	4	6	9	8	42
\((2,3)\)	\(S_3 \times S_3\)	36	16	9	32	132
\((3,2)\)	\((S_2)^3\)	8	21	42	189	1428
\((3,3)\)	\((S_3)^3\)	216	78	42	556	9057

Game	\(I_0\)	\(I_1\)	\(I_2\)	\(I_3\)	\(I_4\)
PD	18	\(-42\)	98	2	1
Stag Hunt	8	\(-16\)	32	32	16
Chicken	2	\(-14\)	98	18	9
Pure Coord	0	0	0	8	4
Match Penn	0	0	0	32	\(-16\)

Abstract

Introduction

Scope

Game-Theoretic Background

Games and Payoff Space

Solution Concepts

Game Classes

Named Game Examples

Symmetries

Groups and Group Actions

Permutation Groups

The Strategy Relabeling Group

Invariant Theory

Group Actions, Orbits, and Invariants

The Reynolds Operator

Example

Generators, Syzygies, and Finite Generation

The Molien Series

The Quotient Space

The Invariant Ring of \((2,2)\)-Games

Mean-Zero Coordinates

Computing the Molien Series and Generators

Degree-2 Generators: Magnitudes and Alignments

Degree-3 Generators: Triple Products

Relations (Syzygies) Among the Generators

Game-Theoretic Conditions in Invariant Coordinates

Game Classes and Interaction Conditions

Dominance and Solvability

Mixed Nash Equilibrium Candidate

Named Game Examples

Relation to Robinson-Goforth Ordinal Types

Explicit Robinson-Goforth Representatives

Computable Map from Invariants to Robinson-Goforth Representatives

Cardinal Refinement Beyond Robinson-Goforth

The Invariant Ring of \((n,k)\)-Games

Setup: Payoff Space and Relabeling Group

Mean-Zero Coordinates and Contrast Blocks

The Relabeling Action on Contrast Blocks

Complete Classification by Invariants

Degree-2 Family Matrices

Example: Family Structure for \((3,3)\)-Games

The Inductive Structure of the Generator Construction

Base Case: The \((2,2)\) Basis in Family Language

Adding a Player: \((n-1,k) \to (n,k)\)

Adding a Strategy: \((n,k-1) \to (n,k)\)

The Step \((2,2) \to (2,3)\)

Inductive Construction of the Quotient Coordinates

Molien Series Checks Across \((n,k)\)

The Generalized Ordinal Classification

Binary Games (\(k = 2\)): Parity and Sign Recovery

Non-Binary Games (\(k \geq 3\)): Discriminant Loci

The Complete Inductive Picture for Ordinal Classification

Applications and Further Structure

Scaling Laws

Stabilization in \(k\)

Degree-3 Growth and the Polynomial Threshold

The Degree Hierarchy

Equilibrium Diagnostics

Two-Player Full-Support Indifference Determinant

General \(n\)-Player Incidence-Space Jacobian

Relation to the Hodge Decomposition

Cycle Witnesses and Degree Heuristics

Algorithms and Computation

Computing the Group Action

Computing the Molien Series

Computing Generators

Computing Syzygies

Reproducibility

Conclusion

Summary

Discussion

Appendix A. Computational Details for \((2,2)\)

Appendix B. The \((3,3)\)-Game Invariant Ring and Typology

Appendix C. The Wreath Product (\(D_4\)) Invariant Ring

C.0. Player Permutation and the Wreath Product

C.0b. The \(D_4\) Computation

C.1. Molien Series and Generators

C.2. Syzygies

C.3. Game Classes

C.4. Named Games