# Measuring the Non-Transitivity in Chess
## 3 Theoretical Formulations and Methods
### Non-Transitivity Quantification
#### 3.3.1 Payoff Matrix Construction
For any strategy \(s\in S_{g}\), the corresponding win-rate \(TS(s)\) is

\[TS(s)=\frac{1}{|S_{g}|-1}\sum_{z\in S_{g}}I[M_{1}(s,z)>0]. \tag{4}\]

Therefore, if we define the transitive strength of a layer to be the average win-rate of the strategies within that layer, the transitive strength of the layers would be ordered in descending order. Hence, intuitively, one can see the \(k\)-layered finite game of skill geometry as separating the transitive and non-transitive components of the strategy space. Thenon-transitivity is contained within each layer, whereas the transitivity variation happens across layers. It is, thus, intuitive to use the layer sizes as a measure of non-transitivity. Furthermore, in Definition 5, the layer size increases monotonically up to a certain layer, from which it then decreases monotonically. Thus, when the transitive strength of each layer is plotted against its size, a two-dimensional spinning top structure would be observed if the change in size is strictly monotonic and \(k>2\). It is also for this reason that [5] named this geometry the spinning top geometry. For every finite game, while there always exists \(k\geq 1\) for which the game is a \(k\)-layered finite game of skill, a value of \(k>1\) does not always exist for any game; furthermore, the layered geometry is not useful if \(k=1\). Therefore, a relaxation to the \(k\)-layered geometry is required. In this alternative, a layer is only required to be \"overall better\" than the succeeding layers; however, it is not necessary that every strategy in a given layer beats every strategy in any succeeding layers. Such a layer structure was obtained through Nash Clustering. Let \(\text{Nash}(\mathbf{\mathcal{M}}|X)\), where \(X\subset S_{g}\), denote the symmetric NE of a two-player zero-sum symmetric game, in which both players are restricted to only the strategies in \(X\), and \(\mathbf{\mathcal{M}}\) is the payoff matrix from the perspective of player \(1\). Furthermore, let \(\text{supp}(\text{Nash}(\mathbf{\mathcal{M}}|X))\) denote the set of pure strategies that are in support of the symmetric NE. Finally, let the set notation \(A\setminus B\) denote the set \(A\) excluding the elements that are in set \(B\). **Definition 6**. : _Nash Clustering of a finite two-player zero-sum symmetric game produces a set of clusters \(C\), defined as_

\[C =\{C_{j}:j\in\mathbb{N}_{1},C_{j}\
eq\emptyset\},\ \text{ where }\] \[C_{0} =\emptyset,\ \ C_{i}=supp\Big{(}\text{Nash}(\mathbf{\mathcal{M}}|S_{g} \setminus\bigcup_{k=0}^{i-1}C_{k})\Big{)},\ \ \ \forall i\geq 1. \tag{5}\]

Furthermore, to ensure that the Nash Clustering procedure is unique, we use the maximum entropy NE in Equation 1. Following Nash Clustering, the measure of non-transitivity would, thus, be the size or number of strategies in each cluster. We then applied the Relative Population Performance (RPP) [27] to determine whether a layer or cluster is overall better than another cluster. Given two Nash clusters \(C_{i}\) and \(C_{j}\), \(C_{i}\) is overall better or wins against \(C_{j}\) if \(\text{RPP}(C_{i},C_{j})>0\). When using the RPP as a relative cluster performance measure, the requirement that any given cluster is overall better than any succeeding clusters proves to hold [5]. Following this, one can then use the fraction of clusters beaten, or win-rate, defined in Equation 6, as the measure of transitive strength of each cluster:

\[TS(C_{a})=\frac{1}{|C|-1}\sum_{C_{i}\in C}I\Big{[}\text{RPP}\big{(}C_{a},C_{i} \big{)}>0\Big{]}, \tag{6}\]

where \(I\) is the indicator function. We refer to the above win-rate as the RPP win-rate. Using the RPP win-rate as the measure of transitive strength of a Nash cluster guarantees that the transitive strength of Nash clusters are arranged in descending order. **Theorem 2**. : _Let \(C\) be the Nash Clustering of a two-player zero-sum symmetric game. Then, \(TS(C_{i})>TS(C_{j})\ \forall i<j,C_{i},C_{j}\in C\)._

Proof. : Let \(C\) be the Nash Clustering of a two-player zero-sum symmetric game.