# Measuring the Non-Transitivity in Chess
## 3 Theoretical Formulations and Methods
### Game Theory Preliminaries
#### 3.1.1 Normal Form (NF) Games  
In NF games, every player takes a single action simultaneously. Such games are fully defined by a payoff matrix \(\boldsymbol{\mathcal{M}}\), where  
\[\boldsymbol{\mathcal{M}}_{d_{1},d_{2},...,d_{n}}=\big{\{}M_{1}(a_{1},a_{2},...,a_{n}),...,M_{n}(a_{1},a_{2},...,a_{n})\big{\}},\]  
with \(a_{k}\in A_{k}\), \(d_{k}\in[|A_{k}|]\), \(k\in[n]\), \(A_{k}\) denoting the action space of the \(k^{\text{th}}\) player, and \(d_{k}\) denoting the index corresponding to \(a_{k}\). \(\boldsymbol{\mathcal{M}}\) fully specifies an NF game as it contains all the components of a game by Definition 1. In an NF game, the strategy adopted by a player is the single action taken by that player. Therefore, the action space \(A_{k}\) is equivalent to the strategy space \(S_{k}\) for \(k\in[n]\).  
An NF game is zero-sum when \(\sum_{\varepsilon\in\mathcal{M}_{d_{1},...,d_{n}}}z=0\) for \(d_{k}\in[|A_{k}|]\), \(k\in[n]\). For two-player zero-sum NF games, the entries of \(\boldsymbol{\mathcal{M}}\) can, therefore, be represented by a single number, as the payoff of one player is the negative of the other. Additionally, if the game is symmetric (i.e., both players have identical strategy spaces), then the matrix \(\boldsymbol{\mathcal{M}}\) is skew-symmetric.  
A well-known solution concept that describes the equilibrium of NF games is the Nash Equilibrium (NE) [6; 21]. Let \(\mathbf{p_{i}}(s)\), where \(s\in S_{i}\), \(\mathbf{p_{i}}\in\Delta_{|S_{i}|}\), and \(i\in[n]\), denote the probability of player \(i\) playing the pure strategy \(s\) according to probability vector \(\mathbf{p_{i}}\). Additionally, let \(p=\{\mathbf{p_{1}},...,\mathbf{p_{n}}\}\), and \(p[j:\mathbf{k}]\) denote changing the \(j^{\text{th}}\) element in \(p\) to the probability vector \(\mathbf{k}\), where \(\mathbf{k}\in\Delta_{|S_{j}|}\).  
**Definition 2**.: _The set of distributions \(p^{*}\), where \(p^{*}=\{\mathbf{p_{1}^{*}},...,\mathbf{p_{n}^{*}}\}\) and \(\mathbf{p_{1}^{*}}\in\Delta_{|S_{i}|}\;\forall i\in[n]\), is an NE if \(\sum_{s\in S}p^{*}(s)M_{i}(s)\geq\sum_{s\in S}p^{*}[i:\mathbf{e_{k}^{|S_{i}|} }](s)M_{i}(s)\;\forall i\in[n]\), \(k\in[|S_{i}|]\), where \(p^{*}(s)=\prod_{j\in[n]}\mathbf{p_{j}^{*}}(s_{j})\) and \(s=\{s_{1},...,s_{n}\}\), \(s_{i}\in S_{i}\;\forall i\in[n]\)._  
Definition 2 implies that, under an NE, no player can increase their expected payoff by unilaterally deviating to a pure strategy. While such an NE always exists [6], it might not be unique. To guarantee the uniqueness of the obtained NE, we apply the maximum entropy condition when solving for the NE. The maximum-entropy NE has been proven to be unique [22].  
**Theorem 1**.: _Any two-player zero-sum symmetric game always has a unique maximum entropy NE, given by \(\{\mathbf{p^{*}},\mathbf{p^{*}}\}\) where \(\mathbf{p^{*}}\in\Delta_{|S_{g}|}\), where \(S_{g}\) is the strategy space for each of the two players [22]._  
As a consequence of Theorem 1, finding the maximum entropy NE of a two-player zero-sum symmetric game amounts to solving the Linear Programming (LP) problem shown in Equation (1):  
\[\mathbf{p^{*}}=\operatorname*{arg\,max}_{\mathbf{P}}\sum_{j\in[|S _{g}|]}-\mathbf{p}_{j}\log\mathbf{p}_{j}\] \[\text{s. t.}\quad\mathcal{M}\mathbf{p}\leq\mathbf{0}_{|S_{g}|}\] \[\mathbf{p}\geq\mathbf{0}_{|S_{g}|}\] \[\mathbf{1}_{|S_{g}|}^{\top}\mathbf{P}=1, \tag{1}\]  
where \(\boldsymbol{\mathcal{M}}\) is the skew-symmetric payoff matrix of the first player.