Deep Dives with Lichess II: Transitivity in Chess

Transitivity, in essence, means that objects can be ordered or ranked linearly, dismissing the existence of cycles. For example, height is transitive; it is impossible to find three people such that the first is taller than the second, who is taller than the third, who is taller… than… the first? However, in other situations, cyclic behavior is entirely expected, such as in the game of Rock Papers Scissors: rock always beats scissors, which always beats paper, which always beats rock. In this second post of our Lichess.org series, we took a deeper dive into the Lichess.org dataset to investigate the prevalence of transitivity-breaking cycles in chess.^{1 2}

A. Elo Rating System

The Elo chess rating system is currently in use by the U.S. and international chess federations to rate and match players. In Elo, a player’s rating is updated after each game based on the player’s expected versus actual performance. The system was adopted by the U.S. Chess Federation in 1960, replacing the Harkness Rating System, which does not consider the players’ ratings and the expected outcomes of games in its update mechanism. This simpler system compares a player’s rating to the average and updates it considering only wins, losses, and draws. Elo has since been applied to various sports, video games, even dating apps and animal behavior research.

B. Transitivity

An important assumption resting behind 1-dimensional ranking systems such as Elo is transitivity, which is key for ordering elements of a set (or, more simply, for ordering numbers on a line). Transitivity borrows this ordering structure to, perhaps sometimes artificially, impose the same structure to sets other than numbers (e.g., for ranking preferences and determining “what is better”).

More precisely, for a given set and a relation between elements of the set, say >, the relation is transitive if for every three elements a, b, and c such that a > b and b > c, then a > c.

But is it possible to find three chess players, say Altan, Bhavesh, and Cecília, such that Altan consistently beats Bhavesh, Bhavesh consistently beats Cecília, but Cecília consistently beats Altan? Altan may be strong against common openings but has little experience with unorthodox ones, which are often played by Cecília. Bhavesh, on the other hand, never deviates from the same opening– which Altan has mastered playing against, but which happens to be Cecília’s weakness.

Balduzzi et. al (2018) point out that “Elo bakes-in the assumption that relative skill is transitive; but Elo is meaningless – it has no predictive power – in cyclic games like rock-paper-scissors”³. The authors investigate the algebraic structure behind pairwise comparisons and find that there are two main components: a transitive component and a cyclic component.⁴ The latter, they show, cannot be handled by many ranking systems, including Elo. However, no statements are made about the possibility of cyclicality in chess.

C. Analysis

To investigate the prevalence of transitivity-breaking cycles in chess, we used all Lichess.org Bullet data from January 2013 to June 2021, a total of 9.6 million games.⁵ Although we consider a large timeframe, we limit our analysis to intra-month comparisons and, in the end, aggregate the monthly results. This is to avoid comparing wins and losses at different stages of a player’s skill level.

Finding transitivity breaking triplets means identifying three players, say A, B, and C, such that A consistently beats B, B consistently beats C, and C consistently beats A. To handle the idea of consistent wins, we defined a win-ratio w and set a threshold n for the minimum number of games played by a pair of agents. In other words, for any two players A and B, we say that A consistently beats B whenever A and B have played a minimum of n games together and A’s win ratio against B is greater than or equal to w.

There are tradeoffs in setting n and w. For instance, it is desirable to have high w and high, but it is not often that any two given players have played a large number of games together. For varying minimum number of games and win ratios, the eligible number of triplets are detailed below along with the number of triplets that break transitivity.⁶ Every set of three players such that each has played at least n games with every other is considered an eligible triplet. A triplet breaks transitivity whenever the win-ratios satisfying w cause a cycle between the players in the triplet.

The table above shows that there are not many occurrences of cycles, especially with stronger win ratios and higher numbers of minimum games.⁷ This suggests that the cyclic component of chess is minor, perhaps even fully unimportant. However, a clearer picture would be provided with a higher number of eligible triplets when the minimum number of games is higher.

