Диссертация (Манипулирование в задаче коллективного принятия решений), страница 11

Генерировался 1 млн профилей предпочтений,для которых проводился анализ и расчет всех описанных вышеиндексов.Рассмотрим индекс Нитцана-Келли. Для каждого правила профильможет быть манипулируем или нет. Таким образом, мы имеем дело сбиномиальным распределением с вероятностью p (истинное значениеиндекса).

Так как выборка достаточно большая, по центральнойпредельной теореме случайная величинаNK  pp (1  p)nимеет стандартноенормальное распределение [10, стр. 166]. Тогда доверительный интервалиндекса будет определяться как:NK  z / 2NK (1  NK )NK (1  NK ) p  NK  z / 2nnИзвестно, что максимальная дисперсия для биномиальногораспределения будет наблюдаться, когда NK =0,5. Подставляя значенияв формулу доверительного интервала, получаем, что с вероятностью95% истинное значение индекса лежит в области примерно 0,001 в обестороны от полученного значения индекса.

Приближенная длинадоверительного интервала может быть рассчитана для каждого значенияиндекса NK , но не будет превышать 0,002 (по 0,001 в обе стороны).67Для индекса I1 ситуация несколько иная. Фактически дляпостроения доверительного интервала мы должны рассматриватьвыборку профилей, каждый из которых принимает какое-то значение поin1  ijформуле. Выборочное среднее и есть значение индекса. Ввидуn  (m!1)сложности вычислений, значения для каждого профиля не сохранялисьпри подсчете индекса, поэтому нет возможности оценить выборочнуюдисперсию. В то же время мы знаем, что по определению  ij величинаin1  ijпринимает значения от 0 до 1, причем в среднем ближе к 0, чемn  (m!1)к 1. Подробнее об этом упомянуто в Главе 4. Мы знаем, чтомаксимальновозможнаядисперсиядляраспределения,котороепринимает значения от 0 до 1, равно 0,25.

Таким образом, мы можемсказать, что погрешность в оценке для I1 , как и для индекса NK , небудет превышать 0,001 в обе стороны, однако стоит ожидать вреальности более низких значений для 95%-го доверительногоинтервала.Ситуация с индексами I 2 и I 3 похожа на предыдущую, однакостоит понимать, что характеристики профилейnZi =1 ijnизменяются не впромежутке от 0 до 1, а в промежутке от 0 до 2 m  2 ( 2 m  1 – это длиналинейного порядка альтернатив, а 2 m  2 – это максимальный выигрыш,который может быть получен при манипулировании). Разумеется,реальные пределы изменения значений могут быть гораздо меньше.Таким образом, можно точно сказать, что погрешность в оценке небудет превышать 0,001  2m  2 в обе стороны, т.е.

0,006 для 3-хальтернатив, 0,014 для 4-х и 0,03 для 5-ти. Там, где это возможно,доверительные интервалы сокращены.68Глава 4. Манипулируемость правил голосованияГлава по оценке манипулируемости имеет следующую структуру.Сначалавсеправиладетальнопроанализированыпостепениманипулируемости, затем по свободе манипулирования и затем поэффективности манипулирования. В рамках первого направлениясопоставления поочередно рассмотрено пять групп правил, и в каждойиз них выделено одно или несколько наименее манипулируемых правил.Затем произведено общее сопоставление наименее манипулируемыхправил и сделаны выводы.

Глава завершается рассмотрением случаяслабого манипулирования и анализом разрешимости правил принятиярешений.4.1. Степень манипулируемости.Заметим, что для случая трех альтернатив все описанные вышеалгоритмы расширения предпочтений дают четыре различных линейныхупорядочения. Назовем их в соответствии с алгоритмом, которыйприводит к такому линейному порядку следующим образом:1. (Leximin3) aEPi a, bEPi bEPi a, cEPi a, b, cEPi b, cEPi c;2. (Leximax3) aEPi a, bEPi a, b, cEPi a, cEPi bEPi b, cEPi c;3. (PWorst3) aEPi a, bEPi bEPi a, b, cEPi a, cEPi b, cEPi c ;4.

(PBest3) aEPi a, bEPi a, cEPi a, b, cEPi bEPi b, cEPi c.Цифра 3 обозначает количество альтернатив, для которыхиспользуется метод. Следует отметить, что для случая трех альтернативметод усреднения рангов дает любое из 4-х упорядочений в зависимостиот применяемого дополнения.Данные расширенные предпочтения отличаются между собойлишь соотношением между тремя средними наборами.

Таким образом,степень манипулируемости различных правил (значение индексаНитцана-Келли) должна быть сильно похожа, за исключением тех69случаев, когда искажение предпочтений приводит к изменению выборавнутри этой группы наборов.4.1.1. Позиционные (порядковые) правила: 1-я частьРассмотрим следующие порядковые правила: относительноебольшинство, одобряющее голосование с q=2 и q=3, правило Борда,правило Блэка и пороговое правило.

