Games, Invariants, and Alignment

Introduction

In the post/paper draft here I wrote about using invariants to classify normal-form games. That post is a monster that I ultimately need to carve up and revise significantly; the purpose of this post is to explain a core set of the ideas, give some explanation of the ideas (so you don’t have to wait forever for me to revise) and motivate the project in the larger scheme of my interests.

Game Equivalency and Invariant Theory

Let’s start by considering some basic normal-form games with 2 players, each choosing between 2 strategies (i.e. \((2,2)\)-games, in my parlance). Player 1 will be represented by payoff matrix \(A\), player 2 will be represented by payoff matrix \(B\). For example, here is Prisoner’s Dilemma, represented by two matrices:

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

However, these two matrices are also Prisoner’s Dilemma:

\[ A = \begin{pmatrix} 2 & 6 \\ 1 & 4 \end{pmatrix}, \qquad B = \begin{pmatrix} 2 & 1 \\ 6 & 4 \end{pmatrix} \]

We can qualitatively tell that they are the same because of how the players behave in each game. In both games, both players have a strategy they prefer no matter what the other player does, but if they both play their individual preferred strategy, they end up worse off than if they had both agreed on the same strategy.

On the other hand, here is Stag Hunt:

\[ A = \begin{pmatrix} 4 & 0 \\ 2 & 2 \end{pmatrix}, \qquad B = \begin{pmatrix} 4 & 2 \\ 0 & 2 \end{pmatrix} \]

Players behave qualitatively differently in Stag Hunt than in Prisoner’s Dilemma. In Stag Hunt (like in Prisoner’s Dilemma) both players are best off playing the same strategy on the other player. Here, though, the players prefer cooperating to playing their individual strategy.

Why do we call both of the first two examples “Prisoner’s Dilemma”? They have different payoff matrices. Can we somehow tell they are the same based on the numbers in the payoff matrix? Similarly, Stag Hunt is different than the Prisoner’s Dilemma. Can we tell that it is not Prisoner’s Dilemma by looking at the numbers in the payoff matrix?

What we ultimately want is a map that, given a game, returns its type. Call this function \(q\). That is, if we have two instances of Prisoner’s Dilemma, we also have:

