Estimation of Skill Distribution from a Tournament

Ali Jadbabaie, Anuran Makur, Devavrat Shah

This paper, presented at NeurIPS 2020, provides a rigorous mathematical framework for a question sports fans and economists ask every day: How do we measure the "quality" or "competitiveness" of a whole league based only on win/loss records?

The Challenge of Measuring Competitiveness

In statistics, we often want to learn the "shape" of a population (a probability density function). Usually, we assume we can see samples from that population directly. However, in many real-world scenarios—like sports or finance—we don't see an agent's "true skill" number. Instead, we only see the noisy, quantized outcome of a "game": Agent A beat Agent B.

The challenge is two-fold:

  1. Noisy Data: A single win doesn't define a skill level; luck plays a role.
  2. Relative Observations: We only see how agents compare to each other, not their absolute values.

Existing research has largely focused on estimating the skill of individual players (like Elo ratings). This paper shifts the focus to the distribution of the entire population, allowing us to answer broader questions like "Is this league getting more competitive over time?" or "Are these mutual fund managers actually skilled, or just lucky?"

A Two-Stage Algorithm for Skill Distribution

The authors propose a surprisingly simple two-stage algorithm to estimate the entire probability distribution of skills in a population using only pairwise tournament results:

  1. Skill Parameter Estimation (Rank Centrality): First, they use a spectral method called "Rank Centrality." This treats the tournament as a graph where nodes are players and edges are games. By finding the "stationary distribution" of a Markov chain on this graph, they get a point estimate for each player's skill.
  2. Kernel Density Estimation (KDE): They then take these estimated skill levels and pass them through a Parzen-Rosenblatt kernel—a standard tool for smoothing data points into a continuous curve.

The "Aha!" Moment: The core technical contribution is proving that the errors introduced in Stage 1 (estimating individual skills) do not "pollute" Stage 2. They show that as the number of players ($n$) grows, the error in the final distribution estimate vanishes at the same rate as if you had known the players' exact skills from the start. They established that their method achieves a Mean Squared Error (MSE) scaling of $\tilde{O}(n^{-1+\epsilon})$, which matches the minimax lower bounds for density estimation.

Real-World Applications: Sports and Finance

The authors validated their model on several real-world datasets, including International Cricket, International Soccer, European Club Soccer, and Finance. To quantify competitiveness, they use "negative differential entropy" as a metric.

  • High Negative Entropy: The skill distribution has a tall, narrow peak. Most players are very similar in skill, making games unpredictable and the league highly competitive.
  • Low Negative Entropy: The distribution is spread out. There are clear "stars" and "bottom-feeders," making outcomes easier to predict.

The "EPL is Best" Myth

The data supports the popular belief that the English Premier League (EPL) is the most competitive among top European soccer leagues.

Skill distributions of major soccer leagues

As seen in the estimated skill distributions, the EPL's curve is the most concentrated (highest negative entropy), meaning the gap between the best and worst teams is smaller than in other leagues like Spain's La Liga or Germany's Bundesliga.

Evolution of Cricket Competitiveness

The authors also analyzed ICC World Cup data from 2003 to 2019 to see how the sport has evolved.

Evolution of skill distribution in the Cricket World Cup

They quantified the 2019 Cricket World Cup as significantly more "exciting" and competitive than earlier iterations. The 2003 version was dominated by a few powerhouses (shown by a sharper peak), whereas recent tournaments show a skill distribution closer to uniform among top teams.

Market Darwinism in Finance

In their mutual fund analysis, the authors found that the 2008 financial crisis acted as a filter. Before 2008, there was a wide spread of fund quality. After the crash, the distribution flattened and shifted, suggesting that low-skill funds were "weeded out," leaving a more competent (if more uniform) industry.

Limitations and Future Work

While powerful, the framework has some limitations:

  • Model Simplicity: The study relies on the Bradley-Terry-Luce model, which assumes the probability of winning is a simple ratio of skills. It doesn't account for home-field advantage, specific team matchups, or injuries.
  • Connectivity: The algorithm requires the tournament graph to be "connected" (i.e., you can compare any two players through a chain of matches). It may struggle with highly fragmented tournaments.
  • Direct Estimation: The authors suggest that a future direction could be developing an algorithm that estimates entropy directly from game data, rather than estimating the full distribution first.

This paper provides a robust theoretical foundation for analyzing the macro-level competitiveness of any system based on pairwise comparisons, opening new doors for sports analytics and economic modeling.

Summary updated

Abstract

In this paper, we study the problem of learning the skill distribution of a population of agents from observations of pairwise games in a tournament. These games are played among randomly drawn agents from the population. The agents in our model can be individuals, sports teams, or Wall Street fund managers. Formally, we postulate that the likelihoods of outcomes of games are governed by the parametric Bradley-Terry-Luce (or multinomial logit) model, where the probability of an agent beating another is the ratio between its skill level and the pairwise sum of skill levels, and the skill parameters are drawn from an unknown, non-parametric skill density of interest. The problem is, in essence, to learn a distribution from noisy, quantized observations. We propose a surprisingly simple and tractable algorithm that learns the skill density with near-optimal minimax mean squared error scaling as $n^{-1+\varepsilon}$, for any $\varepsilon>0$, so long as the density is smooth. Our approach brings together prior work on learning skill parameters from pairwise comparisons with kernel density estimation from non-parametric statistics. Furthermore, we prove information theoretic lower bounds which establish minimax optimality of the skill parameter estimation technique used in our algorithm. These bounds utilize a continuum version of Fano's method along with a careful covering argument. We apply our algorithm to various soccer leagues and world cups, cricket world cups, and mutual funds. We find that the entropy of a learnt distribution provides a quantitative measure of skill, which in turn provides rigorous explanations for popular beliefs about perceived qualities of sporting events, e.g., soccer league rankings. Finally, we apply our method to assess the skill distributions of mutual funds. Our results shed light on the abundance of low quality funds prior to the Great Recession of 2008, and the domination of the industry by more skilled funds after the financial crisis.
BibTeX
@inproceedings{jadbabaie2020estimation,
  author = {Ali Jadbabaie and Anuran Makur and Devavrat Shah},
  title = {{Estimation of Skill Distribution from a Tournament}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
}
Figure