# An Elo-like System for Massive Multiplayer Competitions

Aram Ebtekar  VancouverBCCanada<EMAIL_ADDRESS>and  Paul Liu  Stanford
UniversityStanfordCAUSA<EMAIL_ADDRESS>
###### Abstract.

Rating systems play an important role in competitive sports and games. They
provide a measure of player skill, which incentivizes competitive performances
and enables balanced match-ups. In this paper, we present a novel Bayesian
rating system for contests with many participants. It is widely applicable to
competition formats with discrete ranked matches, such as online programming
competitions, obstacle courses races, and some video games. The simplicity of
our system allows us to prove theoretical bounds on robustness and runtime. In
addition, we show that the system _aligns incentives_ : that is, a player who
seeks to maximize their rating will never want to underperform.
Experimentally, the rating system rivals or surpasses existing systems in
prediction accuracy, and computes faster than existing systems by up to an
order of magnitude.

##  1\. Introduction

Competitions, in the form of sports, games, and examinations, have been with
us since antiquity. Many competitions grade performances along a numerical
scale, such as a score on a test or a completion time in a race. In the case
of a college admissions exam or a track race, scores are standardized so that
a given score on two different occasions carries the same meaning. However, in
events that feature novelty, subjectivity, or close interaction,
standardization is difficult. The Spartan Races, completed by millions of
runners, feature a variety of obstacles placed on hiking trails around the
world (Spa, [n.d.]). Rock climbing, a sport to be added to the 2020 Olympics,
likewise has routes set specifically for each competition. DanceSport,
gymnastics, and figure skating competitions have a panel of judges who rank
contestants against one another; these subjective scores are known to be noisy
(Premelč et al., 2019). Most board games feature considerable inter-player
interaction. In all these cases, scores can only be used to compare and rank
participants at the same event. Players, spectators, and contest organizers
who are interested in comparing players’ skill levels across different
competitions will need to aggregate the entire history of such rankings. A
strong player, then, is one who consistently wins against weaker players. To
quantify skill, we need a _rating system_.

Good rating systems are difficult to create, as they must balance several
mutually constraining objectives. First and foremost, the rating system must
be accurate, in that ratings provide useful predictors of contest outcomes.
Second, the ratings must be efficient to compute: in video game applications,
rating systems are predominantly used for matchmaking in massively multiplayer
online games (such as Halo, CounterStrike, League of Legends, etc.) (Herbrich
et al., 2006; Minka et al., 2018; Yang et al., 2014). These games have
hundreds of millions of players playing tens of millions of games per day,
necessitating certain latency and memory requirements for the rating system
(Agarwal and Lorch, 2009). Third, the rating system must align incentives.
That is, players should not modify their performance to “game” the rating
system. Rating systems that can be gamed often create disastrous consequences
to player-base, more often than not leading to the loss of players from the
game (pok, [n.d.]). Finally, the ratings provided by the system must be human-
interpretable: ratings are typically represented to players as a single number
encapsulating their overall skill, and many players want to understand and
predict how their performances affect their rating (Glickman, 1995).

Classically, rating systems were designed for two-player games. The famous Elo
system (Elo, 1961), as well as its Bayesian successors Glicko and Glicko-2,
have been widely applied to games such as Chess and Go (Glickman, 1995, 1999,
2012). Both Glicko versions model each player’s skill as a real random
variable that evolves with time according to Brownian motion. Inference is
done by entering these variables into the Bradley-Terry model, which predicts
probabilities of game outcomes. Glicko-2 refines the Glicko system by adding a
rating volatility parameter. Unfortunately, Glicko-2 is known to be flawed in
practice, potentially incentivising players to lose. This was most notably
exploited in the popular game of Pokemon Go (pok, [n.d.]); see Section 5.1 for
a discussion of this issue.

The family of Elo-like methods just described only utilize the binary outcome
of a match. In settings where a scoring system provides a more fine-grained
measure of match performance, Kovalchik (Kovalchik, 2020) has shown variants
of Elo that are able to take advantage of score information. For competitions
consisting of several set tasks, such as academic olympiads, Forišek (Forišek,
2009) developed a model in which each task gives a different “response” to the
player: the total response then predicts match outcomes. However, such systems
are often highly application-dependent and hard to calibrate.

Though Elo-like systems are widely used in two-player contests, one needn’t
look far to find competitions that involve much more than two players. Aside
from the aforementioned sporting examples, there are video games such as
CounterStrike and Halo, as well as academic olympiads: notably, programming
contest platforms such as Codeforces, TopCoder, and Kaggle (Cod, [n.d.]b; Top,
[n.d.]; Kag, [n.d.]). In these applications, the number of contestants can
easily reach into the thousands. Some more recent works present interesting
methods to deal with competitions between two teams (Huang et al., 2006; Chen
and Joachims, 2016; Li et al., 2018; Gong et al., 2020), but they do not
present efficient extensions for settings in which players are sorted into
more than two, let alone thousands, of distinct places.

In a many-player ranked competition, it is important to note that the pairwise
match outcomes are not independent, as they would be in a series of 1v1
matches. Thus, TrueSkill (Herbrich et al., 2006) and its variants (Nikolenko
et al., 2010; Dangauthier et al., 2007; Minka et al., 2018) model a player’s
performance during each contest as a single random variable. The overall
rankings are assumed to reveal the total order among these hidden performance
variables, with various strategies used to model ties and teams. These
TrueSkill algorithms are efficient in practice, successfully rating userbases
that number well into the millions (the Halo series, for example, has over 60
million sales since 2001 (Hal, [n.d.])).

The main disadvantage of TrueSkill is its complexity: originally developed by
Microsoft for the popular Halo video game, TrueSkill performs approximate
belief propagation on a factor graph, which is iterated until convergence
(Herbrich et al., 2006). Aside from being less human-interpretable, this
complexity means that, to our knowledge, there are no proofs of key properties
such as runtime and incentive alignment. Even when these properties are
discussed (Minka et al., 2018), no rigorous justification is provided. In
addition, we are not aware of any work that extends TrueSkill to non-Gaussian
performance models, which might be desirable to limit the influence of outlier
performances (see Section 5.2).

It might be for these reasons that platforms such as Codeforces and TopCoder
opted for their own custom rating systems. These systems are not published in
academia and do not come with Bayesian justifications. However, they retain
the formulaic simplicity of Elo and Glicko, extending them to settings with
much more than two players. The Codeforces system includes ad hoc heuristics
to distinguish top players, while curbing rampant inflation. TopCoder’s
formulas are more principled from a statistical perspective; however, it has a
volatility parameter similar to Glicko-2, and hence suffers from similar
exploits (Forišek, 2009). Despite their flaws, these systems have been in
place for over a decade, and have more recently gained adoption by additional
platforms such as CodeChef and LeetCode (Lee, [n.d.]; Cod, [n.d.]a).

#### Our contributions

In this paper, we describe the Elo-MMR rating system, obtained by a principled
approximation of a Bayesian model very similar to TrueSkill. It is fast,
embarrassingly parallel, and makes accurate predictions. Most interesting of
all, its simplicity allows us to rigorously analyze its properties: the “MMR”
in the name stands for “Massive”, “Monotonic”, and “Robust”. “Massive” means
that it supports any number of players with a runtime that scales linearly;
“monotonic” means that it _aligns incentives_ so that a rating-maximizing
player always wants to perform well; “robust” means that rating changes are
bounded, with the bound being smaller for more consistent players than for
volatile players. Robustness turns out to be a natural byproduct of accurately
modeling performances with heavy-tailed distributions, such as the logistic.
TrueSkill is believed to satisfy the first two properties, albeit without
proof, but fails robustness. Codeforces only satisfies aligned incentives, and
TopCoder only satisfies robustness.

Experimentally, we show that Elo-MMR achieves state-of-the-art performance in
terms of both prediction accuracy and runtime. In particular, we process the
entire Codeforces database of over 300K rated users and 1000 contests in well
under a minute, beating the existing Codeforces system by an order of
magnitude while improving upon its accuracy. A difficulty we faced was the
scarcity of efficient open-source rating system implementations. In an effort
to aid researchers and practitioners alike, we provide open-source
implementations of all rating systems, datasets, and additional processing
used in our experiments at https://github.com/EbTech/EloR/.

#### Organization

In Section 2, we formalize the details of our Bayesian model. We then show how
to estimate player skill under this model in Section 3, and develop some
intuitions of the resulting formulas. As a further refinement, Section 4
models skill evolutions from players training or atrophying between
competitions. This modeling is quite tricky as we choose to retain players’
momentum while ensuring it cannot be exploited for incentive-misaligned rating
gains. Section 5 proves that the system as a whole satisfies several salient
properties, the most critical of which is aligned incentives. Finally, we
present experimental evaluations in Section 6.

##  2\. A Bayesian Model for Massive Competitions

We now describe the setting formally, denoting random variables by capital
letters. A series of competitive rounds, indexed by $t=1,2,3,\ldots$, take
place sequentially in time. Each round has a set of participating players
$\mathcal{P}_{t}$, which may in general overlap between rounds. A player’s
skill is likely to change with time, so we represent the skill of player $i$
at time $t$ by a real random variable $S_{i,t}$.

In round $t$, each player $i\in\mathcal{P}_{t}$ competes at some performance
level $P_{i,t}$, typically close to their current skill $S_{i,t}$. The
deviations $\\{P_{i,t}-S_{i,t}\\}_{i\in\mathcal{P}_{t}}$ are assumed to be
i.i.d. and independent of $\\{S_{i,t}\\}_{i\in\mathcal{P}_{t}}$.

Performances are not observed directly; instead, a ranking gives the relative
order among all performances $\\{P_{i,t}\\}_{i\in\mathcal{P}_{t}}$. In
particular, ties are modelled to occur when performances are exactly equal, a
zero-probability event when their distributions are continuous.111 The
relevant limiting procedure is to treat performances within $\epsilon$-width
buckets as ties, and letting $\epsilon\rightarrow 0$. This technicality
appears in the proof of Theorem 3.3. This ranking constitutes the
observational evidence $E_{t}$ for our Bayesian updates. The rating system
seeks to estimate the skill $S_{i,t}$ of every player at the present time $t$,
given the historical round rankings $E_{\leq t}:=\\{E_{1},\ldots,E_{t}\\}$.

We overload the notation $\Pr$ for both probabilities and probability
densities: the latter interpretation applies to zero-probability events, such
as in $\Pr(S_{i,t}=s)$. We also use colons as shorthand for collections of
variables differing only in a subscript: for instance,
$P_{:,t}:=\\{P_{i,t}\\}_{i\in\mathcal{P}_{t}}$. The joint distribution
described by our Bayesian model factorizes as follows:

