СИ-2011

[Евгений Машеров]

В чисто математическом плане задача сведения набора парных сравнений к единому рейтингу почти тривиальна (в вычислительном - уже не столь тривиальна, но основные трудности тут вне математики).
Если A(i,j) это сравнение силы i-того и j-того игроков (скажем, как соотношение числа их и поражений, или же набранных очков и т.п.), а X(j) это "правильный" рейтинг j-того игрока, то естественно ожидать, что, если просуммировать рейтинги всех игроков, с которыми сыграл данный, умноженные на этот, отражающий во сколько раз i-тый игрок сильнее j-того, то получим правильный рейтинг i-того, возможно, умноженный на какую-то константу (содержательно это означает, что за победу над сильным игроком надо давать больше, чем над слабым, и даже умеренный проигрыш "гроссу" может больше указывать на силу игрока, чем его триумф над новичком).
Формально это можно записать, как
Ax=lx, где А - матрица сравнений игроков, х - вектор их рейтингов, l - постоянная величина, то есть это задача на собственные значения матрицы А (можно показать, что искомая наша величина соответствует максимальному собственному значению l).
По теореме Фробениуса-Перрона, если матрица А имеет неотрицательные значения (в данном случае её элементы - "относительные силы" игроков и A(i,j)=1/A(j,i), а для игроков, которые меж собой не встречались - пишем 0; на диагонали, то есть сравнивая с самими собою, пишем 1, впрочем, это несущественно) и неразложима (то есть, даже если два игрока i,j не встречались, можно выстроить цепочку из игроков от i-того до j-того так, чтобы соседи по цепочке меж собой играли; понятно, что если игроки распадаются на два подмножества так, что игроки из одного никогда не играли со вторым, то единого рейтинга быть не может) - существует вектор х с положительными элементами, который и будет искомым рейтингом.
Хотя матрица велика, а сложность задачи кубична, так что для такой размерности используют суперкомпьютеры, нам нужен только один вектор, и для него есть простой и достаточно быстрый метод (степенной).
Проблема в том, чтобы набрать все эти сравнения (а для начала - как оценить сравнение? Как вариант - отношением сумм набраных очков, но что делать, если кто-то в нуле или в минусе?)
Но если кто-то соберёт такой материал - то, зная матрицу А, сам рейтинг можно будет получить легко.

[Svetlana_S]

Сообщение от Евгений Машеров

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

Может быть не только на два

[Raykoffff]

Сообщение от Евгений Машеров

Проблема в том, чтобы набрать все эти сравнения (а для начала - как оценить сравнение? Как вариант - отношением сумм набраных очков, но что делать, если кто-то в нуле или в минусе?)

Как вариант - взять за точку отсчёта не 0, а, скажем, -10000.

[Svetlana_S]

Сообщение от Евгений Машеров

... если матрица А имеет неотрицательные значения (в данном случае её элементы - "относительные силы" игроков и A(i,j)=1/A(j,j),

A(i,j)=1/A(j,i)