Прошел семинар НУГ "Построение рейтингов методами коллективного выбора"

На семинаре был заслушан доклад Субочева А.Н. «Агрегированное ранжирование альтернатив, основанное на методе марковских блужданий по мажоритарному графу». Мажоритарный граф представляет собой бинарное отношение, основанное на попарном сравнении альтернатив методом простого большинства. В таком графе могут встречаться циклы (самый простой пример – парадокс Кондорсе). В случае отсутствия циклов решения на этом графе хорошо изучены это победитель Кондерсе и различные расширения в случае его отсутствия. При наличии циклов предложено следующее решение. Рассмотрим процесс перехода от одной альтернативы на мажоритарном графе к другой соответствующего случайному блужданию (в более общем случае марковскому процессу). При этом к некоторым альтернативам будем возвращаться чаще, к некоторым реже, а к некоторым, покинув их однажды, никогда не произойдет возврата. Те альтернативы, к которым возвращаются при таком блуждании с большей вероятностью, в некотором смысле имеют преимущество перед альтернативами, к которым процесс возвращается реже. Таким образом, строится рейтинг всех альтернатив.