(1) $\displaystyle\Pr(S_{:,:},P_{:,:},E_{:})$
$\displaystyle=\prod_{i}\Pr(S_{i,0})\prod_{i,t}\Pr(S_{i,t}\mid
S_{i,t-1})\prod_{i,t}\Pr(P_{i,t}\mid S_{i,t})\prod_{t}\Pr(E_{t}\mid P_{:,t}),$
$\displaystyle\text{where }\Pr(S_{i,0})$ is the initial skill prior,
$\displaystyle\Pr(S_{i,t}\mid S_{i,t-1})$ is the skill evolution model
(Section 4), $\displaystyle\Pr(P_{i,t}\mid S_{i,t})$ is the performance model,
and $\displaystyle\Pr(E_{t}\mid P_{:,t})$ is the evidence model.

For the first three factors, we will specify log-concave distributions (see
Definition 3.1). The evidence model, on the other hand, is a deterministic
indicator. It equals one when $E_{t}$ is consistent with the relative ordering
among $\\{P_{i,t}\\}_{i\in\mathcal{P}_{t}}$, and zero otherwise.

Finally, our model assumes that the number of participants $|\mathcal{P}_{t}|$
is large. The main idea behind our algorithm is that, in sufficiently massive
competitions, from the evidence $E_{t}$ we can infer very precise estimates
for $\\{P_{i,t}\\}_{i\in\mathcal{P}_{t}}$. Hence, we can treat these
performances as if they were observed directly.

That is, suppose we have the skill prior at round $t$:

(2) $\pi_{i,t}(s):=\Pr(S_{i,t}=s\mid P_{i,<t}).$

Now, we observe $E_{t}$. By Equation 1, it is conditionally independent of
$S_{i,t}$, given $P_{i,\leq t}$. By the law of total probability,

$\displaystyle\Pr(S_{i,t}=s\mid P_{i,<t},\,E_{t})$
$\displaystyle=\int\Pr(S_{i,t}=s\mid P_{i,<t},\,P_{i,t}=p)\Pr(P_{i,t}=p\mid
P_{i,<t},\,E_{t})\,\mathrm{d}p$ $\displaystyle\rightarrow\Pr(S_{i,t}=s\mid
P_{i,\leq t})\quad\text{almost surely as }|\mathcal{P}_{t}|\rightarrow\infty.$

The integral is intractable in general, since the performance posterior
$\Pr(P_{i,t}=p\mid P_{i,<t},\,E_{t})$ depends not only on player $i$, but also
on our belief regarding the skills of all $j\in\mathcal{P}_{t}$. However, in
the limit of infinite participants, Doob’s consistency theorem (Freedman,
1963) implies that it concentrates at the true value $P_{i,t}$. Since our
posteriors are continuous, the convergence holds for all $s$ simultaneously.

Indeed, we don’t even need the full evidence $E_{t}$. Let
$E^{L}_{i,t}=\\{j\in\mathcal{P}:P_{j,t}>P_{i,t}\\}$ be the set of players
against whom $i$ lost, and $E^{W}_{i,t}=\\{j\in\mathcal{P}:P_{j,t}<P_{i,t}\\}$
be the set of players against whom $i$ won. That is, we only see who wins,
draws, and loses against $i$. $P_{i,t}$ remains identifiable using only
$(E^{L}_{i,t},E^{W}_{i,t})$, which will be more convenient for our purposes.

Passing to the limit $|\mathcal{P}_{t}|\rightarrow\infty$ serves to justify
some common simplifications made by algorithms such as TrueSkill: since
conditioning on $P_{i,\leq t}$ makes the skills of different players
independent of one another, it becomes accurate to model them as such. In
addition to simplifying derivations, this fact ensures that a player’s
posterior is unaffected by rounds in which they are not a participant,
arguably a desirable property in its own right. Furthermore, $P_{i,\leq t}$
being a sufficient statistic for skill prediction renders any additional
information, such as domain-specific raw scores, redundant.

Finally, a word on the rate of convergence. Suppose we want our estimate to be
within $\epsilon$ of $P_{i,t}$, with probability at least $1-\delta$. By
asymptotic normality of the posterior (Freedman, 1963), it suffices to have
$O(\frac{1}{\epsilon^{2}}\sqrt{\log\frac{1}{\delta}})$ participants.

When the initial prior, performance model, and evolution model are all
Gaussian, treating $P_{i,t}$ as certain is the _only_ simplifying
approximation we will make; that is, in the limit
$|\mathcal{P}_{t}|\rightarrow\infty$, our method performs _exact_ inference on
Equation 1. In the following sections, we focus some attention on generalizing
the performance model to non-Gaussian log-concave families, parametrized by
location and scale. We will use the logistic distribution as a running example
and see that it induces robustness; however, our framework is agnostic to the
specific distributions used.

The rating $\mu_{i,t}$ of player $i$ after round $t$ should be a statistic
that summarizes their posterior distribution: we’ll use the maximum a
posteriori (MAP) estimate, obtained by setting $s$ to maximize the posterior
$\Pr(S_{i,t}=s\mid P_{i,\leq t})$. By Bayes’ rule,

(3) $\mu_{i,t}:=\operatorname*{arg\,max}_{s}\pi_{i,t}(s)\Pr(P_{i,t}\mid
S_{i,t}=s).$

This objective suggests a two-phase algorithm to update each player
$i\in\mathcal{P}_{t}$ at round $t$. In phase one, we estimate $P_{i,t}$ from
$(E^{L}_{i,t},E^{W}_{i,t})$. By Doob’s consistency theorem, our estimate is
extremely precise when $|\mathcal{P}_{t}|$ is large, so we assume it to be
exact. In phase two, we update our posterior for $S_{i,t}$ and the rating
$\mu_{i,t}$ according to Equation 3.

We will occasionally make use of the prior rating, defined as

$\mu_{i,t}^{\pi}:=\operatorname*{arg\,max}_{s}\pi_{i,t}(s).$

##  3\. A two-phase algorithm for skill estimation

###  3.1. Performance estimation

In this section, we describe the first phase of Elo-MMR. For notational
convenience, we assume all probability expressions to be conditioned on the
prior context $P_{i,<t}$, and omit the subscript $t$.

Our prior belief on each player’s skill $S_{i}$ implies a prior distribution
on $P_{i}$. Let’s denote its probability density function (pdf) by

(4) $f_{i}(p):=\Pr(P_{i}=p)=\int\pi_{i}(s)\Pr(P_{i}=p\mid
S_{i}=s)\,\mathrm{d}s,$

where $\pi_{i}(s)$ was defined in Equation 2. Let

$F_{i}(p):=\Pr(P_{i}\leq p)=\int_{-\infty}^{p}f_{i}(x)\,\mathrm{d}x,$

be the corresponding cumulative distribution function (cdf). For the purpose
of analysis, we’ll also define the following “loss”, “draw”, and “victory”
functions:

$\displaystyle l_{i}(p)$
$\displaystyle:=\frac{\mathrm{d}}{\mathrm{d}p}\ln(1-F_{i}(p))=\frac{-f_{i}(p)}{1-F_{i}(p)},$
$\displaystyle d_{i}(p)$ $\displaystyle:=\frac{\mathrm{d}}{\mathrm{d}p}\ln
f_{i}(p)=\frac{f^{\prime}_{i}(p)}{f_{i}(p)},$ $\displaystyle v_{i}(p)$
$\displaystyle:=\frac{\mathrm{d}}{\mathrm{d}p}\ln
F_{i}(p)=\frac{f_{i}(p)}{F_{i}(p)}.$

Evidently, $l_{i}(p)<0<v_{i}(p)$. Now we define what it means for the
deviation $P_{i}-S_{i}$ to be log-concave.

###### Definition 3.0.

An absolutely continuous random variable on a convex domain is log-concave if
its probability density function $f$ is positive on its domain and satisfies

$f(\theta
x+(1-\theta)y)>f(x)^{\theta}f(y)^{1-\theta},\;\forall\theta\in(0,1),x\neq y.$

We note that log-concave distributions appear widely, and include the Gaussian
and logistic distributions used in Glicko, TrueSkill, and many others. We’ll
see inductively that our prior $\pi_{i}$ is log-concave at every round. Since
log-concave densities are closed under convolution (An, 1997), the independent
sum $P_{i}=S_{i}+(P_{i}-S_{i})$ is also log-concave. The following lemma
(proved in the appendix) makes log-concavity very convenient:

###### Lemma 3.2.

If $f_{i}$ is continuously differentiable and log-concave, then the functions
$l_{i},d_{i},v_{i}$ are continuous, strictly decreasing, and

$l_{i}(p)<d_{i}(p)<v_{i}(p)\text{ for all }p.$

For the remainder of this section, we fix the analysis with respect to some
player $i$. As argued in Section 2, $P_{i}$ concentrates very narrowly in the
posterior. Hence, we can estimate $P_{i}$ by its MAP, choosing $p$ so as to
maximize:

$\Pr(P_{i}=p\mid E^{L}_{i},E^{W}_{i})\propto
f_{i}(p)\Pr(E^{L}_{i},E^{W}_{i}\mid P_{i}=p).$

Define $j\succ i$, $j\prec i$, $j\sim i$ as shorthand for $j\in E^{L}_{i}$,
$j\in E^{W}_{i}$, $j\in\mathcal{P}\setminus(E^{L}_{i}\cup E^{W}_{i})$ (that
is, $P_{j}>P_{i}$, $P_{j}<P_{i}$, $P_{j}=P_{i}$), respectively. The following
theorem yields our MAP estimate:

###### Theorem 3.3.

Suppose that for all $j$, $f_{j}$ is continuously differentiable and log-
concave. Then the unique maximizer of $\Pr(P_{i}=p\mid E^{L}_{i},E^{W}_{i})$
is given by the unique zero of

$Q_{i}(p):=\sum_{j\succ i}l_{j}(p)+\sum_{j\sim i}d_{j}(p)+\sum_{j\prec
i}v_{j}(p).$

The proof is relegated to the appendix. Intuitively, we’re saying that the
performance is the balance point between appropriately weighted wins, draws,
and losses. Let’s look at two specializations of our general model, to serve
as running examples in this paper.

#### Gaussian performance model

If both $S_{j}$ and $P_{j}-S_{j}$ are assumed to be Gaussian with known means
and variances, then their independent sum $P_{j}$ will also be a known
Gaussian. It is analytic and log-concave, so Theorem 3.3 applies.

We substitute the well-known Gaussian pdf and cdf for $f_{j}$ and $F_{j}$,
respectively. A simple binary search, or faster numerical techniques such as
the Illinois algorithm or Newton’s method, can be employed to solve for the
maximizing $p$.

Figure 1. $L_{2}$ versus $L_{R}$ for typical values (left). Gaussian versus
logistic probability density functions (right).

#### Logistic performance model

Now we assume the performance deviation $P_{j}-S_{j}$ has a logistic
distribution with mean 0 and variance $\beta^{2}$. In general, the rating
system administrator is free to set $\beta$ differently for each contest.
Since shorter contests tend to be more variable, one reasonable choice might
be to make $1/\beta^{2}$ proportional to the contest duration.

