Даниел Карабекян (гу – вшэ) «Свойства расширенных предпочтений. Задача манипулирования в голосовании»

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

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

Можно выделить две группы методов расширения предпочтений: ординальные и неординальные (не путать с кардинальными). Отличие первых заключается в подходе к предпочтениям наборов с точки зрения теории ожидаемого выигрыша.

Всего рассматривается четыре неординальных способа. Два неординальных метода (лексимин и лексимакс) можно встретить в [5, 7], в то время как два других способа из этой категории (по убыванию вероятности наилучшей и по возрастанию вероятности наихудшей) не рассматривались ранее. Основным преимуществом неординальных методов является полное устранение несравнимости. Доказано, что если обычные предпочтения являются линейным порядком, то расширенные предпочтения, построенные любым из неординальных способов, тоже будут линейным порядком.

Представим два разработанных неординальных (неранговых) метода, до этого не встречавшиеся в научной литературе. Данные способы упорядочивания альтернатив отличаются от методов "лекси" тем, что участник голосования ориентируется не на наличие альтернативы в итоговом выборе, а на вероятность того, что именно это альтернатива выиграет в итоге. Здесь различаются два способа: упорядочивание по убыванию вероятности наилучшей альтернативы, и возрастанию вероятности наихудшей. Рассмотрим эти способы.

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

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

Предложим математическое описание данного метода. Для данных предпочтений строятся расширенные предпочтения по принципу убывания вероятности наилучшей следующим способом. Сравниваются два коллективных выбора .

Упорядочим элементы общественного выбора в порядке убывания предпочтения, то есть: и , где и . Далее производим следующее сопоставление:

1. 
   Если , то .
   
2. 
   Если и , то .
   
3. 
   Если и , где , то соотношение имеет место если и только если для наименьшего , такого, что
   

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

Для данных предпочтений строятся расширенные предпочтения по принципу убывания вероятности наилучшей следующим способом. Сравниваются два коллективных выбора .

Упорядочим элементы общественного выбора в порядке убывания предпочтения, то есть: и , где и . Далее производим следующее сопоставление:

1. 
   Если , то .
   
2. 
   Если и , то .
   
3. 
   Если и , где , то соотношение имеет место если и только если для наибольшего , такого, что
   

В данном случае можно также утверждать, что расширенные предпочтения построенные по вероятностным методам также будут линейным порядком, как и обычные.

1. 
   Лексимин – лексимакс дополнения,
   
2. 
   Вероятностные дополнения,
   
3. 
   Рискофил – рискофоб дополнения,
   
4. 
   Дополнения, основанные на упорядочивании по мощности.
   

Таким образом, можно сформулировать несколько утверждений.

Если обычные предпочтения являются линейным порядком, то и расширенные предочетения, построенные по принципу лексимин, лексимакс или любым из вероятностных методов будут линейным порядком.

Это условие для отношений , удовлетворяющих антисимметричности, связности и транзитивности, и методов "лекси" было показано в статье Каймака и Санвера. Доказательство леммы в общем виде следует из определения всех способов.

Если обычные предпочтения являются линейным порядком, то расширенные предпочтения, построенные по ранговому методу с дополнениями будут являться линейным порядком, если

1. 
   Последнее дополнение является лексимин, лексимакс или вероятностным дополнением.
   
2. 
   Последнее дополнение является упорядочиванием по мощности и количество альтернатив .
   
3. 
   Последнее дополнение является рискофил, рискофоб дополнением и .
   

Стоит упомянуть, что часть алгоритмов расширения предпочтений при малом числе альтернатив дают одинаковые результаты. В частности, для 3, 4 и 5 альтернатив можно построить 4, 10 и 12 способов расширения предпочтений соответственно. Однако количество способов при большем числе альтернатив неизвестно. Основываясь на результатах леммы 2 можно лишь утверждать, что при достаточно больших для одних и тех же обычных предпочтений может быть построено не более 56 различных расширенных предпочтений. Более подробной информации, а возможных совпадениях способов можно получить только путем последовательного применения всех алгоритмов для разных .

1. 
   Aleskerov F, Kurbanov E (1999) «Degree of manipulability of social choice procedures», in: Alkan et al. (eds.) Current Trends in Economics. Springer, Berlin Heidelberg New York
   
2. 
   Favardin P, Lepelley D (2006) «Some further results on the manipulability of social choice rules», Social Choice and Welfare Volume 26: 485-509
   
3. 
   Gibbard A (1973) «Manipulation of voting schemes», Econometrica Volume 41: 587-601
   
4. 
   Kelly J (1993) «Almost all social choice rules are highly manipulable, but few aren’t», Social Choice and Welfare Volume 10: 161–175
   
5. 
   Pattanaik P (1978) «Strategy and group choice». North-Holland, Amsterdam
   
6. 
   Pritchard G, Wilson M (2005) «Exact results on manipulability of positional voting rules», CDMTCS Research Report Series
   
7. 
   Sanver R., Ozyurt S. (submitted) «A general impossibility result on strategy-proof social choice hyperfunctions», Submitted to Games and Economic Behavior
   
8. 
   Satterthwaite M (1973) «The existence of a strategy proof voting procedure: a topic in social choice theory», Ph. D. dissertation, University of Wisconsin
   
9. 
   Satterthwaite M (1975) «Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions», Journal of Economic Theory Volume 10: 187-217