\[ q(g_{PD}) = q(g_{PD}') \]

Furthermore, \(q\) should be such that Stag Hunt is not equal to Prisoner’s Dilemma:

\[ q(g_{PD}) \neq q(g_{SH}) \]

We could define our game type function \(q\) using some ordinal method. That would entail checking to see which entries are larger than other entries. But ordinal methods lose some information about the actual payoff sizes, so they can’t distinguish between games where there’s a small temptation versus a large temptation, or two games that have the same preference ranking but very different welfare, mixed equilibria, basins of attraction, or learning dynamics. So we want a cardinal method to preserve these qualities.

But using cardinal payoffs creates a second problem. The raw payoff matrices contain both real strategic structure and arbitrary choices of description. The names and orderings of strategies are arbitrary. Calling the first row “Cooperate” and the second row “Defect” is just a convention, and swapping the two row labels should not create a new game. Likewise, adding a constant to all of one player’s payoffs changes the displayed numbers, but not that player’s incentives.

Looking more closely at the Prisoner’s Dilemma examples, we can see that it is possible to transform the first example into the second. Take the first PD and swap player 1’s two row labels (rename “row 1” to “row 2” and vice versa). The payoffs rearrange as

\[ A' = \begin{pmatrix} 5 & 1 \\ 3 & 0 \end{pmatrix}, \qquad B' = \begin{pmatrix} 0 & 1 \\ 3 & 5 \end{pmatrix} \]

No payoff has changed, only labels. A column swap on player 2 gives another rearrangement of the same payoffs:

\[ A'' = \begin{pmatrix} 1 & 5 \\ 0 & 3 \end{pmatrix}, \qquad B'' = \begin{pmatrix} 1 & 0 \\ 5 & 3 \end{pmatrix} \]

Finally, add \(1\) to every payoff for both players:

\[ A''' = \begin{pmatrix} 2 & 6 \\ 1 & 4 \end{pmatrix}, \qquad B''' = \begin{pmatrix} 2 & 1 \\ 6 & 4 \end{pmatrix} \]

These operations carry the first PD’s payoff array through a family of four matrices that all encode the same game. The row and column swaps changed the strategy labels and the additive shift changed the payoff baselines, but the strategic incentives did not change. Now we can see that our two PD examples were indeed the same, up to this set of transformations.

So we have three transformation types above that should not affect our game type¹: permutation by rows, permutation by columns, and adding a constant. Recalling our game type map \(q\), under any of these game transformations \(g \to g'\), we ought to have

\[q(g) = q(g')\]

One way to think about this is that a displayed payoff matrix contains both the underlying game type and presentation data, such as which row name was put first, which column name was put first, and which payoff baseline was chosen for each player. If we identify the game type \(q(g)\) with a chosen canonical representative, then every displayed version could be recovered from that representative by specifying these extra presentation coordinates: a row permutation, a column permutation, and two additive constants. Schematically, this looks like

\[g = (\text{row permutation},\text{column permutation}) \cdot q(g) + (m_A J,m_B J) \]

where \(J\) is the \(2\) by \(2\) matrix of all ones, and \(m_A,m_B\) are the payoff baselines added to players \(1\) and \(2\).

Informally, we could also write the displayed game in coordinate form: \[ g \leftrightarrow (q(g), \text{row permutation},\text{column permutation}, m_A,m_B) \]

where \(q(g)\) is the “canonical” representative of the game, and the remaining entries are presentation data.

In this example, the first two transformations are discrete choices, where we either swap the rows or do not, and either swap the columns or do not. The additive transformations are continuous choices, where we add some number to every entry of \(A\), and some possibly different number to every entry of \(B\).

We could also go in a reverse direction. Suppose we had a given game \(g\). We could undo each operation in a canonical way to get the canonical representative.

\[ (\text{row permutation},\text{column permutation})^{-1} \cdot (g - (m_A J,m_B J)) = q(g) \]

However, this introduces a new problem, which is how do we determine the row permutation, the column permutation, and the constants \(m_A,m_B\) from the displayed game?

For the additive part, there is an obvious answer. We choose \(m_A\) and \(m_B\) to be the players’ mean payoffs:

\[ m_A = \frac{1}{4}(a_1 + a_2 + a_3 + a_4) \] \[ m_B = \frac{1}{4}(b_1 + b_2 + b_3 + b_4) \]

Subtracting these means removes the payoff baselines and leaves the mean-zero payoff space.

To see why this works, suppose we add some new constant \(x\) to every entry of matrix \(A\). Then \[ m_{A+xJ} = \frac{1}{4}(a_1 + a_2 + a_3 + a_4 + 4x) = \frac{1}{4}(a_1 + a_2 + a_3 + a_4) + x = m_A + x \]

This means that under the operation “addition by an additive constant” the mean-centered matrix transforms as follows:

\[ A - m_AJ \to_{+x} (A+xJ)-m_{A+xJ}J = (A+xJ)-(m_A+x)J = A-m_AJ \]

That is, mean-centering gives the same result no matter which additive baseline was used. We have quotiented out the additive presentation coordinate.

That all takes care of additive constants. Once we replace \(A\) and \(B\) by their mean-centered versions, the payoff baselines are gone.

Can we use the same idea to remove the row and column labels? We could choose a canonical row and column ordering, then send every relabeled version of the game to that representative. In other words, for each mean-zero game \(g\), we would like to choose a permutation \(\sigma_g\) such that

\[ q(g)=\sigma_g^{-1}\cdot g \]

The issue is that there is no obvious analogue of “subtract the mean” for row and column labels. Any rule for choosing the canonical row and column ordering would be a convention.

However, instead of explicitly choosing the canonical representative \(q(g)\), we can look for coordinates that depend only on \(q(g)\). That is, we look for a coordinate map

\[ I(g)=(f_1(g),\ldots,f_N(g)) \]

such that relabeling the game does not change the coordinates:

\[ I(\sigma\cdot g)=I(g) \]

Equivalently, each coordinate function satisfies

\[ f_i(\sigma\cdot g)=f_i(g) \]

So we are looking for functions that are invariant to the underlying transformations.

For a \((2,2)\)-game, the row and column relabelings form the group

\[ S_2 \times S_2 \]

The set of all relabeled versions of a mean-zero game \(g\) is its orbit:

\[ \mathrm{Orb}(g)={\sigma\cdot g:\sigma\in S_2\times S_2} \]

Choosing a canonical representative means choosing one element of this orbit. Invariant coordinates assign the same coordinate values to every element of the orbit. If the invariant coordinates also separate the orbits, then they give a canonical coordinate description of the game type, without requiring us to choose one representative matrix.

Seen after the fact, our additive constant case was also a baby version of invariant theory. The map \(A \mapsto A-m_AJ\) is constant on every additive-shift family \(A \mapsto A+xJ\), and it is complete for that family because two distinct matrices have the same mean-centered form iff they differ by an additive constant. So the mean-centered matrix, which is invariant under additive shifts, uniquely defines each orbit.

Overall, this is the setup we were looking at in the invariant theory post. For a finite group acting linearly on a finite-dimensional vector space, polynomial invariants can separate orbits. In this setting, that means that if two mean-zero games are not related by row and column relabeling, then some polynomial invariant will give them different values. Moreover, there are standard procedures for finding a finite list of such invariants.

Calculating Invariants

So how do we actually get the invariants, and what do they look like? This, again, is a question we looked at abstractly in the computational invariant theory post, but now specialize to games in the paper.

We start by transforming coordinates into the mean-zero payoff space in which the relabeling action is simple.

If we have

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

then define

\[ \begin{aligned} r_A &= (a_1 + a_2) - (a_3 + a_4) \\ c_A &= (a_1 + a_3) - (a_2 + a_4) \\ d_A &= (a_1 - a_3) - (a_2 - a_4) \end{aligned} \]

and analogously \(r_B, c_B, d_B\) for player 2. We can call these the row contrast, the column contrast, and the interaction. The row contrast \(r_A\) records how much player 1’s payoff shifts from row 2 to row 1. The column contrast \(c_A\) records how much player 1’s payoff shifts from column 2 to column 1. The interaction \(d_A\) is the “difference-in-differences”, which asks “how much better is row 1 than row 2 when player 2 chooses column 1, compared to how much better row 1 is than row 2 when player 2 chooses column 2”? Note that \(d_A\) can be written as above, or written equivalently as \((a_1 - a_2) - (a_3 - a_4)\), so it answers the same question with rows and columns swapped. In short, \(d_A\) measures how much the two players’ strategies depend on each other². If \(d_A = 0\), the two players strategies do not depend on each other³.

If \(A\) is mean-zero, then these three numbers determine \(A\):

\[ A = \frac{1}{4} \begin{pmatrix} r_A+c_A+d_A & r_A-c_A-d_A \\ -r_A+c_A-d_A & -r_A-c_A+d_A \end{pmatrix} \]

So the six numbers

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

are coordinates on the mean-zero payoff space.

The row swap and the column swap acts on these coordinates by sign flips. Swapping player 1’s two rows sends \(r_A \mapsto -r_A\) and \(d_A \mapsto -d_A\) (the interaction picks up a sign because one of its two axes was flipped) while leaving \(c_A\) unchanged, and similarly for \(B\). So the row swap negates four of six coordinates: \(\{r_A, d_A, r_B, d_B\}\). The column swap negates the four involving the column index: \(\{c_A, d_A, c_B, d_B\}\).

So if we have a polynomial in \((r_A, c_A, d_A, r_B, c_B, d_B)\), that polynomial is invariant if and only if every monomial has even total degree in the row-flipped variables \(\{r_A, d_A, r_B, d_B\}\) and even total degree in the column-flipped variables \(\{c_A, d_A, c_B, d_B\}\).

For example, here’s a polynomial (aka game harmony)

\[ r_Ar_B + c_Ac_B + d_Ad_B \]

The first monomial is degree 2 in row-flipped variables, the second is degree 2 in column-flipped, and the third is degree 2 in both. So this polynomial is invariant under \(S_2 \times S_2\).

Using invariant theory, the paper shows that all invariant polynomials for \((2,2)\) games can be written in terms of the following 17 invariants.

Id	Expression	Interpretation
\(g_1\)	\(r_A^2\)	Player 1 row contrast magnitude
\(g_2\)	\(r_A r_B\)	Cross-player row contrast alignment
\(g_3\)	\(c_A^2\)	Player 1 column contrast magnitude
\(g_4\)	\(c_A c_B\)	Cross-player column contrast alignment
\(g_5\)	\(d_A^2\)	Player 1 interaction strength
\(g_6\)	\(d_A d_B\)	Interaction alignment (coordination vs anti-coordination)
\(g_7\)	\(r_B^2\)	Player 2 row contrast magnitude
\(g_8\)	\(c_B^2\)	Player 2 column contrast magnitude
\(g_9\)	\(d_B^2\)	Player 2 interaction strength
\(g_{10}\)	\(c_A d_A r_A\)
\(g_{11}\)	\(c_A d_B r_A\)
\(g_{12}\)	\(c_B d_A r_A\)
\(g_{13}\)	\(c_B d_B r_A\)
\(g_{14}\)	\(c_A d_A r_B\)
\(g_{15}\)	\(c_A d_B r_B\)
\(g_{16}\)	\(c_B d_A r_B\)
\(g_{17}\)	\(c_B d_B r_B\)

Generating all the invariants implies that we can separate orbits with these 17 monomials as coordinates⁴. The paper goes on to show that this set can be used to recover other well-known game classifications (like Robinson-Goforth), and to define well-known subsets of games (like potential games) by setting conditions on them.

Beyond that, let us review our original example in this light. Let:

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

be the mean-zero contrast coordinates, and let

\[ I(g)=(g_1,\ldots,g_{17}) \]

be the invariant coordinate vector, ordered according to the table above.

For the first Prisoner’s Dilemma, we get

\[ z(g_{PD})=(-3,7,-1,7,-3,-1) \]

and

\[ I(g_{PD}) = (9,-21,49,-21,1,1,49,9,1,21,21,-9,-9,-49,-49,21,21) \]

For the second displayed Prisoner’s Dilemma, the contrast coordinates change:

\[ z(g_{PD}')=(3,-7,-1,-7,3,-1) \]

This is expected, because we changed the row and column labels. But the invariant coordinates are the same:

\[ I(g_{PD}') = (9,-21,49,-21,1,1,49,9,1,21,21,-9,-9,-49,-49,21,21) \]

So the two displayed Prisoner’s Dilemmas get the same invariant fingerprint.

For Stag Hunt, on the other hand, we get

\[ z(g_{SH})=(0,4,4,4,0,4) \]

and

\[ I(g_{SH}) = (0,0,16,0,16,16,16,0,16,0,0,0,0,64,64,0,0) \]

This vector is different from the Prisoner’s Dilemma vector, so the invariant coordinates distinguish the two game types.

Alternative Invariants and Alignment

Of course, a 17-entry vector is not how we want to think about games. Sure, it’s a fingerprint, but not a very explanatory one. Can we reorganize these invariants into quantities with game-theoretic meaning?

Let’s start by looking at the payoff functions in terms of contrasts and interaction terms. Encode the row and column choices by \(s_1,s_2\in\{-1,1\}\), then player \(A\)’s payoff can be written as

\[ u_A(s_1,s_2) = m_A + \frac{s_1}{4}r_A + \frac{s_2}{4}c_A + \frac{s_1s_2}{4}d_A \]

and player \(B\)’s payoff can be written as

\[ u_B(s_1,s_2) = m_B + \frac{s_1}{4}r_B + \frac{s_2}{4}c_B + \frac{s_1s_2}{4}d_B \]

This is the usual payoff-matrix view in equation form, with one payoff function for player \(A\), and one payoff function for player \(B\).

Equivalently, if

\[ e_A= \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \qquad e_B= \begin{pmatrix} 0 \\ 1 \end{pmatrix} \]

then the whole payoff vector is

\[ u(s_1, s_2) = e_A \left( m_A + \frac{s_1}{4}r_A + \frac{s_2}{4}c_A + \frac{s_1s_2}{4}d_A \right) + e_B \left( m_B + \frac{s_1}{4}r_B + \frac{s_2}{4}c_B + \frac{s_1s_2}{4}d_B \right) \]

This equation is grouped by payoff recipient. First we describe player \(A\)’s payoff function, then player \(B\)’s payoff function.

Let’s rearrange this a bit. Collect the two players’ row, column, and interaction coordinates into vectors:

\[ v_{\{1\}} = \begin{pmatrix} r_A\\ r_B \end{pmatrix}, \qquad v_{\{2\}} = \begin{pmatrix} c_A\\ c_B \end{pmatrix}, \qquad v_{\{1,2\}} = \begin{pmatrix} d_A\\ d_B \end{pmatrix} \]

If we hadn’t removed the mean payoffs, we might also have the following vector:

\[ v_{\varnothing} = \begin{pmatrix} m_A\\ m_B \end{pmatrix} \]

We’ll include the mean payoffs here as it helps make clearer what’s going on when we transform the relevant equations.

Each vector describes how one part of the game enters the two payoff functions

Then the payoff vector becomes

\[ u(s_1, s_2) = v_{\varnothing} + \frac{s_1}{4}v_{\{1\}} + \frac{s_2}{4}v_{\{2\}} + \frac{s_1s_2}{4}v_{\{1,2\}} \]

All we’ve done so far is regroup the coefficients. But now, instead of the equation being organized along players, it’s organized along each subset of players. The zero-player component sets the payoff baseline, the one-player components describe unilateral effects, and the two-player component describes the irreducible joint effect.

This is sort of like “Fourier-transforming” our game. The payoff table gives values at full strategy profiles, but the subset transform decomposes that table into the payoff effects generated at the level of each “organization”.⁵

To make this explicit, let

\[ N=\{1,2\} \]

For each subset \(S\subseteq N\), define

\[ w_S(s_1,s_2)=\prod_{i\in S}s_i \]

with

\[ w_{\varnothing}(s_1,s_2)=1 \]

The four functions are

\[ w_{\varnothing}=1,\qquad w_{\{1\}}=s_1,\qquad w_{\{2\}}=s_2,\qquad w_{\{1,2\}}=s_1s_2 \]

The baseline component is the average payoff vector:

\[ v_{\varnothing} = \frac{1}{4} \sum_{s_1,s_2} u(s_1,s_2) \]

The non-baseline subset components are the signed payoff sums:

\[ v_S = \sum_{s_1,s_2} w_S(s_1,s_2)u(s_1,s_2) \qquad S\neq\varnothing \]

For \(S=\{1\}\) this gives the row contrast vector:

\[ v_{\{1\}} = \sum_{s_1,s_2} s_1u(s_1,s_2) = \begin{pmatrix} r_A\\ r_B \end{pmatrix} \]

For \(S=\{2\}\) this gives the column contrast vector:

\[ v_{\{2\}} = \sum_{s_1,s_2} s_2u(s_1,s_2) = \begin{pmatrix} c_A\\ c_B \end{pmatrix} \]

For \(S=\{1,2\}\) this gives the interaction vector:

\[ v_{\{1,2\}} = \sum_{s_1,s_2} s_1s_2u(s_1,s_2) = \begin{pmatrix} d_A\\ d_B \end{pmatrix} \]

So the transform from payoff entries to contrasts asks a game-theoretic question: at what organizational level is this payoff effect generated?

The inverse expression is

\[ u(s_1,s_2) = v_{\varnothing} + \frac{1}{4} \sum_{\varnothing\neq S\subseteq N} w_S(s_1,s_2)v_S \]

Thus every payoff vector at a profile is assembled from the baseline effect, the two unilateral organizational effects, and the joint organizational effect.

The subset decomposition is still not invariant under relabeling. We’ve removed the payoff-recipient grouping, not yet removed the arbitrary orientation of the strategy axes. If player \(1\)’s two strategies are swapped, then \(s_1\) changes sign, so every component involving player \(1\) changes sign. If player \(2\)’s two strategies are swapped, then every component involving player \(2\) changes sign.

Let \(T\subseteq N\) be the set of strategy axes being flipped. If a component has subset label \(S\), then flipping the axes in \(T\) changes its sign by

\[ \chi_S(T)=(-1)^{|S\cap T|} \]

For example, if \(T=\{1\}\), then

\[ \chi_{\varnothing}(\{1\})=1 \]

\[ \chi_{\{1\}}(\{1\})=-1 \]

\[ \chi_{\{2\}}(\{1\})=1 \]

\[ \chi_{\{1,2\}}(\{1\})=-1 \]

So flipping the first strategy axis changes the signs of the \(\{1\}\) and \(\{1,2\}\) organizations, but not the \(\varnothing\) or \(\{2\}\) organizations.

For the averaging formulas, we can absorb the factors of \(1/4\) into the coefficients. Define

\[ x_{\varnothing}=v_{\varnothing} \]

and for \(S\neq\varnothing\) define

\[ x_S=\frac{1}{4}v_S \]

Then

\[ u(s_1,s_2) = \sum_{S\subseteq N} w_S(s_1,s_2)x_S \]

The relabeled payoff expression is

\[ \psi_T(s_1,s_2) = \sum_{S\subseteq N} \chi_S(T)w_S(s_1,s_2)x_S \]

Equivalently,

\[ \psi_T(s_1,s_2) = v_{\varnothing} + \chi_{\{1\}}(T)\frac{s_1}{4}v_{\{1\}} + \chi_{\{2\}}(T)\frac{s_2}{4}v_{\{2\}} + \chi_{\{1,2\}}(T)\frac{s_1s_2}{4}v_{\{1,2\}} \]

The expression \(\psi_T\) is the same game viewed after flipping the strategy axes in \(T\).

Now average over one relabeled expression:

\[ K_1(T) = \frac{1}{4} \sum_{s_1,s_2} \psi_T(s_1,s_2) \]

The signed terms cancel because

\[ \sum_{s_1,s_2}s_1=0,\qquad \sum_{s_1,s_2}s_2=0,\qquad \sum_{s_1,s_2}s_1s_2=0 \]

Therefore

\[ K_1(T)=v_{\varnothing} \]

The first averaged quantity recovers the zero-organization component, namely the baseline payoff vector.

The next step is to compare two presentations of the same game. Define

\[ K_2(T) = \frac{1}{4} \sum_{s_1,s_2} \psi_{\varnothing}(s_1,s_2) \otimes \psi_T(s_1,s_2) \]

In the above, \(\otimes\) is the outer product. Since a payoff effect is a vector across payoff recipients, comparing two payoff effects means asking how each recipient’s payoff effect in one presentation lines up with each recipient’s payoff effect in the other. The outer product keeps this full comparison, as its \((P,Q)\) entry multiplies the effect on recipient \(P\) in the first presentation by the effect on recipient \(Q\) in the relabeled presentation.

This is a second-order subset comparison, which compares the original presentation of the game with the presentation obtained by flipping the axes in \(T\).

Now expand it:

\[ \begin{aligned} K_2(T) &= \frac{1}{4} \sum_{s_1,s_2} \left( \sum_{R\subseteq N} w_R(s_1,s_2)x_R \right) \otimes \left( \sum_{S\subseteq N} \chi_S(T)w_S(s_1,s_2)x_S \right) \\[4pt] &= \sum_{R,S\subseteq N} \chi_S(T) \left( \frac{1}{4} \sum_{s_1,s_2} w_R(s_1,s_2)w_S(s_1,s_2) \right) x_R\otimes x_S \end{aligned} \]

The profile average in parentheses is \(1\) when \(R=S\) and \(0\) otherwise. In game-theoretic terms, comparisons between different organizational levels wash out over the full profile space. A row effect compared with a column effect is positive in two cells and negative in two cells. A row effect compared with itself has the same sign in every cell.

Therefore only matching organizational components survive:

\[ K_2(T) = \sum_{S\subseteq N} \chi_S(T)x_S\otimes x_S \]

Returning to the \(v_S\) notation, this becomes

\[ K_2(T) = v_{\varnothing}\otimes v_{\varnothing} + \frac{\chi_{\{1\}}(T)}{16}v_{\{1\}}\otimes v_{\{1\}} + \frac{\chi_{\{2\}}(T)}{16}v_{\{2\}}\otimes v_{\{2\}} + \frac{\chi_{\{1,2\}}(T)}{16}v_{\{1,2\}}\otimes v_{\{1,2\}} \]

Thus the outer products appear as the same-organization terms in the second-order subset comparison. They are not inserted by hand.

Writing out the four relabelings gives

\[ K_2(\varnothing) = v_{\varnothing}\otimes v_{\varnothing} + \frac{1}{16}v_{\{1\}}\otimes v_{\{1\}} + \frac{1}{16}v_{\{2\}}\otimes v_{\{2\}} + \frac{1}{16}v_{\{1,2\}}\otimes v_{\{1,2\}} \]

\[ K_2(\{1\}) = v_{\varnothing}\otimes v_{\varnothing} - \frac{1}{16}v_{\{1\}}\otimes v_{\{1\}} + \frac{1}{16}v_{\{2\}}\otimes v_{\{2\}} - \frac{1}{16}v_{\{1,2\}}\otimes v_{\{1,2\}} \]

\[ K_2(\{2\}) = v_{\varnothing}\otimes v_{\varnothing} + \frac{1}{16}v_{\{1\}}\otimes v_{\{1\}} - \frac{1}{16}v_{\{2\}}\otimes v_{\{2\}} - \frac{1}{16}v_{\{1,2\}}\otimes v_{\{1,2\}} \]

\[ K_2(\{1,2\}) = v_{\varnothing}\otimes v_{\varnothing} - \frac{1}{16}v_{\{1\}}\otimes v_{\{1\}} - \frac{1}{16}v_{\{2\}}\otimes v_{\{2\}} + \frac{1}{16}v_{\{1,2\}}\otimes v_{\{1,2\}} \]

These four equations can be inverted by adding and subtracting according to the same subset sign pattern.

The baseline product is

\[ v_{\varnothing}\otimes v_{\varnothing} = \frac{1}{4} \left( K_2(\varnothing) + K_2(\{1\}) + K_2(\{2\}) + K_2(\{1,2\}) \right) \]

The \(\{1\}\) organization product is

\[ v_{\{1\}}\otimes v_{\{1\}} = 4 \left( K_2(\varnothing) - K_2(\{1\}) + K_2(\{2\}) - K_2(\{1,2\}) \right) \]

The \(\{2\}\) organization product is

\[ v_{\{2\}}\otimes v_{\{2\}} = 4 \left( K_2(\varnothing) + K_2(\{1\}) - K_2(\{2\}) - K_2(\{1,2\}) \right) \]

The \(\{1,2\}\) organization product is

\[ v_{\{1,2\}}\otimes v_{\{1,2\}} = 4 \left( K_2(\varnothing) - K_2(\{1\}) - K_2(\{2\}) + K_2(\{1,2\}) \right) \]

So the quadratic invariants are the second-order organizational alignment matrices.

For the \(\{1\}\) organization,

\[ M_{\{1\}} = v_{\{1\}}v_{\{1\}}^\top = \begin{pmatrix} r_A^2 & r_Ar_B\\ r_Ar_B & r_B^2 \end{pmatrix} \]

For the \(\{2\}\) organization,

\[ M_{\{2\}} = v_{\{2\}}v_{\{2\}}^\top = \begin{pmatrix} c_A^2 & c_Ac_B\\ c_Ac_B & c_B^2 \end{pmatrix} \]

For the \(\{1,2\}\) organization,

\[ M_{\{1,2\}} = v_{\{1,2\}}v_{\{1,2\}}^\top = \begin{pmatrix} d_A^2 & d_Ad_B\\ d_Ad_B & d_B^2 \end{pmatrix} \]

Each matrix describes one “organization” (subset of players). The diagonal entries measure how strongly that organizational component affects each payoff recipient. The off-diagonal entry measures alignment between payoff recipients within that organizational component.

Thus the nine quadratic invariants can be seen as the entries of three alignment matrices, one for each non-baseline organization.

The second-order comparison separates organizations one at a time, but a game is not just a collection of separate organizations. The singleton organizations and the joint organization have to assemble into one payoff surface.

To see this assembly information, compare three presentations of the same game:

\[ K_3(T,U) = \frac{1}{4} \sum_{s_1,s_2} \psi_{\varnothing}(s_1,s_2) \otimes \psi_T(s_1,s_2) \otimes \psi_U(s_1,s_2) \]

Expanding gives

\[ \begin{aligned} K_3(T,U) &= \frac{1}{4} \sum_{s_1,s_2} \left( \sum_{R\subseteq N} w_R(s_1,s_2)x_R \right) \otimes \left( \sum_{S\subseteq N} \chi_S(T)w_S(s_1,s_2)x_S \right) \otimes \left( \sum_{L\subseteq N} \chi_L(U)w_L(s_1,s_2)x_L \right) \\[4pt] &= \sum_{R,S,L\subseteq N} \chi_S(T)\chi_L(U) \left( \frac{1}{4} \sum_{s_1,s_2} w_R(s_1,s_2)w_S(s_1,s_2)w_L(s_1,s_2) \right) x_R\otimes x_S\otimes x_L \end{aligned} \]

The profile average is nonzero whenever each player index must appear in an even number of the three organizations, as thats when the signs cancel. Alternatively, we can define this in terms of the symmetric difference between the three sets (usually denoted with \(\triangle\), so \(\{1\} \triangle \{2\} \triangle \{1,2\} = \varnothing\)). Therefore

\[ K_3(T,U) = \sum_{S,L\subseteq N} \chi_S(T)\chi_L(U) x_{S\triangle L}\otimes x_S\otimes x_L \]

Therefore, the two singleton organizations and the joint organization together can survive the permutation operator.

For example, taking the \(\{1\}\) component from the first factor, the \(\{2\}\) component from the second factor, and the \(\{1,2\}\) component from the third factor gives

\[ \begin{aligned} & \frac{1}{4} \sum_{s_1,s_2} \left( \frac{s_1}{4}v_{\{1\}} \right) \otimes \left( \chi_{\{2\}}(T)\frac{s_2}{4}v_{\{2\}} \right) \otimes \left( \chi_{\{1,2\}}(U)\frac{s_1s_2}{4}v_{\{1,2\}} \right) \\[4pt] &= \frac{\chi_{\{2\}}(T)\chi_{\{1,2\}}(U)}{64} \left( \frac{1}{4} \sum_{s_1,s_2} s_1s_2(s_1s_2) \right) v_{\{1\}}\otimes v_{\{2\}}\otimes v_{\{1,2\}} \\[4pt] &= \frac{\chi_{\{2\}}(T)\chi_{\{1,2\}}(U)}{64} v_{\{1\}}\otimes v_{\{2\}}\otimes v_{\{1,2\}} \end{aligned} \]

By contrast, a term like

\[ v_{\{1\}}\otimes v_{\{2\}}\otimes v_{\{1\}} \]

does not survive, because its profile sign is

\[ s_1s_2s_1=s_2 \]

and

\[ \frac{1}{4} \sum_{s_1,s_2}s_2=0 \]

So the third-order comparison only keeps products with organizational labels that close up under symmetric difference.

The cubic tensor can be isolated from the sixteen third-order equations. From the general formula above,

\[ x_{S\triangle L}\otimes x_S\otimes x_L = \frac{1}{16} \sum_{T,U\subseteq N} \chi_S(T)\chi_L(U)K_3(T,U) \]

Taking \(S=\{2\}\) and \(L=\{1,2\}\) gives

\[ x_{\{1\}}\otimes x_{\{2\}}\otimes x_{\{1,2\}} = \frac{1}{16} \sum_{T,U\subseteq N} \chi_{\{2\}}(T)\chi_{\{1,2\}}(U)K_3(T,U) \]

Since \(x_S=\frac{1}{4}v_S\) for nonempty \(S\), this becomes

\[ v_{\{1\}}\otimes v_{\{2\}}\otimes v_{\{1,2\}} = 4 \sum_{T,U\subseteq N} \chi_{\{2\}}(T)\chi_{\{1,2\}}(U)K_3(T,U) \]

Written out, the sign pattern is

\[ \begin{aligned} v_{\{1\}}\otimes v_{\{2\}}\otimes v_{\{1,2\}} = 4\Big( & K_3(\varnothing,\varnothing) - K_3(\varnothing,\{1\}) - K_3(\varnothing,\{2\}) + K_3(\varnothing,\{1,2\}) \\ & + K_3(\{1\},\varnothing) - K_3(\{1\},\{1\}) - K_3(\{1\},\{2\}) + K_3(\{1\},\{1,2\}) \\ & - K_3(\{2\},\varnothing) + K_3(\{2\},\{1\}) + K_3(\{2\},\{2\}) - K_3(\{2\},\{1,2\}) \\ & - K_3(\{1,2\},\varnothing) + K_3(\{1,2\},\{1\}) + K_3(\{1,2\},\{2\}) - K_3(\{1,2\},\{1,2\}) \Big) \end{aligned} \]

The entries of the cubic tensor are

\[ \left( v_{\{1\}}\otimes v_{\{2\}}\otimes v_{\{1,2\}} \right)_{PQR} = r_Pc_Qd_R \qquad P,Q,R\in\{A,B\} \]

These are exactly the eight cubic invariants from the table, written in row-column-interaction order. The table may write the same monomials in a different order, such as \(c_Ad_Br_A\), but multiplication is commutative.

Putting everything together, the \(17\) invariant generators can be reorganized as

\[ \left( M_{\{1\}}, M_{\{2\}}, M_{\{1,2\}}, v_{\{1\}}\otimes v_{\{2\}}\otimes v_{\{1,2\}} \right) \]

where

\[ M_S=v_Sv_S^\top \]

The three matrices are the degree-\(2\) layer, which describe magnitude and alignment within each organization. Their diagonal entries measure how strongly that organization affects each payoff recipient, and their off-diagonal entries measure whether the two payoff recipients move together or against each other along that organization.

The cubic tensor is the degree-\(3\) layer, which records a cross-organization coupling: one effect from the \(\{1\}\) organization, one effect from the \(\{2\}\) organization, and one effect from the \(\{1,2\}\) organization. These three survive together because their subset labels close up under symmetric difference.

Note also that if we included the \(\varnothing\) set, we would have a fourth matrix, \(v_{\varnothing}v_{\varnothing}^\top\), which records alignment in baseline payoff levels rather than in strategic effects

So the invariant vector is a subset-organized description of the game: first the alignment structure inside each organization, then the compatibility structure across organizations.

Higher Dimensions

Let’s now extend what we have into higher dimensions.

In a \((2,2)\) game, each non-baseline subset has only one internal direction. In higher \(n\), we need to deal with groups of more than \(2\) players. Instead of numbers attached to each subset, we get contrast blocks.

Let \(N=\{1,\ldots,n\}\) and suppose each player has \(k\) strategies. A game consists of \(n\) payoff functions

\[ u_p:\{1,\ldots,k\}^N\to\mathbb R \]

one for each payoff recipient \(p\in N\).

For each subset \(S\subseteq N\) and each payoff recipient \(p\), define \(T_{S,p}\) to be the pure \(S\)-effect in player \(p\)’s payoff function. The empty component is the payoff mean:

\[ T_{\varnothing,p} = \frac{1}{k^n} \sum_{x\in\{1,\ldots,k\}^N} u_p(x) \]

For \(S\neq\varnothing\), the \(S\)-component is obtained by averaging over the players outside \(S\) and then subtracting all lower-order effects:

\[ T_{S,p}(x_S) = \frac{1}{k^{n-|S|}} \sum_{x_{N\setminus S}} u_p(x_S,x_{N\setminus S}) - \sum_{R\subsetneq S} T_{R,p}(x_R) \]

We can view this as the higher-dimensional version of the row-column-interaction decomposition.

The singleton components are main effects, which measure how a payoff recipient’s payoff varies with one player’s strategy axis after averaging over everyone else. The two-player components are residual pairwise interactions, which measure the part of the payoff variation generated by two players’ strategy axes together, after removing both singleton effects. The three-player components are residual three-way interactions, which measure the part of the payoff variation that cannot be explained by any singleton or pairwise effects. This pattern continues ad infinitum.

Based on this, the payoff function decomposes as

\[ u_p = \sum_{S\subseteq N} T_{S,p} \]

After removing player-specific payoff means, the empty component disappears and we get

\[ u_p^0 = \sum_{\varnothing\neq S\subseteq N} T_{S,p} \]

So a mean-zero game can be read as a collection of subset-indexed payoff effects:

\[ S \longmapsto (T_{S,1},\ldots,T_{S,n}) \]

The subset \(S\) says where the strategic dependence is generated and the player index \(p\) says whose payoff receives that effect.

The \((2,2)\) game had three non-baseline “organizations”, \(\{1\}\),\(\{2\}\), and \(\{1,2\}\) In general, a \(n\)-player game has \(2^n-1\) non-baseline organizations. We can also scale up in terms of strategies. For a single strategy coordinate, write

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

where \(\mathbf 1\) is the constant direction and \(W=\mathbf 1^\perp\) is the \((k-1)\)-dimensional contrast space.

For a subset \(S\), the corresponding contrast block is

\[ C_S \cong \bigotimes_{i\in S} W_i \]

Therefore

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

For \(k=2\), every \(W_i\) is one-dimensional, so every contrast block is one-dimensional, so the \((2,2)\) case collapses to scalar row, column, and interaction contrasts. For \(k=3\), each singleton organization has dimension \(2\), each pairwise organization has dimension \(4\), and each three-player organization has dimension \(8\), etc. Thus, adding players creates more subset families, while adding strategies thickens each family.

The relabeling group is

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

An element of this group relabels each player’s strategies and applies that relabeling to the corresponding coordinate in every payoff tensor. The order of the effect is invariant to change in label. That is, relabeling cannot turn a singleton effect into a pairwise effect, or a pairwise effect into a three-way effect.

Once the payoff space has been decomposed into subset components, each nonempty subset \(S\) gives a collection of contrast blocks

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

one for each payoff recipient.

The relabeling group may change coordinates inside the contrast block \(C_S\), but it preserves the inner product on that block. Therefore the basic degree-\(2\) invariant attached to \(S\) is the Gram matrix

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

In coordinates, this is

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

This is the higher-dimensional analogue of the three matrices from the \((2,2)\) case:

\[ v_{\{1\}}v_{\{1\}}^\top, \qquad v_{\{2\}}v_{\{2\}}^\top, \qquad v_{\{1,2\}}v_{\{1,2\}}^\top \]

The matrix \(M_S\) is indexed by an organization \(S\), but its rows and columns are payoff recipients. The diagonal entry \(M_S[p,p]\) measures the size of the payoff effect that organization \(S\) generates for recipient \(p\). The off-diagonal entry \(M_S[p,q]\) measures whether payoff recipients \(p\) and \(q\) are aligned or opposed inside that same organization.

So the degree-\(2\) layer gives one alignment matrix for each nonempty subset of players. In the \((2,2)\) case, the interaction-alignment coordinate \(d_Ad_B\) is the off-diagonal entry of \(M_{\{1,2\}}\). In the general case, the off-diagonal entries of \(M_S\) are the corresponding subset-level alignment coordinates.

For every nonempty subset \(S\subseteq N\), there is one symmetric \(n\) by \(n\) family matrix \(M_S\). Each such matrix has \(\frac{n(n+1)}{2}\) independent entries. Since there are \(2^n-1\) nonempty subsets, the degree-\(2\) layer has \((2^n-1)\frac{n(n+1)}{2}\) coordinates.

The degree 2 coordinate count depends on the number of players, but not on the number of strategies. The number of strategies changes the internal dimension of each contrast block, and therefore changes the geometry behind each Gram matrix. However, regardless, we can expect one subset-indexed matrix for each nonempty organization.

Now that we’ve investigated the degree 2 layer, we can look at the higher order effects. The next layer, starting at degree 3, asks what happens when we compare three organizational components at once. In a \((3,3)\) game, each player has three strategies, so a singleton component like \(T_{\{1\},p}\) is no longer a single number, but instead it is a contrast vector over player \(1\)’s three strategies

\[ T_{\{1\},p}(a) \qquad a\in\{1,2,3\} \]

A pairwise component like \(T_{\{1,2\},p}\) is a contrast table over two strategy coordinates:

\[ T_{\{1,2\},p}(a,b) \qquad a,b\in\{1,2,3\} \]

and the three-player component is a contrast array

\[ T_{\{1,2,3\},p}(a,b,c) \]

The degree-\(3\) invariants come from multiplying three such components and summing over strategy labels in a way that does not depend on what the strategies are called.

The old \((2,2)\) cubic has a direct analogue. By taking a singleton effect from organization \(\{1\}\), a singleton effect from organization \(\{2\}\), and a pairwise interaction from organization \(\{1,2\}\):

\[ T_{\{1\},p}, \qquad T_{\{2\},q}, \qquad T_{\{1,2\},r} \]

These can be combined as

\[ \sum_{a,b} T_{\{1\},p}(a) T_{\{2\},q}(b) T_{\{1,2\},r}(a,b) \]

This is the higher-strategy version of the row-column-interaction cubic, and it measures whether the \(\{1,2\}\) interaction is arranged so that it agrees with the \(\{1\}\) and \(\{2\}\) singleton effects.

But when \(k=3\), there is also a second kind of degree-\(3\) information. Because each singleton contrast space is now two-dimensional, we can also multiply three effects from the same organization and sum over the shared strategy label:

\[ \sum_a T_{\{1\},p}(a) T_{\{1\},q}(a) T_{\{1\},r}(a) \]

This doesn’t compare organizations, but instead describes the structure inside the \(\{1\}\) organization itself by asking whether the effects of organization \(\{1\}\) on three payoff recipients share the same asymmetric pattern across player \(1\)’s three strategies.

This kind of term has no binary analogue. To see why, suppose player \(1\) has only two strategies. Let

\[ x_1,x_2 \]

be the two values of one contrast over player \(1\)’s strategy coordinate. Since it is a contrast, its values sum to zero:

\[ x_1+x_2=0 \]

So

\[ x_2=-x_1 \]

Now take three such contrasts, with values

\[ x_1,x_2 \]

\[ y_1,y_2 \]

\[ z_1,z_2 \]

Their same-coordinate cubic sum is

\[ x_1y_1z_1+x_2y_2z_2 \]

But each second value is the negative of the first, so this becomes

\[ x_1y_1z_1+(-x_1)(-y_1)(-z_1)=0 \]

Thus a same-coordinate cubic expression cancels automatically when there are only two strategies. With three strategies, the contrast values only have to sum to zero across three labels, so the analogous cubic sum need not cancel.

Thus, in a \((3,3)\) game, degree \(3\) starts to add multiple kinds of information. Some degree-\(3\) invariants couple different organizations, like the \(\{1\}\), \(\{2\}\), \(\{1,2\}\) example above. Others measure internal shape inside a single organization, which only becomes possible once the contrast blocks have dimension greater than one.

Thus, degree \(2\) gives one matrix per organization. Degree \(3\) has to account for all the ways three organizational components can be multiplied and summed in a relabeling-invariant way. Furthermore, as we progress up the ladder of degrees, we see more and more higher order couplings, expanding in a combinatorial way⁶. Already, for a \((3,3)\) game, the degree-\(2\) layer has 42 coordinates, while degree-\(3\) has 556 coordinates. More players create more organizations, and more strategies give each organization more internal structure.

Other Stuff in the Paper

The paper also has some other ideas. To review quickly (full disclosure, Claude Opus 4.8 wrote this section based on the paper):

Recovering the classical taxonomies

The oldest classifications of \((2,2)\)-games are ordinal: they only record which payoff is bigger than which. Robinson and Goforth’s “periodic table” has \(144\) no-tie types; Rapoport and Guyer’s earlier strict-ordinal scheme has \(78\). Both fall out of the invariant coordinates as coarsenings. If you keep only the signs of the degree-\(2\) invariants and throw away their magnitudes, you recover a canonical \(12\)-sign vector that is exactly the Robinson-Goforth type. The paper makes this map explicit: given a generator vector \((g_1,\ldots,g_{17})\), it reconstructs the sign pattern and canonicalizes it under row and column swaps. Enlarging the relabeling group to also identify the two players (the wreath product \((S_k)^n \rtimes S_n\), treated in Appendix C) collapses the table further and recovers Rapoport-Guyer. So the ordinal taxonomies are not competitors to the invariant ring; they are what you get by remembering signs and forgetting cardinal geometry.

Cutting out the standard game classes

Most named families of games are defined by equations or inequalities on the payoffs, and those translate directly into conditions on the generators. A game is potential exactly when \(d_A = d_B\), i.e. \(g_5 = g_6 = g_9\). It is zero-sum when \(B = -A\), which in the invariants reads \(g_1 = g_7 = -g_2\), \(g_3 = g_8 = -g_4\), \(g_5 = g_9 = -g_6\). Symmetric games are those with a representative satisfying \(B = A^\top\). Coordination versus anti-coordination is the sign of the interaction-alignment coordinate \(g_6 = d_A d_B\). In other words, these familiar classes are algebraic subvarieties and sign regions sitting inside the quotient, not separate definitions bolted on from outside.

Reading off equilibrium structure

The same coordinates detect strategic structure. Player \(1\) has a strictly dominant strategy precisely when \(r_A^2 > d_A^2\) (their own-strategy contrast beats their interaction), and similarly \(c_B^2 > d_B^2\) for player \(2\); a \((2,2)\)-game is solvable by iterated strict dominance iff \(g_1 > g_5\) or \(g_8 > g_9\), so solvability is a semialgebraic condition. The fully mixed indifference equations are nondegenerate exactly when \(g_6 = d_A d_B \neq 0\), which is why \(g_6\) doubles as the mixed-equilibrium discriminant. This generalizes: for two-player \((2,k)\)-games the full-support indifference condition is a payoff-only invariant determinant of degree \(2(k-1)\), and for \(n \geq 3\) the natural object is a Jacobian form on the payoff–mixed-strategy incidence space, polynomial of degree \(n(k-1)\) in the payoff entries. Equilibrium structure is thus encoded as polynomial conditions on the same coordinates, with no solution concept assumed up front.

Scaling laws and a degree hierarchy

The ring grows in a structured way. The number of degree-\(d\) invariants \(h_d(n,k)\) stabilizes once \(k \geq d\) — adding more strategies past that point thickens the contrast blocks but stops producing new degree-\(d\) relations — and the binary (\(k=2\)) degree-\(3\) invariants have a closed-form super-polynomial growth rate in \(n\). There is also a hierarchy in which strategic features first appear: contrast magnitudes and interaction alignment at degree \(2\), skewness and cyclic directionality at degree \(3\), higher-order cyclic patterns at degree \(4\) and above. This is the same hierarchy the alignment-matrix and cubic-tensor story above is the first two rungs of.

The Hodge connection

Candogan, Menache, Ozdaglar, and Parrilo decompose any game into potential, harmonic, and nonstrategic parts. That decomposition is linear and relabeling-compatible, so it sits inside the invariant ring: the Hodge components give a coordinate split of the payoff space, and the invariant polynomials can then be sorted by which Hodge pieces they involve. The harmonic part is where cycling lives, which connects to the next point.

Cycle witnesses

Best-response cycles (the thing that makes Matching Pennies and Rock-Paper-Scissors tick) leave a polynomial signature. A label-complete cyclic witness produces a natural degree-\(k\) invariant, and a sign-reversing pair produces a degree-\(2k\) one. The paper is careful that these are existence statements — “here is an invariant that sees this cycle” — rather than universal lower bounds on the degree at which cycling becomes visible.

Computation

All of this is constructive. The generators come from applying the Reynolds operator to monomials and keeping what is linearly independent of products of lower-degree generators; the Molien series tells you the target dimension in each degree so you know when to stop; syzygies are computed the same way. The appendices carry this out: Appendix A tabulates the named \((2,2)\) values, Appendix B is the \((3,3)\) atlas (the \(598\) invariants through degree \(3\), \(42\) quadratic and \(556\) cubic) together with a typology, Appendix C is the wreath-product computation, and Appendix D is the Python. That being said, computation is a problem we will have to deal with in some other way as this thread develops.

Applications

I am in the process of extending this work across a number of applications. Here’s some thoughts

Game Embeddings

The 17 generators give us an embedding of \((2,2)\)-games into a high dimensional space. The map \(u \mapsto (g_1(u), \ldots, g_{17}(u))\) sends the mean-zero payoff space into \(\mathbb{R}^{17}\), and its image is the six-dimensional variety cut out by the syzygies. Since this embedding quotients only labels and keeps every cardinal feature, it can annotate the coarser embeddings with the cardinal data they discard. Cross-player alignment coordinates like \(g_2 = r_A r_B\) are invisible to any per-player block-diagonal embedding, because they probe how the two players’ payoff landscapes line up rather than each player’s structure in isolation. And because the framework is polynomial rather than pictorial, it keeps going at \((3, 3)\), \((3, 4)\), and beyond. It could be interesting to study these embeddings in an ML context.

Alignment

The off-diagonal entries

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

are a cardinal, per-channel, relabeling-invariant measure of whether two agents’ incentives move together or against each other inside organization \(S\). At \((2, 2)\) the off-diagonals are the three scalars \(r_A r_B\), \(c_A c_B\), \(d_A d_B\), with \(d_A d_B\) the channel separating coordination from anti-coordination. For larger \((n, k)\) they are the off-diagonals of one Gram matrix per organization. Alignment, in this framework, is a vector indexed by organizational channel. When does a collection of agents start to behave like a single agent? It might be possible to define agent identity based on which alignment channels carry weight.

Mechanism Design and Game Balance

Instead of reading invariants off a game, fix a target invariant signature and ask which games realize it. Mechanism design becomes incentive design modulo the relabeling gauge. You specify the alignment profile you want, and the construction tells you which semialgebraic region of payoff space realizes it.

For example, dominance for player 1 is \(r_A^2 > d_A^2\), iterated-dominance solvability is a sign condition on the degree-2 generators, and interaction alignment is the sign of \(d_A d_B\). “Does this game have a dominant-strategy exploit” can thus be answered by running a polynomial-inequality test on the invariants rather than a case analysis on payoff entries.

Game Abstraction and Reduction

We may be able to collapse large games into a smaller canonical forms by passing to invariant coordinates and truncating the high-order organizational blocks. This is similar to the idea behind differentiable game canonicalization. Even better, could we find salient “sub games” within a larger game?

Inverse Problems and Agent Detection

Because the invariants are relabeling-invariant summary statistics that can be estimated from data, we could potentially observe behavior or payoffs and thereby infer what game is being played. For example, which blocks are nonzero tells you what level of interaction structure is active, and which alignment cross-products carry weight tells you how the active players’ incentives sit relative to each other. With enough trajectories, the number and types of interacting agents become estimable rather than postulated. This connects to inverse reinforcement learning, inverse games, and auction bidder inference, and, through the role of the averaging operator, potentially also collects back to questions related to the inspection bias posts. The agent-detection direction in particular reframes a standard problem in multi-agent learning: rather than assuming a fixed agent decomposition and learning payoffs, learn the decomposition and the payoffs jointly by fitting the invariant signature.

Sparsity and Selection

Games that arise “in-the-wild” appear sparse in the organizational basis, as only a handful of low-order interactions carry weight, and most high-order blocks are essentially zero. If that holds, the decomposition could give a principled notion of a game’s complexity. This would provide a natural route to compressing large games by truncating the empty levels. The looser version of the conjecture is that, under operations by some selection operator, this sparse structure is produced. Games-in-the-wild are sparse because denser games are selected against, generation by generation⁷.

This potentially joins the algebraic classification work here with other topics on this blog, such selection and agency are the load-bearing concerns. The detailed treatments will be the subjects of future efforts.

Footnotes

1. Stopping here is arbitrary in the sense that the equivalence relation depends on what we want the classification to preserve. Different papers in this space use different conventions about which features they preserve and which they quotient out. In this section I am quotienting out transformations that do not change the players’ incentive differences. Other features, such as total welfare or player identity, can be factored out of the canonical representative and recorded as separate coordinates if they matter for the application. As we will see, working in invariant coordinates makes this bookkeeping easier, since we can choose which features to keep and which to ignore based on the application. We could also quotient by less if, for example, we care strongly about strategy identity, although doing so makes the classification basically moot.

2. We can also see \(d_A\) as the row-by-column interaction term in a 2-by-2 ANOVA - more on this later.

3. For example, if \(A = \begin{pmatrix}2 & -1 \\ 1 & -2 \end{pmatrix}\), then \(d_A = (2 - (-1)) - (1 - (-2)) = 3 - 3 = 0\), so player 1’s payoff splits cleanly into a row effect and a column effect with no joint dependence on player 2’s strategy.

4. Note that this doesn’t imply there isn’t a smaller separating set.

5. What I’m calling an organization of order \(|S|\) is sometimes called the \(S\)-component, or the interaction order in the ANOVA / factorial-design literature.

6. I’d conjecture that “real” games tend to be highly sparse. That is, we don’t usually have to consider the full powerset of agents when we do analysis, as only a very small number of organizations actually form. More on this later.

7. I have some evidence for this, not yet on this blog. In high dimensions, from what I can tell the generic game looks Matching-Pennies-like and is therefore unstable. Probably most high-order structure thus fails to persist, and what remains is aligned. The nature of the selection operator is still an open question.