Манипулирование при неполной информации

Манипулирование при неполной информации

Ю. А. Веселова

Национальный исследовательский университет «Высшая школа экономики» (НИУ ВШЭ); Институт проблем управления РАН, Москва.

e-mail: *****@***ru

В теории коллективного выбора известна проблема подверженности правил принятия коллективных решений манипулированию со стороны избирателей [1], [2]. Участники голосования могут намеренно сообщить свои неискренние предпочтения с целью добиться более выгодного для них результата голосования. Степень манипулируемости как вероятность возникновения такой ситуации, при которой хотя бы одному избирателю будет выгодно исказить свои предпочтения, рассматривается в [3], [4], [5]. Базовая предпосылка большинства исследований – наличие полной информации у каждого из участников голосования о предпочтениях всех остальных избирателей (избирателям известен весь профиль предпочтений ). Такое допущение хотя и является довольно сильным, оно позволяет решить достаточно просто задачу сравнения правил по степени манипулируемости.

В данной работе рассматривается аналогичная задача, но в предположении о наличии неполной информации у избирателей. Неполнота информации может быть нескольких типов. В модели используется функция публичной информации (poll information function), введенная в [6], которая может быть интерпретирована как результат предварительного опроса избирателей, оглашаемый перед выборами, т. е. вместо профиля предпочтений избирателей известно, например, лишь количество очков, которые набрал каждый и кандидатов при заданном профиле предпочтений и заданном правиле выбора. Другой пример функции публичной информации – функция, которая ставит в соответствие каждому профилю победителя голосования. Это также может быть информация только о любимых кандидатах всех избирателей или информация о предпочтениях некоторого подмножества избирателей (т. е. часть профиля предпочтений).

Таким образом, обладая некоторой информацией о профиле предпочтений и зная свои собственные предпочтения, каждый избиратель имеет множество согласующихся с этой информацией профилей предпочтений – информационное множество . Если для любого профиля предпочтений и для любого избирателя информационное множество при функции публичной информации , , нестрого включает в себя информационное множество при функции публичной информации , , то является не менее информативной, чем .

Как сравнить манипулируемость правил при наличии неполной информации у избирателей? Для решения этой проблемы рассматривается две модели манипулирования. В первой модели используется концепция доминирующей стратегии: если существует такое неискреннее предпочтение избирателя , , , при котором во всех профилях его информационного множества результат правила является не менее предпочтительным для избирателя , чем результат правила при его искренних предпочтениях , и для некоторых профилей из - более предпочтительным, то говорим, что избиратель имеет стимул манипулировать при публичной информации типа . Профиль предпочтений допускает манипулирование, если существует хотя бы один избиратель, имеющий стимул манипулировать при данном профиле предпочтений.

Рассчитывается индекс (доля профилей предпочтений, допускающих манипулирование) для пяти позиционных правил коллективного выбора: правила относительного большинства, правила Борда, двухступенчатой мажоритарной системы, правила передачи голосов и правила вето. Рассматриваемые функции публичной информации, упорядоченные в порядке убывания информативности: 1) Профиль предпочтений (Profile); 2) Количество очков, набранных кандидатами по правилу (Score); 3) Ранжирование кандидатов по правилу (Rank); 4) Победители по правилу (Winner); 5) Единственный победитель, выбираемый по алфавитному порядку в случае множественного выбора (1Winner).

Правила коллективного выбора

1. Правило относительного большинства. Выбор по данному правилу определяется как множество альтернатив, являющихся наилучшими для наибольшего числа избирателей, т. е.

,

где , а - скалярное произведение.

2. Правило Борда [18]. По данному правилу для каждой альтернативы вычисляется ранг Борда как сумма рангов по всем избирателям. Или, с помощью вектора очков ,

.

3. Правило Коупленда [20]. Выбирается альтернатива, для которой количество побед минус количество поражений по мажоритарному отношению наибольшее, т. е.

,

.

4. Правило передачи голосов (Процедура Хара) Выбирается альтернатива, имеющая более 50% первых мест в предпочтениях избирателей. Если таковой нет, то из профиля исключается альтернатива, имеющая наименьшее число первых мест. Процедура повторяется до тех пор, пока не будет выбрана какая-либо альтернатива.[1]

Рис. 1. Индекс для правила относительного большинства.

Рис. 2. Индекс для правила Борда.

Результаты вычисления индекса для перечисленных правил коллективного выбора представлены на рис. 1-4. На графиках видно, что доля профилей, допускающих манипулирование при менее информативной функции информации, больше. Более того, уже начиная с 10 избирателей, практически всегда найдется избиратель, которому будет выгодно исказить свои предпочтения, если известен единственный победитель. Это противоречит интуитивному предположению о том, что манипулирование тем менее вероятно, чем меньше информации у избирателей, и чем больше число участников голосования. С другой стороны, этот эффект просто объясняется тем, что среди большого количества избирателей более вероятно найти такого, у которого есть стимул манипулировать, даже если вероятность улучшить результат голосования для него очень мал.

Рис. 3. Индекс для правила передачи голосов.

Рис. 4. Индекс для правила Коупленда.

Следовательно, индекс в данном случае не показывает нам полную картину манипулирования. Вводится в рассмотрение следующий индекс. Каждому профилю предпочтений ставится не просто 1, в случае, если он допускает манипулирование, а число от 0 до 1. Для каждого избирателя в профиле находится доля профилей из , при которых манипулированием достигается более выгодный исход. Таким образом, стимул к манипулированию получает численную оценку. Далее вычисляется максимальный по всем избирателям стимул к манипулированию, который и ставится в соответствие профилю предпочтений. Рассматривая такой индекс, получаем интуитивно понятный результат – манипулируемость правил коллективного выбора стремится к нулю с увеличением количества избирателей и уменьшением количества доступной информации о предпочтениях коллектива.

Литература

1.  Gibbard A. Manipulation of voting schemes: a general result //Econometrica: journal of the Econometric Society. – 1973. – С. 587-601.

2.  Satterthwaite M. A. Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions //Journal of economic theory. – 1975. – Т. 10. – №. 2. – С. 187-217.

3.  и др. Оценка степени манипулируемости известных схем агрегирования в условиях множественного выбора //Журнал новой экономической ассоциации. – 2009. – №. 1-2. – С. 37-61.

4.  Aleskerov F. et al. On the degree of manipulability of multi-valued social choice rules //Essays in Honor of Hannu Nurmi, Homo Oeconomicus. – 2011. – №28 (1/2). – С. 205-216.

5.  Pritchard G., Wilson M. Exact results on manipulability of positional voting rules //Social Choice and Welfare. – 2007. – Vol. 29. – №3. – P. 487-513.

6.  Reijngoud A., Endriss U. Voter Response to Iterated Poll Information //In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2012), June 2012.

[1] Существуют и другие вариации этого правила, отличающиеся порядком передачи голосов от исключаемых альтернатив к оставшимся или квотой, необходимой для перехода на следующий этап. Обзор различных вариантов правила передачи голосов представлен в [22].