От ABC до CBA

[sevabashirov]

Среди массы всевозможных конкурсов прогнозов, проводимых не только в ЖЖ, есть группа конкурсов, где требуется угадать расстановку мест. Результаты выборов, турнирная таблица в чемпионате - что угодно. Напрашивается назвать такие прогнозы ординалистскими, в противовес кардиналистским, где конкурс сводится к точности попадания в какие-либо конкретные числа. Для прогнозирования чисел нужно больше трудозатрат, но с другой стороны очевиднее подсчет итогов.

Фактически мы имеем набор перестановок из N элементов - возможны N! (факториал от N) различных вариантов. И итоговую перестановку (результат соревнования). Понятно, что если у двух и более участников идентичные прогнозы, это никак не разрешить численно, и обычно в правилах оговаривается, что в таком случае происходит (засчитывается ничья / приоритет у более раннего прогноза / дублирование запрещается на этапе приема прогнозов). Так что положим, что одинаковых прогнозов нет. Каким же образом расставить места у всех остальных?

Разберем на атомы отдельно взятую перестановку N элементов. Насколько она точна? Очевидно, что точность складывается из угадывания правильного порядка в каждой из пар элементов. Всего таких пар N (N-1) / 2 (как рукопожатий в известной задаче). Но все ли они равноценны? Явно нет, одно дело перепутать 4-е место с 5-м, и совсем другое - 1-е с 10-м. Если дать каждой паре вес, для любой перестановки можно вычислить сумму весов верно указанных результатов попарных сравнений. Или - что то же самое, но наоборот - ошибочных (тогда сортировка итогов будет по возрастанию, а не по убыванию).

Какими же могут (или даже должны) быть веса?


1) Если у "итогов соревнования" все-таки имеется количественная подоплека, логично за вес пары принять разницу абсолютных результатов. Кардинализм рулит. Проценты голосов, набранные баллы... Таким образом наглядно подчеркивается, что чем сильнее разрыв между двумя результатами, пусть даже соседними, тем важнее его угадать - тем ошибка губительнее. Вполне справедливо.

Этот подход, пожалуй, опробую в сентябре на конкурсе по выборам в Госдуму - а именно на том из них, где нужно будет угадать расстановку результатов всех партий. Проведу, скорее всего, в world_elections, кому интересно. Также планирую и конкурс с угадыванием 1-2 мест по всем регионам, с картами - формат, как показала практика, заходит на ура.

2) А если чисел нет, есть только расстановка мест? Или же по каким-то причинам не хочется учитывать разницу в ширине отрывов? Тогда можно:

а) Уравнять веса вообще всех пар - самое простое и самое тупое, т.к. веса пары соседей и пары лидер-аутсайдер явно не равноценны, о чем уже написал;

б) Считать весом пары разницу между занятыми местами. У пар соседей - по 1, у двух крайних - N-1. Дешево и сердито, но эта дешевизна оборачивается тем, что сумма всех весов меньше, чем количество перестановок - по принципу Дирихле будет куча равных сумм весов у разных прогнозов. Например, у таких, где единственная ошибка в какой-либо паре соседей.

Как упорядочить их? Что важнее - правильно расставить 1-2 места и ошибиться в 3-4, или наоборот? Интуитивно чем выше места, тем важнее правильно расставить, но на одной интуиции далеко не уедешь, надо как-то формализовать...

в) И такой метод есть! См. пост " О кусках".



Что я тут имею в виду? Не владея информацией о конкретных числах, но зная упорядоченный набор, существует формула, описывающая среднюю долю 1-го, 2-го ... N-го по величине элементов этого набора в общей сумме. В случае, когда эта сумма явно определена и нет никаких процедурных ограничений по распределению, любой элемент может быть размером от 0 до 100%. Голосование - идеальный пример.

Доказано, что в среднем разности размеров соседних по рангу "кусков" пропорциональны 1, 1/2, 1/3 ... 1/(N-1), где за единицу принята разность между двумя крупнейшими. Не размеры самих кусков (это закон Ципфа, он пригоден для неограниченного роста), а именно разности соседних. Остальные разности - не соседних - легко вычислить простым суммированием; для удобства все коэффициенты можно на что-нибудь домножить, избавившись от дробей.
___