Given the mean and variance of the skill prior, the independent sum
$P_{j}=S_{j}+(P_{j}-S_{j})$ would have the same mean, and a variance that’s
increased by $\beta^{2}$. Unfortunately, we’ll see that the logistic
performance model implies a form of skill prior from which it’s tough to
extract a mean and variance. Even if we could, the sum does not yield a simple
distribution.

For experienced players, we expect $S_{j}$ to contribute much less variance
than $P_{j}-S_{j}$; thus, in our heuristic approximation, we take $P_{j}$ to
have the same form of distribution as the latter. That is, we take $P_{j}$ to
be logistic, centered at the prior rating
$\mu^{\pi}_{j}=\operatorname*{arg\,max}\pi_{j}$, with variance
$\delta_{j}^{2}=\sigma_{j}^{2}+\beta^{2}$, where $\sigma_{j}$ will be given by
Equation 8. This distribution is analytic and log-concave, so the same methods
based on Theorem 3.3 apply. Define the scale parameter
$\bar{\delta}_{j}:=\frac{\sqrt{3}}{\pi}\delta_{j}$. A logistic distribution
with variance $\delta_{j}^{2}$ has cdf and pdf:

$\displaystyle F_{j}(x)$
$\displaystyle=\frac{1}{1+e^{-(x-\mu^{\pi}_{j})/\bar{\delta}_{j}}}=\frac{1}{2}\left(1+\tanh\frac{x-\mu^{\pi}_{j}}{2\bar{\delta}_{j}}\right),$
$\displaystyle f_{j}(x)$
$\displaystyle=\frac{e^{(x-\mu^{\pi}_{j})/\bar{\delta}_{j}}}{\bar{\delta}_{j}\left(1+e^{(x-\mu^{\pi}_{j})/\bar{\delta}_{j}}\right)^{2}}=\frac{1}{4\bar{\delta}_{j}}\operatorname{sech}^{2}\frac{x-\mu^{\pi}_{j}}{2\bar{\delta}_{j}}.$

The logistic distribution satisfies two very convenient relations:

$\displaystyle F^{\prime}_{j}(x)=f_{j}(x)$
$\displaystyle=F_{j}(x)(1-F_{j}(x))/\bar{\delta}_{j},$ $\displaystyle
f^{\prime}_{j}(x)$ $\displaystyle=f_{j}(x)(1-2F_{j}(x))/\bar{\delta}_{j},$

from which it follows that

$d_{j}(p)=\frac{1-2F_{j}(p)}{\bar{\delta}}=\frac{-F_{j}(p)}{\bar{\delta}}+\frac{1-F_{j}(p)}{\bar{\delta}}=l_{j}(p)+v_{j}(p).$

In other words, a tie counts as the sum of a win and a loss. This can be
compared to the approach (used in Elo, Glicko, TopCoder, and Codeforces) of
treating each tie as half a win plus half a loss.222Elo-MMR, too, can be
modified to split ties into half win plus half loss. It’s easy to check that
Lemma 3.2 still holds if $d_{j}(p)$ is replaced by
$w_{l}l_{j}(p)+w_{v}v_{j}(p)$ for some $w_{l},w_{v}\in[0,1]$ with
$|w_{l}-w_{v}|<1$. In particular, we can set $w_{l}=w_{v}=0.5$. The results in
Section 5 won’t be altered by this change.

Finally, putting everything together:

$Q_{i}(p)=\sum_{j\succeq i}l_{j}(p)+\sum_{j\preceq i}v_{j}(p)=\sum_{j\succeq
i}\frac{-F_{j}(p)}{\bar{\delta}_{j}}+\sum_{j\preceq
i}\frac{1-F_{j}(p)}{\bar{\delta}_{j}}.$

Our estimate for $P_{i}$ is the zero of this expression. The terms on the
right correspond to probabilities of winning and losing against each player
$j$, weighted by $1/\bar{\delta}_{j}$. Accordingly, we can interpret
$\sum_{j\in\mathcal{P}}(1-F_{j}(p))/\bar{\delta}_{j}$ as a weighted expected
rank of a player whose performance is $p$. Similar to the performance
computations in Codeforces and TopCoder, $P_{i}$ can thus be viewed as the
performance level at which one’s expected rank would equal $i$’s actual rank.

###  3.2. Belief update

Having estimated $P_{i,t}$ in the first phase, the second phase is rather
simple. Ignoring normalizing constants, Equation 3 tells us that the pdf of
the skill posterior can be obtained as the pointwise product of the pdfs of
the skill prior and the performance model. When both factors are
differentiable and log-concave, then so is their product. Its maximum is the
new rating $\mu_{i,t}$; let’s see how to compute it for the same two
specializations of our model.

#### Gaussian skill prior and performance model

When the skill prior and performance model are Gaussian with known means and
variances, multiplying their pdfs yields another known Gaussian. Hence, the
posterior is compactly represented by its mean $\mu_{i,t}$, which coincides
with the MAP and rating; and its variance $\sigma_{i,t}^{2}$, which is our
uncertainty regarding the player’s skill.

#### Logistic performance model

When the performance model is non-Gaussian, the multiplication does not
simplify so easily. By Equation 3, each round contributes an additional factor
to the belief distribution. In general, we allow it to consist of a collection
of simple log-concave factors, one for each round in which player $i$ has
participated. Denote the participation history by

${\mathcal{H}}_{i,t}:=\\{k\in\\{1,\ldots,t\\}:i\in\mathcal{P}_{k}\\}.$

Since each player can be considered in isolation, we’ll omit the subscript
$i$. Specializing to the logistic setting, each $k\in{\mathcal{H}}_{t}$
contributes a logistic factor to the posterior, with mean $p_{k}$ and variance
$\beta_{k}^{2}$. We still use a Gaussian initial prior, with mean and variance
denoted by $p_{0}$ and $\beta_{0}^{2}$, respectively. Postponing the
discussion of skill evolution to Section 4, for the moment we assume that
$S_{k}=S_{0}$ for all $k$. The posterior pdf, up to normalization, is then

$\displaystyle\pi_{0}(s)\prod_{k\in{\mathcal{H}}_{t}}\Pr(P_{k}=p_{k}\mid
S_{k}=s)$ (5)
$\displaystyle\propto\exp\left(-\frac{(s-p_{0})^{2}}{2\beta_{0}^{2}}\right)\prod_{k\in{\mathcal{H}}_{t}}\operatorname{sech}^{2}\left(\frac{\pi}{\sqrt{12}}\frac{s-p_{k}}{\beta_{k}}\right).$

Maximizing the posterior density amounts to minimizing its negative logarithm.
Up to a constant offset, this is given by

$\displaystyle L(s)$
$\displaystyle:=L_{2}\left(\frac{s-p_{0}}{\beta_{0}}\right)+\sum_{k\in{\mathcal{H}}_{t}}L_{R}\left(\frac{s-p_{k}}{\beta_{k}}\right),$
$\displaystyle\text{where }L_{2}(x)$ $\displaystyle:=\frac{1}{2}x^{2}\text{
and }L_{R}(x):=2\ln\left(\cosh\frac{\pi x}{\sqrt{12}}\right).$ (6)
$\text{Thus,
}L^{\prime}(s)=\frac{s-p_{0}}{\beta_{0}^{2}}+\sum_{k\in{\mathcal{H}}_{t}}\frac{\pi}{\beta_{k}\sqrt{3}}\tanh\frac{(s-p_{k})\pi}{\beta_{k}\sqrt{12}}.$

$L^{\prime}$ is continuous and strictly increasing in $s$, so its zero is
unique: it is the MAP $\mu_{t}$. Similar to what we did in the first phase, we
can solve for $\mu_{t}$ with either binary search or Newton’s method.

We pause to make an important observation. From Equation 6, the rating carries
a rather intuitive interpretation: Gaussian factors in $L$ become $L_{2}$
penalty terms, whereas logistic factors take on a more interesting form as
$L_{R}$ terms. From Figure 1, we see that the $L_{R}$ term behaves
quadratically near the origin, but linearly at the extremities, effectively
interpolating between $L_{2}$ and $L_{1}$ over a scale of magnitude
$\beta_{k}$

It is well-known that minimizing a sum of $L_{2}$ terms pushes the argument
towards a weighted mean, while minimizing a sum of $L_{1}$ terms pushes the
argument towards a weighted median. With $L_{R}$ terms, the net effect is that
$\mu_{t}$ acts like a robust average of the historical performances $p_{k}$.
Specifically, one can check that

$\mu_{t}=\frac{\sum_{k}w_{k}p_{k}}{\sum_{k}w_{k}},\text{ where
}w_{0}:=\frac{1}{\beta_{0}^{2}}\text{ and }$ (7)
$w_{k}:=\frac{\pi}{(\mu_{t}-p_{k})\beta_{k}\sqrt{3}}\tanh\frac{(\mu_{t}-p_{k})\pi}{\beta_{k}\sqrt{12}}\text{
for }k\in{\mathcal{H}}_{t}.$

$w_{k}$ is close to $1/\beta_{k}^{2}$ for typical performances, but can be up
to $\pi^{2}/6$ times more as $|\mu_{t}-p_{k}|\rightarrow 0$, or vanish as
$|\mu_{t}-p_{k}|\rightarrow\infty$. This feature is due to the thicker tails
of the logistic distribution, as compared to the Gaussian, resulting in an
algorithm that resists drastic rating changes in the presence of a few
unusually good or bad performances. We’ll formally state this _robustness_
property in Theorem 5.7.

#### Estimating skill uncertainty

While there is no easy way to compute the variance of a posterior in the form
of Equation 5, it will be useful to have some estimate $\sigma_{t}^{2}$ of
uncertainty. There is a simple formula in the case where all factors are
Gaussian. Since moment-matched logistic and normal distributions are
relatively close (c.f. Figure 1), we apply the same formula:

(8)
$\frac{1}{\sigma_{t}^{2}}:=\sum_{k\in\\{0\\}\cup{\mathcal{H}}_{t}}\frac{1}{\beta_{k}^{2}}.$

##  4\. Skill evolution over time

Factors such as training and resting will change a player’s skill over time.
If we model skill as a static variable, our system will eventually grow so
confident in its estimate that it will refuse to admit substantial changes. To
remedy this, we introduce a skill evolution model, so that in general
$S_{t}\neq S_{t^{\prime}}$ for $t\neq t^{\prime}$. Now rather than simply
being equal to the previous round’s posterior, the skill prior at round $t$ is
given by

(9) $\pi_{t}(s)=\int\Pr(S_{t}=s\mid S_{t-1}=x)\Pr(S_{t-1}=x\mid
P_{<t})\,\mathrm{d}x.$

