Об устойчивых решениях в ординальной задаче выбора

Доклады Академии Наук. Информатика. 2009. Т. 426. № 3. С. 318–320.

Алескеров Ф. Т., Субочев А. Н.

Ординальная задача группового выбора определяется конечным множеством альтернатив и тем, что мнения участников относительно альтернатив выражается в виде бинарных отношений предпочтений; решение задачи ищется в виде выбора наилучшей альтернативы. В теории в качестве такой альтернативы обычно принимается победитель Кондорсе – альтернатива, более предпочтительная по сравнению с другими альтернативами для большинства участников при парном сравнении. Однако победитель Кондорсе в общем случае отсутствует, поэтому предлагается расширить множество выбираемых альтернатив до некоторых всегда непустых подмножеств общего множества альтернатив, строящихся с помощью отношения мажоритарного доминирования, определяемого бинарными отношениями предпочтения участников (альтернатива a доминирует над альтернативой b, если для большинства участников a более предпочтительна чем b).

В настоящей работе в рамках такого класса отношений мажоритарного доминирования, как турниры (связные и асимметричные отношения), рассматриваются три концепции решений: доминирующее множество, слабоустойчивое множество, непокрытое множество. Сформулирован критерий, определяющий принадлежность альтернативы объединению минимальных слабоустойчивых множеств, и как следствие доказывается, что непокрытое множество является подмножеством объединения минимальных слабоустойчивых множеств. Далее идея устойчивости используется для обобщения концепции непокрытого множеств. Вводится понятие k-устойчивых альтернатив и классов k-устойчивых альтернатив. Определяются их свойства и соотношение с указанными выше концепциями решений.

Ординальная задача группового выбора определяется конечным множеством альтернатив и тем, что мнения участников относительно альтернатив выражается в виде бинарных отношений предпочтений; решение задачи ищется в виде выбора наилучшей альтернативы. В теории в качестве такой альтернативы обычно принимается победитель Кондорсе – альтернатива, более предпочтительная по сравнению с другими альтернативами для большинства участников при парном сравнении. Однако победитель Кондорсе в общем случае отсутствует, поэтому предлагается расширить множество выбираемых альтернатив до некоторых всегда непустых подмножеств общего множества альтернатив, строящихся с помощью отношения мажоритарного доминирования, определяемого бинарными отношениями предпочтения участников (альтернатива a доминирует над альтернативой b, если для большинства участников a более предпочтительна чем b).

В настоящей работе в рамках такого класса отношений мажоритарного доминирования, как турниры (связные и асимметричные отношения), рассматриваются три концепции решений: доминирующее множество, слабоустойчивое множество, непокрытое множество. Сформулирован критерий, определяющий принадлежность альтернативы объединению минимальных слабоустойчивых множеств, и как следствие доказывается, что непокрытое множество является подмножеством объединения минимальных слабоустойчивых множеств. Далее идея устойчивости используется для обобщения концепции непокрытого множеств. Вводится понятие k-устойчивых альтернатив и классов k-устойчивых альтернатив. Определяются их свойства и соотношение с указанными выше концепциями решений.

Ключевые слова: коллективный выбор, social choice, majority relation, top cycle, uncovered set, externally stable set, k-stable alternative, k-stable set, мажоритарное отношение, максимальный цикл, непокрытое множество, внешнеустойчивое множество, k-устойчивая альтернатива, k-устойчивое множество, правило большинства, majority rule, tournament solution, турнирное решение