Rating represents win probability. In a match, for every 400 points player A is rated higher than player B, player A is 10 times more likely to win (exponentially).

• If player A is rated 400 points higher than player B, then out of 11 games, player A should win 10 and player B should win 1.
• If player A is rated 800 points higher than player B, then out of 101 games, player A should win 100 and player B should win 1.

This can be written mathematically in terms of the sigmoid function as $$$\sigma(\Delta / \beta)$$$, where $$$\beta = \frac{400}{\ln 10} = 173.7178$$$.

I think this is interesting.

In order to create a random process that aligns with the true skills of the players, we use the following system:

Suppose I'm 3000 and Benq is 3800. Out of 101 contests, I should beat him in 1 and he should beat me in 100. Let's give me 1 "share" and Benq 100 "shares". Each share is an independent uniformly random real number from 0 to 1. Clearly, out of all 101 shares, each of them has an equal probability of being the highest. So if I have 1 and he has 100, then he should beat me 100 out of 101 times, as desired.

To extend this to a massive competition scenario, we simply have each contestant take the highest number of their shares. Then we'll rank in order of highest number to lowest number. With a bit of work, you can see that for any pairwise comparison between players $$$i$$$ and $$$j$$$, the process aligns with what is expected to happen.

This is not over yet, because drawing 100 or 1000 shares for LGMs takes a lot of time. And what about fractional shares?

Well, luckily we'll use the funny fact that if $$$x, y, z$$$ are uniform in $$$[0, 1]$$$, then the distribution of $$$max(x, y)$$$ and $$$\sqrt{z}$$$ are actually the same. And this generalizes: the maximum of $$$x_1, ..., x_n$$$ is identical in distribution to $$$z^{1/n}$$$. And it also works for rational (and then by approximation, real) $$$n$$$.

So, in the code, we set the arbitrary starting point of a 3000 rated player having 1 share. So a 3400 would have 10; a 2600 would have 0.1. The exact starting point isn't super important, but do be aware of floating point precision. Then, we calculate the number of shares each player has, which may be a real number. Then rolling their maximum share is random.random() ** (1/shares).

Then, after that, we just sort the list of players, and update the ratings according to CF's formula. We also apply the "rating inflation adjustment" to keep the sum of all ratings the same.

True rating 3750 would get to 4012 (+262)
True rating 3700 would get to 3951 (+251)
True rating 3650 would get to 3904 (+254)
True rating 3600 would get to 3844 (+244)
True rating 3550 would get to 3782 (+232)
True rating 3500 would get to 3725 (+225)
True rating 3400 would get to 3614 (+214)
True rating 3350 would get to 3551 (+201)
True rating 3300 would get to 3491 (+191)
True rating 3250 would get to 3437 (+187)
True rating 3200 would get to 3379 (+179)
True rating 3150 would get to 3323 (+173)
True rating 3100 would get to 3267 (+167)
True rating 3050 would get to 3208 (+158)
True rating 3000 would get to 3152 (+152)
True rating 2950 would get to 3099 (+149)
True rating 2900 would get to 3040 (+140)
True rating 2850 would get to 2987 (+137)
True rating 2800 would get to 2930 (+130)
True rating 2750 would get to 2871 (+121)
True rating 2700 would get to 2815 (+115)
True rating 2650 would get to 2758 (+108)
True rating 2600 would get to 2702 (+102)
True rating 2550 would get to 2644 (+94)
True rating 2500 would get to 2586 (+86)
True rating 2450 would get to 2529 (+79)
True rating 2400 would get to 2470 (+70)
True rating 2350 would get to 2412 (+62)
True rating 2300 would get to 2350 (+50)
True rating 2250 would get to 2290 (+40)
True rating 2200 would get to 2227 (+27)
True rating 2150 would get to 2166 (+16)
True rating 2100 would get to 2102 (+2)
True rating 2050 would get to 2037 (-13)
True rating 2000 would get to 1970 (-30)
True rating 1950 would get to 1903 (-47)
True rating 1900 would get to 1831 (-69)

greateric is currently rated 2141 and just placed 29th in round 1108 div 2, and because he blackmailed Mike, this round is rated for him.

We can either explicitly store everybody's rating deviation, or, what is closer to the existing system, we'll just arbitrarily say everyone's rating deviation is 100. So we'll store the distribution of greateric's skill numerically (for now, it's just a normal distribution):

Normal(mu=2141, sigma=100)
x=     probability density
...
2140   0.00398922
2141   0.00398942
2142   0.00398922
...
2300   0.00112704
...

Now, we need to calculate the likelihood, if you remember how that works from my last blog. The likelihood of rating $$$y$$$ asks, "if our rating was actually $$$y$$$, what is the probability we observe what we observe?" In this scenario, it's the probability of placing $$$29$$$th if my rating was $$$y$$$.

Calculating the likelihood is expensive — you're essentially asking, out of $$$n$$$ participants, what is the probability you lose to $$$28$$$ of them? The probability you lose to each contestant is different, since it depends on the difference in rating between your pretend rating $$$y$$$ and their rating.

Luckily, you can model this as the probability of a sum of 0/1 Bernoulli variables equalling $$$k = 28$$$. This can be done with DP in $$$O(nk) = O(n^2)$$$, or via generating functions and FFT in $$$O(n \operatorname{polylog} n)$$$.

Then, multiply the prior PDF and the likelihood pointwise, and renormalize appropriately. This is the posterior. Calculate a summary statistic, you can do this with mode, mean, or median of the resulting distribution, and make this the new rating.

This should, theoretically, be the most statistically sound method, and should outperform the current heuristic of moving the rating halfway to the perf of the place that is the geometric mean of the expected and actual place. The drawback is that it is fairly expensive. If you keep track of $$$m$$$ values in the distribution, then for each player you have to calculate $$$m$$$ likelihoods in $$$O(n \operatorname{polylog} n)$$$ each, for a total time of $$$O(n^2 m \operatorname{polylog} n)$$$ time. Depending on what $$$m$$$ is in real life, you could also try precomputing all the likelihoods, since you pay $$$O(n \operatorname{polylog} n)$$$ once to get the entire polynomial, giving you the likelihoods for every placing of a specific rating. If $$$M$$$ is the number of rating divisions across the entire rating space, you'd pay only $$$O(nm + Mn \operatorname{polylog} n)$$$, which should be better if $$$M \lt nm$$$, which is probably true.

Take a real life example with $$$n = 30{,}000$$$. I asked ChatGPT to write a python script to do FFT multiplication and its script can multiply $$$30{,}000$$$ polynomials using FFT in 0.25 seconds. If we assume a precision of 1 rating point (probably good enough, since we're more interested in the shape of the distribution anyway rather than specific points), then let's say there are $$$M = 6000$$$ (say, from -500 to +5500) useful places to calculate the likelihood, and $$$m \approx 800$$$ (go out $$$4\sigma$$$, or dynamically calculate the lower and upper bound based on when the probabilities reach a threshold of negligible) because going too far isn't super helpful if all the probabilities are tiny anyway. Then 6000 of these FFTs will take around 25 minutes to calculate (or less, since it's parallelizable) and a few hundred MB of memory to store, and the $$$O(nm)$$$ update step should take less than a few seconds. Not too bad? There are probably more small improvements, like maybe bundling multiple users of the same rating together.