The factors in the integrand are the skill evolution model and the previous
round’s posterior, respectively. Following other Bayesian rating systems
(e.g., Glicko, Glicko-2, and TrueSkill (Glickman, 1999, 2012; Herbrich et al.,
2006)), we model the skill diffusions $S_{t}-S_{t-1}$ as independent zero-mean
Gaussians. That is, $\Pr(S_{t}\mid S_{t-1}=x)$ is a Gaussian with mean $x$ and
some variance $\gamma_{t}^{2}$. The Glicko system sets $\gamma_{t}^{2}$
proportionally to the time elapsed since the last update, corresponding to a
continuous Brownian motion. Codeforces and TopCoder simply set $\gamma_{t}$ to
a constant when a player participates, and zero otherwise, corresponding to
changes that are in proportion to how often the player competes. Now we are
ready to complete the two specializations of our rating system.

#### Gaussian skill prior and performance model

If both the prior and performance distributions at round $t-1$ are Gaussian,
then the posterior is also Gaussian. Adding an independent Gaussian diffusion
to our posterior on $S_{t-1}$ yields a Gaussian prior on $S_{t}$. By
induction, the skill belief distribution forever remains Gaussian. This
Gaussian specialization of the Elo-MMR framework lacks the R for robustness
(see Theorem 5.7), so we call it Elo-MM$\chi$.

#### Logistic performance model

After a player’s first contest round, the posterior in Equation 5 becomes non-
Gaussian, rendering the integral in Equation 9 intractable.

A very simple approach would be to replace the full posterior in Equation 5 by
a Gaussian approximation with mean $\mu_{t}$ (equal to the posterior MAP) and
variance $\sigma_{t}^{2}$ (given by Equation 8). As in the previous case,
applying diffusions in the Gaussian setting is a simple matter of adding means
and variances.

With this approximation, no memory is kept of the individual performances
$P_{t}$. Priors are simply Gaussian, while posterior densities are the product
of two factors: the Gaussian prior, and a logistic factor corresponding to the
latest performance. To ensure robustness (see Section 5.2), $\mu_{t}$ is
computed as the argmax of this posterior _before_ replacement by its Gaussian
approximation. We call the rating system that takes this approach Elo-
MMR($\infty$).

As the name implies, it turns out to be a special case of Elo-MMR($\rho$). In
the general setting with $\rho\in[0,\infty)$, we keep the full posterior from
Equation 5. Since we cannot tractably compute the effect of a Gaussian
diffusion, we seek a heuristic derivation of the next round’s prior, retaining
a form similar to Equation 5 while satisfying many of the same properties as
the intended diffusion.

###  4.1. Desirable properties of a “pseudodiffusion”

We begin by listing some properties that our skill evolution algorithm,
henceforth called a “pseudodiffusion”, should satisfy. The first two
properties are natural:

  * •

_Aligned incentives._ First and foremost, the pseudodiffusion must not break
the aligned incentives property of our rating system. That is, a rating-
maximizing player should never be motivated to lose on purpose (Theorem 5.5).

  * •

_Rating preservation._ The pseudodiffusion must not alter the
$\operatorname*{arg\,max}$ of the belief density. That is, the rating of a
player should not change: $\mu^{\pi}_{t}=\mu_{t-1}$.

In addition, we borrow four properties of Gaussian diffusions:

  * •

_Correct magnitude._ Pseudodiffusion with parameter $\gamma^{2}$ must increase
the skill uncertainty, as measured by Equation 8, by $\gamma^{2}$.

  * •

_Composability._ Two pseudodiffusions applied in sequence, first with
parameter $\gamma_{1}^{2}$ and then with $\gamma_{2}^{2}$, must have the same
effect as a single pseudodiffusion with parameter
$\gamma_{1}^{2}+\gamma_{2}^{2}$.

  * •

_Zero diffusion._ In the limit as $\gamma\rightarrow 0$, the effect of
pseudodiffusion must vanish, i.e., not alter the belief distribution.

  * •

_Zero uncertainty._ In the limit as $\sigma_{t-1}\rightarrow 0$ (i.e., when
the previous rating $\mu_{t-1}$ is a perfect estimate of $S_{t-1}$), our
belief on $S_{t}$ must become Gaussian with mean $\mu_{t-1}$ and variance
$\gamma^{2}$. Finer-grained information regarding the prior history $P_{\leq
t}$ must be erased.

In particular, Elo-MMR($\infty$) fails the _zero diffusion_ property because
it simplifies the belief distribution, even when $\gamma=0$. In the proof of
Theorem 4.1, we’ll see that Elo-MMR($0$) fails the _zero uncertainty_
property. Thus, it is in fact necessary to have $\rho$ strictly positive and
finite. In Section 5.2, we’ll come to interpret $\rho$ as a kind of inverse
momentum.

###  4.2. A heuristic pseudodiffusion algorithm

Each factor in the posterior (see Equation 5) has a parameter $\beta_{k}$.
Define a factor’s weight to be $w_{k}:=1/\beta_{k}^{2}$, which by Equation 8
contributes to the total weight $\sum_{k}w_{k}=1/\sigma_{t}^{2}$. Here, unlike
in Equation 7, $w_{k}$ does not depend on $|\mu_{t}-p_{k}|$.

The approximation step of Elo-MMR($\infty$) replaces all the logistic factors
by a single Gaussian whose variance is chosen to ensure that the total weight
is preserved. In addition, its mean is chosen to preserve the player’s rating,
given by the unique zero of Equation 6. Finally, the diffusion step of Elo-
MMR($\infty$) increases the Gaussian’s variance, and hence the player’s skill
uncertainty, by $\gamma_{t}^{2}$; this corresponds to a decay in the weight.

To generalize the idea, we interleave the two steps in a continuous manner.
The approximation step becomes a transfer step: rather than replace the
logistic factors outright, we take away the same fraction from each of their
weights, and place the sum of removed weights onto a new Gaussian factor. The
diffusion step becomes a decay step, reducing each factor’s weight by the same
fraction, chosen such that the overall uncertainty is increased by
$\gamma_{t}^{2}$.

To make the idea precise, we generalize the posterior from Equation 5 with
fractional multiplicities $\omega_{k}$, initially set to $1$ for each
$k\in\\{0\\}\cup{\mathcal{H}}_{t}$. The $k$’th factor is raised to the power
$\omega_{k}$; in Equations 6 and 8, the corresponding term is multiplied by
$\omega_{k}$. In other words, the latter equation is replaced by

$\frac{1}{\sigma_{t}^{2}}:=\sum_{k\in\\{0\\}\cup{\mathcal{H}}_{t}}w_{k},\text{
where }w_{k}:=\frac{\omega_{k}}{\beta_{k}^{2}}.$

For $\rho\in[0,\infty]$, the Elo-MMR($\rho$) algorithm continuously and
simultaneously performs transfer and decay, with transfer proceeding at $\rho$
times the rate of decay. Holding $\beta_{k}$ fixed, changes to $\omega_{k}$
can be described in terms of changes to $w_{k}$:

$\displaystyle\dot{w}_{0}$ $\displaystyle=-r(t)w_{0}+\rho
r(t)\sum_{k\in{\mathcal{H}}_{t}}w_{k},$ $\displaystyle\dot{w}_{k}$
$\displaystyle=-(1+\rho)r(t)w_{k}\quad\text{for }k\in{\mathcal{H}}_{t},$

where the arbitrary decay rate $r(t)$ can be eliminated by a change of
variable $\mathrm{d}\tau=r(t)\mathrm{d}t$. After some time $\Delta\tau$, the
total weight will have decayed by a factor $\kappa:=e^{-\Delta\tau}$,
resulting in the new weights:

$\displaystyle w_{0}^{new}$ $\displaystyle=\kappa
w_{0}+\left(\kappa-\kappa^{1+\rho}\right)\sum_{k\in{\mathcal{H}}_{t}}w_{k},$
$\displaystyle w_{k}^{new}$ $\displaystyle=\kappa^{1+\rho}w_{k}\quad\text{for
}k\in{\mathcal{H}}_{t}.$

In order for the uncertainty to increase from $\sigma_{t-1}^{2}$ to
$\sigma_{t-1}^{2}+\gamma_{t}^{2}$, we must solve
$\kappa/\sigma_{t-1}^{2}=1/(\sigma_{t-1}^{2}+\gamma_{t}^{2})$ for the decay
factor:

Algorithm 1 Elo-MMR($\rho,\beta,\gamma$)

for all rounds $t$ do

for all players $i\in\mathcal{P}_{t}$ in parallel do

if $i$ has never competed before then

$\mu_{i},\sigma_{i}\leftarrow\mu_{newcomer},\sigma_{newcomer}$

$p_{i},w_{i}\leftarrow[\mu_{i}],[1/\sigma_{i}^{2}]$

diffuse($i,\gamma,\rho$)

$\mu^{\pi}_{i},\delta_{i}\leftarrow\mu_{i},\sqrt{\sigma_{i}^{2}+\beta^{2}}$

for all $i\in\mathcal{P}_{t}$ in parallel do

update($i,E_{t},\beta$)

Algorithm 2 diffuse($i,\gamma,\rho$)

$\kappa\leftarrow(1+\gamma^{2}/\sigma_{i}^{2})^{-1}$

$w_{G},w_{L}\leftarrow\kappa^{\rho}w_{i,0},(1-\kappa^{\rho})\sum_{k}w_{i,k}$

$p_{i,0}\leftarrow(w_{G}p_{i,0}+w_{L}\mu_{i})/(w_{G}+w_{L})$

$w_{i,0}\leftarrow\kappa(w_{G}+w_{L})$

for all $k\neq 0$ do

$w_{i,k}\leftarrow\kappa^{1+\rho}w_{i,k}$

$\sigma_{i}\leftarrow\sigma_{i}/\sqrt{\kappa}$

Algorithm 3 update($i,E,\beta$)

$p\leftarrow\mathrm{zero}\left(\sum_{j\preceq
i}\frac{1}{\delta_{j}}\left(\tanh\frac{x-\mu^{\pi}_{j}}{2\bar{\delta}_{j}}-1\right)+\sum_{j\succeq
i}\frac{1}{\delta_{j}}\left(\tanh\frac{x-\mu^{\pi}_{j}}{2\bar{\delta}_{j}}+1\right)\right)$

$p_{i}$.push($p$)

$w_{i}$.push($1/\beta^{2}$)

$\mu_{i}\leftarrow\mathrm{zero}\left(w_{i,0}(x-p_{i,0})+\sum_{k\neq
0}\frac{w_{i,k}\beta^{2}}{\bar{\beta}}\tanh\frac{x-p_{i,k}}{2\bar{\beta}}\right)$

$\kappa=\left(1+\frac{\gamma_{t}^{2}}{\sigma_{t-1}^{2}}\right)^{-1}.$

In order for this operation to preserve ratings, the transferred weight must
be centered at $\mu_{t-1}$; see Algorithm 2 for details.