Переходим к практике. Случай с двумя элементами тривиален; с тремя - все 6 возможных расстановок легко расставляются по приоритету даже "без бумажки". Допустим, верный порядок - ABC, тогда порядок от наилучшего прогноза к наихудшему такой:

1) ABC - всё верно
2) ACB - перепутано BC
3) BAC - перепутано AB (что критичнее, чем BC)
4) CAB - угадано только AB
5) BCA - угадано только BC (что менее значимо, чем AB)
6) CBA - всё наоборот, несмотря на то, что B попало на свое место.

Общий ранг центрально-симметричен (совпадает с собой при повороте на 180°), и это общая закономерность.

С четырьмя элементами (верный порядок - ABCD) так просто не отделаться. Посчитаем веса шести пар (AB, AC, AD, BC, BD, CD) по двум указанным методикам:

1) AB = BC = CD = 1, AC = BD = 2, AD = 3 (сумма - 10). Домножим всё для удобства на 18 (получится соответственно 3 по 18, 2 по 36 и 54, сумма - 180);
2) Если AB = 1, то BC = 1/2, а CD = 1/3, но умножим всё на 30. Тогда AB = 30, BC = 15, CD = 10, AC = 45, BD = 25, AD = 55 (сумма - тоже 180).

А вот теперь можно считать и сортировать. Ниже таблица, отсортированная по среднему из двух весов (знак + означает попадание в результат, * - промах):

Вес №1
18
36
54
18
36
18
Итог
по
весу
№1
Итог
по
весу
№2

Вес №2
30
45
55
15
25
10

Пара
AB
AC
AD
BC
BD
CD

A
B
C
D
+
+
+
+
+
+
180
180

A
B
D
C
+
+
+
+
+
*
162
170

A
C
B
D
+
+
+
*
+
+
162
165

B
A
C
D
*
+
+
+
+
+
162
150

B
A
D
C
*
+
+
+
+
*
144
140

A
D
B
C
+
+
+
+
*
*
126
145

A
C
D
B
+
+
+
*
*
+
126
140

C
A
B
D
+
*
+
*
+
+
126
120

A
D
C
B
+
+
+
*
*
*
108
130

B
C
A
D
*
*
+
+
+
+
126
105

C
B
A
D
*
*
+
*
+
+
108
90

C
A
D
B
+
*
+
*
*
+
90
95

B
D
A
C
*
+
*
+
+
*
90
85

D
A
B
C
+
+
*
+
*
*
72
90

D
A
C
B
+
+
*
*
*
*
54
75

B
C
D
A
*
*
*
+
+
+
72
50

D
B
A
C
*
+
*
+
*
*
54
60

B
D
C
A
*
*
*
+
+
*
54
40

C
B
D
A
*
*
*
*
+
+
54
35

C
D
A
B
+
*
*
*
*
+
36
40

D
C
A
B
+
*
*
*
*
*
18
30

D
B
C
A
*
*
*
+
*
*
18
15

C
D
B
A
*
*
*
*
*
+
18
10

D
C
B
A
*
*
*
*
*
*
0
0

Вышло, что в верхнюю половину (топ-12) попали те и только те перестановки, где верно угадано AD (победитель поставлен выше аутсайдера). Для большего числа элементов это не обязательно будет выполняться.
___

г) Другой подход проще и бескомпромисснее - вес каждой пары соседей многократно меньше веса предыдущей пары. То есть AB весомее BC, например, в 10 раз, BC весомее CD тоже в 10 раз. Разница должна быть больше, чем количество пар, диапазон которых захватывает центр (в данном случае хватит и 5, потому что через центр проходят 4 пары - кроме AB и CD).

Смысловое наполнение - важнее всего правильно выявить лидера. Применив те же вычисления, получаем другой (но тоже симметричный) порядок (указаны суммарные веса перестановок):

ABCD - 343
ABDC - 342
ACBD - 333
ADBC - 331
ACDB - 322
ADCB - 321
BACD - 243
BADC - 242
CABD - 223
DABC - 220
CADB - 212
DACB - 210
BCAD - 133
BDAC - 131
CBAD - 123
DBAC - 120
CDAB - 101
DCAB - 100
BCDA - 22
BDCA - 21
CBDA - 12
DBCA - 10
CDBA - 1
DCBA - 0

Какой подход в каком случае более адекватен - решать вам.

А про ординализм и кардинализм еще будет разговор, и некоторые читатели наверняка догадались, в какую тему я клоню.