Критика

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