TLDR: Exact implementation of CF rating system described in original blog yields systematic bias. Mathematically impossible rating deflation detected in certain contests. Possible links to % of new accounts.
Originally uploaded onto another account, I feel like the blog was poorly written back so I rewritten certain parts and upload it here instead.
Background
A few days ago, I was messing around and trying to implement my own rating change calculator for Codeforces (basically my implementation of Carrot). All formulas and calculations are derived from this blog. When I compared my results with Codeforces actual rating changes, I observed a very significant positive bias.
Keep in mind that all calculations are done with True rating, Which accounted for ramp-up offset. The graph only includes data from 12 hand-picked contests (1000, 1100, 1200, 1300, 1400, 1500, 1585, 2000, 2050, 2130, 2200, 2234), but the trend generalize to other contests too (more on this later).
As for why Carrot tends to have a negative bias instead, I believe Carrot uses displayed rating for new players instead of true rating (?). Not too sure on this, but feel free to leave a comment if you have any info on this.
While troubleshooting the issue, I discovered that lots of Codeforces rounds has mathematically impossible deflation.
As explained by this blog, to prevent rating inflation (top rated players repeatedly gaining rating from low rated players), Codeforces employs a layer of rating adjustment:
Let $$$s_{i}$$$, $$$r_{i}$$$ be the rating before contest and rating after preliminary calculations of $$$i$$$-th player. Let $$$\Delta_{i} = r_{i} - s_{i}$$$. Keep in mind $$$=$$$ is assignment.
- $$$r_{i} = r_{i}-\overline{\Delta}-1$$$, ($$$\overline{\Delta}$$$ is arithmetic mean of $$$\Delta_{i}$$$)
- $$$r_{i} = r_{i} + min(max(-\frac{\sum_{i \in S}\Delta_{i}}{|S|},-10),0) $$$, ($$$S$$$ is the set of $$$min(n,4\sqrt{n})$$$ players with highest $$$s_{i}$$$)
Looking at the formula, we can see that total delta is at most $$$-n$$$ after the first round of adjustment, and at most $$$-11n$$$ after the second. Hence, it is impossible for a round to have $$$\overline{\Delta} \lt -11$$$ after all the adjustments, yet the data paints the opposite story. Perhaps Codeforces has another hidden layer of adjustment we didn't know about?
Possible theory
I spent some time thinking about where the deflation (and the positive bias) could've come from. So far, my most convincing theory is that it correlates with the number of "ramping-up" accounts in each contest.
Take a look at these graphs: 
The first graph describes the composition of new/old accounts in each sampled contest, and the third describes mean error for each group of players if we use the original algorithm to predict rating changes.
$$$S_{x}$$$ refers to new players participating in their $$$x$$$-th contests, and $$$\text{old}$$$ refers to players who exhausted all their ramp-up offset, or are from the old ramp-up system.
From here, we can see a few things:
- Errors for contests with close to $$$100\%$$$ players from the $$$\text{old}$$$ group are near $$$0$$$. (VERY SUS)
- Errors for $$$S_{1}$$$ are always close to $$$0$$$. (Sorta sus?)
- Errors scales with $$$\%$$$ of new players (Not a very clear trend)
I've also tried looking at other aspects (error by rank/error by rating), but error by %new accounts seems the most plausible to me. And intuitively, this makes sense if the goal is to prevent rating of good players to spiral out of control by siphoning the tasteful 1400 rating from new accounts. I can definitely see a system where they add an additional offset for older accounts.
Overtaking higher rated players by… performing worse than them
In the original blog, the inflation adjustment for all players in a contest is uniform. Since the error we get is most definitely not uniformed across all players, I suspected there might be a case where the following condition is violated:
“If the participant A had worse rating than the participant B before the contest and finished the contest on the worse place then after recalculations the the rating of A can’t be greater than the rating of B”
Turns out, there is!
Look at vernov.egor and unchainedos. If we work out their true rating, it would’ve been $$$1413 \to 1290$$$ for vernov.egor and $$$1400 \to 1299$$$ for unchainedos. Granted unchainedos didn’t rank strictly lower than vernov.egor, but we can all agree that this kind of overtake should not have happened.
Concluding remarks
The point I’m trying to make is, The official Codeforces blog on their rating system doesn’t seem to fully explain every single step in their calculations, unless there were some updates to the system since 2015 that I missed. If that is the case, feel free to point it out.
Codeforces team, if you see this, please confirm whether there are additional hidden mechanism related to rating inflation or not. I'd love to know either way.
Obviously, it is entirely possible that there are errors in my data pipeline and calculations, which is another reason why I wanted to post this blog. I will probably add a link to my calculations in a future update. But for now, that’s all I wanted to say.
