Вторник 8-го февраля, 17-00

Вторник, 8 февраля, ауд. 106. Начало в 17:00.

Докладчик: С.А. Образцова.

Тема: Сложность манипулирования результатами голосования.

Abstract

В своей статье "The computational difficulty of manipulating an election" Bartholdi, Tovey and Trick доказали, что множество известных правил для определения победителя при голосовании (Plurality, Borda, Copeland and Maximin) позволяют легко манипулировать результатами голосования. Но в этой статье было сделано важное предположение, что цель манипулятора сделать так, чтобы предпочитаемый им кандидат был среди кандидатов с наибольшим числом очков, или, что тоже самое, что ничьи разбиваются в пользу манипулятора. В докладе будут рассмотрены более общие правила разбивания ничьих и для простых правил разбивания ничьих будет доказана NP-сложность манипулирования результатами голосования для ряда правил (семейство Scoring rules, Copeland, Maximin, Bucklin). Для вероятностного способа разбиения ничьей будут построены алгоритмы для нескольких правил (Scoring rules, специальный случай Maximin, Bucklin) и доказана NP-сложность для общего случая Maximin и Copeland. Доклад основан на результатах совместной работы с Эдит Элкинд.