Although, based on the Lichess data, transitivity-breaking triplets are infrequent in chess, they do occur. Are they equally distributed across ratings? Are there just as many cycles among lower-ranked players than higher-ranked players? To investigate this, we created buckets of ratings in 100-point intervals (e.g., 1600-1699 are classified as “1600”). Then, we averaged the rating of the players in the transitivity-breaking triplets, and made the plot below, where the x-axis has the ratings, the y-axis the proportion of transitivity-breaking cycles, and different colored lines for varying win-ratios.

As suggested in Table 1, we see that as the win-ratio increases, the overall number of cycles decreases. The above figure suggests the possibility of a bimodal distribution of transitivity-breaking triplets in lower and higher ratings. However, unfortunately, a full analysis of the distribution of cycles is outside the scope of this blog post.

But who are these cyclic players? We identified three highly ranked Lichess players and found that Grandmasters Fidel Corrales and Oliver Barbosa, together with FIDE Master Manu David form a transitivity-breaking triplet (their Lichess usernames, respectively, are ficorrales, vroeli, and FlamingFM, with respective ratings of 2829, 2885, and 2855). Fidel has played 16 games against Manu, winning 68.8% of the time, while Manu has played 13 games against Oliver, winning 69.2% of the time. Lastly, Oliver has won against Fidel 65% of the time over 20 games.

Based on the enormous Lichess dataset, we conclude that the cyclic component in chess is not strong enough to cast significant doubt over Elo and similar ranking systems.

Before closing this blog post, we will briefly mention a bit of game theory and the fascinating literature of social choice theory, where similar themes to those elaborated in this blog post have or are starting to make noise.

D. Similar Themes in Game Theory and Social Choice Theory

Game theory, at its most basic, is the mathematical study of strategic interactions. Social choice theory is chiefly concerned with voting systems that combine group opinion or choice to maximize a certain set of objectives or criteria, usually relating to fairness and welfare. A recent algebraic decomposition of games by Jessie and Saari (2019) shows that many techniques of computing solutions of games, including the Nash equilibrium, do not consider certain components of the game’s structure.⁸ To put it another way, there is a component of games that contains all information necessary to compute Nash equilibria and other similar solution concepts, and nothing more. But there are other components, too. Jessie and Kendall (2015) devised a set of game theory experiments to test human response to changes in one of these components and found that the influence is nontrivial.⁹ This is impactful: much like there are pairwise comparisons where a system like Elo may be inappropriate (e.g., Rock Paper Scissors), there are games (in the game theoretic sense) where the Nash equilibrium misses exactly what is being sought.

Social choice theory arguably began with considerations of Plato, and maybe even before. But the introduction of a particular voting method by Condorcet in the 18th century stimulated concerns about the legitimacy of certain voting methods in reflecting the actual views of the voters. This area has since been haunted by paradoxes, where “cycles” play a leading role. Condorcet believed that majority rule is a good candidate for aggregating social choice but recognized that such a method could mysteriously allow counter-intuitive results. Much later, in the 20th century, additional paradoxes were discussed by Arrow’s famous impossibility theorem and Sen’s liberal paradox (1952 and 1970, respectively). Arrow’s theorem very roughly states that there exists no fair voting system.¹⁰ Sen’s paradox, similarly, purports that in certain conditions a social planner is forced to choose Pareto inferior outcomes.¹¹

These paradoxes have received significant attention in the literature. Saari pioneered geometric techniques of investigating transitivity-breaking cycles behind both Arrow’s and Sen’s theorems. In short, certain voting systems reduce voters’ preferences to one dimension which, due to additional nuance in the original preference structure, can cause cycles. In some sense, this is exactly what is going on with the Elo system applied to games with cyclic structures. Saari’s geometric techniques allow one to construct paradoxes and even “cook up” voting systems that allow any candidate to win. (That is not part of our consulting work, sorry.) Stay tuned for our next post in our Deep Dives with Lichess series. If you have any specific chess curiosities, please feel free to contact us at info@iamecon.com.