Интернет-вещание РАДИО СПОРТ

• WWRR •
• Вверх •
• МИР РЕЙТИНГОВ •
• ФУТБОЛ •
• ХОККЕЙ •
• ТЕННИС •
• ШАХМАТЫ •
• ФОРМУЛА 1 •
• ОЛИМПИАДЫ •
• CF •
• БЕНДИ •
• ВОЛЕЙБОЛ •
• ЭКОНОМИКА •
• БИБЛИОТЕКА •
• T1-12 МИФИ •
• Яхты ... •
• Гандбол •
• Радио СПОРТ •
• Е Клуб •
• Об авторе •

Гостевая
 

271314@mail.ru

Проблема ранжирования

Ю.Волвовский

yuri.volvovskiy@pvspricing.com

Проблема ранжирования довольно неприятна для всех соревнований, в которых участвуют несколько команд, но которые по сути представляют собой серию индивидуальных поединков. Таковы все футбольные, баскетбольные и тому подобные турниры, таковы же и шахматные турниры. Это в беге легко - прибежавший первым бежал быстрее всех остальных, прибежавший вторым - быстрее всех, кроме первого. В шахматных же турнирах зачастую каждый участник проигрывает как минимум одну партию. Но если А проиграл Б, то как может А быть сильнее Б? И кто тогда победитель? Однозначного решения нет - все зависит от критериев, которыми мы захотим пользоваться.

Традиционный подход

Традиционно проблема ранжирования решается следующим образом: игроку дается  w очков за каждую победу,  d очков за ничью и l очков за поражение. Мы наложим два стандартных условия: w > d > l ≥ 0 и d = 0.5*(w + l). Если игрок А сыграл несколько партий, из которых a завершились победой, b - ничьей, и c - поражением, то он в общей сложности наберет aw + bd + cl очков. В турнире с n участниками, число очков, набранное i-ым игроком, B⁽¹⁾­_i­ , может быть записано формулой:

B⁽¹⁾­_i­    = ∑_j≠i p_ij B⁽⁰⁾_j

где p_ij - очки набранные игроком i против игрока j , а   B⁽⁰⁾_j = 1 (этот выбор обозначений станет понятен позже).  В турнире, где все участники сыграли одинаковое число партий, чем больше очков набрал игрок, тем выше его итоговое место. Очевидно, ранжирование не изменится. если мы умножим w,d и l на одно и то же число. Поэтому в дальнейшем мы будем считать, что d = 1, w = 1 + k, а l = 1 – k. У описанной системы есть по крайней мере один существенный недостаток: очень часто два участника набирают одно и тоже число очков. Чтобы разрешить проблему ранжирования в этом случае приходится прибегать к дополнительным коэффициентам, из которых наиболее разумным для круговых турниров является коэффициент Бергера, B⁽²⁾­_i­ , определяемый по формуле

B⁽²⁾­_i­    = ∑_j≠i p_ij B⁽¹⁾_j.

Это определение представляется нам удачным по двум причинам. Во-первых, его легко обобщить: например, если случилось, что два участника набрали одинаковое число очков и их коэффициент Бергера совпадает, то мы можем рассмотреть следуюший коэффициент

B⁽³⁾­_i­    = ∑_j≠i p_ij B⁽²⁾_j,

и так далее. Приятный математический способ обобщить эту конструкцию - это ввести обобщенные очки

B­_i­    = ∑ B^(s)_iξ^s,

где ξ - бесконечно малая. Второе хорошее свойство коэффициента Бергера заключается в том, что он вознаграждает игроков за победы над сильными соперниками. Таким образом, важно не только сколько раз ты выиграл, но и у кого.

Е – рейтинг

С другой стороны, у коэффициента Бергера есть очевидный недостаток - по самому своему определению, он вторичен. Возникает естественный вопрос: а нельзя ли ввести какой-нибудь независимый коэффициент, обладающий теми же пооложительными свойствами? Определение коэффициента Бергера нетрудно видоизменить:

λ_i r_i = ∑_j≠i p_ij r_j ,

где r_i - новый рейтинг, который мы пытаемся ввести, а λ­­_i - некий нормировочный множитель. Мы получаем систему из n линейных уравнений с n неизвестными. Одна проблема: система допускает очевидное решение r_i = 0. Поскольку, в общем случае, у системы линейных уравнений есть единственное решение, то кажется, что мы зашли в тупик.  Но здесь находится элегантное решение: выбором  нормировочных множителей λ­­_i  мы можем добиться того, чтобы система стала вырожденной, тогда у нее появятся дополнительные решения. Симметрия между участниками турнира подсказывает подходящий выбор нормировочных множителей:

λ_i = ∑_j≠i p_ji .

При таком определении, система будет иметь одномерное семейство пропорциональных решений. Чтобы зафиксировать одно из них, достаточно наложить какое-нибудь дополнительное условие, например, r₁ = 1. Для решения задачи ранжирования нормировка несущественна, так что мы будем свободно менять ее, если это будет нам удобно. Заметим, что ранжирование зависит от параметра k. Рейтинг, ассоциированный с этим параметром, мы условимся называть kЕ-рейтингом.

Хорош ли Е-рейтинг?

 Сложный вопрос. Есть лишь несколько критериев, которым безусловно должны удовлетворять все разумные системы ранжирования. Я вижу два таких критерия: 1) если А сыграл со всеми участниками турнира не хуже, чем Б, и не проиграл Б микроматч, то А должен стоять не ниже Б; 2) пусть таблицы турниров А и Б отличаются результатом одной единственной партии. Тогда участник, лучше проведший эту партию в турнире Б, в итоговой таблице турнира Б должен стоять не ниже, чем в итоговой таблице турнира А. Другими словами, хорошая игра не должна наказываться. Традиционная система (обобщенные очки B_­i­ ) удовлетворяет обоим условиям. Доказать то же самое про Е-рейтинг не так просто, но я уверен, что и он удовлетворяет обоим условиям.

 Высказывалось следующее возражение против Е-рейтинга: возможны ситуации, когда игрок, лидирующий перед последним туром, выигрывает свою последнюю партию и финиширует вторым. Пример несложно построить. Рассмотрим турнир с 6 участниками: пусть А обыграл В и Д, Б обыграл Г и Е, В обыграл Г, а остальные сыгранные партии закончились вничью. В последнем туре А играет с Г, Б - с В, а Д - с Е. Перед последним туром Е-рейтинг А  равен 373, Б - 354, В - 61, Г - 30, Д  - 89, и Е - 93. В последнем туре А обыгрывает Г, Б - В, а Е - Д. Теперь Е-рейтинг А равен 374, Б - 390, В - 37, Г - 22, Д - 64, а Е - 112. Приведем таблицы:

Аргумент выглядит довольно убедительно, однако стоит заметить, что и традиционная система очков ведет себя точно так же. По очкам А и Б идут вровень, а коэффициент Бергера резко меняется после последнего тура.

Я хочу предложить еще один критерий, которому - на мой взгляд - должна удовлетворять разумная система ранжирования: 3) рассмотрим два турнира - А и Б. Пусть турнир А играется в один круг, а турнир Б - в два круга, причем все партии первого круга оканчиваются вничью, а все партии второго круга - с теми же результатами, что и соответствующие партии турнира А. Тогда ранжирования турниров А и Б должны совпадать.

Е-рейтинг этому условию не удовлетворяет. Для примера рассмотрим первый круг Сан-Луиса. Ранжирование по 1E-рейтингу дает следующую картину: