Критика

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

Сухую статистику надо НЕ мочить, ее надо РАЗМАЧИВАТЬ, можно с пивом ...

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

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


Гостевая

 

Rambler's Top100 Service

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(1)­i­ , может быть записано формулой:

B(1)­i­    = ∑ji pij B(0)j

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

B(2)­i­    = ∑ji pij B(1)j.

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

B(3)­i­    = ∑ji pij B(2)j,

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

B­i­    = ∑ B(s)iξs,

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

Е – рейтинг

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

λi ri = ∑ji pij rj ,

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

λi = ∑ji pji .

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

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

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

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

 

А

Б

В

Г

Д

Е

Е-рейтинг

очки

Бергер

А

*

1

2

 

2

1

373

6

23

Б

1

*

 

2

1

2

354

6

19

В

0

 

*

2

1

1

61

4

10

Г

 

0

0

*

1

1

30

2

6

Д

0

1

1

1

*

 

89

3

12

Е

1

0

1

1

 

*

93

3

12

 

 

А

Б

В

Г

Д

Е

Е-рейтинг

очки

Бергер

А

*

1

2

2

2

1

374

8

31

Б

1

*

2

2

1

2

390

8

33

В

0

0

*

2

1

1

37

4

12

Г

0

0

0

*

1

1

22

2

8

Д

0

1

1

1

*

0

64

3

14

Е

1

0

1

1

2

*

112

5

20

 

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

 

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

 

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

 

 Петер ЛЕКО

2763

 

 

 1 

 0 

 2 

 1 

 2 

 1 

 0 

330

6

2

 Александр МОРОЗЕВИЧ 

2707

 1 

 

 

 0 

 1 

 2 

 1 

 1 

 0 

365

5

3

 Петр СВИДЛЕР

2738

 2

 2 

 

 

 2

 1

 1 

 1 

 0 

635

3

4

 Юдит ПОЛГАР

2735

 0 

 1 

 0 

 

 

 0 

 1 

 2 

 0 

136

8

5

 Вишванатан АНАНД

2788

 1 

 0 

 1 

 2 

 

 

 2 

 0 

 1 

938

2

6

 Майкл АДАМС

2719

 0 

 1 

 1 

 1 

 0 

 

 

 1 

 0 

156

7

7

 Рустам КАСЫМЖАНОВ

2670

 1 

 1 

 1 

 0 

 2 

 1 

 

 

 0 

420

4

8

 Веселин ТОПАЛОВ

2788

 2 

 2 

 2 

 2 

 1 

 2 

 2 

 

 

5020

1

 

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

 

 Петер ЛЕКО

2763

 

 

 2 

 1 

 3 

 2 

 3 

 2 

 1 

875

4

2

 Александр МОРОЗЕВИЧ 

2707

 2 

 

 

 1 

 2 

 3 

 2 

 2 

 1 

807

6

3

 Петр СВИДЛЕР

2738

 3

 3 

 

 

 3

 2

 2 

 2 

 1 

1158

2

4

 Юдит ПОЛГАР

2735

1

 2 

 1 

 

 

 1 

 2

 3 

 1 

618

8

5

 Вишванатан АНАНД

2788

 2 

 1 

 2 

 3 

 

 

 3 

 1 

 2 

975

3

6

 Майкл АДАМС

2719

 1 

 2 

 2 

 2 

 1 

 

 

 2 

 1 

635

7

7

 Рустам КАСЫМЖАНОВ

2670

 2 

 2 

 2 

 1 

 3 

 2 

 

 

 1 

839

5

8

 Веселин ТОПАЛОВ

2788

 3 

 3 

 3 

 3 

 2 

 3 

 3 

 

 

2093

1

 

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

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

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

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

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

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

si = ∑j≠i ij

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

Aij = 1 +ξ sij, иii  = 1 – n + ξ∑j≠i ij .

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

ri = 1 + ∑k=1 r(k)i ξk,      ∑i r(k)i = 0.

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

r(1)i = 2 si / n

r(2)i = 2 (s2i + ∑j≠i sij j)/n2,

и так далее. Легко видеть, что неравенство r(1)i  > r(1)j  эквивалентно неравенству B(1)i  > B(1)j  , а в случае равенства r(1)i  = r(1)j  неравенство r(2)i  > r(2)j  эквивалентно неравенству B(2)i  > B(2)j. Таким образом, ξЕ-рейтинг в точности эквивалентен обобщенным традиционным очкам, или - упрощенно - обычным очкам с коэффициентом Бергера в качестве дополнительного коэффициента.

Выводы

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

horizontal rule

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

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

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.
 
Самые неприступные крепости в головах наших ...