Alright, clickbait title aside, how do tourist and jiangly get to 4000 rating? In chess, real life ratings cap out at around 2900, and even on online sites like Lichess, the highest bullet players are 3300-3400, and just around 3000 for the other modes.

Also, anecdotally, if rating is correct, the model predicts that someone who is 2940 should beat me 99.1% of the time. I have a gut feeling I beat more than 0.9% of GMs and LGMs in round 1105 and round 1108.

Review on rating models if you forgot

The mechanistic explanation

Okay, let me explain two reasons that could potentially cause this and why this isn't pure cope.

1. Event variance

A 400 higher rating implies a 10x higher chance to win a game. But what is a "game"?

Suppose I have created a game called "Super-Chess" where you play best 2 out of 3. Assume for simplicity that there are no draws. If A is rated 400 higher than B, then A should win $$$\frac{10}{11}$$$ of the time against B in a single game. But in a round of 3 game of "Super-Chess", A's win chance is actually

$$$\displaystyle P(A^3) + P(A^2B^1) = \left(\frac{10}{11}\right)^3 + 3\left( \frac{10}{11} \right)^2\left( \frac{1}{11} \right) \approx 97.67\%.$$$

So, in "Super-Chess", A would be rated about 649 points higher (because $$$\sigma(649/\beta) = 0.9767$$$), instead of 400.

The main point here is that if a "game" has less variance, then ratings will be stretched out more. In the case of Codeforces, a "game" is an entire contest, which contains multiple problems. So this can serve to reduce variance and stretch the ratings out a bit more.

2. (What we're going to investigate today) Flawed rating calculation

According to Mike's blog, the rating delta is half of the difference between (old rating) and (performance of the place that is the geometric mean between the expected place and actual place).

This calculation might be biased upwards, since by AM-GM the geometric mean is always smaller than the arithmetic mean. Also, near the top of the leaderboard, this difference can be dramatic, since performance can change by 50-100 by moving a single place.

Methodology

We will sample a few div1 or div1+2 rounds (and we're doing both modern and pre-AI rounds for fun). For each one, we'll run simulations of a user with rating $$$r$$$:

Use code I already wrote for the old "are div1 ratings harder" blog to calculate the performance of each placing
Calculate this user's expected placing if their rating is $$$r$$$
Simulate the user's actual placing by just randomly rolling 0/1 for each participant. This should, at least in theory, model a realistic perf that the user gets.
Calculate the delta if they got this placing in round, and calculate the expected value over many trials (1000 per rating per contest).

We'll then aggregate total values and see if there are differences in the expected rating change if you are of different ratings.

Results

Here's your high-res graph again:

The relation is almost perfectly exponential — it turns into a line when you change the Y to a log scale. If you're 3600, you could be earning 5-10 undeserved points of delta every contest! But if you're 3000 or below, you get less than a point.

Does this actually affect us in real life?

These differences don't seem to be big enough to matter.

If your rating is 3500, you can maintain it with around 3480 level skill.
If your rating is 3400, you can maintain it with around 3385 level skill.

That seems inconsequential.

So this blog is complete cope. Unless...

Community simulation

It's possible that the high rated LGMs can pull each other up. Rating is relative — if Mike manually added 300 rating to every LGM, and they only did div0s with each other, their inflated ratings would stay.

But is this a big enough effect in practice? Could the LGMs keep their inflated ratings without leaking them back to everyone else? Let's simulate again.

Methods

We simulate all div1 players, with their ratings rounded down to the nearest 50 just to make things a bit easier. The playerbase looks like:

{3750: 1, 3700: 1, 3650: 2, 3600: 1, 3550: 2, 3500: 1, 3400: 2, 3350: 4, 3300: 3, ..., 2100: 993, 2050: 357, 2000: 531, 1950: 765, 1900: 1165}

We'll initialize each player with their real rating / their actual skill, and nominal rating / CF rating. For example, Benq becomes a Player(real_rating=3750, rating=3750).

How to simulate a the randomness in placings?

We simulated 200 trials, each of 100 contests in sequence. After each contest, nominal ratings are updated, but we assume their true ratings/skills do not change.

Results

Here are the graphs:

1900-2400

2400-3000

3000+

Everything

So, it seems like this is true! There is some fairly dramatic inflation at the top. And it only takes maybe 40 contests for it to fully converge. And surprisingly, it starts as early as deep red level: if your true skill is 2600, your actual rating will probably be around 2702. For LGMs, the inflation can be as high as 150-200 points.

Table of results for each rating

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)

Is this a big problem?

Not really. It just means that the scale is a bit more stretched out than it should, especially near the top. The ratings still maintain the ability to compare.

I would assume it would also be possible to fix with some math by switching the update formula to something based on likelihood estimation. We can't simply use performance is that the performance of 1st place is infinitely large. We could do numerical max a posteriori estimation — with some rating deviation (either explicitly stored or implicitly set to, say, 100, for everyone), and we numerically update the distribution (as in, we store the distribution as a table of probability densities at, say, 0.1 rating increments) and calculate the new center (whether that be expectation, median, mode, or whatever). Also I guess calculating likelihood (which is $$$P(\text{get place 67} | \text{rating 2900})$$$) is not trivial, since you have some weird sum of Bernoulli variables.

Math rant about making the perfect system

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)$$$.

Genfunc

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.

That's it for today! As always, thanks for reading, and you can find the code and figures on my GitHub.