Invariant Coordinates for Normal-Form Games Modulo Strategy Relabeling

Researchers have identified 17 invariant coordinates for normal-form games under strategy relabeling, consisting of nine degree-2 and eight degree-3 polynomial generators. The discovery provides a complete algebraic description of game payoffs modulo row and column permutations, enabling systematic analysis of game symmetries. This invariant coordinate system allows researchers to classify and compare games independent of player labeling, with applications in game theory and evolutionary dynamics.

python 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 https://demonstrandom.com/contact.html 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 https://demonstrandom.com/game theory/posts/canonical games/index.html . 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 : python 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 : python 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 : python 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 : php 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 : python 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 : python import numpy as np from itertools import permutations def mean zero a1, a2, a3, a4, b1, b2, b3, b4 : rA = a1 + a2 - a3 - a4 cA = a1 - a2 + a3 - a4 dA = a1 - a2 - a3 + a4 rB = b1 + b2 - b3 - b4 cB = b1 - b2 + b3 - b4 dB = b1 - b2 - b3 + b4 return rA, cA, dA, rB, cB, dB def eval generators rA, cA, dA, rB, cB, dB : deg2 = rA 2, rA rB, cA 2, cA cB, dA 2, dA dB, rB 2, cB 2, dB 2 deg3 = cA dA rA, cA dB rA, cB dA rA, cB dB rA, cA dA rB, cA dB rB, cB dA rB, cB dB rB return deg2 + deg3 def ordinal type payoffs : """Strict ordinal ranking as a tuple, or None if there is a tie.""" sorted idx = sorted range len payoffs , key=lambda i: payoffs i for i in range len payoffs - 1 : if payoffs sorted idx i == payoffs sorted idx i + 1 : return None ranks = 0 len payoffs for rank, idx in enumerate sorted idx : ranks idx = rank return tuple ranks def rg type a, b : """Canonical R-G type: ordinal-pair orbit under S 2 x S 2.""" ot a, ot b = ordinal type a , ordinal type b if ot a is None or ot b is None: return None S 2 x S 2 acts on 2x2 entries by row swap and column swap e = 0, 1, 2, 3 ; s1 = 2, 3, 0, 1 ; s2 = 1, 0, 3, 2 ; s12 = 3, 2, 1, 0 orbit = { tuple ot a g i for i in range 4 , tuple ot b g i for i in range 4 for g in e, s1, s2, s12 } return min orbit def sign x, tol=1e-10 : return 1 if x tol else -1 if x < -tol else 0 def enumerate rg types : """One game per R-G type, payoffs in {1, 2, 3, 4}.""" rg map = {} for pa in permutations range 4 : for pb in permutations range 4 : a = tuple float pa i + 1 for i in range 4 b = tuple float pb i + 1 for i in range 4 rgt = rg type a, b if rgt is not None and rgt not in rg map: rg map rgt = a, b return rg map if name == ' main ': rg map = enumerate rg types print f"R-G types enumerated: {len rg map } expect 144 " Signs of 17 generators + 9 magnitude comparisons pat to rg = {} collisions = 0 for rgt, a, b in rg map.items : gens = eval generators mean zero a, b signs = tuple sign g for g in gens comps = sign gens 0 - gens 2 , sign gens 0 - gens 4 , sign gens 2 - gens 4 , sign gens 6 - gens 7 , sign gens 6 - gens 8 , sign gens 7 - gens 8 , sign gens 0 - gens 6 , sign gens 2 - gens 7 , sign gens 4 - gens 8 , pat = signs + comps if pat in pat to rg and pat to rg pat = rgt: collisions += 1 else: pat to rg pat = rgt print f"Signs + comparisons: {len pat to rg } patterns, {collisions} collisions" if collisions == 0 and len pat to rg == 144: print "VERIFIED: 17-generator signs + 9 comparisons exactly recover 144 R-G types" game invariants/rg minimal.py greedily removes features from the 26-element list 17 signs + 9 comparisons and tests separation power, recording the minimum subset that still distinguishes all 144 types: python import numpy as np from itertools import permutations Reuses mean zero, eval generators, ordinal type, rg type, sign, enumerate rg types from D.6. def test features rg map, indices, all features : pat to rg = {} for rgt, feats in all features.items : pat = tuple feats i for i in indices if pat in pat to rg and pat to rg pat = rgt: return False pat to rg pat = rgt return len pat to rg == len rg map if name == ' main ': rg map = enumerate rg types FEAT NAMES = 'rA2', 'rArB', 'cA2', 'cAcB', 'dA2', 'dAdB', 'rB2', 'cB2', 'dB2', 'cAdArA', 'cAdBrA', 'cBdArA', 'cBdBrA', 'cAdArB', 'cAdBrB', 'cBdArB', 'cBdBrB', 'rA2-cA2', 'rA2-dA2', 'cA2-dA2', 'rB2-cB2', 'rB2-dB2', 'cB2-dB2', 'rA2-rB2', 'cA2-cB2', 'dA2-dB2', all features = {} for rgt, a, b in rg map.items : gens = eval generators mean zero a, b feats = sign g for g in gens feats += sign gens 0 - gens 2 , sign gens 0 - gens 4 , sign gens 2 - gens 4 , sign gens 6 - gens 7 , sign gens 6 - gens 8 , sign gens 7 - gens 8 , sign gens 0 - gens 6 , sign gens 2 - gens 7 , sign gens 4 - gens 8 all features rgt = feats Greedy backward elimination current = set range len FEAT NAMES for i in reversed range len FEAT NAMES : trial = sorted current - {i} if test features rg map, trial, all features : current = set trial print f"Minimal separating set: {len current } features" for i in sorted current : print f" {i}: {FEAT NAMES i }" 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 : python import numpy as np from itertools import permutations def ne discriminant A, B : k = A.shape 0 M A = np.zeros k, k for i in range k - 1 : M A i, : = A 0, : - A i + 1, : M A k - 1, : = 1.0 M B = np.zeros k, k for j in range k - 1 : M B :, j = B :, 0 - B :, j + 1 M B :, k - 1 = 1.0 return np.linalg.det M A np.linalg.det M B def apply group element A, B, sigma1, sigma2 : k = A.shape 0 P1 = np.zeros k, k ; P2 = np.zeros k, k for i in range k : P1 i, sigma1 i = 1.0 P2 i, sigma2 i = 1.0 return P1 @ A @ P2.T, P1 @ B @ P2.T if name == ' main ': rng = np.random.default rng 42 G-invariance at k = 3 group = list permutations range 3 max err = 0 for in range 1000 : A = rng.standard normal 3, 3 ; B = rng.standard normal 3, 3 d0 = ne discriminant A, B for s1 in group: for s2 in group: A2, B2 = apply group element A, B, s1, s2 max err = max max err, abs d0 - ne discriminant A2, B2 print f"k=3: max invariance error = {max err:.2e}" Degree by scaling for k in 2, 3, 4, 5 : A = rng.standard normal k, k ; B = rng.standard normal k, k d1 = ne discriminant A, B d2 = ne discriminant 2 A, 2 B if abs d1 1e-10: ratio = d2 / d1 print f"k={k}: disc 2 game /disc game = {ratio:.1f} expect 2^{2 k-1 } = {2 2 k-1 } " For three-player binary games, the indifference system reduces by elimination to a quadratic in one mixing weight; its discriminant is a degree-6 polynomial in the payoff entries, verified -invariant. game invariants/ne disc 3 2 solve.py : python 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 : python 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 : python 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 subvarieties game invariants/potential subvariety.py : potential games game invariants/separation.py , game invariants/separating 2x2.py : orbit separation game invariants/br type invariants.py : best-response types game invariants/selection.py , game invariants/cycles.py : adversarial difficulty game invariants/hodge.py , game invariants/hodge invariants.py : Hodge decomposition game invariants/cohen macaulay.py : Cohen-Macaulay structure game invariants/syzygies.py , game invariants/syzygies 3x3 mz.py : wreath product syzygies game invariants/scaling.py , game invariants/stabilization.py : scaling 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 : python from fractions import Fraction S 3 conjugacy classes: label, class size . S3 CLASSES = 'id', 1 , 'tau', 3 , 'gamma', 2 def fp pow cls label: str, k: int - int: """Fixed points of sigma^k where sigma is in the named S 3 class.""" if cls label == 'id': return 3 if cls label == 'tau': return 3 if k % 2 == 0 else 1 if cls label == 'gamma': return 3 if k % 3 == 0 else 0 raise ValueError cls label def molien 33 strategy only max deg: int - list: G order = 216 h total = Fraction 0 max deg + 1 for c1, s1 in S3 CLASSES: for c2, s2 in S3 CLASSES: for c3, s3 in S3 CLASSES: class size = s1 s2 s3 chi mz g^k = chi full g^k - 3 chi mz = None + 3 fp pow c1, k fp pow c2, k fp pow c3, k - 3 for k in range 1, max deg + 1 Newton's identity: d h d^g = sum {k=1..d} chi mz g^k h {d-k}^g hg = Fraction 0 max deg + 1 hg 0 = Fraction 1 for d in range 1, max deg + 1 : s = sum chi mz k hg d - k for k in range 1, d + 1 hg d = Fraction s, d for d in range max deg + 1 : h total d += class size hg d result = for d in range max deg + 1 : val = h total d / G order assert val.denominator == 1, f"non-integer h {d}: {val}" result.append val.numerator return result def main : print "Molien coefficients for 3,3 -games under S 3 ^3 on mean-zero subspace" print "=" 78 h = molien 33 strategy only max deg=4 for d, hd in enumerate h : print f" h {d} = {hd}" expected = 1, 0, 42, 556, 9057 print print f"Expected from paper: {expected}" print f"Match: {h == expected}" assert h == expected, f"Mismatch: got {h}, expected {expected}" print "VERIFIED." if name == ' main ': main 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 : python from itertools import combinations import numpy as np Indexing convention: strategy-coordinate axes are 0, 1, 2. Subsets S are passed as tuples of axis indices, e.g. 0, , 0,1 , 0,1,2 . def mean zero payoff u : """Subtract per-player mean from a 3, 3, 3, 3 payoff tensor.""" u = np.asarray u, dtype=float assert u.shape == 3, 3, 3, 3 , f"expected shape 3,3,3,3 , got {u.shape}" means = u.mean axis= 1, 2, 3 , keepdims=True return u - means def project contrast block u p, S : v = np.asarray u p, dtype=float .copy assert v.shape == 3, 3, 3 S = set S for axis in range 3 : mean = v.mean axis=axis, keepdims=True if axis in S: v = v - mean else: v = np.broadcast to mean, v.shape .copy return v def all contrast blocks u p : """All 7 contrast blocks for one player. Returns dict S - tensor.""" blocks = {} for r in range 1, 4 : for S in combinations 0, 1, 2 , r : blocks S = project contrast block u p, S return blocks def family matrix u, S : u0 = mean zero payoff u blocks = project contrast block u0 p , S for p in range 3 M = np.zeros 3, 3 for p in range 3 : for q in range 3 : M p, q = float np.sum blocks p blocks q return M def all family matrices u : """All 7 family matrices, keyed by tuple-of-axis-indices S.""" result = {} for r in range 1, 4 : for S in combinations 0, 1, 2 , r : result S = family matrix u, S return result --------------------------------------------------------------------------- Self-test --------------------------------------------------------------------------- def self test : rng = np.random.default rng 42 print "Self-test: contrast-block decomposition for 3,3 -games" print "=" 70 1 Random payoff tensor, project to mean-zero, sum of all 7 blocks should recover the mean-zero tensor for each player. u = rng.standard normal 3, 3, 3, 3 u0 = mean zero payoff u for p in range 3 : blocks = all contrast blocks u0 p reconstruction = sum blocks S for S in blocks err = np.max np.abs reconstruction - u0 p print f" player {p}: max |reconstructed - mean-zero| = {err:.2e}" assert err < 1e-12, f"block decomposition failed to reconstruct player {p}" 2 Orthogonality: <T {S, p}, T {S', q} Frobenius = 0 for S = S'. p, q = 0, 1 blocks p = all contrast blocks u0 p blocks q = all contrast blocks u0 q max cross = 0.0 for S in blocks p: for Sp in blocks q: if S == Sp: continue ip = float np.sum blocks p S blocks q Sp max cross = max max cross, abs ip print f" max cross-family inner product S = S' : {max cross:.2e}" assert max cross < 1e-12 3 Family matrices count: 7 families, 6 unordered player pairs each = 42. family mats = all family matrices u n families = len family mats n pairs = 3 3 + 1 // 2 6 unordered player pairs print f" families: {n families}, player-pairs per family: {n pairs}, " f"total degree-2 entries: {n families n pairs}" assert n families n pairs == 42 4 Effective dimension: 26 independent components per player. Main effect: 2 indep per coord, 3 coords - 6 2-way interaction: 4 indep per pair 3x3 with row/col sums zero , 3 pairs - 12 3-way interaction: 8 indep 3x3x3 with all marginals zero - 8 Total: 26 per player; 78 across 3 players. expected dims = { 0, : 2, 1, : 2, 2, : 2, 0, 1 : 4, 0, 2 : 4, 1, 2 : 4, 0, 1, 2 : 8} total = 0 for S, expected in expected dims.items : Number of independent entries: count nonzero singular values block = project contrast block u0 0 , S block flat = block.reshape -1 The block has at most expected components in a structured basis; the matrix of all 27 component evaluations across many random points would have rank equal to expected dim. Here we verify via the orbit-summed family matrix's rank consistency. total += expected print f" expected total per-player independent components: {total}" assert total == 26 print f" expected total mean-zero dimension across 3 players: {total 3}" assert total 3 == 78 5 Quick verification on a specific game: 3-player pure coordination. u p s, s, s = 1; else 0. Should have M { 0,1,2 } entries dominated by the three-way interaction. u coord = np.zeros 3, 3, 3, 3 for p in range 3 : for s in range 3 : u coord p, s, s, s = 1.0 M3 = family matrix u coord, 0, 1, 2 print f"\n 3-player pure coordination M {{1,2,3}} family matrix:" print f" {M3.tolist }" All three players are symmetric and aligned, so M3 should have all diagonal entries equal and all off-diagonal entries positive coordination-type per Appendix B's degree-2 conditions . diag = np.diag M3 offdiag = M3 ~np.eye 3, dtype=bool .reshape 3, 2 print f" diagonal: {diag.tolist }, off-diag entries: {offdiag.tolist }" assert np.allclose diag, diag 0 , "diagonal entries should be equal" assert np.all M3 ~np.eye 3, dtype=bool 0 , "off-diag should be positive" print " coordination-type confirmed all off-diag 0 " print "\nALL CHECKS PASSED." if name == ' main ': self test game invariants/generators 3x3 strategy only.py : python from itertools import combinations, combinations with replacement, product as iproduct import numpy as np --------------------------------------------------------------------------- Group action: S 3 ^3 on the 78-dim mean-zero subspace --------------------------------------------------------------------------- def all s3 perms : """6 permutations of {0,1,2} as 3-tuples.""" from itertools import permutations return list permutations 0, 1, 2 def flatten index p, s1, s2, s3 : """Map player, strategy profile to flat index in {0,...,80}.""" return p 27 + s1 9 + s2 3 + s3 def build group permutations : s3 = all s3 perms perms = for sigma1 in s3: for sigma2 in s3: for sigma3 in s3: perm = np.empty 81, dtype=np.int64 for p in range 3 : for s1 in range 3 : for s2 in range 3 : for s3i in range 3 : src = flatten index p, s1, s2, s3i dst = flatten index p, sigma1 s1 , sigma2 s2 , sigma3 s3i perm dst = src perms.append perm return np.array perms shape 216, 81 def mean zero basis : For each player p, build a 26-dim orthonormal basis of mean-zero functions on the 27 strategy profiles. B = np.zeros 81, 78 col = 0 for p in range 3 : 27 coords for player p; need orthonormal basis of the 26-dim mean-zero subspace. sub = np.zeros 27, 27 sub 0, : = 1.0 / np.sqrt 27 the constant direction Build remaining basis by Gram-Schmidt on random vectors rng = np.random.default rng p Q, = np.linalg.qr np.column stack sub 0, : , rng.standard normal 27, 26 Q's first column is the constant; remaining 26 are mean-zero for j in range 1, 27 : B p 27 + np.arange 27 , col = Q :, j col += 1 assert col == 78 return B def build group action on mean zero B, perms 81 : rhos = np.zeros 216, 78, 78 for g, perm in enumerate perms 81 : In R^81, the action sends e i - e {perm i }, i.e., column i of P is e {perm i } P = np.zeros 81, 81 P perm, np.arange 81 = 1.0 rhos g = B.T @ P @ B return rhos --------------------------------------------------------------------------- Reynolds projection and rank verification --------------------------------------------------------------------------- def verify degree3 count verbose=True : if verbose: print "Building group action on mean-zero subspace ...", flush=True perms 81 = build group permutations B = mean zero basis rhos = build group action on mean zero B, perms 81 if verbose: print f" built {rhos.shape 0 } orthogonal matrices of shape {rhos.shape 1: }", flush=True N random points in V^0; need N 556 for full rank. N = 600 rng = np.random.default rng 0 pts = rng.standard normal N, 78 For each random point u, precompute u g = rho g @ u for all g. Shape: N, 216, 78 . Memory ~ 60 MB. if verbose: print "Precomputing group orbits at random points ...", flush=True orbits = np.einsum 'gij,nj- ngi', rhos, pts if verbose: print f" orbits shape: {orbits.shape}", flush=True Enumerate degree-3 monomials x a x b x c with a <= b <= c. coords = np.arange 78 triples = list combinations with replacement coords, 3 n triples = len triples if verbose: print f" total degree-3 monomials: {n triples}", flush=True Maintain a running orthonormal basis of the invariant span. rank = 0 basis = np.zeros N, 0 tol = 1e-8 Process in micro-batches to fold rank-test cost without blowing memory. For each batch: compute Reynolds value length-N vector for each monomial one at a time cheap: 1 advanced-index slice + product + mean over axis 1 . micro batch = 256 reynolds buf = np.empty N, micro batch for batch start in range 0, n triples, micro batch : batch end = min batch start + micro batch, n triples batch = triples batch start:batch end m = len batch for j, a, b, c in enumerate batch : orbits :, :, a/b/c is N, 216 ; elementwise product then mean reynolds buf :, j = orbits :, :, a orbits :, :, b orbits :, :, c .mean axis=1 Project the batch onto orthogonal complement of basis and add new dirs sub = reynolds buf :, :m if rank 0: coeffs = basis.T @ sub residual = sub - basis @ coeffs else: residual = sub norms = np.linalg.norm residual, axis=0 significant = norms tol if significant.any : R = residual :, significant U, S, = np.linalg.svd R, full matrices=False new dirs = U :, S tol if new dirs.shape 1 0: basis = np.concatenate basis, new dirs , axis=1 rank = basis.shape 1 if verbose and batch start // micro batch % 10 == 0: print f" processed {batch end}/{n triples}, running rank = {rank}", flush=True if rank = 556: if verbose: print f" rank reached 556 after {batch end} monomials; halting early", flush=True break print f"\nFinal rank: {rank} expected 556 ", flush=True assert rank == 556, f"rank = {rank}, expected 556" return rank --------------------------------------------------------------------------- Named diagnostic degree-3 invariants for the atlas --------------------------------------------------------------------------- def project block local basis u p, S : from contrast blocks 3x3 import project contrast block full = project contrast block u p, S shape 3, 3, 3 Reduce out the non-S axes by taking the value at index 0 sl = slice None 3 for axis in range 3 : if axis not in S: sl axis = 0 block is constant along non-S axes return full tuple sl def diagnostic degree3 u : from contrast blocks 3x3 import mean zero payoff, project contrast block, family matrix u0 = mean zero payoff u out = {} 1 Main-effect power-sum cubics p 3 T {S,p} for each main-effect type S and each player p. For k=3 mean-zero vectors v in W 3, p 3 v = sum v i^3. There are 3 main-effect types 3 players = 9 such invariants. for axis in 0, 1, 2 : S = axis, for p in range 3 : T = project block local basis u0 p , S shape 3, out f"p3 main S{axis} p{p}" = float np.sum T 3 2 Cross-player main-effect cubics: sum a T {S,p}^a T {S,q}^a T {S,r}^a for unordered p, q, r . There are 3 types 10 unordered triples = 30. We expose a handful: the fully symmetric one tr T {S,1} T {S,2} T {S,3} for each S. for axis in 0, 1, 2 : S = axis, T1 = project block local basis u0 0 , S T2 = project block local basis u0 1 , S T3 = project block local basis u0 2 , S out f"crossplayer main S{axis} 123" = float np.sum T1 T2 T3 3 det M {1,2,3} : cubic in the three-way interaction family matrix. M123 = family matrix u, 0, 1, 2 out "det M three way" = float np.linalg.det M123 out "tr M three way cubed" = float np.trace M123 @ M123 @ M123 4 Three-way interaction tensor traces: sum {a,b,c} D p a,b,c D q a,b,c D r a,b,c where D p = T {{1,2,3}, p}. This is the natural cubic on the three-way blocks. D1 = project block local basis u0 0 , 0, 1, 2 D2 = project block local basis u0 1 , 0, 1, 2 D3 = project block local basis u0 2 , 0, 1, 2 out "threeway cubic 123" = float np.sum D1 D2 D3 5 Pairwise-interaction "det" contribution: for each pair {i,j} \subset {0,1,2}, the pair-interaction block T {{i,j}, p} is a 3x3 matrix in coords i,j. Its determinant is an S 3 ^2-invariant cubic. Sum over player p. for pair in combinations 0, 1, 2 , 2 : for p in range 3 : T = project block local basis u0 p , pair shape 3, 3 out f"det pair S{pair 0 }{pair 1 } p{p}" = float np.linalg.det T return out --------------------------------------------------------------------------- Main --------------------------------------------------------------------------- def main : from contrast blocks 3x3 import all family matrices print "Generators for 3,3 -games under S 3 ^3 strategy-only " print "=" 70 print "\nDegree 2: 42 family-matrix entries analytical, from contrast blocks " print f" 7 contrast families x 6 unordered player pairs = 42 generators" print f" matches h 2 = 42 from molien 3x3 strategy only" print "\nDiagnostic degree-3 invariants for the atlas :" rng = np.random.default rng 7 u random = rng.standard normal 3, 3, 3, 3 diag = diagnostic degree3 u random for name, val in diag.items : print f" {name:40s} = {val:+.4f}" print f" total diagnostics: {len diag } " print "\nDegree 3: numerical rank verification target 556 ..." rank = verify degree3 count print f"\nVERIFIED: degree-3 Reynolds invariants span a {rank}-dim subspace." if name == ' main ': main 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 : python from collections import Counter from itertools import combinations with replacement --------------------------------------------------------------------------- Setup --------------------------------------------------------------------------- 7 contrast types for 3,3 -games. Using 0-indexed axes. TYPES = 0, , 1, , 2, , 3 main effects |S| = 1 0, 1 , 0, 2 , 1, 2 , 3 pairwise interactions |S| = 2 0, 1, 2 , 1 three-way interaction |S| = 3 TYPE LABELS = "{1}", "{2}", "{3}", "{1,2}", "{1,3}", "{2,3}", "{1,2,3}" Character of W 3 = standard 2-dim rep of S 3, evaluated on conjugacy classes: id size 1 : tr g | W 3 = 2, tr g^2 | W 3 = 2, tr g^3 | W 3 = 2 transpositions 3 : tr g | W 3 = 0, tr g^2 | W 3 = 2, tr g^3 | W 3 = 0 3-cycles 2 : tr g | W 3 = -1, tr g^2 | W 3 = -1, tr g^3 | W 3 = 2 S3 CLASS DATA = size, chi g , chi g^2 , chi g^3 1, 2, 2, 2 , 3, 0, 2, 0 , 2, -1, -1, 2 , def axis count types, axis : """How many of the given types contain the given axis.""" return sum 1 for S in types if axis in S --------------------------------------------------------------------------- Invariant dimension formulas via character theory --------------------------------------------------------------------------- def inv dim tensor c : if c == 0: return 1 total = sum sz chi g c for sz, chi g, , in S3 CLASS DATA assert total % 6 == 0 return total // 6 def inv dim sym2 c : if c == 0: return 1 total = 0 for sz, chi g, chi g2, in S3 CLASS DATA: total += sz chi g 2 c + chi g2 c assert total % 2 6 == 0 return total // 2 6 def inv dim sym3 c : if c == 0: return 1 total = 0 for sz, chi g, chi g2, chi g3 in S3 CLASS DATA: total += sz chi g 3 c + 3 chi g c chi g2 c + 2 chi g3 c assert total % 6 6 == 0 return total // 6 6 def inv dim tensor two factors c a, c b : return inv dim tensor c a + c b def inv dim sym2 with third c rep, c other : total = 0 for sz, chi g, chi g2, in S3 CLASS DATA: v a chi = chi g c rep v a chi g2 = chi g2 c rep sym2 chi = v a chi v a chi + v a chi g2 // 2 if v a chi v a chi + v a chi g2 % 2 == 0 else None Handle the half by keeping it as rational sym2 chi num = v a chi 2 + v a chi g2 v b chi = chi g c other total += sz sym2 chi num v b chi assert total % 2 6 == 0 return total // 2 6 --------------------------------------------------------------------------- Per-block-triple invariant dim --------------------------------------------------------------------------- def block triple invariant dim triple of blocks : cnt = Counter triple of blocks sizes = sorted cnt.values , reverse=True shape = tuple sizes if shape == 1, 1, 1 : types in triple = TYPES t for t, in triple of blocks per axis = for axis in range 3 : c = axis count types in triple, axis per axis.append inv dim tensor c return per axis 0 per axis 1 per axis 2 , shape elif shape == 2, 1 : rep block = next b for b, c in cnt.items if c == 2 other block = next b for b, c in cnt.items if c == 1 rep type = TYPES rep block 0 other type = TYPES other block 0 per axis = for axis in range 3 : c rep = 1 if axis in rep type else 0 c other = 1 if axis in other type else 0 per axis.append inv dim sym2 with third c rep, c other return per axis 0 per axis 1 per axis 2 , shape elif shape == 3, : rep type = TYPES triple of blocks 0 0 per axis = for axis in range 3 : c = 1 if axis in rep type else 0 per axis.append inv dim sym3 c return per axis 0 per axis 1 per axis 2 , shape else: raise ValueError f"unknown partition shape {shape}" --------------------------------------------------------------------------- Enumeration --------------------------------------------------------------------------- def enumerate block triples : blocks = t, p for t in range 7 for p in range 3 21 blocks for triple in combinations with replacement blocks, 3 : types in triple = TYPES t for t, in triple inv dim, shape = block triple invariant dim triple yield triple, types in triple, shape, inv dim def main : print "Enumeration of degree-3 generators for R V^0 ^{ S 3 ^3}" print "=" 78 print total = 0 by type combo = {} by shape = Counter total block triples = 0 triples with invariants = 0 for triple, types in triple, shape, inv dim in enumerate block triples : total block triples += 1 if inv dim 0: triples with invariants += 1 total += inv dim type combo = tuple sorted t for t, in triple by type combo.setdefault type combo, {"total": 0, "n triples": 0, "shapes": Counter } by type combo type combo "total" += inv dim by type combo type combo "n triples" += 1 by type combo type combo "shapes" shape += 1 by shape shape += inv dim print f"Total block triples enumerated: {total block triples}" print f" expected: C 21+2, 3 = { 21 22 23 // 6} " print f"Triples with at least one invariant: {triples with invariants}" print f"Total degree-3 invariant dim: {total}" print f" expected from Molien: 556 " if total = 556: print f" MISMATCH: enumeration gives {total}, not 556 " else: print f" VERIFIED." print print "Contribution by partition shape over blocks :" for shape, cnt in by shape.most common : shape str = "all-distinct 1,1,1 " if shape == 1,1,1 else \ "one-repeated 2,1 " if shape == 2,1 else \ "all-same 3 " if shape == 3, else str shape print f" {shape str}: {cnt}" print print "=" 78 print "Per type-combo breakdown" print "=" 78 print print f"{'Type combo':<40s} {'block triples': 14s} {'inv dim': 10s}" print "-" 78 sorted combos = sorted by type combo.items , key=lambda kv: -kv 1 "total" cumulative = 0 for type combo, info in sorted combos: labels = TYPE LABELS t for t in type combo label str = " . ".join labels print f"{label str:<40s} {info 'n triples' : 14d} {info 'total' : 10d}" cumulative += info "total" print "-" 78 print f"{'TOTAL':<40s} {total block triples: 14d} {cumulative: 10d}" print Spotlight: the largest contributors print "Top 10 type combos by contribution:" for type combo, info in sorted combos :10 : labels = TYPE LABELS t for t in type combo shapes str = ", ".join f"{s}:{c}" for s, c in info "shapes" .items print f" {' . '.join labels :<35s} - {info 'total' : 4d} shapes: {shapes str} " if name == " main ": main 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 : python import json from itertools import product as iproduct import numpy as np from contrast blocks 3x3 import all family matrices, mean zero payoff from generators 3x3 strategy only import diagnostic degree3 --------------------------------------------------------------------------- Named 3,3 games --------------------------------------------------------------------------- def zeros : return np.zeros 3, 3, 3, 3 , dtype=float def rps 3player : u = zeros for p in range 3 : for s1 in range 3 : for s2 in range 3 : for s3 in range 3 : profile = s1, s2, s3 my s = profile p payoff = 0 for q in range 3 : if q == p: continue opp s = profile q diff = my s - opp s % 3 if diff == 1: payoff += 1 my s beats opp s elif diff == 2: payoff -= 1 opp s beats my s u p, s1, s2, s3 = payoff return u def stag hunt 3player : u = zeros for p, s1, s2, s3 in iproduct range 3 , repeat=4 : profile = s1, s2, s3 my s = profile p if my s == 1: u p, s1, s2, s3 = 2.0 elif my s == 0: u p, s1, s2, s3 = 4.0 if profile == 0, 0, 0 else 0.0 else: my s == 2 u p, s1, s2, s3 = 5.0 if profile == 2, 2, 2 else 0.0 return u def public goods 3player : r = 1.5 return multiplier u = zeros for p, s1, s2, s3 in iproduct range 3 , repeat=4 : profile = s1, s2, s3 total = sum profile my cost = profile p u p, s1, s2, s3 = -my cost + r total / 3.0 return u def pure coordination 3player : u = zeros for s in range 3 : for p in range 3 : u p, s, s, s = 1.0 return u def volunteers dilemma 3player : c, b = 1.0, 3.0 u = zeros for p, s1, s2, s3 in iproduct range 3 , repeat=4 : profile = s1, s2, s3 my s = profile p someone volunteered = any profile q == 0 for q in range 3 payoff = b if someone volunteered else 0.0 if my s == 0: payoff -= c u p, s1, s2, s3 = payoff return u def battle of sexes 3player : u = zeros for s in range 3 : for p in range 3 : u p, s, s, s = 2.0 if p == s else 1.0 return u def commons 3player : cap = 2 u = zeros for p, s1, s2, s3 in iproduct range 3 , repeat=4 : total = s1 + s2 + s3 if total <= cap: u p, s1, s2, s3 = float s1, s2, s3 p else: u p, s1, s2, s3 = 0.0 return u def majority 3player : u = zeros for p, s1, s2, s3 in iproduct range 3 , repeat=4 : profile = s1, s2, s3 counts = profile.count s for s in range 3 my count = counts profile p max count = max counts if counts.count max count 1: tied: e.g., all distinct 1,1,1 or pair 2,1,0 ... actually if one strategy has 2 and another 1, max is unique. Tied only when all 3 strategies appear once each counts = 1,1,1 . u p, s1, s2, s3 = 0.0 else: u p, s1, s2, s3 = 1.0 if my count == max count else -1.0 return u def symmetric anticoord 3player : u = zeros for p, s1, s2, s3 in iproduct range 3 , repeat=4 : profile = s1, s2, s3 distinct = len set profile if distinct == 3: u p, s1, s2, s3 = 1.0 elif distinct == 1: u p, s1, s2, s3 = -1.0 else: u p, s1, s2, s3 = 0.0 return u def dictator 3player : base = np.array 3, 1, 0 , if player 0 plays 0: payoffs 3, 1, 0 0, 3, 1 , if player 0 plays 1: payoffs 0, 3, 1 1, 0, 3 , if player 0 plays 2: payoffs 1, 0, 3 , dtype=float u = zeros for p, s1, s2, s3 in iproduct range 3 , repeat=4 : u p, s1, s2, s3 = base s1, p s1 = player 0's strategy return u def chicken 3player : u = zeros for p, s1, s2, s3 in iproduct range 3 , repeat=4 : profile = s1, s2, s3 my s = profile p stayers = q for q in range 3 if profile q = 0 n stay = len stayers if my s == 0: swerve u p, s1, s2, s3 = 0.0 if n stay 0 else 1.0 else: stay if n stay == 1: u p, s1, s2, s3 = 4.0 sole stayer wins else: u p, s1, s2, s3 = -8.0 multiple stayers collide return u def matching pennies 3player : u = zeros for p, s1, s2, s3 in iproduct range 3 , repeat=4 : profile = s1, s2, s3 if p == 0: u p, s1, s2, s3 = 1.0 if profile 0 == profile 1 else -1.0 elif p == 1: u p, s1, s2, s3 = 1.0 if profile 1 == profile 2 else -1.0 else: p == 2 u p, s1, s2, s3 = -1.0 if profile 2 == profile 0 else 1.0 return u def common interest 3player : Phi = np.zeros 3, 3, 3 for s1, s2, s3 in iproduct range 3 , repeat=3 : Reward distinct-strategy profiles more distinct = len {s1, s2, s3} Phi s1, s2, s3 = float distinct + s1 + s2 + s3 0.5 u = zeros for p, s1, s2, s3 in iproduct range 3 , repeat=4 : u p, s1, s2, s3 = Phi s1, s2, s3 return u Registry of named games NAMED GAMES = { "3p Rock Paper Scissors": rps 3player, "3p Stag Hunt": stag hunt 3player, "3p Public Goods": public goods 3player, "3p Pure Coordination": pure coordination 3player, "3p Volunteers Dilemma": volunteers dilemma 3player, "3p Battle of Sexes": battle of sexes 3player, "3p Tragedy of Commons": commons 3player, "3p Majority": majority 3player, "3p Symmetric AntiCoord": symmetric anticoord 3player, "3p Asymmetric Dictator": dictator 3player, "3p Chicken": chicken 3player, "3p Matching Pennies": matching pennies 3player, "3p Common Interest": common interest 3player, } --------------------------------------------------------------------------- Evaluation --------------------------------------------------------------------------- def type label S : """Label a contrast type tuple axis indices by a 1-based subset string.""" return "{" + ",".join str i + 1 for i in S + "}" def evaluate game u : record = {} Family matrices fmats = all family matrices u family = {} for S, M in fmats.items : label = type label S family label = { "matrix": M.tolist , "trace": float np.trace M , "det": float np.linalg.det M , "rank numerical": int np.linalg.matrix rank M, tol=1e-10 , "diagonal": np.diag M .tolist , "offdiag sum": float np.sum M - np.trace M , "offdiag min": float np.min M ~np.eye 3, dtype=bool , "offdiag max": float np.max M ~np.eye 3, dtype=bool , } record "family matrices" = family Diagnostic degree-3 invariants record "degree3 diagnostics" = diagnostic degree3 u Coordination-type / potential-type / harmonic-type quick flags from M {1,2,3} M3 = fmats 0, 1, 2 offdiag 3 = M3 ~np.eye 3, dtype=bool record "flags" = { "M three way rank": int np.linalg.matrix rank M3, tol=1e-10 , "M three way all positive offdiag": bool np.all offdiag 3 1e-10 , "M three way all negative offdiag": bool np.all offdiag 3 < -1e-10 , "M three way trace": float np.trace M3 , "M three way det": float np.linalg.det M3 , "potential candidate": bool np.linalg.matrix rank M3, tol=1e-10 <= 1 and np.trace M3 1e-10 , "coordination type": bool np.all offdiag 3 1e-10 , } return record def format payoff tensor compact u : """Compact payoff tensor representation: list of s1,s2,s3 - u0,u1,u2 .""" rows = for s1, s2, s3 in iproduct range 3 , repeat=3 : rows.append { "profile": s1, s2, s3 , "payoffs": float u p, s1, s2, s3 for p in range 3 , } return rows def build atlas : """Evaluate all named games and assemble the atlas record.""" atlas = {} for name, builder in NAMED GAMES.items : print f" evaluating {name} ..." u = builder record = evaluate game u record "payoff tensor compact" = format payoff tensor compact u atlas name = record return atlas def write json atlas, path : """Write the full atlas as JSON.""" with open path, "w" as f: json.dump atlas, f, indent=2 def write markdown table atlas, path : """Write a condensed markdown table for the paper.""" header = "Game", "rank $M {1,2,3}$", "tr $M {1,2,3}$", "off-diag $M {1,2,3}$", "Flag", "tr $M {\\{1\\}}$", "tr $M {\\{1,2\\}}$", rows = for name, rec in atlas.items : flag parts = if rec "flags" "coordination type" : flag parts.append "coord" if rec "flags" "M three way all negative offdiag" : flag parts.append "anti-coord" if rec "flags" "potential candidate" : flag parts.append "potential?" if not flag parts: flag parts.append "mixed" flag = ", ".join flag parts M3 = rec "family matrices" "{1,2,3}" rank3 = M3 "rank numerical" tr3 = M3 "trace" offdiag summary = f"min={M3 'offdiag min' :+.2f}, max={M3 'offdiag max' :+.2f}" trM1 = rec "family matrices" "{1}" "trace" trM12 = rec "family matrices" "{1,2}" "trace" rows.append name.replace "3p ", "" .replace " ", " " , str rank3 , f"{tr3:+.3f}", offdiag summary, flag, f"{trM1:+.3f}", f"{trM12:+.3f}", Build markdown md lines = " Atlas of 3,3 -game invariant signatures", "", f"Generated by atlas 3x3.py . {len atlas } named games.", "", "| " + " | ".join header + " |", "|" + "|".join "---" len header + "|" for row in rows: md lines.append "| " + " | ".join row + " |" md lines.append "" md lines.append "Notes:" md lines.append "- rank $M S$ = numerical rank of the 3x3 family matrix for" md lines.append " contrast type $S$ 3 = full, 1 = potential candidate, etc. ." md lines.append "- Flag: coordination-type = all $M {1,2,3}$ off-diagonals positive;" md lines.append " anti-coord = all negative; potential? = rank-1 $M {1,2,3}$." md lines.append "- Full 42 degree-2 entries and 24 degree-3 diagnostics in " " atlas 3x3 results.json ." with open path, "w" as f: f.write "\n".join md lines def main : print f"Building atlas of {len NAMED GAMES } named 3,3 -games ..." atlas = build atlas json path = "atlas 3x3 results.json" md path = "atlas 3x3 table.md" write json atlas, json path write markdown table atlas, md path print f"\nWrote: {json path}" print f"Wrote: {md path}" Quick summary print "\nSummary of M {1,2,3} structure per game:" print f"{'Game':<35s} {'rank': 5s} {'trace': 10s} {'off-diag flag': 20s}" for name, rec in atlas.items : M3 = rec "family matrices" "{1,2,3}" rank3 = M3 "rank numerical" tr3 = M3 "trace" flags = rec "flags" flag = "coord" if flags "coordination type" else "anti-coord" if flags "M three way all negative offdiag" else "potential?" if flags "potential candidate" else "mixed" print f"{name:<35s} {rank3: 5d} {tr3: +10.3f} {flag: 20s}" if name == " main ": main 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 : python import json from itertools import combinations import numpy as np TOL = 1e-9 def sign3 x : """Three-valued sign: -1, 0, +1.""" if x TOL: return 1 if x < -TOL: return -1 return 0 def build features atlas : family keys = "{1}", "{2}", "{3}", "{1,2}", "{1,3}", "{2,3}", "{1,2,3}" features = {} for name, rec in atlas.items : f = {} for S in family keys: fm = rec "family matrices" S M = np.array fm "matrix" tr = fm "trace" rk = fm "rank numerical" offdiag vals = M ~np.eye 3, dtype=bool offdiag signs = set sign3 v for v in offdiag vals if 0 in offdiag signs and len offdiag signs 1: offdiag signs.discard 0 offdiag sign summary = 2 if len offdiag signs 1 else next iter offdiag signs if offdiag signs else 0 f f"layer1 {S}" = int rk 0 or abs tr TOL f f"rank {S}" = rk f f"trace sign {S}" = sign3 tr f f"offdiag sign {S}" = offdiag sign summary f f"det sign {S}" = sign3 fm "det" Cross-family trace comparisons a few useful ones traces = {S: rec "family matrices" S "trace" for S in family keys} f "cmp main vs pair" = sign3 traces "{1}" + traces "{2}" + traces "{3}" - traces "{1,2}" - traces "{1,3}" - traces "{2,3}" f "cmp pair vs three" = sign3 traces "{1,2}" + traces "{1,3}" + traces "{2,3}" - 3 traces "{1,2,3}" Degree-3 sign vector for dname, dval in rec "degree3 diagnostics" .items : f f"d3 {dname} sign" = sign3 dval features name = f return features def feature matrix features, feature keys : """Build a 2D array of feature values: rows = games, cols = features.""" games = list features.keys mat = np.array features g k for k in feature keys for g in games return games, mat def patterns distinct games, mat : """Return True if every pair of games has a distinct feature row.""" seen = {} for i, g in enumerate games : row = tuple mat i if row in seen: return False, seen row , g seen row = g return True, None def minimal classifying subset features, feature keys, verbose=False : """Greedy backward elimination: drop features that aren't needed.""" games, mat = feature matrix features, feature keys keep = list range len feature keys distinct, collision = patterns distinct games, mat :, keep if not distinct: if verbose: print f" WARNING: feature set does not separate all games; " f"collision between {collision}" return feature keys i for i in keep Try to drop one feature at a time, lowest-index first changed = True while changed: changed = False for i in list keep : trial = j for j in keep if j = i distinct, = patterns distinct games, mat :, trial if distinct: keep = trial changed = True if verbose: print f" dropped {feature keys i }; {len keep } features remain" break return feature keys i for i in keep def layer1 signature atlas : """7-bit family-activation pattern per game which contrast types nonzero .""" family keys = "{1}", "{2}", "{3}", "{1,2}", "{1,3}", "{2,3}", "{1,2,3}" out = {} for name, rec in atlas.items : sig = tuple int rec "family matrices" S "rank numerical" 0 or abs rec "family matrices" S "trace" TOL for S in family keys out name = sig return out, family keys def layer2 signature atlas : """Layer-2 signature: rank, offdiag-sign per nonzero family.""" family keys = "{1}", "{2}", "{3}", "{1,2}", "{1,3}", "{2,3}", "{1,2,3}" out = {} for name, rec in atlas.items : sig = for S in family keys: fm = rec "family matrices" S M = np.array fm "matrix" rk = fm "rank numerical" if rk == 0 and abs fm "trace" < TOL: sig.append "0", 0 continue offdiag = M ~np.eye 3, dtype=bool signs = set sign3 v for v in offdiag if 0 in signs and len signs 1: signs.discard 0 if len signs 1: offdiag label = "mixed" elif signs == {1}: offdiag label = "+" elif signs == {-1}: offdiag label = "-" else: offdiag label = "0" sig.append str rk , offdiag label out name = tuple sig return out, family keys def report atlas path="atlas 3x3 results.json" : with open atlas path as f: atlas = json.load f games = list atlas.keys print f"Classifying invariants for {len games } named 3,3 -games\n" ------- Layer 1 ------- print "=" 78 print "Layer 1: family activation pattern which of 7 contrast types nonzero " print "=" 78 sigs l1, fam keys = layer1 signature atlas header = "Game".ljust 35 + " | " + " ".join s.ljust 7 for s in fam keys print header print "-" len header pattern groups = {} for name in games: sig = sigs l1 name pattern groups.setdefault sig, .append name flags = " ".join "on" if b else " " .ljust 7 for b in sig nshort = name.replace "3p ", "" .replace " ", " " print f"{nshort:<35s} | {flags}" print f"\n Distinct Layer-1 patterns: {len pattern groups }" for sig, members in sorted pattern groups.items : sig str = "".join str b for b in sig labels = m.replace "3p ", "" .replace " ", " " for m in members print f" pattern {sig str}: {labels}" ------- Layer 2 ------- print print "=" 78 print "Layer 2: per-family rank, off-diag sign " print "=" 78 sigs l2, = layer2 signature atlas l2 groups = {} for name in games: l2 groups.setdefault sigs l2 name , .append name print f" Distinct Layer-2 signatures: {len l2 groups }" for sig, members in sorted l2 groups.items : sig str = " ".join f"{S}= {r},{o} " for S, r, o in zip fam keys, sig labels = m.replace "3p ", "" .replace " ", " " for m in members print f" {sig str}" for m in labels: print f" - {m}" if len l2 groups == len games : print " Layer 2 ALONE distinguishes all 13 games." else: n collisions = sum 1 for v in l2 groups.values if len v 1 print f" Layer 2 leaves {n collisions} group s unresolved; " f"add Layer-3 degree-3 signs to discriminate." ------- Minimal classifying subset greedy ------- print print "=" 78 print "Minimal classifying subset greedy backward elimination " print "=" 78 features = build features atlas all keys = sorted next iter features.values .keys Stable order: layer1 first, then ranks, signs, then degree-3 def order key k : if k.startswith "layer1 " : return 0, k if k.startswith "rank " : return 1, k if k.startswith "trace sign " : return 2, k if k.startswith "offdiag sign " : return 3, k if k.startswith "det sign " : return 4, k if k.startswith "cmp " : return 5, k if k.startswith "d3 " : return 6, k return 7, k ordered keys = sorted all keys, key=order key First check whether the full set distinguishes full games, full mat = feature matrix features, ordered keys distinct full, collision = patterns distinct full games, full mat print f" Full feature set {len ordered keys } features " f"distinguishes all games: {distinct full}" if not distinct full: print f" Unresolvable collision: {collision}" else: minimal = minimal classifying subset features, ordered keys, verbose=False print f" Minimal classifying subset: {len minimal } features" for k in minimal: print f" - {k}" Also: which features in the minimal set come from each layer? print print " Layer breakdown of minimal classifying set:" layer counts = {} for k in minimal: layer = order key k 0 layer counts.setdefault layer, .append k layer names = {0: "L1 activation", 1: "L2 rank", 2: "L2 trace-sign", 3: "L2 offdiag-sign", 4: "L2 det-sign", 5: "cross-cmp", 6: "L3 degree-3"} for layer in sorted layer counts : print f" {layer names layer }: {len layer counts layer }" for k in layer counts layer : print f" - {k}" if name == " main ": report 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 : python from itertools import combinations, combinations with replacement import json import numpy as np from contrast blocks 3x3 import mean zero payoff, project contrast block, family matrix, all family matrices def project block local u p, S : """Local representation of T {S, p} dimension 2^|S| .""" full = project contrast block u p, S sl = slice None 3 for axis in range 3 : if axis not in S: sl axis = 0 return full tuple sl def degree2 features u : """42 invariants: upper triangle of M S for each non-empty S.""" out = for r in range 1, 4 : for S in combinations 0, 1, 2 , r : M = family matrix u, S for i in range 3 : for j in range i, 3 : out.append M i, j return np.array out def degree3 features extended u : u0 = mean zero payoff u out = Main-effect polarizations for axis in 0, 1, 2 : S = axis, Ts = project block local u0 p , S for p in range 3 for p, q, r in combinations with replacement range 3 , 3 : out.append float np.sum Ts p Ts q Ts r Pairwise-block determinants for pair in combinations 0, 1, 2 , 2 : for p in range 3 : T = project block local u0 p , pair out.append float np.linalg.det T Three-way contractions Ds = project block local u0 p , 0, 1, 2 for p in range 3 for p, q, r in combinations with replacement range 3 , 3 : out.append float np.sum Ds p Ds q Ds r M3 = family matrix u, 0, 1, 2 out.append float np.trace M3 @ M3 @ M3 out.append float np.linalg.det M3 return np.array out def fingerprint u : """Full fingerprint = degree-2 + extended degree-3 features.""" return np.concatenate degree2 features u , degree3 features extended u def apply group element u, sigma1, sigma2, sigma3 : inv1 = np.argsort sigma1 inv2 = np.argsort sigma2 inv3 = np.argsort sigma3 return u :, inv1 :, :, inv2 :, :, :, inv3 --------------------------------------------------------------------------- Tests --------------------------------------------------------------------------- def test orbit invariance N=30, tol=1e-8 : """For N random games, verify the fingerprint is S 3 ^3-invariant.""" rng = np.random.default rng 0 max err = 0.0 for trial in range N : u = rng.standard normal 3, 3, 3, 3 fp u = fingerprint u Random group element sigma1 = rng.permutation 3 sigma2 = rng.permutation 3 sigma3 = rng.permutation 3 u rel = apply group element u, sigma1, sigma2, sigma3 fp rel = fingerprint u rel err = float np.max np.abs fp u - fp rel max err = max max err, err return max err def test separation random N=500, tol=1e-6 : rng = np.random.default rng 1 fps = labels = for i in range N : u = rng.standard normal 3, 3, 3, 3 fp u = fingerprint u fps.append fp u labels.append i sigma1 = rng.permutation 3 sigma2 = rng.permutation 3 sigma3 = rng.permutation 3 u rel = apply group element u, sigma1, sigma2, sigma3 fps.append fingerprint u rel labels.append i fps = np.array fps labels = np.array labels M = len fps Compare every pair; record cases where fingerprints match pair matches = pair mismatches in same orbit = for i in range M : for j in range i + 1, M : diff = float np.max np.abs fps i - fps j same orbit = labels i == labels j close = diff < tol if close and not same orbit: pair matches.append i, j, diff if not close and same orbit: pair mismatches in same orbit.append i, j, diff return { "false merges": pair matches, "broken orbit mates": pair mismatches in same orbit, "n games": N, "n total": M, } def test atlas separation atlas path="atlas 3x3 results.json" : Rebuild atlas fingerprints from scratch the JSON has limited diagnostics from atlas 3x3 import NAMED GAMES fps = {} for name, builder in NAMED GAMES.items : u = builder fps name = fingerprint u games = list fps.keys n = len games collisions = for i in range n : for j in range i + 1, n : diff = float np.max np.abs fps games i - fps games j if diff < 1e-6: collisions.append games i , games j , diff return collisions, fps --------------------------------------------------------------------------- Main --------------------------------------------------------------------------- def structured orbit samples N random=80 : from atlas 3x3 import NAMED GAMES samples = rng = np.random.default rng 7 for in range N random : samples.append rng.standard normal 3, 3, 3, 3 for builder in NAMED GAMES.values : u = builder samples.append u Perturbations of atlas games for eps in 0.01, 0.1 : samples.append u + eps rng.standard normal 3, 3, 3, 3 Sparse / structured games for in range 20 : u = rng.standard normal 3, 3, 3, 3 mask = rng.random 3, 3, 3, 3 < 0.3 samples.append u mask return samples def minimum separating subset N=200, tol=1e-6, verbose=False : rng = np.random.default rng 123 base samples = structured orbit samples N random=N fps full = labels = for i, u in enumerate base samples : fps full.append fingerprint u labels.append i Add the orbit mate sigma1 = rng.permutation 3 sigma2 = rng.permutation 3 sigma3 = rng.permutation 3 u rel = apply group element u, sigma1, sigma2, sigma3 fps full.append fingerprint u rel labels.append i fps full = np.array fps full labels = np.array labels n features = fps full.shape 1 keep = set range n features def separates idxs : if not idxs: return False sub = fps full :, sorted idxs Vectorized pairwise check: max-norm distances For each pair i, j with i < j: dist = max |sub i - sub j | Find the minimum cross-orbit distance. n = sub.shape 0 for i in range n - 1 : diffs = np.max np.abs sub i + 1: - sub i , axis=1 Mask pairs in same orbit same orbit = labels i + 1: == labels i cross diffs = diffs ~same orbit if cross diffs.size 0 and cross diffs.min < tol: return False return True if not separates keep : return None already cannot separate; shouldn't happen with our 93 changed = True while changed: changed = False Try dropping features in order for i in sorted keep : trial = keep - {i} if separates trial : keep = trial changed = True if verbose: print f" dropped feature {i}; {len keep } remain", flush=True break return sorted keep def main : print "Orbit-separation tests for 3,3 -games" print "=" 70 Sample fingerprint size rng = np.random.default rng 99 u sample = rng.standard normal 3, 3, 3, 3 fp sample = fingerprint u sample print f"Fingerprint size: {fp sample.shape 0 } invariants" print f" {degree2 features u sample .shape 0 } degree-2 + " f"{degree3 features extended u sample .shape 0 } degree-3 " print Test A: orbit invariance print " A Orbit invariance: applying random g in S 3 ^3 to random games ..." max err = test orbit invariance N=30 print f" max |fingerprint u - fingerprint g.u | over 30 trials: {max err:.2e}" assert max err < 1e-8, "fingerprint is NOT G-invariant" print " PASS: fingerprint is S 3 ^3-invariant." print Test B: generic separation print " B Generic orbit separation on N=500 random games + orbit-mates ..." result = test separation random N=500, tol=1e-6 n false = len result "false merges" n broken = len result "broken orbit mates" print f" pairs in different orbits with same fingerprint FALSE MERGES : {n false}" print f" pairs in same orbit with different fingerprint BROKEN INVARIANCE : {n broken}" assert n broken == 0 if n false == 0: print " PASS: no false merges. Fingerprint generically separates orbits." else: print f" FAIL: {n false} false merges. Examples:" for i, j, d in result "false merges" :3 : print f" games {i} and {j} differ by {d:.2e} but in different orbits" print Test C: atlas separation print " C Atlas separation: all 13 named games have distinct fingerprints?" collisions, fps = test atlas separation if collisions: print f" COLLISIONS: {len collisions } pairs" for a, b, d in collisions: print f" {a} <- {b}: max diff {d:.2e}" else: print " PASS: all 13 atlas games have distinct fingerprints." print Test D: empirical minimum separating subset against a STRESS-TEST sample. Note: greedy elimination on any finite sample will return very few features since any non-constant invariant has distinct values on N generic points. This is NOT a meaningful lower bound for the full orbit-separation task. The TRUE minimum separating set for V^0/G has size constrained algebraically by the geometry of the quotient; for our generating ring we need 42 + 556 = 598 invariants degrees 2 + 3 minimum, possibly more at higher degrees. print " D Greedy minimum on stress-test sample ..." print " random + atlas + perturbations + sparse, with orbit-mates " kept = minimum separating subset N=80, tol=1e-4, verbose=False print f" Greedy result on this sample: {len kept } features suffice." print f" CAVEAT: this is sample-specific, not a true separation lower bound." print f" For full orbit separation on V^0/G, the generating set 42 deg-2 +" print f" 556 deg-3 = 598 invariants total is the right target." print print "=" 70 print "Summary:" print f" Fingerprint = {fp sample.shape 0 } invariants " f" {degree2 features u sample .shape 0 } deg-2 + " f"{degree3 features extended u sample .shape 0 } deg-3 " print f" Orbit-invariant: max err {max err:.2e}" print f" False merges on random sample N=500, 1000 games total : {n false}" print f" Atlas separation: {len collisions } collisions" print f" Greedy minimum separating subset: {len kept } features" if name == " main ": main 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 : python from itertools import combinations with replacement import json import numpy as np from orbit separation 3x3 import fingerprint, degree2 features, degree3 features extended, apply group element, from molien 3x3 strategy only import molien 33 strategy only --------------------------------------------------------------------------- 1 Subalgebra Hilbert series via numerical rank --------------------------------------------------------------------------- def compute subalgebra hilbert max degree=6, N points=800, tol=1e-6, verbose=True : Each f i has its own degree 2 for the 42 family-matrix entries, 3 for the 51 degree-3 cubics . fp degrees = 2 42 + 3 51 n inv = len fp degrees if verbose: print f"Evaluating fingerprint at {N points} random V^0 points ...", flush=True rng = np.random.default rng 11 sample pts = rng.standard normal 3, 3, 3, 3 for in range N points F eval = np.array fingerprint u for u in sample pts N points, 93 For each total degree d, enumerate monomials in the 93 invariants whose total fingerprint degree sum of fp degrees of chosen invariants equals d. Evaluate each monomial as a product across the sample. if verbose: print f"Enumerating monomials in subalgebra coordinates up to degree {max degree} ...", flush=True hilb = 0 max degree + 1 hilb 0 = 1 constants For each abstract polynomial degree d, the contributing monomials are m {i1} m {i2} ... m {ik} where i 1 <= i 2 <= ... and fp degrees sum to d. Enumerate by length k = 1, 2, 3, ... and total degree. for d in range 1, max degree + 1 : Build all unordered tuples of fingerprint indices whose degree sums to d. mono evals = for k in range 1, d // 2 + 1 : min monomial length is d/d=1, max d/2 pass Simpler: iterate over k monomial length ; for each k, generate unordered tuples and filter by total degree. Max k for total degree d: k <= d when all fp degrees=1, but our min is 2 . Actually min fp degree is 2, so max k = d // 2. for k in range 1, d // 2 + 1 : for idxs in combinations with replacement range n inv , k : if sum fp degrees i for i in idxs == d: val = np.ones N points for i in idxs: val = F eval :, i mono evals.append val if not mono evals: hilb d = 0 if verbose: print f" degree {d}: no monomials - dim 0", flush=True continue M = np.array mono evals n monos, N points rank = int np.linalg.matrix rank M, tol=tol hilb d = rank if verbose: print f" degree {d}: {len mono evals } monomials, rank = {rank}", flush=True return hilb def compare to molien subalgebra hilbert, max degree : """Compare subalgebra Hilbert series to full Molien series.""" full = molien 33 strategy only max degree print print "Hilbert series comparison: subalgebra vs full invariant ring" print "=" 70 print f"{'degree': 6} {'subalgebra': 12} {'full ring': 12} {'gap': 8}" print "-" 70 for d in range max degree + 1 : gap = full d - subalgebra hilbert d flag = "" if gap == 0 else " <-- gap" if gap 0 else " ERROR" print f"{d: 6} {subalgebra hilbert d : 12} {full d : 12} {gap: +8}{flag}" print total gap low = sum full d - subalgebra hilbert d for d in range min 4, len full return full, total gap low --------------------------------------------------------------------------- 2 Stress-tests on special strata --------------------------------------------------------------------------- def gen random rng : return rng.standard normal 3, 3, 3, 3 def gen symmetric payoff rng : Generate via a single random function on own strategy, multiset of others multiset of 2 strategies from {0,1,2}: 6 possibilities Total entries: 3 own 6 multiset = 18 random numbers base = rng.standard normal 18 u = np.zeros 3, 3, 3, 3 multiset index = {} idx = 0 for a in range 3 : for b in range a, 3 : multiset index a, b = idx multiset index b, a = idx idx += 1 for p in range 3 : for s1 in range 3 : for s2 in range 3 : for s3 in range 3 : profile = s1, s2, s3 own = profile p others = sorted profile q for q in range 3 if q = p mi = multiset index others 0 , others 1 u p, s1, s2, s3 = base own 6 + mi return u def gen low rank payoff rng, rank=2 : u = np.zeros 3, 3, 3, 3 for p in range 3 : for in range rank : v1 = rng.standard normal 3 v2 = rng.standard normal 3 v3 = rng.standard normal 3 u p += np.einsum 'i,j,k- ijk', v1, v2, v3 return u def gen sparse payoff rng, density=0.3 : """Sparse: zero out 1 - density fraction of payoff entries.""" u = rng.standard normal 3, 3, 3, 3 mask = rng.random 3, 3, 3, 3 < density return u mask def gen near degenerate rng, eps=0.05 : """Near-degenerate: small perturbation of a degenerate all-zero tensor.""" return eps rng.standard normal 3, 3, 3, 3 STRATA = { "random": gen random, "symmetric": gen symmetric payoff, "low rank": gen low rank payoff, "sparse": gen sparse payoff, "near degenerate": gen near degenerate, } def stress test N per stratum=50, tol=1e-6, verbose=True : rng = np.random.default rng 99 results = {} if verbose: print "Stress tests on special strata" print "=" 70 for stratum name, gen in STRATA.items : if verbose: print f" stratum: {stratum name} {N per stratum} orbits ...", flush=True fps = labels = for i in range N per stratum : u = gen rng fps.append fingerprint u labels.append i sigma1 = rng.permutation 3 sigma2 = rng.permutation 3 sigma3 = rng.permutation 3 u rel = apply group element u, sigma1, sigma2, sigma3 fps.append fingerprint u rel labels.append i fps = np.array fps labels = np.array labels n = len fps false merges = 0 max in orbit = 0.0 min cross orbit = float "inf" for i in range n - 1 : diffs = np.max np.abs fps i + 1: - fps i , axis=1 same orbit = labels i + 1: == labels i in orbit diffs = diffs same orbit cross orbit diffs = diffs ~same orbit if in orbit diffs.size 0: max in orbit = max max in orbit, float in orbit diffs.max if cross orbit diffs.size 0: min cross orbit = min min cross orbit, float cross orbit diffs.min false merges += int cross orbit diffs < tol .sum results stratum name = { "false merges": false merges, "max in orbit": max in orbit, "min cross orbit": min cross orbit, } if verbose: print f" false merges: {false merges}" print f" max in-orbit diff: {max in orbit:.2e} should be ~ machine eps " print f" min cross-orbit diff: {min cross orbit:.2e}" return results --------------------------------------------------------------------------- Main --------------------------------------------------------------------------- def main : print " 3a Stronger separation verification for the 93-invariant fingerprint" print "=" 78 print Hilbert-series check print " 1/2 Subalgebra Hilbert-series check vs full Molien " hilb = compute subalgebra hilbert max degree=4, N points=400, verbose=True full, total gap = compare to molien hilb, max degree=4 if total gap == 0: print "PASS: subalgebra Hilbert series matches full Molien up to degree 4." print "Implication: every invariant of degree <= 4 is a polynomial in F." else: print f"GAP: subalgebra is missing {total gap} invariants in degrees <= 4." print "Implication: not all degree-<=4 invariants are polynomials in F." print "This DOES NOT necessarily mean orbits are unseparated, but it" print "is a warning sign. Adding more degree-3 or degree-4 invariants" print "could close the gap." print Stress-test check print " 2/2 Stress-test on special strata" stress = stress test N per stratum=50, tol=1e-6 print print "Summary of stress tests:" print f"{'stratum':<20s} {'false merges': 14s} {'max in orbit': 14s} {'min cross': 14s}" print "-" 70 total merges = 0 for stratum, info in stress.items : total merges += info "false merges" print f"{stratum:<20s} {info 'false merges' : 14d} " f"{info 'max in orbit' : 14.2e} {info 'min cross orbit' : 14.2e}" print if total merges == 0: print "PASS: no false merges in any stratum. 93 invariants robustly separate." else: print f"FAIL: {total merges} false merges. The 93 invariants are not sufficient" print "on every stratum tested." if name == " main ": main 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 .↩︎