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}")
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.
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 players and strategies per player (which we denote as an “-game”). Each finite normal-form game can be represented by a multidimensional array of payoffs in . 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 -games, where we compute an explicit generating set of invariants, together with relations among them, that completely classify -games up to relabeling. We show that this generalizes the Robinson and Goforth (2005) combinatorial taxonomy of -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 -games under strict ordinal equivalence.
We then generalize the construction to finite -games. For each fixed , the resulting invariant ring separates strategy-relabeling orbits, giving an invariant-theoretic classification of -games. In practice, this classification is realized by computing finite generating sets of polynomial invariants and the relations among them. Beyond the complete explicit case, we develop the computational pipeline needed for larger cases, including the 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 once and a closed-form super-polynomial growth rate for binary degree- invariants. We also describe how label-complete cyclic witnesses produce natural degree- invariants and sign-reversing pairs produce degree- 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 . For , the natural object is a Jacobian form on the payoff–mixed-strategy incidence space, polynomial in payoff entries of degree .
Many of the common -games have familiar names. The Prisoner’s Dilemma, Stag Hunt, Chicken, Battle of the Sexes, Matching Pennies, etc. are standard examples of -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 -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 -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 -games, with two players and three strategies per player. Although a few examples, such as Rock-Paper-Scissors, are well known, most -games have no standard names and no useful catalog. In fact, the number of strict ordinal types of -games exceeds .1 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 -games, computing explicit generators, syzygies, game class conditions, and the connection to the Robinson-Goforth ordinal classification. We generalize to -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 -game details, and software documentation.
We develop a computational invariant-theoretic framework for finite normal-form -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 (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 .
Let be a set of players. For each player , let be a finite strategy set with , and let be the payoff function for player . We call the elements of strategy profiles, and the payoff to player at profile . The complete tuple is called a finite normal-form game. If and every player has strategies, we call the game an -game.
A general finite normal-form game has payoff entries, and an -game has payoff entries. Since the payoff functions determine the game once the player and strategy sets are fixed, the space of -games can be identified with .
When and both players have strategies, we can write the game as a pair of matrices , where is the payoff to player 1 and is the payoff to player 2 at the strategy profile . For , the payoff functions are arrays indexed by . We will occasionally return to the two-player matrix notation for concreteness and visualization.
Given a strategy profile , we write for the strategies of all players other than , and for the full profile.
We call a probability distribution over a mixed strategy for player . When , we write
for the -simplex. Thus, a mixed strategy is an element . For a two-player game with mixed strategies , the expected payoffs are and (Neumann and Morgenstern 1944; Nash 1950).
We call the set of strategies maximizing the best response of player to . We call a profile of mixed strategies a Nash equilibrium if each is a best response to . Nash (1950) showed that every finite game has at least one Nash equilibrium.
We say that a strategy for player is strictly dominated if there exists such that for all . 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.
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 for all . Similarly, a game is constant-sum if is constant across all strategy profiles . Constant-sum games are therefore strategically equivalent to zero-sum games after a payoff shift. With the convention that and are the two payoffs at the same profile , a two-player game is zero-sum if and only if (Neumann and Morgenstern 1944).
We call a game an exact potential game (Monderer and Shapley 1996) if there exists a function such that for each player , each strategy , and each alternative strategy , with held fixed,
Thus every unilateral payoff improvement produces the same change in . Pure Nash equilibria are the specific strategy profiles that are local maxima of with respect to unilateral deviations.
We say that an -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 .
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 invariant coordinates below, these distinctions will correspond to explicit sign conditions.
We illustrate with named -games. A general -game has 8 payoff entries:
where is the payoff to player 1 and the payoff to player 2. We refer to the outcome with payoffs as . The payoff space is with coordinates .
Table 1 summarizes the named -games used in this paper.
| Game | P1 ranking | P2 ranking | Class | NE |
|---|---|---|---|---|
| Prisoner’s Dilemma | 3, 1, 4, 2 | 2, 1, 4, 3 | potential | unique |
| Stag Hunt | 1, 3, 4, 2 | 1, 2, 4, 3 | potential | and |
| Chicken | 3, 1, 2, 4 | 2, 1, 3, 4 | anti-coordination | and |
| Pure Coordination | 1, 4 (others 0) | 1, 4 (others 0) | coordination | and |
| Matching Pennies | (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 despite being Pareto superior. In the Stag Hunt, changing one inequality relative to the PD creates two equilibria: is payoff-dominant but 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 creates a best-response cycle with no pure equilibrium.
Rock-Paper-Scissors (RPS) extends the cycling structure of Matching Pennies to . The standard RPS game is a zero-sum game with and , where each strategy beats one strategy and loses to another. The unique Nash equilibrium is the uniform mixture .
The named examples above are highly structured. The standard symmetric examples satisfy , while Matching Pennies is zero-sum with . A generic game in has and 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.
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 ’s strategies is an element of the symmetric group , which acts on the payoff array by permuting the corresponding indices. A permutation of the players is an element of the symmetric group , 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.
A group is a set 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 , the group of permutations of objects.
A group action of on a set assigns to each a transformation of , written , such that the identity element fixes every and
The orbit of is
The orbits partition into equivalence classes. The quotient is the set of these orbits, and the quotient map sends each element to its orbit . There may not in general be a natural way to identify with a subset of , and the quotient space may also have a different geometric or algebraic structure than the original space.
Permutations form a group, called the “symmetric group”, commonly denoted for permutations of distinct objects. itself consists of different elements. For example, 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: denotes the transposition swapping and , while denotes the cycle .
We can also represent permutations by permutation matrices. Let be the standard basis of . For , define by
Thus the -th column of is , and multiplying by permutes coordinates according to .
For each player , a permutation relabels player ’s strategies. Since every payoff array is indexed by the same strategy profile , the permutation acts on every payoff array by permuting the -th index:
Thus the same relabeling of player ’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 , this action becomes matrix multiplication. With the convention , a permutation of player 1’s strategies acts by
and a permutation of player 2’s strategies acts by
Left multiplication by permutes rows; right multiplication by permutes columns. Both and are permuted in the same way, since both payoff matrices are indexed by the same strategy profiles.
For a -game with , the nontrivial element of has permutation matrix . Then
The first swaps rows (relabeling player 1’s strategies), the second swaps columns (relabeling player 2’s strategies). Both act on the same way.
For an -game, each payoff array is indexed by . The nontrivial element of the -th copy of flips the -th coordinate in every player’s payoff array.
For an -game, each player has an independent copy of 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
An element relabels all players’ strategies simultaneously. The factor relabels player ’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 .
When the players are interchangeable (as in anonymous mechanism design or evolutionary settings), we can additionally permute the players themselves by . The resulting group is the wreath product
which we treat separately in Appendix C.
We now review the elements of invariant theory needed for the classification. Standard references are Derksen and Kemper (2015) and Sturmfels (2008). Throughout, is a finite group acting linearly on a finite-dimensional real vector space .
A linear action of on is a group homomorphism . The orbit of a point is the set , and the stabilizer of is . Two points lie in the same orbit if and only if one can be obtained from the other by applying some group element.
Let denote the ring of real-valued polynomial functions on . Since degree polynomials form a subspace , the ring is graded by polynomial degree. The group action preserves degree, and therefore the invariant ring inherits this grading. A polynomial is -invariant if for all and . The set of all -invariant polynomials forms a subring
where
called the invariant ring.
For finite groups, invariants can be constructed explicitly by averaging. The Reynolds operator is defined as
This map is a linear projection from onto . 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- invariants, one applies to a basis of degree- monomials and collects the linearly independent results.
Let act on by swapping coordinates: .
Then is the ring of symmetric polynomials, generated by and . These two generators are algebraically independent, so is a polynomial ring. Every symmetric polynomial in and can be written uniquely as a polynomial in and . For example, the symmetric polynomial can be expressed in terms of the generators as .
By the Hilbert–Noether finite-generation theorem for invariant rings (Hilbert 1890; Noether 1926), the invariant ring is finitely generated as an -algebra. That is, there exist finitely many invariants such that every invariant polynomial can be written as a polynomial in . We call a set of generators for the invariant ring.
In the symmetric polynomial example above, the generators are algebraically independent: there is no nontrivial polynomial relation satisfied by the generators. In general, generators need not be algebraically independent.
Given generators , we can consider the surjection defined by . This map sends each abstract polynomial in the to the corresponding polynomial in the generators, evaluated on . The kernel of is the ideal of all polynomial relations among the generators that hold identically on . We call these relations, or “syzygies”, among the generators. For example, if as polynomial functions on , then 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 .
The Molien series is a generating function that counts the dimension of the space of invariants at each polynomial degree. For a finite group acting on via the representation , the Molien series is defined as
where is the number of linearly independent degree- invariants. The formula follows from Molien’s theorem (see Derksen and Kemper 2015, Ch. 3). In practice, the sum over group elements can often be reduced to a sum over conjugacy classes, since depends only on the conjugacy class of .
The Molien series does not describe the invariants themselves. Instead, it gives the dimension of the invariant space in each degree. By comparing with the span of products of lower-degree generators, we can determine when new generators are needed and check explicit computations.
The generators define a map
The image of this map, denoted , realizes the quotient of by the action of . For finite groups , points of this quotient correspond to orbits. Two points lie in the same orbit if and only if , i.e., if and only if they take the same values on all generators. Equivalently, the generators separate orbits: satisfy if and only if for all .
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.
Before developing the general construction, we will work out the smallest nontrivial case in full, which is the invariant ring of -games under strategy relabeling by the action of the symmetry group , 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 case simplifies the 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 -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 -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.
We first pass to mean-zero coordinates, removing the two player-specific payoff means. Consider a two-player game with payoff matrices and . We write player 1’s payoff matrix as
Based on player 1’s payoff entries , we define
and similarly for player 2 with entries in . We call the row contrast2, the column contrast, and the interaction. The words “row” and “column” refer to the payoff table coordinates. Thus is player 1’s own-strategy contrast, while is player 2’s own-strategy contrast.
The remaining coordinate for player 1 is the payoff sum
and similarly for player 2.
The inverse change of coordinates for player 1 is
The same inverse formula holds for .
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, give linear coordinates on the six-dimensional mean-zero payoff space.
We use unnormalized contrast coordinates, omitting the conventional 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 , the group acts by the following two sign-flip generators:
Proof. Let . Swapping player 1’s strategies swaps the two rows, sending . Under this swap,
The same row swap acts on player 2’s payoff matrix in the same way, so and are negated while is fixed. This gives the formula for .
Similarly, swapping player 2’s strategies swaps the two columns, sending . A direct substitution gives , , . The same column swap acts on player 2’s payoff matrix, so and are negated while is fixed. This gives the formula for .
Since the action is diagonal in these coordinates, a monomial is invariant exactly when it has even total degree in the variables negated by and even total degree in the variables negated by . Thus every invariant monomial has even total degree in
and even total degree in
Equivalently, because the sign-flip action does not mix monomials, a polynomial in the six mean-zero coordinates is -invariant if and only if every monomial appearing in it satisfies these two parity conditions.
We compute the Molien series for this action on the six-dimensional mean-zero payoff space. The first several coefficients are
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.
| Degree | (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 is the dimension of the degree- invariant subspace, not the number of generators in degree . The “new generators” column records what remains after quotienting by products of lower-degree generators.
The invariant ring is generated by the invariants listed below, all of degree or . That is, all degree-4 invariants are products of lower-degree generators. The degree- computation, together with Noether’s bound (Noether 1926), proves that no generators occur above degree . The degree- and degree- rank checks are additional consistency checks, as products of the listed generators span the Molien-predicted dimensions and .
Theorem 1 ( generators) The invariant ring of the mean-zero payoff space under is generated by the following nine degree- invariants and eight degree- 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.
The 9 degree-2 generators are listed in Table 3.
| Id | Expression | Interpretation |
|---|---|---|
| Player 1 row contrast magnitude | ||
| Cross-player row contrast alignment | ||
| Player 1 column contrast magnitude | ||
| Cross-player column contrast alignment | ||
| Player 1 interaction strength | ||
| Interaction alignment (coordination vs anti-coordination) | ||
| Player 2 row contrast magnitude | ||
| Player 2 column contrast magnitude | ||
| Player 2 interaction strength |
These are the nine quadratic monomials in satisfying the two parity conditions above. Each has a direct game-theoretic interpretation. In particular, and are separate invariants, so the quotient distinguishes player 1’s own-strategy contrast from player 2’s own-strategy contrast.
The 8 degree-3 generators (Table 4) are all triple products mixing one coordinate from each of the three types (row, column, interaction).
| Id | Expression |
|---|
These are the products . Each measures a coupling among one row contrast, one column contrast, and one interaction contrast. For example, 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 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 , but not the sign of the triple product .
The first relations (also called syzygies) occur in degree . There are three degree- relations, all of the form :
In degree , the product map has relations. These are binomial relations of the form , arising when two products of generators expand to the same underlying monomial.
| 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.
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.
The relabeling-invariant classes below correspond to polynomial equations or inequalities in the generators (Table 6).
| Class | Condition in generators | Coordinate meaning |
|---|---|---|
| Potential | ||
| Anti-potential | ||
| Zero-sum | , , | |
| Interaction-aligned | ||
| Interaction-opposed |
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
equivalently
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 . 3
On the other hand, the potential, anti-potential, zero-sum, and interaction-alignment conditions above are all expressible using degree- invariants alone.
The degree- generators detect more than interaction alignment. They also detect whether a player has a strictly dominant pure strategy. In a -game, dominance is controlled by the comparison between a player’s own-strategy contrast and their interaction contrast. For player 1 this comparison is versus ; for player 2 it is versus .
We say that a strict ordinal -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 strictly dominates the other against both columns. In mean-zero coordinates, the payoff differences between row 1 and row 2 are
when player 2 plays column 1, and
when player 2 plays column 2. Row 1 strictly dominates row 2 if both differences are positive, i.e. . Row 2 strictly dominates row 1 if both are negative, i.e. . Therefore player 1 has a strictly dominant row if and only if
Similarly, player 2 has a strictly dominant column if and only if
In a strict ordinal -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 -game is solvable by iterated strict dominance if and only if
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 strictly dominates the other. The second is exactly the condition that one column of 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- generators:
or
Thus solvability by iterated strict dominance is a semialgebraic condition in the quotient.
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 -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
where is the probability that player 2 plays column 1. Setting this equal to zero gives
Thus player 1’s indifference equation is nondegenerate exactly when .
Similarly, if is the probability that player 1 plays row 1, player 2’s expected payoff difference between column 1 and column 2 is
so player 2’s indifference equation is
This equation is nondegenerate exactly when .
Therefore the determinant product of the two mixed-indifference equations is, up to the irrelevant scalar factor ,
Thus detects whether the mixed-indifference equations are nondegenerate. If , the equations have a unique mixed-equilibrium candidate:
It is interior (all players have positive probabilities for all strategies) whenever
and
In generator coordinates, this is
Therefore, the degree- generators detect whether a fully mixed equilibrium exists, and if so, whether it is interior. The degree- generator detects whether the mixed-indifference equations are nondegenerate, i.e., whether a unique mixed-equilibrium candidate exists.
The values in Table 8 depend on the particular cardinal representatives chosen for each named game. We use the following representatives:
| Game | ||
|---|---|---|
| Prisoner’s Dilemma | ||
| Stag Hunt | ||
| Chicken | ||
| Pure Coordination | ||
| Matching Pennies |
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, records interaction alignment, while and detect strict dominance for players 1 and 2.
| Game | Diagnosis | |||
|---|---|---|---|---|
| PD | 1 | 8 | 8 | both players dominant; interaction-aligned |
| Stag Hunt | 16 | no dominance; interaction-aligned | ||
| Chicken | 9 | no dominance; interaction-aligned in | ||
| Pure Coord | 4 | pure interaction; no dominance | ||
| Match Penn | interaction-opposed; no dominance |
The full degree- and degree- 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 and , so both players have strictly dominant strategies. Stag Hunt, Chicken, Pure Coordination, and Matching Pennies all fail these inequalities.
The sign of 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 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 sense4.
Robinson and Goforth (2005) classified -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 . Robinson and Goforth’s classification gives no-tie types.
We now show how to recover those types from the invariant values. The output will be a canonical -sign vector. This makes the Robinson-Goforth type a concrete object:
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 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
For a game with no payoff ties, define the player 1 comparison vector
Define analogously from . The labeled ordinal form of the game is
Not every vector in can occur. The six signs for each player must come from a transitive order of four payoffs. For example, one cannot have .
Row and column swaps act on the outcome labels by
Thus
acts on 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
where lexicographic order uses . 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
we get
For the Stag Hunt representative
we get
For the Chicken representative
we get
For a no-tie Matching Pennies representative, take
Then
The standard Matching Pennies matrix has payoff ties, so it produces zero entries in this sign vector and is not one of the no-tie Robinson-Goforth types. A no-tie representative such as the one above should be used when referring to its Robinson-Goforth type.
Let
be a valid vector of generator values, so that
for some -game. We define a computable map
from invariant values to canonical Robinson-Goforth representatives.
First extract the six contrast magnitudes from the degree- generators:
The are always non-negative because they are squares of real numbers.
Now form the finite set of contrast vectors
with these magnitudes and with generator values . That is, each coordinate has the prescribed absolute value,
with the convention that if a magnitude is zero then the corresponding coordinate is zero. We then keep only those sign choices satisfying
for every
There are at most sign choices to check, and fewer when some magnitudes vanish.
For each surviving , compute the comparison-sign vector
where
and
The Robinson-Goforth representative is the canonical row-column representative
This is the desired map
The definition is independent of the chosen surviving sign pattern . Indeed, if two contrast vectors have the same full generator values, then they lie in the same 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 is , so the sign vector lies in
rather than
Such a game is not one of the 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 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.
As we saw, the invariant ring recovers and refines the Robinson-Goforth classification system. Robinson-Goforth keeps only the canonical -sign vector, but the invariant coordinates retain additional game information.
For example, the symmetric Prisoner’s Dilemma representatives
and
have the same Robinson-Goforth representative, but different invariant values. In particular, the first has
while the second has
Robinson-Goforth records that these games have the same ordinal type. The invariant coordinates also record how far apart they are cardinally inside that type.
For interpretation, it is useful to package several degree- combinations into strategic diagnostics. Define three sector-alignment polynomials
and six within-player comparison polynomials
These values are degree- diagnostics inside the quotient. The first three compare the two players’ payoff landscapes sector-by-sector (row contrast, column contrast, and interaction contrast), while the remaining six compare the relative sizes of row, column, and interaction structure within each player’s payoff function.
In particular, is positive exactly when player 1 has a strictly dominant row, while is positive exactly when player 2 has a strictly dominant column. The interaction diagnostic records whether the two players’ interaction contrasts agree in sign. We can interpret this as a measure of interaction alignment (although it is not as a complete test for coordination in the best-response sense).
We now extend the construction from the case to arbitrary -games. An -game has players, each with strategies, so its payoff space is . The main symmetry group is still the strategy-relabeling group, . An element relabels player ’s strategies by , and applies the corresponding permutation to the -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 using the same logic as in the 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.
For each player , let be player ’s payoff function. We write a (pure) strategy profile as . The group acts by
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 , this is the row and column relabeling we saw in the case.
As in the case, we first remove payoff means. For each player , define the player-specific payoff mean
Subtracting this mean gives the mean-zero payoff array . After removing these player-specific means, the mean-zero payoff space has dimension .
We now decompose each mean-zero payoff array into contrast blocks. A contrast type is indexed by a non-empty subset . For each type and each player , let be the corresponding contrast block, with
For a particular game, let denote player ’s component of type . This component measures the part of player ’s payoff array that varies jointly with the strategy coordinates in , after averaging over the coordinates not in and subtracting lower-order effects.
For a -game, the non-empty subsets of are . For player , these are exactly the row contrast, column contrast, and interaction contrast: , , . For player : , , .
Proposition 3 (Mean-Zero Contrast Decomposition) For every -game, the mean-zero payoff space decomposes as
where . Thus
Proof. Fix a player . The payoff array can be identified with an element of , with one tensor factor for each strategy coordinate. In each factor, decompose
where is the one-dimensional constant subspace and is the -dimensional contrast subspace consisting of vectors whose coordinates sum to zero.
Expanding
gives one summand for each subset .5 is used in the factors indexed by and is used in the remaining factors. The summand with is the constant payoff component. That is, the player-specific payoff mean. Removing this component leaves exactly the summands indexed by non-empty subsets .
For a fixed non-empty , the corresponding block has dimension
Summing over all non-empty and then over all players gives
For , each block is one-dimensional, so the contrast types are simply the non-empty subsets. For , each strategy coordinate contributes two independent contrast directions, so . In general, the dimension count is
For example, in a -game, the mean-zero subspace has dimension .
The seven contrast types are summarized in Table 9:
| Type | Count of types | Dim of each block | Total per payoff array | |
|---|---|---|---|---|
| Main effects () | 1 | 3 | ||
| Two-way interactions () | 2 | 3 | ||
| Three-way interaction () | 3 | 1 | ||
| Totals | ||||
| 7 types | ||||
| 26 |
The group preserves the contrast-block decomposition. If , then the factor acts on a block whenever . If , then relabeling player ’s strategies does not affect the block . Thus relabeling can permute coordinates inside a block, but can’t turn a type- block into a type- block.
For , every block is one-dimensional. Relabeling strategy coordinate changes the sign of the contrast coordinates whose type contains . This is the sign-flip action from the section. For , 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.
We now apply the invariant-theoretic quotient construction to arbitrary -games.
Theorem 2 (Complete Classification) Let act on the mean-zero payoff space by relabeling each player’s strategy set. Let be any finite generating set of the invariant ring
Then the map
is constant on strategy-relabeling orbits and separates those orbits. Therefore two mean-zero games have the same invariant coordinates if and only if they differ by a relabeling of strategies.
By the above, for every fixed , the invariant ring gives a complete cardinal classification of -games modulo strategy relabeling and player-specific payoff shifts. The statement above takes any finite generating set as input. Theorem 6 builds a generating set explicitly via the contrast-block Reynolds construction.
Proof. Because 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 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 that separates orbits if two points lie in the same orbit whenever every 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 acting linearly on a finite-dimensional real vector space , the invariant ring admits a separating subset of size at most .
For the present setting, . The Derksen-Kemper bound gives an explicit upper bound on the number of polynomial invariants needed to distinguish all -orbits of -games. For this is , but the actual generating set has 17 generators, which is also separating but is not the minimum. For the bound gives invariants, considerably smaller than the full generating set ( degree- plus at least degree- generators (see Proposition 5 for the binary analog of this count).6
The degree-2 invariants in the setting generalize the nine quadratic generators from the section, which were , then , and .
In the general case, each scalar contrast is replaced by a contrast block , where is a non-empty subset of strategy indices and is the player whose payoff array is being measured. For each contrast type and each pair of players , define
Here the inner product is the natural Euclidean inner product on the contrast block
Equivalently, after choosing the standard contrast coordinates in the block, it is the coordinatewise sum
This is invariant under strategy relabeling because relabeling acts in the same way on and .
For each , the degree- invariants form an symmetric matrix . The diagonal entries measure the magnitude of player ’s payoff variation of type . The off-diagonal entries measure “alignment” between players and in that same contrast type.
For each of the contrast types , and each unordered pair of players with allowed, there is one degree- invariant. The number of such player pairs is .
Theorem 4 (Degree-2 Gram image) Fix a non-empty contrast type and write
The family matrix
is the Gram matrix of vectors in an -dimensional contrast block. Therefore M_S is a positive semidefinite matrix of rank at most .
Conversely, every positive semidefinite matrix of rank at most occurs as for some choice of contrast components .
Proof. Fix a non-empty contrast type , and let
be the corresponding contrast block. For each player , identify the copy with , and write
Then
Thus is exactly the Gram matrix of the vectors
It follows immediately that is positive semidefinite. Indeed, for any ,
Therefore .
Also, if is the matrix whose -th column is , then
Hence
Conversely, let be any positive semidefinite matrix with
By the spectral theorem, there are orthonormal vectors and positive eigenvalues such that
Define vectors by
where the remaining coordinates are zero. Then for every ,
Thus is the Gram matrix of vectors in an -dimensional contrast block.
Finally, because the mean-zero payoff space decomposes as a direct sum of the contrast blocks
the components may be chosen independently inside their type- blocks. Therefore the vectors constructed above can be realized as the contrast components
of some mean-zero game, for instance by setting all other contrast components to zero. Hence every positive semidefinite matrix of rank at most occurs as .
Theorem 5 (Degree-2 Family Count) The degree- mean-zero invariant layer has one family matrix for each non-empty contrast type . Therefore its dimension is
for all . In particular, the degree- count depends on but not on .
Proof. Let
be the standard -dimensional contrast representation of . For each non-empty , the type- contrast block is naturally isomorphic to
with the remaining tensor factors constant. Thus
for each player .
Degree- invariants are -invariant bilinear pairings among the contrast blocks. If , then some strategy coordinate lies in exactly one of . In that coordinate, one block carries the contrast representation , while the other carries the trivial representation. Since has no -invariant vectors, there is no nonzero invariant pairing between and . Therefore degree- invariants only pair blocks of the same contrast type.
Now fix . The representation has, up to scale, a unique invariant inner product, namely the tensor-product Euclidean inner product. Hence for every pair of players , the unique degree- invariant pairing between and is
Because , a fixed contrast type contributes one invariant for each unordered player pair . There are
such pairs.
Finally, there are non-empty contrast types . Therefore
We can verify this by Molien computation for some low-degree
| 2 | 3 | 3 | 9 | | 3 | 7 | 6 | 42 | | 4 | 15 | 10 | 150 | | 5 | 31 | 15 | 465 |
The formula factorizes as (number of contrast types) (number of player pairs); Table 10 tabulates the count through . The contrast types depend on but not on , while the player pairs depend on alone.
For a -game, the degree- generators form families. Each family contains generators, so there are degree- generators in total. We organize these into family matrices, with one row per contrast type (Table 11):
| Family (type ) | Interpretation | Generators |
|---|---|---|
| Payoff variation with strategy coordinate 1 | for | |
| Payoff variation with strategy coordinate 2 | for | |
| Payoff variation with strategy coordinate 3 | for | |
| Joint variation with coordinates 1 and 2 | for | |
| Joint variation with coordinates 1 and 3 | for | |
| Joint variation with coordinates 2 and 3 | for | |
| Joint variation with all three coordinates | for |
Within each family, the 6 generators form a symmetric matrix indexed by players:
In this subsection we describe the generator construction for the invariant ring of -games inductively, starting from the case. There are two directions of generalization: we can add a player, , or we can add a strategy, . Since every -game can be reached from by a sequence of these two steps, these two principles organize the generator structure for all finite games.
We recall the generators of the invariant ring under , now presented in the family language. The contrast types are , corresponding to row contrast, column contrast, and interaction contrast: , , . Since , each contrast block is one-dimensional for each player.
The degree-2 generators organize into 3 families of 3 (Table 12):
| Family | Interpretation | |||
|---|---|---|---|---|
| Row contrast magnitudes and alignment | ||||
| Column contrast magnitudes and alignment | ||||
| Interaction magnitudes and alignment |
Each family is a symmetric matrix indexed by players. The diagonal entries measure magnitudes, and the off-diagonal entry measures alignment. Since , the entries are scalar products .
The degree- generators are cross-family triple products. A product is invariant under if and only if each strategy index appears in an even number of the three types . For , the only even-parity triple of types is : index appears in and , index appears in and , so each index appears twice. The degree- generators are therefore the products
one from each family, with all player assignments.
The basis therefore has nine degree- generators from the family matrices and eight degree- generators from the cross-family triple products, for generators total.
Adding a player changes the family layer. The contrast types for an -game are the non-empty subsets of . The contrast types for an -game are the non-empty subsets of . Thus adding player creates exactly the new types with . There are such new types. The old types remain present.
For each old type , the family matrix grows from an symmetric matrix to an symmetric matrix. Each old family gains the entries for . Each new type with contributes a new family matrix . Since 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 , this gives the count .
For binary games, the degree- 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 , the old binary degree- type triple is
Its player assignments grow from to . There are also
new type triples involving the new coordinate . Together with the old triple, this gives type triples total. Hence
This illustrates the recurrence of Proposition 5.
Proposition 4 (Add-Player Step For the Degree-2 Family Layer) Assume the degree- mean-zero invariant layer for -games is indexed by pairs
Then the degree- mean-zero invariant layer for -games is obtained as follows.
First, each old type
remains present, and its family matrix grows from size to size . Thus each old type contributes new entries,
Second, the new contrast types are exactly the subsets
with . There are such types, and each contributes a full symmetric family matrix.
Therefore the add-player increment is
Consequently, if
then
Proof. The contrast types for -games are the non-empty subsets of . The contrast types for -games are the non-empty subsets of . Hence the old types are the non-empty subsets not containing , and the new types are the subsets containing . There are new types.
For an old type , the internal contrast block has dimension , which is unchanged because and are unchanged. But there is now one contrast component for each of the players. Hence the old family matrix grows from an symmetric matrix to an symmetric matrix. This adds exactly entries, namely the entries involving the new player index .
There are old types, so old types contribute
new degree- invariants.
Each new type with contributes a full symmetric family matrix
So each new type contributes
degree- invariants. Since there are new types, the new-type contribution is
Therefore
Adding this to the inductive hypothesis gives
Proposition 5 (Add-Player Step for Binary Degree- Triples) For binary games, identify contrast types with nonzero vectors in , using symmetric difference as addition. Let be the number of unordered triples of distinct non-empty contrast types satisfying
Then
Consequently,
Since each type triple admits player assignments, the binary degree- count satisfies
Proof. For , each contrast block is one-dimensional. The strategy swap in coordinate changes the sign of exactly when . Therefore a cubic monomial
is invariant if and only if each coordinate appears in an even number of . Equivalently,
Now pass from players to players. The old triples are exactly the triples not containing in any of their three contrast types. These are the old triples.
A genuinely new invariant triple must involve the new coordinate . Because the parity condition requires to occur an even number of times, the coordinate must occur in exactly two of the three contrast types. Thus every new triple has the form
where and inside . Once and are chosen, we are forced to choose by .
For each fixed non-empty , there are choices of . The two new types and are distinct because . However, choosing or choosing gives the same unordered pair of new types. Therefore each fixed contributes unordered new triples.
There are choices of non-empty , so the number of genuinely new type triples is
Hence
With base case , this recurrence solves to
Finally, for each unordered type triple , the player indices attached to the three types may be chosen independently in . Thus each type triple contributes degree- invariants, giving
Adding a strategy changes the internal representation carried by each contrast type, but not the set of contrast types. Both -games and -games have one contrast family for each non-empty subset
For type , the contrast block grows from dimension
to dimension
The player indexing does not change. Thus each degree- family matrix remains an symmetric matrix
Therefore the degree- count is unchanged:
Adding a strategy leaves the degree- family indexing fixed, while changing the internal form of the invariants inside each contrast block.
For , the contrast types remain
Write
where , ,
and
Thus and are main-effect contrast vectors, while is a row- and column-sum-zero interaction matrix.
The old binary cross-family cubic
stabilizes to the contraction
There are such invariants, one for each player assignment .
The degree- invariant layer for decomposes by type pattern as follows (Table 13).
| Type pattern | Invariant form | Count |
|---|---|---|
| , | ||
| , | ||
| , | ||
| , | ||
| , |
Therefore
The invariants of type and are the new main-effect cubics. The invariants of type are the stabilized binary cross-family cubics. The remaining degree- invariants are not all pure interaction-family cubics. They consist of invariants of type , invariants of type , and pure interaction invariants of type .
Proof. For , the standard contrast representation of is two-dimensional. It has, up to scale, one invariant inner product
and one invariant symmetric cubic form
The main-effect blocks and each carry a copy of . Hence within one main-effect family, the degree- invariants are precisely the polarizations
Since the player labels range over two players and the expression is symmetric in them, each main-effect family contributes
cubic invariants. The two main-effect families therefore contribute .
Next consider one , one , and one . The interaction block carries , with the first factor acted on by row relabeling and the second by column relabeling. The unique contraction is
The three player labels are independent, so this contributes
invariants.
Now consider one and two ’s. The row coordinate uses the cubic invariant , while the column coordinate uses the inner product. This gives
Here , while the pair is unordered because the two ’s enter symmetrically. Hence this contributes
invariants. The same argument for one and two ’s contributes another invariants.
Finally, three interaction blocks use the cubic invariant in both the row and column coordinates, giving
Again are unordered player labels from a two-element set, so this contributes
pure interaction-family cubics.
The six type patterns have distinct multidegrees in the variables , so the corresponding invariant spaces are linearly independent. Their total dimension is
This equals the Molien coefficient for the mean-zero representation. Therefore the listed invariants span the full degree- invariant layer.
The two inductive steps above give the general construction for all -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 -invariant ring is literally an extension of the - or -invariant ring. Rather, the point is that every -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 and , the contrast-block Reynolds construction produces a finite set of polynomial invariants that separates strategy-relabeling orbits of mean-zero -games. Equivalently, it gives a complete invariant-theoretic classification of -games modulo strategy relabeling and player-specific payoff shifts.
More explicitly, let
be the mean-zero contrast decomposition, with
Apply the Reynolds operator for
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
The values of these generators separate -orbits in . Thus two mean-zero -games have the same invariant coordinates if and only if they differ by a relabeling of strategies.
Proof. For each player , the mean-zero payoff array lies in
Using the decomposition
we obtain
where the coordinates outside carry the trivial representation. The summand is the player-specific payoff mean. Removing these means gives
The group
acts independently on the strategy coordinates. In coordinate , the block carries if , and the trivial representation if . Therefore the group action preserves the contrast type and the player label . Hence every monomial in the contrast coordinates has a well-defined block pattern
counted with multiplicity, and the Reynolds operator preserves this block pattern.
Now compare with the two smaller directions.
First, adding a player changes the set of contrast types from the non-empty subsets of to the non-empty subsets of . The old contrast types are those not containing . The new contrast types are exactly those containing . The internal representation attached to an old type does not change, since 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 . 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 to . The set of contrast types does not change, and neither does the set of player labels. What changes is the internal representation
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 is finite, the invariant ring
is finitely generated. Moreover, the Reynolds operator
is a projection from onto . Hence, in each degree , Reynolds averages of degree- monomials span the full degree- 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 have the same values on all generators if and only if they lie in the same -orbit. Equivalently, the constructed invariant coordinates classify mean-zero -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- invariants.
As a computational check on the inductive construction, Table 14 compares the mean-zero Molien coefficients for several -games under the strategy-relabeling group .
| Group | MZ dim | |||||
|---|---|---|---|---|---|---|
| 4 | 6 | 9 | 8 | 42 | ||
| 36 | 16 | 9 | 32 | 132 | ||
| 8 | 21 | 42 | 189 | 1428 | ||
| 216 | 78 | 42 | 556 | 9057 |
The degree- column agrees with the family-matrix formula . So for both and , and for both and , and the degree- count depends on the number of players but not on the number of strategies.
The degree- column shows the two inductive effects separately. Adding a player, , raises the degree- count from to , creating more contrast families, more even-parity triples, and more player assignments. Adding a strategy, , raises the degree- count from to . The family structure is unchanged, but new intra-family cubic invariants appear inside the enlarged contrast blocks. The row combines both effects. There are more contrast families from the additional player and richer internal invariant rings from the additional strategy, giving and .
The interaction-alignment diagnostic from the section generalizes directly. For any -game, the -way interaction family plays the role of , and its off-diagonal entries measure pairwise alignment between players’ highest-order interaction components. A detailed treatment of the computation is given in Appendix B.
The ordinal classification of an -game is the ranking of each player’s payoff entries, considered up to strategy relabeling. In mean-zero coordinates, the ordinal type is determined by the signs of the pairwise payoff differences per player. Each difference is a linear combination of the contrast coordinates . The group 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 . It remains to show how this works in practice, and how the invariant structure organizes the ordinal classification.
When , every contrast block is one-dimensional. Thus each contrast component is a scalar, and the relabeling action is a sign-flip action indexed by the strategy coordinates contained in . A monomial is invariant exactly when each strategy coordinate appears an even number of times.
For binary games, the ordinal type modulo 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 .
In low degree, the relevant sign data include:
the signs of the off-diagonal family-matrix entries for , recording interaction alignment between players within the same contrast type;
the within-player magnitude comparisons
for contrast types ;
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 , 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 , each strategy coordinate has the decomposition
where is one-dimensional. Hence every non-empty contrast block is one-dimensional. We write its scalar coordinate as
The strategy-relabeling group is
Let . The relabeling acts on by
Thus changes sign exactly when the relabeling flips an odd number of strategy coordinates contained in .
Now consider a monomial
Under , this monomial is multiplied by
Therefore is invariant under all if and only if each coordinate appears in an even number of the sets . Equivalently,
This proves the even-parity rule for binary invariant monomials.
Next we prove sign recovery. Suppose two binary contrast-coordinate vectors and have the same values on all invariant polynomials. In particular, they have the same quadratic invariants
Hence whenever , and for each nonzero coordinate there is a sign such that
We claim that the signs come from a relabeling in . To see this, consider the vector space over generated by the nonzero coordinates . Define the parity map
by sending the basis vector corresponding to to the indicator vector of . A product of coordinates is invariant exactly when its exponent vector lies in .
Since and have the same values on all invariant monomials, the sign character is trivial on every invariant monomial. Equivalently,
for every . Therefore factors through the quotient
Equivalently, there exists a vector such that
for every nonzero coordinate . Therefore
So is obtained from by a strategy relabeling. Thus the binary invariant values reconstruct the scalar contrast coordinates up to the sign-flip action.
It remains to pass from cardinal contrast coordinates to ordinal type. For each player , the payoff at a binary strategy profile is a linear combination of the contrast coordinates , plus the player-specific mean. Therefore for two profiles , the payoff difference
is a linear combination of the contrast coordinates ; the player-specific mean cancels. Hence, once the contrast coordinates are known up to relabeling, all pairwise payoff-comparison signs
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 -orbit. For any surviving choice, compute the full pairwise payoff-comparison sign vector, and then choose its canonical representative under . 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 .
When , each main-effect contrast is a vector in , and the invariants built from a single contrast type are generated by the power sums . The ordinal type of a -vector with is the ranking of its entries. This ranking is determined by the signs of the pairwise differences , which define a hyperplane arrangement in . The ordinal types (modulo ) are the orbits of the chambers of this arrangement.
The power sums map to the invariant space . This map sends the hyperplane arrangement to a discriminant locus , where
is a polynomial in the power sums (by Newton’s identities). The ordinal types correspond to the connected components of the complement of in invariant space.
For , the discriminant is , which vanishes only at the origin. The complement has one component, so there is one ordinal type (up to ). The two-player information comes from the family matrices and cross-family products, as described above.
For , the discriminant is
Expanding in power sums, with , gives
up to a positive constant. The condition is the no-tie condition for the three entries. The invariant records the skewness of the three-entry contrast vector. is not itself an ordinal type.
For , the discriminant is a degree- polynomial in . The no-tie region is defined by , while the finer chamber information is recovered by pulling back the pairwise comparison signs through the quotient map.
The ordinal classification for is therefore semialgebraic in the invariant coordinates. It is determined by polynomial inequalities, not merely by the signs of individual generators. The discriminant polynomial
defines the tie boundary for a single -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 ordinal classification of an -game is recovered from the invariant ring in two interacting layers:
The family matrices 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 ; 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.
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 and how equilibrium conditions, Hodge-theoretic decompositions, and cyclic witnesses can be studied inside the relabeling quotient.
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 , the number of strategies , and the polynomial degree .
Fix the number of players and the polynomial degree . Computationally, the dimension
stabilizes as the number of strategies increases. The reason is that a degree- monomial can involve at most distinct strategy labels in each coordinate. Once enough labels are available, adding more strategies should not create new degree- orbit types.
For two-player games under , the low-degree Molien coefficients are tabulated in Table 15:
| 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|
| 2 | 9 | 8 | 42 | 48 | 138 |
| 3 | 9 | 32 | 132 | ||
| 4 | 9 | 32 |
The degree- count stabilizes immediately:
The degree- count similarly stabilizes at in the computed range:
The binary row is exceptional in degree , as it has only the eight cross-family cubic generators from the computation. When , new within-family cubic invariants appear, raising the count from to .
We have the following stabilization theorem.
Theorem 7 (Stabilization in the Number of Strategies) Fix and . Then the degree- mean-zero invariant dimension
stabilizes for all . Equivalently, for fixed ,
The threshold is sufficient, though not necessarily minimal.
Proof. Let be the full payoff space. A degree- monomial has the form For each strategy coordinate , this monomial uses only the labels so it uses at most distinct labels in coordinate .
The degree- invariant space has a basis given by orbit sums of degree- monomials. Therefore its dimension is the number of degree- monomial orbits. If , every degree- monomial using labels in is equivalent, under , to one using only labels in , because at most labels are used in each coordinate. Conversely, if two monomials using only labels in are equivalent under , the permutations relating their used labels restrict to bijections between subsets of , and since , these bijections extend to permutations of . Hence they were already equivalent under .
Thus the degree- monomial orbit count in the full payoff space stabilizes for .
Finally, equivariantly, where is the space of player-specific payoff means and is fixed by the group. Hence Removing the fixed mean variables only multiplies the Hilbert series by , so stabilization of the full-space coefficients through degree implies stabilization of the mean-zero coefficients in degree . Therefore
The previous section showed that is polynomial in . The next degree breaks that pattern. For -games under on the mean-zero subspace,
A direct count of even-parity contrast-type triples (Proposition 5) gives the closed form
The leading term scales like , so the count is super-polynomial in . Numerical agreement with this formula for 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 -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- count becomes polynomial in for each . The super-polynomial behavior above is the price of keeping all players distinguishable.
The stabilization and growth results together imply a degree hierarchy of game-theoretic phenomena (Table 16):
| Degree | What it detects | When new -strategy effects appear |
|---|---|---|
| 2 | Contrast magnitudes, interaction strength, cross-player alignment | |
| 3 | Contrast-interaction coupling, skewness, cyclic directionality | |
| 4 | Higher-order contrast distributions, interlocking cyclic structure, -strategy adversarial witnesses |
Each degree adds invariants that detect higher-order polynomial structure in the payoff array. Some of these effects already occur at through cross-family products of scalar contrast coordinates. Others first appear when enough strategy labels are available. At , new degree- invariants appear that detect skewness and cyclic directionality, as in Rock-Paper-Scissors. At , new degree- 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-, degree-, degree-, and higher invariants of a game capture successively finer strategic structure. Two games with the same degree- invariants but different degree- invariants are like two distributions with the same variance but different skewness.
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
and let
The space is the tangent space to the affine simplex , while records payoff vectors modulo addition of a constant. A player is indifferent among all pure strategies exactly when their expected payoff vector is zero in .
Both and carry the standard -dimensional representation of . A strategy relabeling permutes coordinates, preserves , and acts on by the induced quotient action.
Let be a bimatrix game. For player 1, the full-support indifference condition is
where is player 2’s mixed strategy. Passing to the quotient by , this gives an affine linear condition
The associated linear map on tangent directions is
Similarly, player 2’s full-support indifference condition is
and the associated tangent map is
After choosing bases of and , define
The two-player full-support indifference determinant is
Equivalently, in coordinates, is the determinant of the usual system whose first rows are payoff-difference equations and whose final row is the normalization equation. The same holds for .
Proposition 6 (Two-player full-support indifference determinant) For a bimatrix game,
is a -invariant polynomial of degree in the payoff entries. It is nonzero exactly when both full-support indifference systems have unique solutions. For , it agrees with , up to the sign convention used for the indifference rows.
Proof. The map is linear in the entries of . Since and both have dimension , its determinant is homogeneous of degree in the entries of . Similarly, is homogeneous of degree in the entries of . Hence
has degree in the payoff entries.
The affine full-support indifference system for player 1 is
Its linear part on the affine simplex is . Therefore the system has a unique solution if and only if is invertible, i.e. if and only if . The same argument applies to . Thus exactly when both full-support indifference systems have unique solutions.
Now we prove relabeling invariance. Let , where relabels player 1’s strategies and relabels player 2’s strategies. In matrix form,
The induced map on player 1’s indifference operator is
where and denote the induced actions on and . Taking determinants gives
The standard representation has determinant equal to the sign of the permutation, so and . Hence
For player 2, the relevant operator is . Under the same relabeling, its domain is affected by and its codomain by . Thus
Therefore the product transforms as
Thus is invariant under .
For , the spaces and are one-dimensional. With
the tangent direction in player 2’s simplex is proportional to . Then is represented by the payoff difference
Thus , up to the chosen orientation. Similarly , up to orientation. Hence
up to the sign convention used for the bases.
The condition 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, 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.
For , 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 be an -game. For each player , let be their mixed strategy. Write . For each player , define the expected payoff vector by
Player is indifferent among all pure strategies exactly when
Thus the full-support indifference map is
The domain of variations in the mixed-strategy variables is . Thus the Jacobian of the indifference system is the linear map
Define
after choosing compatible bases of and .
Proposition 7 (Full-support Nash incidence Jacobian) For an -game, the full-support indifference map has Jacobian determinant
This is a polynomial in the payoff entries and mixed-strategy coordinates. It is homogeneous of degree 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 , the condition is the local nondegeneracy condition for the full-support indifference system.
Proof. For each player , the expected payoff vector is linear in the payoff entries of player and multilinear in the mixed strategies of the other players. It does not depend on . Therefore the indifference map is polynomial in , linear in the payoff entries of each player, and multilinear in the mixed-strategy variables.
The Jacobian has row-blocks, one for each player. The row-block corresponding to player consists of the derivatives of with respect to the mixed strategies of the players . Every entry in this row-block is linear in player ’s payoff entries.
The total dimension of the domain and codomain is . Thus is an matrix. In every term of its determinant, one entry is chosen from each row. Since the rows belonging to player ’s block are each linear in player ’s payoff entries, every determinant term is homogeneous of degree in the payoff entries of player . Multiplying over all players, every term has total payoff degree . Therefore is homogeneous of degree in the payoff entries.
This determinant is not the zero polynomial. To see this, fix any interior mixed strategy profile . Choose payoff tensors so that, for each player , the indifference vector depends linearly and invertibly only on the mixed strategy of player , with indices read cyclically. In block form, the Jacobian can then be made into a cyclic block-permutation matrix with identity blocks . Such a matrix has nonzero determinant. Hence the polynomial has exact payoff degree .
Now we prove invariance. A relabeling acts on payoff arrays, mixed-strategy coordinates, and payoff-vector quotients. Let denote the induced action on , and let denote the induced action on . The full-support indifference map is equivariant:
Differentiating with respect to gives
Taking determinants yields
But and are the same direct sum of standard representations, one acting on simplex tangent directions and the other acting on payoff differences modulo constants. Therefore . Hence
Finally, if is a full-support equilibrium, then . The local solution structure of the full-support indifference system near is controlled by the derivative . By the inverse function theorem, is locally a nonsingular solution of the indifference system exactly when this derivative is invertible. Equivalently, .
For , 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 .
For , the Jacobian generally depends on the mixed-strategy coordinates. Substituting an equilibrium need not produce a polynomial in the payoff entries.
For example, in a -game, write for the probabilities that players play their first strategy. The binary full-support indifference equations may have the form
When , the full-support solution is . The Jacobian is
so . At the solution, , which is not a polynomial in the payoff parameter . Thus, for , 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 in has been verified numerically for seven combinations (Table 17).
| Degree in payoffs | Verified | |
|---|---|---|
| 2 | ||
| 4 | , verified numerically | |
| 6 | verified numerically | |
| 8 | verified numerically | |
| 3 | verified numerically | |
| 4 | verified numerically | |
| 5 | verified numerically |
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 -game, the payoff space decomposes as
In the Candogan-Ozdaglar-Parrilo decomposition, consists of payoff components that do not depend on the acting player’s own strategy and has dimension . After quotienting by nonstrategic components, the normalized game space decomposes into potential and harmonic components, with the harmonic component having dimension . 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 and is preserved by the strategy-relabeling group .
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 mean-zero coordinates , the potential and anti-potential conditions are visible in the interaction coordinates. The potential condition is , while the anti-potential condition is . In invariant coordinates, these become quadratic conditions: for the potential case, and 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.
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 . Let be linear payoff-comparison forms associated with the edges of that cycle. The product
is a degree- 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
where each is a linear payoff-comparison form supported on one edge of a minimal -cycle. Then the Reynolds average
is a strategy-relabeling invariant of degree .
If an allowed relabeling sends the oriented witness to , then the sign of does not descend to the relabeling quotient. In that case
or an equivalent paired product gives a natural invariant witness of degree .
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 is linear in the payoff entries. Hence
has degree . Applying the Reynolds operator gives
which is invariant by construction and still has degree . Thus a label-complete cyclic witness gives a natural degree- invariant.
If an allowed relabeling sends to , then the sign of is not well-defined on the quotient: two relabeling-equivalent representatives give opposite values of the oriented witness. Therefore itself cannot serve as a signed quotient coordinate for that orientation.
However, is unchanged by , and its Reynolds average is an invariant polynomial of degree . Similarly, if two oriented witnesses transform with opposite signs, then their product gives a degree- invariant.
This proves the existence of natural degree- cycle witnesses and degree- 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 mean-zero space parameterized by
Along this line, and . The degree- invariants record
Thus the basic adversarial interaction is already visible at degree through .
All degree- generators in the strategy-only 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- 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.
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.
Given an -game, the group has order . Each element is a tuple of permutations, one per player. The element acts on the payoff tensor of player by permuting the strategy indices:
This action is linear on the payoff space , so each group element is represented by a permutation matrix of size .
The Molien series is computed by the eigenvalue method. For each group element , we compute the eigenvalues of the representation matrix restricted to the relevant subspace (full, mean-zero, or interaction). The contribution of to the Molien series is
which we expand as a power series in to the desired degree, then average over the group. For the groups , the computation reduces to a sum over elements, each requiring an 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.
Generators are found by the Reynolds-operator method:
Ring closure at degree is verified by checking that the products of all generators at degrees span a space of dimension (the Molien coefficient). By Noether’s bound, the ring is generated in degrees at most .
Syzygies are found by exact symbolic expansion:
Each null vector is a syzygy, linear combinations of products that vanish identically as a polynomial function on .
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.
We have developed an invariant-theoretic framework for finite normal-form games under strategy relabeling. For -games under , 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
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 -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
At degree , these blocks produce family matrices
one for each contrast type . Hence the degree- mean-zero invariant count is
independent of . 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 , 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.
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- 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 -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 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- 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 case admits a complete hand-readable description, but higher 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.
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.
| Game | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| PD | 9 | 49 | 1 | 1 | 49 | 9 | 1 | ||
| Stag Hunt | 4 | 16 | 16 | 16 | 16 | 4 | 16 | ||
| Chicken | 1 | 49 | 9 | 9 | 49 | 1 | 9 | ||
| Pure Coord | 0 | 0 | 0 | 0 | 4 | 4 | 0 | 0 | 4 |
| Match Penn | 0 | 0 | 0 | 0 | 16 | 0 | 0 | 16 |
| Game | ||||||||
|---|---|---|---|---|---|---|---|---|
| PD | 21 | 21 | 21 | 21 | ||||
| Stag Hunt | 16 | 16 | 64 | 64 | ||||
| Chicken | 21 | 21 | 21 | 21 | ||||
| Pure Coord | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Match Penn | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Forthcoming.
In the main text, we treat the players as distinguishable and use the direct product 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 -player -game with payoff arrays , a permutation acts by simultaneously permuting the payoff arrays and their indices:
The payoff array that belonged to player now belongs to player , and the strategy indices are permuted accordingly. For a two-player game, the transposition acts by . 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 a group automorphism if for all . Let and be groups, and suppose acts on by automorphisms (meaning each defines a group automorphism of ). We call the semidirect product the group with underlying set and multiplication
where is the result of acting on . When acts trivially ( for all ), this reduces to the direct product.
For an -game, the strategy permutations form and the player permutations form . A player permutation acts on by rearranging the factors: the strategy permutation that was acting on player now acts on player . Explicitly,
We call the resulting semidirect product the wreath product of with , sometimes written . It has 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 -games, the wreath product is , which is the dihedral group of order 8.
In this appendix we compute the invariant ring of -games under the enlarged group (order 8), which includes the player swap 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 ), with non-trivial syzygies involving an advantage asymmetry quantity . The ring generalizes the 78-type classification of Rapoport and Guyer (1966), who additionally identified the two players, just as the ring generalizes the 144-type classification of Robinson and Goforth (2005).
We work in the same mean-zero coordinates defined in the -Games section. The player swap acts on these coordinates as , , , derived from .
We use the same normalization conventions as the main text: unnormalized coordinates (no factor of ) and orbit-sum Reynolds operator (following Sturmfels 2008). All invariant values on games with integer payoffs are integers.
The Molien series for acting on is
The following table decomposes into products and new generators at each degree.
| Degree | (Molien) | From products | New generators |
|---|---|---|---|
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 2 | 5 | 0 | 5 () |
| 3 | 4 | 0 | 4 () |
| 4 | 23 | 15 | 8 () |
| 5 | 24 | 19 | 5 () |
| 6 | 71 | 71 | 0 (ring closes) |
The ring has 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 is generated in degrees at most . Since , no new generators can appear above degree 8, and the 22 generators are a complete generating set.
| Id | Deg | Expression |
|---|---|---|
| 2 | ||
| 2 | ||
| 2 | ||
| 2 | ||
| 2 | ||
| 3 | ||
| 3 | ||
| 3 | ||
| 3 | ||
| 4 | ||
| 4 | ||
| 4 | ||
| 4 | ||
| 4 | ||
| 4 | ||
| 4 | ||
| 4 | ||
| 5 | ||
| 5 | ||
| 5 | ||
| 5 | ||
| 5 |
Each generator is an orbit sum of a monomial under . The pairing and in each expression reflects the player swap .
The invariant is the product of the two players’ interaction terms. Its sign separates coordination-type games () from anti-coordination-type games (). The invariant also equals the Nash equilibrium discriminant: an interior NE exists if and only if .
The invariants and measure advantage magnitudes, but each mixes two players’ coordinates. This mixing is forced by the player swap: since under the swap, no invariant can separate from . The degree-4 generator resolves this: from and together, one can recover , which measures how evenly the advantage is split between the two players.
The invariant measures cross-player advantage alignment. The quantity will appear as the central syzygy quantity.
The degree-3 generators are the lowest-degree invariants that involve all three types of coordinates (, , and ) simultaneously. They measure how the advantage structure couples to the interaction structure. For games with no advantage structure (, such as Pure Coordination and Matching Pennies), all cubic generators vanish.
The 22 generators define a map that sends each game to its invariant values. Two games lie in the same -orbit if and only if they have the same image under .
The 22 generators are not algebraically independent. We find syzygies by expanding each product of generators as a polynomial in , 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 are linearly independent. The first syzygy appears at degree 5:
At degree 6, there are two syzygies. Both factor through the advantage asymmetry
which is the squared difference between player 1’s row-column advantage product and player 2’s. The degree-6 syzygies are
| Degree | Products | Rank | Syzygies | Notes |
|---|---|---|---|---|
| 4 | 15 | 15 | 0 | All independent |
| 5 | 20 | 19 | 1 | |
| 6 | 45 | 43 | 2 | , both through |
| 7 | 60 | 55 | 5 | |
| 8 | 120 | 106 | 14 |
When , the syzygies simplify to and , which together imply and . On the advantage-symmetric locus (), the four cubic generators collapse to one degree of freedom.
All five named games satisfy , meaning named games live on the advantage-symmetric locus, a measure-zero subset of the full space. When , the syzygies express the squared cubic invariants as products of with the interaction invariants and , constraining the cubic invariants once the advantage asymmetry is known.
| Class | Condition on invariants | Derivation |
|---|---|---|
| Potential | iff | |
| Anti-potential | iff | |
| Symmetric | and | Potential + advantage symmetry |
| Zero-sum | and | Anti-potential + advantage symmetry (necessary, not sufficient at degree 2) |
| Coordination type | : interactions aligned | |
| Anti-coordination type | : interactions opposed |
The Nash equilibrium discriminant for -games is . An interior Nash equilibrium exists if and only if .
Degree-2 invariants:
| Game | |||||
|---|---|---|---|---|---|
| PD | 18 | 98 | 2 | 1 | |
| Stag Hunt | 8 | 32 | 32 | 16 | |
| Chicken | 2 | 98 | 18 | 9 | |
| Pure Coord | 0 | 0 | 0 | 8 | 4 |
| Match Penn | 0 | 0 | 0 | 32 |
Degree-3 invariants:
| Game | ||||
|---|---|---|---|---|
| PD | 42 | 42 | ||
| Stag Hunt | 32 | 128 | ||
| Chicken | 42 | 42 | ||
| Pure Coord | 0 | 0 | 0 | 0 |
| Match Penn | 0 | 0 | 0 | 0 |
Degree-4 invariants:
| Game | ||||||||
|---|---|---|---|---|---|---|---|---|
| PD | 162 | 882 | 18 | 4802 | 98 | |||
| Stag Hunt | 32 | 128 | 128 | 512 | 512 | |||
| Chicken | 2 | 98 | 18 | 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 | |||||
|---|---|---|---|---|---|
| PD | 378 | 2058 | |||
| Stag Hunt | 128 | 512 | 2048 | ||
| Chicken | 42 | 2058 | |||
| Pure Coord | 0 | 0 | 0 | 0 | 0 |
| Match Penn | 0 | 0 | 0 | 0 | 0 |
| Game | Potential | Symmetric | Coord type | Pure NE | |||
|---|---|---|---|---|---|---|---|
| PD | 0 | 4 | 0 | yes | yes | yes | |
| Stag Hunt | 0 | 64 | 0 | yes | yes | yes | |
| Chicken | 0 | 36 | 0 | yes | yes | yes | |
| Pure Coord | 0 | 16 | 0 | yes | yes | yes | |
| Match Penn | 64 | 0 | 0 | no | no | no | none |
All four cooperative games are potential and symmetric. Matching Pennies is anti-potential. All five satisfy , confirming that named games are advantage-symmetric.
For -games, player 1 has a dominant strategy if and only if and have the same sign. These conditions cannot be expressed as polynomial conditions on , because the invariants mix with (the player swap pairs them). Solvability is a semialgebraic condition. The degree-4 invariants and partially resolve this ambiguity.
Rapoport and Guyer (1966) classified -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
The 12 hyperplanes (6 per player) partition 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 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 (strategy relabeling only), while the invariant ring additionally identifies the two players. For symmetric games (), the two quotients agree. For asymmetric games, the player swap can merge Robinson-Goforth classes. For example, the game has a orbit of size 8 containing two Robinson-Goforth classes of size 4.
The Rapoport-Guyer count of 78 types corresponds to the quotient of the ordinal chambers: generic orbits, plus additional types from orbits of size 4 on the symmetric locus.
The 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).
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.
The 17 generators of the invariant ring under strategy relabeling are computed by Reynolds-averaging degree- 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
:
␃WPNCODE0␃
The 22 generators of the invariant ring under the wreath product (including player swap) are computed by the same method. The action on has three generators: row flip, column flip, and the player swap sending , , (derived from ).
game_invariants/generators_2x2_mz.py
:
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]})")
Syzygies are computed by exact symbolic expansion. For each target degree , we enumerate all products of generators of total degree , expand each as a polynomial in , collect monomial coefficients into an integer matrix , and compute the null space of over using SymPy. Each null vector is a syzygy.
game_invariants/syzygies_exact.py
:
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)}')
Molien series for -games under the wreath product are computed via conjugacy classes parameterized by bipartitions, using Newton’s identity to recover the degree- coefficient from fixed-point counts of .
game_invariants/scaling.py
:
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)})")
For the strategy-only group (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 : an explicit Molien average over group elements, the closed form obtained from collapsing the average, and the cleaner triple-count from Proposition 5.
game_invariants/degree3_mz_strategy_only.py
:
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}")
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
:
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')
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 .
The recovery of the 144 Robinson-Goforth types from invariant sign conditions is verified by exhaustive enumeration of all strict-ordinal type pairs, grouped by orbit.
game_invariants/rg_from_invariants.py
:
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
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)")
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:
import numpy as np
from itertools import permutations
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
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]}")
For a -game , the two-player full-support indifference determinant is where are the indifference matrices padded with a normalization row/column. The script verifies -invariance and the proven degree (Proposition 6) for .
game_invariants/verify_ne_discriminant.py
:
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)
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}")
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 -invariant.
game_invariants/ne_disc_3_2_solve.py
:
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 -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
:
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}")
A -game is solvable by iterated strict dominance if and only if at least one player has a strictly dominant strategy, equivalently or in mean-zero coordinates. Verified on 100,000 random games against a brute-force iterated-dominance solver.
game_invariants/verify_solvability.py
:
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'})")
The following scripts compute invariants under the wreath product (including player swap). They are used for Appendix C and for the scaling law computations.
game_invariants/game_classes.py
: game class subvarietiesgame_invariants/potential_subvariety.py
: potential gamesgame_invariants/separation.py
, game_invariants/separating_2x2.py
: orbit separationgame_invariants/br_type_invariants.py
: best-response typesgame_invariants/selection.py
, game_invariants/cycles.py
: adversarial difficultygame_invariants/hodge.py
, game_invariants/hodge_invariants.py
: Hodge decompositiongame_invariants/cohen_macaulay.py
: Cohen-Macaulay structuregame_invariants/syzygies.py
, game_invariants/syzygies_3x3_mz.py
: wreath product syzygiesgame_invariants/scaling.py
, game_invariants/stabilization.py
: scaling lawsAll scripts are in demonstrandom-public-code/invariants/game_invariants/
. Each has a __main__
block and can be run directly with python scriptname.py
.
Newton’s-identity Molien-coefficient computation over conjugacy classes of acting on the 78-dim mean-zero subspace. Output verifies from the paper.
game_invariants/molien_3x3_strategy_only.py
:
from fractions import Fraction
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 = [None] + [
3 * fp_pow(c1, k) * fp_pow(c2, k) * fp_pow(c3, k) - 3
for k in range(1, max_deg + 1)
]
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()
ANOVA-style decomposition: given a payoff tensor, projects to mean-zero, then extracts the 7 contrast blocks for . Computes family matrices . Self-test verifies orthogonality and reconstruction.
game_invariants/contrast_blocks_3x3.py
:
from itertools import combinations
import numpy as np
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
def _self_test():
rng = np.random.default_rng(42)
print("Self-test: contrast-block decomposition for (3,3)-games")
print("=" * 70)
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}"
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
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
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():
block = project_contrast_block(u0[0], S)
block_flat = block.reshape(-1)
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
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()}")
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()
game_invariants/generators_3x3_strategy_only.py
:
from itertools import combinations, combinations_with_replacement, product as iproduct
import numpy as np
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():
B = np.zeros((81, 78))
col = 0
for p in range(3):
sub = np.zeros((27, 27))
sub[0, :] = 1.0 / np.sqrt(27) # the constant direction
rng = np.random.default_rng(p)
Q, _ = np.linalg.qr(np.column_stack([sub[0, :], rng.standard_normal((27, 26))]))
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):
P = np.zeros((81, 81))
P[perm, np.arange(81)] = 1.0
rhos[g] = B.T @ P @ B
return rhos
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 = 600
rng = np.random.default_rng(0)
pts = rng.standard_normal((N, 78))
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)
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)
rank = 0
basis = np.zeros((N, 0))
tol = 1e-8
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):
reynolds_buf[:, j] = (orbits[:, :, a] * orbits[:, :, b] *
orbits[:, :, c]).mean(axis=1)
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
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)
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 = {}
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))
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))
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))
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))
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
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()
Character-formula enumeration: iterates over the 1771 unordered block triples, computes the invariant dim of each via tensor-product / Sym / Sym traces of $W_3 = $ standard rep of , and verifies the total is 556. Confirms the block-partition decomposition.
game_invariants/enumerate_3x3_generators.py
:
from collections import Counter
from itertools import combinations_with_replacement
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}"]
S3_CLASS_DATA = [
(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)
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
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)
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}")
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()
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()
Encodes 13 named -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
:
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
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:
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):
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
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,
}
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 = {}
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
record["degree3_diagnostics"] = diagnostic_degree3(u)
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}",
])
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}")
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()
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
:
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"])
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}"]
)
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]
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")
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}")
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.")
print()
print("=" * 78)
print("Minimal classifying subset (greedy backward elimination)")
print("=" * 78)
features = build_features(atlas)
all_keys = sorted(next(iter(features.values())).keys())
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)
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}")
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()
Constructs the 93-feature candidate separating set (42 degree-2 + 51 degree-3), verifies -invariance and generic orbit separation on random samples plus orbit-mates.
game_invariants/orbit_separation_3x3.py
:
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 = []
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])))
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)))
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]
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)
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)
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"):
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
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)
for eps in (0.01, 0.1):
samples.append(u + eps * rng.standard_normal((3, 3, 3, 3)))
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)
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)]
n = sub.shape[0]
for i in range(n - 1):
diffs = np.max(np.abs(sub[i + 1:] - sub[i]), axis=1)
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
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)
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()
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()
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()
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()
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()
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
:
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
def compute_subalgebra_hilbert(max_degree=6, N_points=800, tol=1e-6, verbose=True):
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)
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 d in range(1, max_degree + 1):
mono_evals = []
for k in range(1, d // 2 + 1): # min monomial length is d/d=1, max d/2
pass
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
def _gen_random(rng):
return rng.standard_normal((3, 3, 3, 3))
def _gen_symmetric_payoff(rng):
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
def main():
print("(3a) Stronger separation verification for the 93-invariant fingerprint")
print("=" * 78)
print()
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()
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()
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
:
"""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()
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!
5/17/2026: Initial version
5/18/2026: Added ANOVA-coincidence footnote at the contrast-block decomposition.
Each player assigns a distinct rank to the nine strategy profiles, giving labeled games. Dividing by the relabeling group of order gives .↩︎
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 , with players distinguishable. If player swaps are also identified, the acting group is the wreath product , 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 (we omit normalization for brevity). This is the cosine similarity of the two players’ payoff perturbations, and we might think of 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, 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.↩︎
The resulting decomposition into main effects, two-way interactions, and higher-order interactions is identical (in terms of linear algebra) to the ANOVA decomposition of a factorial design. The intuition is not quite the same. Here we need a decomposition of the payoff space that is equivariant under strategy relabeling, and the tensor product of irreducible -representations provides one. The coincidence reflects the fact that both constructions decompose using the same -invariant splitting .↩︎
It is not strictly necessary to construct an explicit separating subset of size near , 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).↩︎