Algorithm 1 details the full Elo-MMR($\rho$) rating system. The main loop runs
whenever a round of competition takes place. First, new players are
initialized with a Gaussian prior. Then, changes in player skill are modeled
by Algorithm 2. Given the round rankings $E_{t}$, the first phase of Algorithm
3 solves an equation to estimate $P_{t}$. Finally, the second phase solves
another equation for the rating $\mu_{t}$.

The hyperparameters $\rho,\beta,\gamma$ are domain-dependent, and can be set
by standard hyperparameter search techniques. For convenience, we assume
$\beta$ and $\gamma$ are fixed and use the shorthand
$\bar{\beta}_{k}:=\frac{\sqrt{3}}{\pi}\beta_{k}$.

###### Theorem 4.1.

Algorithm 2 with $\rho\in(0,\infty)$ meets all of the properties listed in
Section 4.1.

###### Proof.

We go through each of the six properties in order.

  * •

_Aligned incentives._ This property will be stated in Theorem 5.5. To ensure
that its proof carries through, the relevant facts to note here are that the
pseudodiffusion algorithm ignores the performances $p_{k}$, and centers the
transferred Gaussian weight at the rating $\mu_{t-1}$, which is trivially
monotonic in $\mu_{t-1}$.

  * •

_Rating preservation._ Recall that the rating is the unique zero of
$L^{\prime}$, defined in Equation 6. To see that this zero is preserved, note
that the decay and transfer operations multiply $L^{\prime}$ by constants
($\kappa$ and $\kappa^{\rho}$, respectively), before adding the new Gaussian
term, whose contribution to $L^{\prime}$ is zero at its center.

  * •

_Correct magnitude._ Follows from our derivation for $\kappa$.

  * •

_Composability._ Follows from _correct magnitude_ and the fact that every
pseudodiffusion follows the same differential equations.

  * •

_Zero diffusion._ As $\gamma\rightarrow 0$, $\kappa\rightarrow 1$. Provided
that $\rho<\infty$, we also have $\kappa^{\rho}\rightarrow 1$. Hence, for all
$k\in\\{0\\}\cup{\mathcal{H}}_{t}$, $w_{k}^{new}\rightarrow w_{k}$.

  * •

_Zero uncertainty._ As $\sigma_{t-1}\rightarrow 0$, $\kappa\rightarrow 0$. The
total weight decays from $1/\sigma_{t-1}^{2}$ to $\gamma^{2}$. Provided that
$\rho>0$, we also have $\kappa^{\rho}\rightarrow 0$, so these weights transfer
in their entirety, leaving behind a Gaussian with mean $\mu_{t-1}$, variance
$\gamma^{2}$, and no additional history. ∎

##  5\. Theoretical Properties

In this section, we see how the simplicity of the Elo-MMR formulas enables us
to rigorously prove that the rating system aligns incentives, is robust, and
is computationally efficient.

###  5.1. Aligned incentives

To demonstrate the need for _aligned incentives_ , let’s look at the
consequences of violating this property in the TopCoder and Glicko-2 rating
systems. These systems track a “volatility” for each player, which estimates
the variance of their performances. A player whose recent performance history
is more consistent would be assigned a lower volatility score, than one with
wild swings in performance. The volatility acts as a multiplier on rating
changes; thus, players with an extremely low or high performance will have
their subsequent rating changes amplified.

While it may seem like a good idea to boost changes for players whose ratings
are poor predictors of their performance, this feature has an exploit. By
intentionally performing at a weaker level, a player can amplify future
increases to an extent that more than compensates for the immediate hit to
their rating. A player may even “farm” volatility by alternating between very
strong and very weak performances. After acquiring a sufficiently high
volatility score, the strategic player exerts their honest maximum performance
over a series of contests. The amplification eventually results in a rating
that exceeds what would have been obtained via honest play. This type of
exploit was discovered in both TopCoder competitions and the Pokemon Go video
game (Forišek, 2009; pok, [n.d.]). For a detailed example, see Table 5.3 of
(Forišek, 2009).

Remarkably, Elo-MMR combines the best of both worlds: we’ll see in Section 5.2
that, for $\rho\in(0,\infty)$, Elo-MMR($\rho$) also boosts changes to
inconsistent players. And yet, as we’ll prove in this section, no such
strategic incentive exists in _any_ version of Elo-MMR.

Recall that, for the purposes of the algorithm, the performance $p_{i}$ is
defined to be the unique zero of the function $Q_{i}(p):=\sum_{j\succ
i}l_{j}(p)+\sum_{j\sim i}d_{j}(p)+\sum_{j\prec i}v_{j}(p)$, whose terms
$l_{i},d_{i},v_{i}$ are contributed by opponents against whom $i$ lost, drew,
or won, respectively. Wins (losses) are always positive (negative)
contributions to a player’s performance score:

###### Lemma 5.1.

Adding a win term to $Q_{i}(\cdot)$, or replacing a tie term by a win term,
always increases its zero. Conversely, adding a loss term, or replacing a tie
term by a loss term, always decreases it.

###### Proof.

By Lemma 3.2, $Q_{i}(p)$ is decreasing in $p$. Thus, adding a positive term
will increase its zero whereas adding a negative term will decrease it. The
desired conclusion follows by noting that, for all $j$ and $p$, $v_{j}(p)$ and
$v_{j}(p)-d_{j}(p)$ are positive, whereas $l_{j}(p)$ and $l_{j}(p)-d_{j}(p)$
are negative. ∎

While not needed for our main result, a similar argument shows that
performance scores are monotonic across the round standings:

###### Theorem 5.2.

If $i\succ j$ (that is, player $i$ beats $j$) in a given round, then player
$i$ and $j$’s performance estimates satisfy $p_{i}>p_{j}$.

###### Proof.

If $i\succ j$ with $i,j$ adjacent in the rankings, then

$Q_{i}(p)-Q_{j}(p)=\sum_{k\sim i}(d_{k}(p)-l_{k}(p))+\sum_{k\sim
j}(v_{k}(p)-d_{k}(p))>0.$

for all $p$. Since $Q_{i}$ and $Q_{j}$ are decreasing functions, it follows
that $p_{i}>p_{j}$. By induction, this result extends to the case where $i,j$
are not adjacent in the rankings. ∎

What matters for incentives is that performance scores be _counterfactually_
monotonic; meaning, if we were to alter the round standings, a strategic
player will always prefer to place higher:

###### Lemma 5.3.

In any given round, holding fixed the relative ranking of all players other
than $i$ (and holding fixed all preceding rounds), the performance $p_{i}$ is
a monotonic function of player i’s prior rating and of player $i$’s rank in
this round.

###### Proof.

Monotonicity in the rating follows directly from monotonicity of the self-tie
term $d_{i}$ in $Q_{i}$. Since an upward shift in the rankings can only
convert losses to ties to wins, monotonicity in contest rank follows from
Lemma 5.1. ∎

Having established the relationship between round rankings and performance
scores, the next step is to prove that, even with hindsight, players will
always prefer their performance scores to be as high as possible:

###### Lemma 5.4.

Holding fixed the set of contest rounds in which a player has participated,
their current rating is monotonic in each of their past performance scores.

###### Proof.

The player’s rating is given by the zero of $L^{\prime}$ in Equation 6. The
pseudodiffusions of Section 4 modify each of the $\beta_{k}$ in a manner that
does not depend on any of the $p_{k}$, so they are fixed for our purposes.
Hence, $L^{\prime}$ is monotonically increasing in $s$ and decreasing in each
of the $p_{k}$. Therefore, its zero is monotonically increasing in each of the
$p_{k}$.

This is almost what we wanted to prove, except that $p_{0}$ is not a
performance. Nonetheless, it is a function of the performances: specifically,
a weighted average of historical ratings which, using this same lemma as an
inductive hypothesis, are themselves monotonic in past performances. By
induction, the proof is complete. ∎

Finally, we conclude that the player’s incentives are aligned with optimizing
round rankings, or raw scores:

###### Theorem 5.5 (Aligned Incentives).

Holding fixed the set of contest rounds in which each player has participated,
and the historical ratings and relative rankings of all players other than
$i$, player $i$’s current rating is monotonic in each of their past rankings.

###### Proof.

Choose any contest round in player $i$’s history, and consider improving
player $i$’s rank in that round while holding everything else fixed. It
suffices to show that player $i$’s current rating would necessarily increase
as a result.

In the altered round, by Lemma 5.3, $p_{i}$ is increased; and by Lemma 5.4,
player $i$’s post-round rating is increased. By Lemma 5.3 again, this
increases player $i$’s performance score in the following round. Proceeding
inductively, we find that performance scores and ratings from this point
onward are all increased. ∎

In the special cases of Elo-MM$\chi$ or Elo-MMR($\infty$), the rating system
is “memoryless”: the only data retained for each player are the current rating
$\mu_{i,t}$ and uncertainty $\sigma_{i,t}$; detailed performance history is
not saved. In this setting, we present a natural monotonicity theorem. A
similar theorem was stated for the Codeforces system in (Cod, [n.d.]b), but no
proofs were given.

###### Theorem 5.6 (Memoryless Monotonicity Theorem).

In either the Elo-MM$\chi$ or Elo-MMR($\infty$) system, suppose $i$ and $j$
are two participants of round $t$. Suppose that the ratings and corresponding
uncertainties satisfy
$\mu_{i,t-1}\geq\mu_{j,t-1},\;\sigma_{i,t-1}=\sigma_{j,t-1}$. Then,
$\sigma_{i,t}=\sigma_{j,t}$. Furthermore, if $i\succ j$ in round $t$, then
$\mu_{i,t}>\mu_{j,t}$. On the other hand, if $j\succ i$ in round $t$, then
$\mu_{j,t}-\mu_{j,t-1}>\mu_{i,t}-\mu_{i,t-1}$.

###### Proof.

The new contest round will add a rating perturbation with variance
$\gamma_{t}^{2}$, followed by a new performance with variance $\beta_{t}^{2}$.
As a result,

$\sigma_{i,t}=\left(\frac{1}{\sigma_{i,t-1}^{2}+\gamma_{t}^{2}}+\frac{1}{\beta_{t}^{2}}\right)^{-\frac{1}{2}}=\left(\frac{1}{\sigma_{j,t-1}^{2}+\gamma_{t}^{2}}+\frac{1}{\beta_{t}^{2}}\right)^{-\frac{1}{2}}=\sigma_{j,t}.$

The remaining conclusions are consequences of three properties:
memorylessness, aligned incentives (Theorem 5.5), and translation-invariance
(ratings, skills, and performances are quantified on a common interval scale
relative to one another).

Since the Elo-MM$\chi$ or Elo-MMR($\infty$) systems are memoryless, we may
replace the initial prior and performance histories of players with any
alternate histories of our choosing, as long as our choice is compatible with
their current rating and uncertainty. For example, both $i$ and $j$ can be
considered to have participated in the same set of rounds, with $i$ always
performing at $\mu_{i,t-1}$. and $j$ always performing at $\mu_{j,t-1}$. Round
$t$ is unchanged.

