# Measuring the Non-Transitivity in Chess
## 3 Theoretical Formulations and Methods
### Non-Transitivity Quantification
#### 3.3.1 Payoff Matrix Construction
Let \(C_{i},C_{j}\in C\) where \(i<j,i,j\in[|C|]\). Let \(n_{i}=\sum_{c\in C}I[\text{RPP}(C_{i},c)>0]\) and \(n_{j}=\sum_{c\in C}I[\text{RPP}(C_{j},c)>0]\). Using the fact that \(\text{RPP}(C_{i},C_{j})\geq 0\ \forall i\leq j,C_{i},C_{j}\in C\), as proven in [5], \(n_{i}=|C|-i\) and \(n_{j}=|C|-j\). As \(i<j\), therefore, \(n_{j}<n_{i}\) and since \(TS(C_{i})=\frac{n_{i}}{|C|-1}\) and \(TS(C_{j})=\frac{n_{j}}{|C|-1}\), then \(TS(C_{i})>TS(C_{j})\). However, working with real data allowed us to use an alternative measure of transitive strength. We used the average Elo rating in Equation (2) of the pure strategies inside each Nash cluster to measure the transitive strength of the cluster. Specifically, given the payoff matrix from Section 3.3.1, each pure strategy corresponds to an Elo rating bin, and the transitive strength of a Nash cluster is therefore taken to be the average Elo rating of the bins inside that cluster. Let \(C_{k}\in C\) be a Nash cluster, \(c_{k}\) be the integer indices of the pure strategies in support of \(C_{k}\), and \(B=\{b_{1},...,b_{m}\}\) be the bins used when constructing the payoff matrix, where each bin \(b_{i}\) has lower and upper bounds \((b_{i}^{t},b_{i}^{H})\), such that the bins corresponding to \(C_{k}\) are \(\{b_{j}\}_{j\in C_{k}}\). The average Elo rating of the Nash cluster \(C_{k}\) is defined as

\[TS_{\text{Elo}}(C_{k})=\frac{1}{|C_{k}|}\sum_{j\in C_{k}}\frac{b_{j}^{L}+b_{j}^ {H}}{2}. \tag{7}\]

Given the average Elo rating against the cluster size for every Nash cluster, the final step would be to fit a curve to illustrate the spinning top geometry. For this purpose, we fitted an affine-transformed skewed normal distribution by minimising the Mean Squared Error (MSE). This completed the procedure of Nash Clustering using the average Elo rating as the measure of transitive strength. In addition to using the average Elo rating, we also investigated the use of win-rates as a measure of transitive strength, as defined in Equation (6). However, instead of using the RPP to define the relative performance between clusters, we used a more efficient metric that achieves the same result when applied to Nash clusters. We refer to this metric as the Nash Population Performance (NPP). Definition 7: Let \(C=\{C_{1},...,C_{|C|}\}\) be the Nash Clustering of a two-player zero-sum symmetric game with payoff matrix \(\mathbf{\mathcal{M}}\). \(NPP(C_{i},C_{j})=\mathbf{p_{i}}^{\top}\mathbf{\mathcal{M}}\mathbf{p_{j}}\), where \(\mathbf{p_{k}}=\text{Nash}(\mathbf{\mathcal{M}}|\bigcup_{r=k}^{|C|}C_{r}\) for \(k\in[|C|]\) and \(C_{i},C_{j}\in C\). Using NPP also satisfies the requirement that any cluster is overall better than the succeeding clusters. Theorem 3: _Let \(C\) be the Nash Clustering of a two-player zero-sum symmetric game. Then, \(NPP(C_{i},C_{j})\geq 0\ \forall i\leq j\), \(C_{i},C_{j}\in C\), and \(NPP(C_{i},C_{j})\leq 0\ \forall i>j\), \(C_{i},C_{j}\in C\)._

The proof of Theorem 3 is given in Appendix C.

Theorem 3 suggests that applying the NPP to compute Equation (6) instead of the RPP would result in an identical win-rate for any Nash cluster, and the descending win-rate guarantee is preserved. Using the NPP is more efficient as, in Definition 7, \(\mathbf{p_{k}}\) for any Nash cluster is the corresponding NE solved during Nash Clustering to obtain that cluster; however, this means that the NPP is more suitable as a relative performance measure of Nash clusters, but less so for general population of strategies. For the latter, the RPP would be more suitable. #### 3.3.3 Rock-Paper-Scissor Cycles

Intuitively, a possible second method to quantify non-transitivity is to measure the length of the longest cycle in the strategy space, as this stems directly from the definition of non-transitivity. A cycle is defined as the sequence of strategies that starts and ends with the same strategy, where any strategy beats the immediate subsequent strategy in the sequence. However, calculating the length of the longest cycle in a directed graph is well-known to be NP-hard [28].