Open Codeforces Rating System [updated on October 2015]

Правка en1, от MikeMirzayanov, 2015-10-26 03:24:11

Starting from October 2015 ratings formulas are open. They are given in the post. It is likely that from time to time we will change them slightly, it will be reflected here.

The basic idea of Codeforces rating system is to generalize Elo rating to support games with multiple participants.

Each community member is characterized by value ri — integer number. Roughly speaking, the higher value means better results in the contests. Rating is calculated/recalculated so that the equality strives to be correct:

where Pi, j is probability that the i-th participant has better result than the j-th participant. Therefore for two participants the probability to win/lose depends on subtraction of their ratings. For example, if the difference of ratings is equal to 200 then stronger participant will win with probability ~0.75. If the difference of ratings is equal to 400 then stronger participant will win with probability ~0.9.

After a contest the values ri change in a way to satisfy main formula better.

Let’s calculate expected place seedi for each participant before contest. It equals to the sum over all other participants of probabilities to win (to have better place than) the i-th plus one because of 1-based place indices:

For example, before Codeforces Round 318 [RussianCodeCup Thanks-Round] (Div. 1) tourist had rating 3503 and his seed was ~1.7, and Petr had rating 3029 and expected place ~10.7.

General idea is to increase ri if actual place is better than seedi and to decrease ri if actual place is worse than seedi.

Having seedi and actual place, let’s calculate their geometric mean mi. You can think about it as an something average between seedi and actual place shifted to the better place. Using binary search find such rating value R which the i-th participant should have to have a seedi = mi. Obviously the rating ri should be modified to become closer to R. We use di = (R - ri) / 2 as rating change for the i-th participant.

It's almost all except the phase of fighting against inflation. Inflation works as follows: the rich get richer. We will try to avoid it. If we assume that the rating was already calculated fair (i.e. everybody has perfect statistically based rating) then expected change of rating after a contest is equal to zero for any participant.

Choose a group of the most rated (before the round) participants and decide that their total rating shouldn’t change. We use heuristic value as a size of such group. Let’s find the sum of di over participants from group and adjust all values di (for all participants) to make the sum to be zero. In other words, ri = ri + inc, where inc =  - sums / s, sums is sum of di over s participants from chosen group.

After the round 327 we restricted the effect in following way. Firstly, we do ri = ri + inc, where inc =  - sum(di) / n - 1, sum(di) is sum of all di. It makes the sum of all di to be near zero and non-positive in the same time. Secondly, we apply idea from the previous paragraph, but inc = min(max( - sums / s,  - 10), 0). Thus, the effect of modification can not reduce rating for more than ~10 points.

By the way, for any consistent rating the following assertions should be true:

  • 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
  • if A finished the contest better than B but A had worse rating before the contest then A should have equal or greater rating change than B.

In particular, formulas are tested to satisfy the both items on each ratings recalculation.

You may read the actual Codeforces code to recalculate ratings here: 13861109.

Теги ratings, rating, points, codeforces, elo, new life

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский MikeMirzayanov 2015-11-01 03:01:07 2 Tiny change: '}^nP_{j,i}.$$\n\nFor' -> '}^nP_{j,i}+1.$$\n\nFor'
ru16 Русский MikeMirzayanov 2015-11-01 03:00:40 2 Мелкая правка: '}^nP_{j,i}.$$\n\nНап' -
en1 Английский MikeMirzayanov 2015-10-26 03:24:11 4086 Initial revision for English translation
ru15 Русский MikeMirzayanov 2015-10-25 23:13:48 344 Обновления перед пересчетом раунда 327
ru14 Русский MikeMirzayanov 2015-10-06 21:31:49 0 (опубликовано)
ru13 Русский MikeMirzayanov 2015-10-06 21:08:20 13
ru12 Русский MikeMirzayanov 2015-10-06 21:07:42 15
ru11 Русский MikeMirzayanov 2015-10-06 21:00:43 11 Мелкая правка: 'которых и здесь речь.\n \nВполне вер' -> 'которых и пойдет здесь речь. Вполне вер'
ru10 Русский MikeMirzayanov 2015-10-06 20:57:14 48 Мелкая правка: 'its_{j = 1, j \ne i}^' -
ru9 Русский MikeMirzayanov 2015-10-06 20:55:22 6
ru8 Русский MikeMirzayanov 2015-10-06 20:52:16 75
ru7 Русский MikeMirzayanov 2015-10-06 20:41:47 6
ru6 Русский MikeMirzayanov 2015-10-06 20:41:16 3 Мелкая правка: 'стников). Понятно, что текущий рей' -> 'стников). Текущий рей'
ru5 Русский MikeMirzayanov 2015-10-06 20:40:46 25 Мелкая правка: 'стников). Понятно, что текущий рей' -> 'стников). Текущий рей'
ru4 Русский MikeMirzayanov 2015-10-06 20:39:22 15 Мелкая правка: 'стников). Понятно, что текущий рей' -> 'стников). Текущий рей'
ru3 Русский MikeMirzayanov 2015-10-06 20:38:11 8 Мелкая правка: ' следует убавить, а есл' -> ' следует уменьшить, а есл'
ru2 Русский MikeMirzayanov 2015-10-06 20:37:10 2 Мелкая правка: '$\n\nгде $$P_{i,j}$$ вероятно' -> '$\n\nгде $P_{i,j}$ вероятно'
ru1 Русский MikeMirzayanov 2015-10-06 20:36:56 3873 Первая редакция (сохранено в черновиках)