Suppose $i\succ j$. Since $i$’s historical performances are all equal or
stronger than $j$’s, Theorem 5.5 implies $\mu_{i,t}>\mu_{j,t}$.

Suppose $j\succ i$. By translation-invariance, if we shift each of $j$’s
performances, up to round $t$ and including the initial prior, upward by
$\mu_{i,t-1}-\mu_{j,t-1}$, the rating changes between rounds will be
unaffected. Players $i$ and $j$ now have identical histories, except that we
still have $j\succ i$ at round $t$. Therefore, $\mu_{j,t-1}=\mu_{i,t-1}$ and,
by Theorem 5.5, $\mu_{j,t}>\mu_{i,t}$. Subtracting the equation from the
inequality proves the second conclusion. ∎

###  5.2. Robust response

Another desirable property in many settings is robustness: a player’s rating
should not change too much in response to any one contest, no matter how
extreme their performance. The Codeforces and TrueSkill systems lack this
property, allowing for unbounded rating changes. TopCoder achieves robustness
by clamping any changes that exceed a cap, which is initially high for new
players but decreases with experience.

When $\rho>0$, Elo-MMR($\rho$) achieves robustness in a natural, smoother
manner. It comes out of the interplay between Gaussian and logistic factors in
the posterior; $\rho>0$ ensures that the Gaussian contribution doesn’t vanish.
Recall the notation used to describe the general posterior in Equations 5 and
6, enhanced with the fractional multiplicities $\omega_{k}$ from Section 4.2.

###### Theorem 5.7.

In the Elo-MMR($\rho$) rating system, let

$\Delta_{+}:=\lim_{p_{t}\rightarrow+\infty}\mu_{t}-\mu_{t-1},\quad\Delta_{-}:=\lim_{p_{t}\rightarrow-\infty}\mu_{t-1}-\mu_{t}.$

Then,

$\frac{\pi}{\beta_{t}\sqrt{3}}\left(\frac{1}{\beta_{0}^{2}}+\frac{\pi^{2}}{6}\sum_{k\in{\mathcal{H}}_{t-1}}\frac{\omega_{k}}{\beta_{k}^{2}}\right)^{-1}\leq\Delta_{\pm}\leq\frac{\pi\beta_{0}^{2}}{\beta_{t}\sqrt{3}}.$

###### Proof.

Using the fact that $0<\frac{d}{dx}\tanh(x)\leq 1$, differentiating Equation 6
yields

$\frac{1}{\beta_{0}^{2}}\leq
L^{\prime\prime}(s)\leq\frac{1}{\beta_{0}^{2}}+\frac{\pi^{2}}{6}\sum_{k\in{\mathcal{H}}_{t-1}}\frac{\omega_{k}}{\beta_{k}^{2}}.$

For every $s\in\mathbb{R}$, in the limit as $p_{t}\rightarrow\pm\infty$, the
new term corresponding to the performance at round $t$ will increase
$L^{\prime}(s)$ by $\mp\frac{\pi}{\beta_{t}\sqrt{3}}$. Since $\mu_{t-1}$ was a
zero of $L^{\prime}$ without this new term, we now have
$L^{\prime}(\mu_{t-1})\rightarrow\mp\frac{\pi}{\beta_{t}\sqrt{3}}.$ Dividing
by the former inequalities yields the desired result. ∎

The proof reveals that the magnitude of $\Delta_{\pm}$ depends inversely on
that of $L^{\prime\prime}$ in the vicinity of the current rating, which in
turn is related to the derivative of the $\tanh$ terms. If a player’s
performances vary wildly, then most of the $\tanh$ terms will be in their
tails, which contribute small derivatives, enabling larger rating changes.
Conversely, the $\tanh$ terms of a player with a very consistent rating
history will contribute large derivatives, so the bound on their rating change
will be small.

Thus, Elo-MMR($\rho$) naturally caps the rating change of all players, and
puts a smaller cap on the rating change of consistent players. The cap will
increase after an extreme performance, providing a similar “momentum” to the
TopCoder and Glicko-2 systems, but without sacrificing aligned incentives
(Theorem 5.5).

By comparing against Equation 8, we see that the lower bound in Theorem 5.7 is
on the order of $\sigma_{t}^{2}/\beta_{t}$, while the upper bound is on the
order of $\beta_{0}^{2}/\beta_{t}$. As a result, the momentum effect is more
pronounced when $\beta_{0}$ is much larger than $\sigma_{t}$. Since the decay
step increases $\beta_{0}$ while the transfer step decreases it, this occurs
when the transfer rate $\rho$ is comparatively small. Thus, $\rho$ can be
chosen in inverse proportion to the desired strength of momentum.

###  5.3. Runtime analysis and optimizations

Let’s look at the computation time needed to process a round with participant
set $\mathcal{P}$, where we again omit the round subscript. Each player $i$
has a participation history ${\mathcal{H}}_{i}$.

Estimating $P_{i}$ entails finding the zero of a monotonic function with
$O(|\mathcal{P}|)$ terms, and then obtaining the rating $\mu_{i}$ entails
finding the zero of another monotonic function with $O(|{\mathcal{H}}_{i}|)$
terms. Using the Illinois or Newton methods, solving these equations to
precision $\epsilon$ takes $O(\log\log\frac{1}{\epsilon})$ iterations. As a
result, the total runtime needed to process one round of competition is

$O\left(\sum_{i\in\mathcal{P}}(|\mathcal{P}|+|{\mathcal{H}}_{i}|)\log\log\frac{1}{\epsilon}\right).$

This complexity is more than adequate for Codeforces-style competitions with
thousands of contestants and history lengths up to a few hundred. Indeed, we
were able to process the entire history of Codeforces on a small laptop in
less than half an hour. Nonetheless, it may be cost-prohibitive in truly
massive settings, where $|\mathcal{P}|$ or $|{\mathcal{H}}_{i}|$ number in the
millions. Fortunately, it turns out that both functions may be compressed down
to a bounded number of terms, with negligible loss of precision.

#### Adaptive subsampling

In Section 2, we used Doob’s consistency theorem to argue that our estimate
for $P_{i}$ is consistent. Specifically, we saw that $O(1/\epsilon^{2})$
opponents are needed to get the typical error below $\epsilon$. Thus, we can
subsample the set of opponents to include in the estimation, omitting the
rest. Random sampling is one approach. A more efficient approach chooses a
fixed number of opponents whose ratings are closest to that of player $i$, as
these are more likely to provide informative match-ups. On the other hand, if
the setting requires aligned incentives to hold exactly, then one must avoid
choosing different opponents for each player.

#### History compression

Similarly, it’s possible to bound the number of stored factors in the
posterior. Our skill-evolution algorithm decays the weights of old
performances at an exponential rate. Thus, the contributions of all but the
most recent $O(\log\frac{1}{\epsilon})$ terms are negligible. Rather than
erase the older logistic terms outright, we recommend replacing them with
moment-matched Gaussian terms, similar to the transfers in Section 4 with
$\kappa=0$. Since Gaussians compose easily, a single term can then summarize
an arbitrarily long prefix of the history.

Substituting $1/\epsilon^{2}$ and $\log\frac{1}{\epsilon}$ for $|\mathcal{P}|$
and $|{\mathcal{H}}_{i}|$, respectively, the runtime of Elo-MMR with both
optimizations becomes

$O\left(\frac{|\mathcal{P}|}{\epsilon^{2}}\log\log\frac{1}{\epsilon}\right).$

Finally, we note that the algorithm is embarrassingly parallel, with each
player able to solve its equations independently. The threads can read the
same global data structures, so each additional thread only contributes $O(1)$
memory overhead.

##  6\. Experiments

In this section, we compare various rating systems on real-world datasets,
mined from several sources that will be described in Section 6.1. The metrics
are runtime and predictive accuracy, as described in Section 6.2.

We compare Elo-MM$\chi$ and Elo-MMR($\rho$) against the industry-tested rating
systems of Codeforces and TopCoder. For a fairer comparison, we hand-coded
efficient versions of all four algorithms in the safe subset of Rust,
parellelized using the Rayon crate; as such, the Rust compiler verifies that
they contain no data races (Stone and Matsakis, 2017). Our implementation of
Elo-MMR($\rho$) makes use of the optimizations in Section 5.3, bounding both
the number of sampled opponents and the history length by 500. In addition, we
test the improved TrueSkill algorithm of (Nikolenko et al., 2010), basing our
code on an open-source implementation of the same algorithm. The inherent
seqentiality of its message-passing procedure prevented us from parallelizing
it.

#### Hyperparameter search

To ensure fair comparisons, we ran a separate grid search for each triple of
algorithm, dataset, and metric, over all of the algorithm’s hyperparameters.
The hyperparameter set that performed best on the first 10% of the dataset,
was then used to test the algorithm on the remaining 90% of the dataset.

The experiments were run on a 2.0 GHz 24-core Skylake machine with 24 GB of
memory. Implementations of all rating systems, hyperparameters, datasets, and
additional processing used in our experiments can be found at
https://github.com/EbTech/EloR/.

###  6.1. Datasets

Dataset | # contests | avg. # participants / contest
---|---|---
Codeforces | 1087 | 2999
TopCoder | 2023 | 403
Reddit | 1000 | 20
Synthetic | 50 | 2500
Table 1. Summary of test datasets.

Due to the scarcity of public domain datasets for rating systems, we mined
three datasets to analyze the effectiveness of our system. The datasets were
mined using data from each source website’s inception up to October 12th,
2020. We also created a synthetic dataset to test our system’s performance
when the data generating process matches our theoretical model. Summary
statistics of the datasets are presented in Table 1.

#### Codeforces contest history

This dataset contains the current entire history of rated contests ever run on
CodeForces.com, the dominant platform for online programming competitions. The
CodeForces platform has over 850K users, over 300K of whom are rated, and has
hosted over 1000 contests to date. Each contest has a couple thousand
competitors on average. A typical contest takes 2 to 3 hours and contains 5 to
8 problems. Players are ranked by total points, with more points typically
awarded for tougher problems and for early solves. They may also attempt to
“hack” one another’s submissions for bonus points, identifying test cases that
break their solutions.

#### TopCoder contest history

This dataset contains the current entire history of algorithm contests ever
run on the TopCoder.com. TopCoder is a predecessor to Codeforces, with over
1.4 million total users and a long history as a pioneering platform for
programming contests. It hosts a variety of contest types, including over 2000
algorithm contests to date. The scoring system is similar to Codeforces, but
its rounds are shorter: typically 75 minutes with 3 problems.

#### SubRedditSimulator threads

