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

• 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-рейтингу дает следующую картину:

Добавим круг ничьих. Теперь ранжирование выглядит так:

Заметим, что второй вариант гораздо ближе к традиционным очкам: Свидлер занимает свое законное второе место (первый вариант благоволил Ананду как единственному устоявшему против Топалова); Леко становится выше Морозевича и Касымжанова. Мы покажем, что это не случайное совпадение.

Утверждение. Ранжирование турнира А по (k/2)Е-рейтингу совпадает с ранжированием турнира Б по kЕ-рейтингу.

Доказательство. Добавление круга ничьих равносильно добалению единицы ко всем клеткам таблицы, или, другими словами, добавления единицы ко всем весам. Таким образом, если в турнире А считать победы с весом 1 + w = 2 + k, ничьи с весом  1+ d = 2 и поражения с весом 1 + l = 2 - k ,то он будет эквивалентен турниру Б. Деля веса на два для получения нормировки d = 1, приходим к требуемому результату.

Можно ли видоизменить Е-рейтинг так, чтобы он удовлетворял условию 3? Да, достаточно рассмотреть ξЕ-рейтинг, где ξ - бесконечно малая. Тогда (ξ/2)  - тоже бесконечно малая, так что наше Утверждение гарантирует, что ξЕ-рейтинг одинаково ранжирует турниры А и Б.

Что такое ξЕ-рейтинг?

Мы покажем, что для однокруговых турниров, ξЕ-рейтинг эквивалентен обобщенным традиционным очкам B_­i­. Положим s_ij = 1, если игрок  i обыграл игрока j, s­_ij = 0, если они сыграли вничью, и s_ij = - 1, если выиграл j. Пусть 

s_i = ∑_j≠i s­_ij

- "плюс", набранный игроком i. ξЕ-рейтинг является решением системы A r = 0, где

A_ij = 1 +ξ s_ij, и A­_ii  = 1 – n + ξ∑_j≠i s­_ij .

 Мы будем искать решение в виде

r_i = 1 + ∑_k=1^∞ r^(k)_i ξ^k,      ∑_i r^(k)_i = 0.

Расписывая уравнения, получаем

r⁽¹⁾_i = 2 s_i / n

r⁽²⁾_i = 2 (s²_i + ∑_j≠i s_ij s­_j)/n²,

и так далее. Легко видеть, что неравенство r⁽¹⁾_i  > r⁽¹⁾_j  эквивалентно неравенству B⁽¹⁾_i  > B⁽¹⁾_j  , а в случае равенства r⁽¹⁾_i  = r⁽¹⁾_j  неравенство r⁽²⁾_i  > r⁽²⁾_j  эквивалентно неравенству B⁽²⁾_i  > B⁽²⁾_j. Таким образом, ξЕ-рейтинг в точности эквивалентен обобщенным традиционным очкам, или - упрощенно - обычным очкам с коэффициентом Бергера в качестве дополнительного коэффициента.

Выводы

Мы показали, что Е-рейтинг не удовлетворяет условию 3, сформулированному выше. Мне это представляется весьма серьезным недочетом. Если вместо Е-рейтинга рассматривать ξЕ-рейтинг, этот недостаток устраняется, однако, для круговиков, ξЕ-рейтинг эквивалентен традиционной системе подсчета очков.

Со временем накопилось несколько вариантов модели е-рейтинга.

Очки абсолютные и относительные
Как сломать стальной шарик
Е-рейтинг для домохозяек
Е-Рейтинг - решение проблемы, или ...
Е-Рейтинг для иноземцев
Е-Рейтинг - чисто спортивная модель
В книге "Мир рейтингов"
Частные случаи
Кого обижает регламент

WWRR
Вверх
СЛОМАТЬ ШАРИК
Домохозяйкам
Е-РЕЙТИНГ:F1
E-Rating (en)
Е-Рейтинг
Е-Rating
Е-Рейтинг. Варианты.
Е-ПРИМЕР
E-Tabling
Theory
Критика
Диалог

WWRR Вверх МИР РЕЙТИНГОВ ФУТБОЛ ХОККЕЙ ТЕННИС ШАХМАТЫ ФОРМУЛА 1 ОЛИМПИАДЫ CF БЕНДИ ВОЛЕЙБОЛ ЭКОНОМИКА БИБЛИОТЕКА T1-12 МИФИ Яхты ... Гандбол Радио СПОРТ Е Клуб Об авторе
 Copyright Eugene Potemkin 1985 - 2005 271314@mail.ru. Last updated: 08/26/06.
 Самые неприступные крепости в головах наших ...