Intransitive Game Simulation


Suppose you have a symmetric two player game with skew-symmetric payoff matrix \(M\). If player \(v\) faces off against \(u\), the payout for \(v\) is \(v^TMu\). For rock-paper-scissors, the matrix is \[ M = \begin{bmatrix} 0 & 1 & -1 \\ -1 & 0 & 1 \\ 1 &-1 & 0 \end{bmatrix} \] and the players are the elementary unit vectors. Using the spectral theorem, one can show that any skew-symmetric \(n\times n\) matrix \(M\) is similar to a matrix of the form \[ \begin{bmatrix} &I\\-I \end{bmatrix} \text{ when }n\text{ is even or } \begin{bmatrix} &I&0\\-I&&0\\0&0&0 \end{bmatrix} \,\text{when }n\text{ is odd}. \] For simplicity, we focus on the case of \(n\) even. So, by applying the appropriate change-of-basis to the players (which are vectors), and breaking each vector in half, i.e. writing \(v=\begin{bmatrix}v_1\\v_2\end{bmatrix}\), the outcome of \(v\) facing off with \(u\) is \[ \langle u_2,v_1\rangle-\langle u_1,v_2\rangle. \] The simulation populates each cell in the grid with a random Guassian vector. Each time step, some number of edges are sampled at random from the grid and the neighbors "battle". The winning player "conquers" their neighbor by copying over itself plus a small perturbation. Colors are generated by projecting the vector at each cell (i.e. the player controlling that cell) to \(\mathbb{R}^3\), applying the sigmoid function entry-wise, and interpreting each entry as an RGB color channel. Each line segment in the diagram on the right represents a cell. The endpoints are \((v_1, v_2)\), and the \(v_1\) endpoint is emphasized.

Proof of similarity

By the spectral theorem, for general \(M\) we may write \[M = PDP^*\] for some unitary \(P\) and diagonal \(D\). Since the entries of \(M\) are real, the columns of \(P\) and entries of \(M\) come in conjugate pairs. Furthermore, \(M\) is skew-symmetric so the entries of \(D\) are pure-imaginary. We may use the unitary gaget \(G = I\otimes \begin{bmatrix}1&1\\i&-i\end{bmatrix}/\sqrt2\) to replace adjacent columns \([v\quad\bar v]\) in \(P\) with \(\sqrt2[\text{Re}(v)\quad\text{Im}(v)]\), and consecutive entries \(\begin{bmatrix}\lambda i\\&-\lambda i\end{bmatrix}\) in \(D\) with \(\begin{bmatrix}&\lambda\\-\lambda\end{bmatrix}\). We do this by reformulating the decomposition of \(M\) as \[M = (PG^*)\cdot(GDG^*)\cdot(GP^*)\] where both \(GP^*\) and \(GDG^*\) are now real. If we collect all the \(\lambda\)s into \(\Lambda\) and re-index the rows and columns, we have \[ GDG^*=\begin{bmatrix}&\Lambda\\-\Lambda\end{bmatrix} \] which allows the futher factorization \[ M = (PG^*) \cdot \begin{bmatrix}\Lambda^{1/2}\\&\Lambda^{1/2}\end{bmatrix} \cdot \begin{bmatrix}&I\\-I\end{bmatrix} \cdot \begin{bmatrix}\Lambda^{1/2}\\&\Lambda^{1/2}\end{bmatrix} (GP^*) \] Finally, for a given player \(v\), denote \[ \begin{bmatrix}\tilde v_1\\\tilde v_2\end{bmatrix}=\begin{bmatrix}\Lambda^{1/2}\\&\Lambda^{1/2}\end{bmatrix}GP^*v \] and similarly for \(u\) so that the outcome \(u^TMv\) is simply \[ u^TMv=\langle\tilde u_2,\tilde v_1\rangle - \langle\tilde u_1,\tilde v_2\rangle. \]