В таблицах 4.1 и 4.2 приведенызначения индекса Нитцана-Келли для указанных выше правил, 3альтернатив и 3, 4 агентов в зависимости от рассматриваемогоупорядочения. Последний столбец содержит значения индекса НитцанаКелли для случая алфавитного разрешения множественного выбора.Таблица 4.1 – Индекс Нитцана-Келли для 3 альтернатив и 3 агентов3 агентаПравило\РасширениеLeximin3 Leximax3 PWorst3 PBest3TBRОтн. большинство0,222200,2222Одобряющее q=20,11110,61110,11110,6111 0,2639Правило Борда0,30560,41670,30560,4167 0,2361Процедура Блэка0,05560,16670,05560,1667 0,1111Пороговое правило0,30560,41670,30560,4167 0,361100,1667Таблица 4.2 – Индекс Нитцана-Келли для 3 альтернатив и 4 агентов4 агентаПравило\РасширениеLeximin3 Leximax3 PWorst3 PBest3TBRОтн.

большинство0,33330,33330,33330,3333 0,1852Одобряющее q=20,29630,29630,29630,2963 0,2755Правило Борда0,36110,40280,36110,4028 0,3102Процедура Блэка0,23610,27780,27780,2361 0,1435Пороговое правило0,40280,40280,40280,4028 0,338070Как видно из таблиц, значения индексов чаще всего совпадаютлибо для Leximin3 и PWorst3, либо для Leximin3 и PBest3. Это чащевсего означает, что манипулирование между наборами, соотношениеммежду которыми и отличаются расширения, невозможно ни при какомпрофилепредпочтений,либовозможно,ноприэтомвсегдаприсутствуют более выгодные варианты манипулирования. Например,Leximin3 и PWorst3 отличаются лишь соотношением между a, b, c иa, c.

Если для какого-то правила имеются одинаковые значения индексаНитцана-Келли для Leximin3 и PWorst3, то значит не существуетникакого профиля предпочтений, для которого правило голосованиядает a, b, c ( a, c), и один из участников может, манипулируя, достичьисхода a, c ( a, b, c), но при этом не может достичь ни одного другого,лучшего для него.

Если бы данная ситуация была возможна, то значенияиндексов отличались.Мы не можем утверждать, что переход из a, b, c в a, c илинаоборотневозможен,таккакиндексотмечаетсамфактманипулируемости профиля, поэтому если одновременно с этимпереходом всегда возможен переход в более хороший набор с точкизрения данных расширений, то это на значении индекса не отразится.Такимобразом,вдальнейшемприописаниирезультатоврассматриваются не все методы, а только те, которые дают существенноотличающиеся друг от друга результаты.Прежде чем переходить к более подробному анализу степениманипулируемости для разного числа агентов, необходимо уделитьбольше внимания нулевой манипулируемости правила относительногобольшинства для 3-х агентов, 3-х альтернатив и расширений Leximax3 иPBest3.

Главным отличием этих расширений является то, что в нихнабор b хуже, чем наборы a, b, c и a, c . Покажем, что именно этотфакт объясняет нулевую манипулируемость. Для трех альтернатив и71трех агентов возможно 216 различных профилей предпочтений. Всепрофили можно условно поделить на три группы:1) Профили, в которых лучшие альтернативы каждого одинаковы;2) Профили, в которых имеются две одинаковых лучшихальтернативы;3) Профили, где все лучшие альтернативы разные.Очевидно, что среди профилей типа 1 манипулирования приправиле относительного большинства быть не может, так как каждый изагентов получает лучшую для себя альтернативу в виде итоговоговыбора.

Среди профилей типа 2 манипулирование также не возможно.Если лучшая альтернатива агента поддержана большинством, тостимулов к манипулированию нет, так как она будет итоговым выбором.Если же лучшая альтернатива "в меньшинстве", то агент не имеетникакого влияния на итоговый выбор. В любом случае будет выбранаальтернатива, которая поддержана большинством. Манипулированиеможет иметь место только в профилях типа 3.Без потери общности предположим, что у первого агента в одномиз таких профилей предпочтения вида aP1bP1c . Так как у всех лучшиеальтернативы разные, выбор в данном профиле будет a, b, c. У агента 1имеется два варианта воздействия на итоговый выбор: назвать в виделучшей альтернативы b или c . Та альтернатива, которую он назовет, ибудет итоговым выбором. Очевидно, что называть c ему не выгодно, таккак c строго хуже a, b, c .

Таким образом, решение о том,манипулировать или нет, зависит от того, что для него лучше: b илиa, b, c . Для расширений Leximax3 и PBest3 набор a, b, c лучше b ,поэтому манипулирование невозможно.Заметим, что данный результат подтверждает наблюдение Барбера[24], о котором говорилось в первой главе. Он утверждал, что для случаятрех альтернатив могут существовать такие расширения предпочтений,72когда будет существовать неманипулируемое недиктаторское правило.Как показано выше, для расширений Leximax3 и PBest3 таким правиломможет быть правило относительного большинства.Вернемся к последним столбцам Табл. 4.1 и 4.2, которые содержатзначения индекса Нитцана-Келли для случая алфавитного правилаустранения несравнимости.

Как описано в Главе 1, данный методнаиболее часто применяется для анализа степени манипулируемости вкачестве простой альтернативы множественному выбору. Как можнозаметить из таблиц (в особенности из Табл. 4.2), данный метод зачастуюприводит к недооценке степени манипулируемости, если сравнивать сослучаем множественного выбора.Рассмотрим, как меняется значение индекса Нитцана-Келли приувеличении числа агентов. На Рис. 4.1 и 4.2 показаны значения индексадля упорядочений Leximin3 и Leximax3, соответственно.По осиабсцисс отложен логарифм числа агентов для того, чтобы более четкобыла видна картина.