This dataset contains data scraped from the current top-1000 most upvoted
threads on the website reddit.com/r/SubredditSimulator/. Reddit is a social
news aggregation website with over 300 million users. The site itself is
broken down into sub-sites called subreddits. Users then post and comment to
the subreddits, where the posts and comments receive votes from other users.
In the subreddit SubredditSimulator, users are language generation bots
trained on text from other subreddits. Automated posts are made by these bots
to SubredditSimulator every 3 minutes, and real users of Reddit vote on the
best bot. Each post (and its associated comments) can thus be interpreted as a
round of competition between the bots who commented.

#### Synthetic data

This dataset contains 10K players, with skills and performances generated
according to the Gaussian generative model in Section 2. Players’ initial
skills are drawn i.i.d. with mean $1500$ and variance $300$. Players compete
in all rounds, and are ranked according to independent performances with
variance $200$. Between rounds, we add i.i.d. Gaussian increments with
variance $35$ to each of their skills.

###  6.2. Evaluation metrics

To compare the different algorithms, we define two measures of predictive
accuracy. Each metric will be defined on individual contestants in each round,
and then averaged:

$\mathrm{\bf
aggregate(metric)}:=\frac{\sum_{t}\sum_{i\in\mathcal{P}_{t}}\mathrm{\bf
metric}(i,t)}{\sum_{t}|\mathcal{P}_{t}|}.$

#### Pair inversion metric (Herbrich et al., 2006)

Our first metric computes the fraction of opponents against whom our ratings
predict the correct pairwise result, defined as the higher-rated player either
winning or tying:

$\mathrm{\bf pair\\_inversion}(i,t):=\frac{\text{\\# correctly predicted
matchups}}{|\mathcal{P}_{t}|-1}\times 100\%.$

This metric was used in the evaluation of TrueSkill (Herbrich et al., 2006).

#### Rank deviation

Our second metric compares the rankings with the total ordering that would be
obtained by sorting players according to their prior rating. The penalty is
proportional to how much these ranks differ for player $i$:

$\mathrm{\bf
rank\\_deviation}(i,t):=\frac{|\text{actual\\_rank}-\text{predicted\\_rank}|}{|\mathcal{P}_{t}|-1}\times
100\%.$

In the event of ties, among the ranks within the tied range, we use the one
that comes closest to the rating-based prediction.

###  6.3. Empirical results

Dataset | Codeforces | TopCoder | TrueSkill | Elo-MM$\boldsymbol{\chi}$ | Elo-MMR($\boldsymbol{\rho}$)
---|---|---|---|---|---
pair inv. | rank dev. | pair inv. | rank dev. | pair inv. | rank dev. | pair inv. | rank dev. | pair inv. | rank dev.
Codeforces | 78.3% | 14.9% | 78.5% | 15.1% | 61.7% | 25.4% | 78.5% | 14.8% |  78.6% |  14.7%
TopCoder | 72.6% | 18.5% | 72.3% | 18.7% | 68.7% | 20.9% | 73.0% | 18.3% |  73.1% |  18.2%
Reddit | 61.5% | 27.3% | 61.4% | 27.4% | 61.5% |  27.2% | 61.6% | 27.3% | 61.6% | 27.3%
Synthetic | 81.7% | 12.9% |  81.7% |  12.8% | 81.3% | 13.1% |  81.7% |  12.8% | 81.7% | 12.8%
Table 2. Performance of each rating system on the pairwise inversion and rank deviation metrics. Bolded entries denote the best performances (highest pair inv. or lowest rank dev.) on each metric and dataset. Dataset | CF | TC | TS | Elo-MM$\boldsymbol{\chi}$ | Elo-MMR($\boldsymbol{\rho}$)
---|---|---|---|---|---
Codeforces | 212.9 | 72.5 | 67.2 | 31.4 | 35.4
TopCoder | 9.60 | 4.25 | 16.8 | 7.00 | 7.52
Reddit | 1.19 | 1.14 | 0.44 | 1.14 | 1.42
Synthetic | 3.26 | 1.00 | 2.93 | 0.81 | 0.85
Table 3. Total compute time over entire dataset, in seconds.

Recall that Elo-MM$\chi$ has a Gaussian performance model, matching the
modeling assumptions of TopCoder and TrueSkill. Elo-MMR($\rho$), on the other
hand, has a logistic performance model, matching the modeling assumptions of
Codeforces and Glicko. While $\rho$ was included in the hyperparameter search,
in practice we found that all values between $0$ and $1$ produce very similar
results.

To ensure that errors due to the unknown skills of new players don’t dominate
our metrics, we excluded players who had competed in less than 5 total
contests. In most of the datasets, this reduced the performance of our method
relative to the others, as our method seems to converge more accurately.
Despite this, we see in Table 2 that both versions of Elo-MMR outperform the
other rating systems in both the pairwise inversion metric and the ranking
deviation metric.

We highlight a few key observations. First, significant performance gains are
observed on the Codeforces and TopCoder datasets, despite these platforms’
rating systems having been designed specifically for their needs. Our gains
are smallest on the synthetic dataset, for which all algorithms perform
similarly. This might be in part due to the close correspondence between the
generative process and the assumptions of these rating systems. Furthermore,
the synthetic players compete in all rounds, enabling the system to converge
to near-optimal ratings for every player. Finally, the improved TrueSkill
performed well below our expectations, despite our best efforts to improve it;
we suspect that the message-passing algorithm breaks down in contests with a
large number of distinct ranks. To our knowledge, we are the first to present
experiments with TrueSkill on contests where the number of distinct ranks is
in the hundreds or thousands. In preliminary experiments, TrueSkill and Elo-
MMR score about equally when the number of ranks is less than about 60.

Now, we turn our attention to Table 3, which showcases the computational
efficiency of Elo-MMR. On smaller datasets, it performs comparably to the
Codeforces and TopCoder algorithms. However, the latter suffer from a
quadratic time dependency on the number of contestants; as a result, Elo-MMR
outperforms them by almost an order of magnitude on the larger Codeforces
dataset.

Finally, in comparisons between the two Elo-MMR variants, we note that while
Elo-MMR($\rho$) is more accurate, Elo-MM$\chi$ is always faster. This has to
do with the skill drift modeling described in Section 4, as every update in
Elo-MMR($\rho$) must process $O(\log\frac{1}{\epsilon})$ terms of a player’s
competition history.

##  7\. Conclusions

This paper introduces the Elo-MMR rating system, which is in part a
generalization of the two-player Glicko system, allowing an unbounded number
of players. By developing a Bayesian model and taking the limit as the number
of participants goes to infinity, we obtained simple, human-interpretable
rating update formulas. Furthermore, we saw that the algorithm is
asymptotically fast, embarrassingly parallel, robust to extreme performances,
and satisfies the important _aligned incentives_ property. To our knowledge,
our system is the first to rigorously prove all these properties in a setting
with more than two individually ranked players. In terms of practical
performance, we saw that it outperforms existing industry systems in both
prediction accuracy and computation speed.

This work can be extended in several directions. First, the choices we made in
modeling ties, pseudodiffusions, and opponent subsampling are by no means the
only possibilities consistent with our Bayesian model of skills and
performances. Second, one may obtain better results by fitting the performance
and skill evolution models to application-specific data.

Another useful extension would be to team competitions. While it’s no longer
straightforward to infer precise estimates of an individual’s performance,
Elo-MM$\chi$ can simply be applied at the team level. To make this useful in
settings where players may form new teams in each round, we must model teams
in terms of their individual members. In the case where a team’s performance
is modeled as the sum of its members’ independent Gaussian contributions,
elementary facts about multivariate Gaussian distributions enable posterior
skill inferences at the individual level. Generalizing this approach remains
an open challenge.

Over the past decade, online competition communities such as Codeforces have
grown exponentially. As such, considerable work has gone into engineering
scalable and reliable rating systems. Unfortunately, many of these systems
have not been rigorously analyzed in the academic community. We hope that our
paper and open-source release will open new explorations in this area.

## Acknowledgements

The authors are indebted to Daniel Sleator and Danica J. Sutherland for
initial discussions that helped inspire this work, and to Nikita Gaevoy for
the open-source improved TrueSkill upon which our implementation is based.
Experiments in this paper were funded by a Google Cloud Research Grant. The
second author is supported by a VMWare Fellowship and the Natural Sciences and
Engineering Research Council of Canada.

## Appendix

###### Lemma 3.2.

If $f_{i}$ is continuously differentiable and log-concave, then the functions
$l_{i},d_{i},v_{i}$ are continuous, strictly decreasing, and

$l_{i}(p)<d_{i}(p)<v_{i}(p)\text{ for all }p.$

###### Proof.

Continuity of $F_{i},f_{i},f^{\prime}_{i}$ implies that of
$l_{i},d_{i},v_{i}$. It’s known (An, 1997) that log-concavity of $f_{i}$
implies log-concavity of both $F_{i}$ and $1-F_{i}$. As a result, $l_{i}$,
$d_{i}$, and $v_{i}$ are derivatives of strictly concave functions; therefore,
they are strictly decreasing. In particular, each of

$v^{\prime}_{i}(p)=\frac{f^{\prime}_{i}(p)}{F_{i}(p)}-\frac{f_{i}(p)^{2}}{F_{i}(p)^{2}},\quad
l^{\prime}_{i}(p)=\frac{-f^{\prime}_{i}(p)}{1-F_{i}(p)}-\frac{f_{i}(p)^{2}}{(1-F_{i}(p))^{2}},$

are negative for all $p$, so we conclude that

$\displaystyle
d_{i}(p)-v_{i}(p)=\frac{f^{\prime}_{i}(p)}{f_{i}(p)}-\frac{f_{i}(p)}{F_{i}(p)}$
$\displaystyle=\frac{F_{i}(p)}{f_{i}(p)}v^{\prime}_{i}(p)<0,$ $\displaystyle
l_{i}(p)-d_{i}(p)=-\frac{f^{\prime}_{i}(p)}{f_{i}(p)}-\frac{f_{i}(p)}{1-F_{i}(p)}$
$\displaystyle=\frac{1-F_{i}(p)}{f_{i}(p)}l^{\prime}_{i}(p)<0.$

∎

###### Theorem 3.3.

Suppose that for all $j$, $f_{j}$ is continuously differentiable and log-
concave. Then the unique maximizer of $\Pr(P_{i}=p\mid E^{L}_{i},E^{W}_{i})$
is given by the unique zero of

$Q_{i}(p)=\sum_{j\succ i}l_{j}(p)+\sum_{j\sim i}d_{j}(p)+\sum_{j\prec
i}v_{j}(p).$

###### Proof.

First, we rank the players by their buckets according to $\lfloor
P_{j}/\epsilon\rfloor$, and take the limiting probabilities as
$\epsilon\rightarrow 0$:

