Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Конкурс'
1 . Рассмотрение решения об отклонении предложения конкурсных торгов Общество с ограниченной ответственностью «Гранд Медикал» по закупке код 21.20.2 -...полностью>>
'Документ'
Коллизии в российском уголовно-процессуальном законодательстве и пути их устранения....полностью>>
'Документ'
№ 8 4 07 октября Черчение (9-10 классы) понедельник 13ч 00мин Каб. №35 8-10 07 октября Начальная школа: окружающий мир (4 классы) понедельник 13ч 00ми...полностью>>
'Документ'
Для возобновления потока российских туристов Египет готов практически на любые меры безопасности, кроме тех, что затрагивают суверенитет страны. В час...полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Д.С. Карабекян

Государственный университет –
Высшая школа экономики

СВОЙСТВА
РАСШИРЕННЫХ ПРЕДПО
ЧТЕНИЙ
В ЗАДАЧЕ
МАНИПУЛИРОВАНИЯ ПРИ ГОЛОСОВАНИИ

Проблема манипулирования при голосовании заключается в том, что избиратель, намеренно исказив свои истинные предпочтения, может добиться лучшего для себя коллективного решения. Теоретические исследования проб­лемы манипулирования были начаты в работах [Gibbard, 1973; Satterthwaite, 1975]. В них было доказано, что любая разумная процедура не защищена от манипулирования со стороны участников голосования. В статьях [Aleskerov, Kurbanov, 1999; Kelly, 1993] был впервые поставлен вопрос о степени манипулируемости схем голосования. Однако оценка уровня манипулируемости на практике – это сложная вычислительная задача, для облегчения решения которой в исследованиях принимается ряд упрощающих предпосылок. Самой главной и жесткой из них является рассмотрение проблемы манипулирования в условиях однозначного выбора путем введения условия устранения несравнимости. Данное условие заключается в том, что из множества выигрывающих альтернатив согласно заранее определенному правилу будет выбран един­ст­венный победитель. Например, в работе [Aleskerov, Kurbanov, 1999] рассматривается устранение несравнимости в соответствии с алфавитным порядком. Такой способ встречается наиболее часто, и он порождает множество проб­лем, например неравноправность участников голосования (избиратели, которые больше всего предпочитают первые альтернативы по алфавиту, заранее на­ходятся в выигрышном положении), что может значительно исказить результаты количественной оценки уровня манипулируемости. Более мягким ус­ловием устранения несравнимости можно считать метод, предложенный в работе [Pritchard, Wilson, 2005]. Он заключается в том, что в итоговом множественном выборе появление всех альтернатив равновероятно, и выигрывающая альтернатива выбирается случайным образом.

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

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

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

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

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

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

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

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

  1. если , то

  2. если и , то

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

Данное определение представлено в виде алгоритма. Из самой формулировки видно, что сравнению поддаются все наборы.

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

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

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

  1. если , то

  2. если и , то

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

Расширенные предпочтения, построенные по этому методу для трех альтернатив и лексикографических предпочтений, имеют вид:

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

Известный ранее способ приписывания полезностей альтернативам, основанный на теории ожидаемого выигрыша, адаптирован для использования в поставленной задаче. Рассмотрен частный случай данного метода – ординальный способ, который в то же время не решает поставленных задач – построенные расширенные предпочтения не обладали свойством связности. Для устранения оставшейся несравнимости Ф.Т. Алескеровым и автором были пред­ложены несколько типов дополнений:

  1. лексимин – лексимакс дополнения;

  2. вероятностные дополнения;

  3. рискофил – рискофоб дополнения;

  4. дополнения, основанные на упорядочивании по мощности.

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

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

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

Доказательство леммы в общем виде следует из определения всех способов.

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

  1. последнее дополнение является правилом лексимин, лексимакс или вероятностным дополнением;

  2. последнее дополнение является упорядочиванием по мощности и количество альтернатив ;

  3. последнее дополнение определяется правилами рискофил, рискофоб дополнением и

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

дополнения множества и . Для рискофил и рискофоб дополнений это и при Нетрудно показать, что если при появляются несравнимые наборы, то и при эти наборы также будут несравнимы.

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

Литература

Aleskerov F., Kurbanov E. Degree of Manipulability of Social Choice Procedures // Alkan et al. (eds.) Current Trends in Economics. Berlin, Heidelberg, N.Y.: Springer, 1999.

Favardin P., Lepelley D. Some Further Results on the Manipulability of Social Choice Rules // Social Choice and Welfare. 2006. Vol. 26. Р. 485–509.

Gibbard A. Manipulation of Voting Schemes // Econometrica. 1973. Vol. 41. Р. 587–601.

Kelly J. Almost All Social Choice Rules Are Highly Manipulable, but Few Aren’t // Social Choice and Welfare. 1993. Vol. 10. Р. 161–175.

Pattanaik P. Strategy and Group Choice. Amsterdam: North-Holland, 1978.

Pritchard G., Wilson M. Exact Results on Manipulability of Positional Voting Rules: CDMTCS Research Report Series. 2005.

Sanver R., Ozyurt S. (submitted) A General Impossibility Result on Strategy-Proof Social Choice Hyperfunctions. Submitted to Games and Economic Behavior.

Satterthwaite M. Strategy-Proofness and Arrow's Conditions: Existence and Correspondence Theorems for Voting Procedures and Social Welfare Functions // Journal of Economic Theory. 1975. Vol. 10. Р. 187–217.



Похожие документы:

  1. Программа дисциплины «Математические модели и методы принятия решений в системах государственного и муниципального управления» для направления 081100. 68 «Государственное и муниципальное управление» подготовки магистра Правительство Российской Федерации

    Программа дисциплины
    ... образования "Национальный исследовательский университет "Высшая школа экономики" Факультет государственного и муниципального управления ... , Москва, 2003, 44 с. 3. Алескеров Ф.Т., Карабекян Д.С., Санвер Р.М., Якуба В.И. «Оценка степени манипулируемости ...
  2. Программа дисциплины «Аналитические методы принятия решений в государственном и муниципальном управлении» для направления 38. 04. 04 «Государственное и муниципальное управление» подготовки магистра Правительство Российской Федерации

    Программа дисциплины
    ... образования "Национальный исследовательский университет "Высшая школа экономики" Факультет государственного и муниципального управления Программа ... , Boulder and London, 1988. Алескеров Ф. Т., Карабекян Д. С., Санвер Р. М., Якуба В. И. Оценка степени ...
  3. Программа дисциплины «Теория принятия решений» для направления 41. 04. 04. «Политология»

    Программа дисциплины
    ... государственное автономное образовательное учреждение высшего профессионального образования "Национальный исследовательский университет ... сфере, 2008, № 1, 4-9 Алескеров Ф.Т., Карабекян Д.С., Санвер Р.М., Якуба В.И. «Оценка степени манипулируемости ...

Другие похожие документы..