$\displaystyle\Pr(\lfloor\frac{P_{j}}{\epsilon}\rfloor>\lfloor\frac{p}{\epsilon}\rfloor)$
$\displaystyle=\Pr(p_{j}\geq\epsilon\lfloor\frac{p}{\epsilon}\rfloor+\epsilon)$
$\displaystyle=1-F_{j}(\epsilon\lfloor\frac{p}{\epsilon}\rfloor+\epsilon)\rightarrow
1-F_{j}(p),$
$\displaystyle\Pr(\lfloor\frac{P_{j}}{\epsilon}\rfloor<\lfloor\frac{p}{\epsilon}\rfloor)$
$\displaystyle=\Pr(p_{j}<\epsilon\lfloor\frac{p}{\epsilon}\rfloor)$
$\displaystyle=F_{j}(\epsilon\lfloor\frac{p}{\epsilon}\rfloor)\rightarrow
F_{j}(p),$
$\displaystyle\frac{1}{\epsilon}\Pr(\lfloor\frac{P_{j}}{\epsilon}\rfloor=\lfloor\frac{p}{\epsilon}\rfloor)$
$\displaystyle=\frac{1}{\epsilon}\Pr(\epsilon\lfloor\frac{p}{\epsilon}\rfloor\leq
P_{j}<\epsilon\lfloor\frac{p}{\epsilon}\rfloor+\epsilon)$
$\displaystyle=\frac{1}{\epsilon}\left(F_{j}(\epsilon\lfloor\frac{p}{\epsilon}\rfloor+\epsilon)-F_{j}(\epsilon\lfloor\frac{p}{\epsilon}\rfloor)\right)\rightarrow
f_{j}(p).$

Let $L_{jp}^{\epsilon}$, $W_{jp}^{\epsilon}$, and $D_{jp}^{\epsilon}$ be
shorthand for the events
$\lfloor\frac{P_{j}}{\epsilon}\rfloor>\lfloor\frac{p}{\epsilon}\rfloor$,
$\lfloor\frac{P_{j}}{\epsilon}\rfloor<\lfloor\frac{p}{\epsilon}\rfloor$, and
$\lfloor\frac{P_{j}}{\epsilon}\rfloor=\lfloor\frac{p}{\epsilon}\rfloor$.
respectively. These correspond to a player who performs at $p$ losing,
winning, and drawing against $j$, respectively, when outcomes are determined
by $\epsilon$-buckets. Then,

$\displaystyle\Pr(E^{W}_{i},E^{L}_{i}\mid P_{i}=p)$
$\displaystyle=\lim_{\epsilon\rightarrow 0}\prod_{j\succ
i}\Pr(L_{jp}^{\epsilon})\prod_{j\prec i}\Pr(W_{jp}^{\epsilon})\prod_{j\sim
i,j\neq i}\frac{\Pr(D_{jp}^{\epsilon})}{\epsilon}$
$\displaystyle=\prod_{j\succ i}(1-F_{j}(p))\prod_{j\prec
i}F_{j}(p)\prod_{j\sim i,j\neq i}f_{j}(p),$ $\displaystyle\Pr(P_{i}=p\mid
E^{L}_{i},E^{W}_{i})$ $\displaystyle\propto
f_{i}(p)\Pr(E^{L}_{i},E^{W}_{i}\mid P_{i}=p)$ $\displaystyle=\prod_{j\succ
i}(1-F_{j}(p))\prod_{j\prec i}F_{j}(p)\prod_{j\sim i}f_{j}(p),$
$\displaystyle\frac{\mathrm{d}}{\mathrm{d}p}\ln\Pr(P_{i}=p\mid E^{L}_{i},$
$\displaystyle E^{W}_{i})=\sum_{j\succ i}l_{j}(p)+\sum_{j\prec
i}v_{j}(p)+\sum_{j\sim i}d_{j}(p)=Q_{i}(p).$

Since Lemma 3.2 tells us that $Q_{i}$ is strictly decreasing, it only remains
to show that it has a zero. If the zero exists, it must be unique and it will
be the unique maximum of $\Pr(P_{i}=p\mid E^{L}_{i},E^{W}_{i})$.

To start, we want to prove the existence of $p^{*}$ such that
$Q_{i}(p^{*})<0$. Note that it’s not possible to have $f^{\prime}_{j}(p)\geq
0$ for all $p$, as in that case the density would integrate to either zero or
infinity. Thus, for each $j$ such that $j\sim i$, we can choose $p_{j}$ such
that $f^{\prime}_{j}(p_{j})<0$, and so $d_{j}(p_{j})<0$. Let
$\alpha=-\sum_{j\sim i}d_{j}(p_{j})>0$.

Let $n=|\\{j:\,j\prec i\\}|$. For each $j$ such that $j\prec i$, since
$\lim_{p\rightarrow\infty}v_{j}(p)=0/1=0$, we can choose $p_{j}$ such that
$v_{j}(p_{j})<\alpha/n$. Let $p^{*}=\max_{j\preceq i}p_{j}$. Then,

$\sum_{j\succ i}l_{j}(p^{*})\leq 0,\quad\sum_{j\sim
i}d_{j}(p^{*})\leq-\alpha,\quad\sum_{j\prec i}v_{j}(p^{*})<\alpha.$

Therefore,

$\displaystyle Q_{i}(p^{*})$ $\displaystyle=\sum_{j\succ
i}l_{j}(p^{*})+\sum_{j\sim i}d_{j}(p^{*})+\sum_{j\prec i}v_{j}(p^{*})$
$\displaystyle<0-\alpha+\alpha=0.$

By a symmetric argument, there also exists some $q^{*}$ for which
$Q_{i}(q^{*})>0$. By the intermediate value theorem with $Q_{i}$ continuous,
there exists $p\in(q^{*},p^{*})$ such that $Q_{i}(p)=0$, as desired. ∎

## References

  * (1)
  * Cod ([n.d.]a) CodeChef Rating System.  codechef.com/ratings
  * Cod ([n.d.]b) Codeforces Rating System.  codeforces.com/blog/entry/20762
  * pok ([n.d.]) Farming Volatility: How a major flaw in a well-known rating system takes over the GBL leaderboard.  reddit.com/r/TheSilphRoad/comments/hwff2d/farming_volatility_how_a_major_flaw_in_a/
  * Hal ([n.d.]) Halo Xbox video game franchise: in numbers.  telegraph.co.uk/technology/video-games/11223730/Halo-in-numbers.html
  * Kag ([n.d.]) Kaggle Progression System.  kaggle.com/progression
  * Lee ([n.d.]) LeetCode Rating System.  leetcode.com/discuss/general-discussion/468851/New-Contest-Rating-Algorithm-(Coming-Soon)
  * Top ([n.d.]) TopCoder Algorithm Rating System.  topcoder.com/community/competitive-programming/how-to-compete/ratings
  * Spa ([n.d.]) Why Are Obstacle-Course Races So Popular?  theatlantic.com/health/archive/2018/07/why-are-obstacle-course-races-so-popular/565130/
  * Agarwal and Lorch (2009) Sharad Agarwal and Jacob R. Lorch. 2009.  Matchmaking for online games and other latency-sensitive P2P systems. In _SIGCOMM 2009_. 315–326.
  * An (1997) Mark Yuying An. 1997\.  Log-concave probability distributions: Theory and statistical testing.  _Duke University Dept of Economics Working Paper_ 95-03 (1997).
  * Chen and Joachims (2016) Shuo Chen and Thorsten Joachims. 2016.  Modeling Intransitivity in Matchup and Comparison Data. In _WSDM 2016_. 227–236.
  * Dangauthier et al. (2007) Pierre Dangauthier, Ralf Herbrich, Tom Minka, and Thore Graepel. 2007.  TrueSkill Through Time: Revisiting the History of Chess. In _NeurIPS 2007_. 337–344.
  * Elo (1961) Arpad E. Elo. 1961\.  New USCF rating system.  _Chess Life_ 16 (1961), 160–161.
  * Forišek (2009) RNDr Michal Forišek. 2009\.  Theoretical and Practical Aspects of Programming Contest Ratings.  (2009).
  * Freedman (1963) David A Freedman. 1963\.  On the asymptotic behavior of Bayes’ estimates in the discrete case.  _The Annals of Mathematical Statistics_ (1963), 1386–1403.
  * Glickman (1995) Mark E Glickman. 1995\.  A comprehensive guide to chess ratings.  _American Chess Journal_ 3, 1 (1995), 59–102.
  * Glickman (1999) Mark E Glickman. 1999\.  Parameter estimation in large dynamic paired comparison experiments.  _Applied Statistics_ (1999), 377–394.
  * Glickman (2012) Mark E Glickman. 2012\.  Example of the Glicko-2 system.  _Boston University_ (2012), 1–6.
  * Gong et al. (2020) Linxia Gong, Xiaochuan Feng, Dezhi Ye, Hao Li, Runze Wu, Jianrong Tao, Changjie Fan, and Peng Cui. 2020\.  OptMatch: Optimized Matchmaking via Modeling the High-Order Interactions on the Arena. In _KDD 2020_. 2300–2310.
  * Herbrich et al. (2006) Ralf Herbrich, Tom Minka, and Thore Graepel. 2006.  TrueSkill${}^{\mbox{TM}}$: A Bayesian Skill Rating System. In _NeurIPS 2006_. 569–576.
  * Huang et al. (2006) Tzu-Kuo Huang, Chih-Jen Lin, and Ruby C. Weng. 2006\.  Ranking individuals by group comparisons. In _ICML 2006_. ACM, 425–432.
  * Kovalchik (2020) Stephanie Kovalchik. 2020\.  Extension of the Elo rating system to margin of victory.  _International Journal of Forecasting_ (2020).
  * Li et al. (2018) Yao Li, Minhao Cheng, Kevin Fujii, Fushing Hsieh, and Cho-Jui Hsieh. 2018.  Learning from Group Comparisons: Exploiting Higher Order Interactions. In _NeurIPS 2018_. 4986–4995.
  * Minka et al. (2018) Tom Minka, Ryan Cleven, and Yordan Zaykov. 2018.  _TrueSkill 2: An improved Bayesian skill rating system_.  Technical Report MSR-TR-2018-8. Microsoft.
  * Nikolenko et al. (2010) Sergey I. Nikolenko, Alexander, and V. Sirotkin. 2010\.  Extensions of the TrueSkill TM rating system. In _In Proceedings of the 9th International Conference on Applications of Fuzzy Systems and Soft Computing_. 151–160.
  * Premelč et al. (2019) Jerneja Premelč, Goran Vučković, Nic James, and Bojan Leskošek. 2019\.  Reliability of judging in DanceSport.  _Frontiers in psychology_ 10 (2019), 1001.
  * Stone and Matsakis (2017) Josh Stone and Nicholas D Matsakis.  The Rayon library (Rust Crate).  crates.io/crates/rayon
  * Yang et al. (2014) Lin Yang, Stanko Dimitrov, and Benny Mantin. 2014\.  Forecasting sales of new virtual goods with the Elo rating system.  _Journal of Revenue and Pricing Management_ 13, 6 (Dec. 2014), 457–469.