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

4.23 – 4.25 можно сделать следующие выводы. Вопервых, минимально манипулируемое правило с точки зрения степениманипулируемости – правило Нэнсона – практически никогда неявляется таковым с точки зрения индекса I 3 . Иначе говоря,манипулирование при правиле Нэнсона самое редкое, однако еслиимеется возможность манипулирования, то в среднем выигрыш от этогоискажения для правила Нэнсона больше, чем для ряда других правил, вкоторых манипулирование бывает чаще.Во-вторых, отметим, что для случая 4-х альтернатив и, особенно,для случая пяти одобряющее голосование с q=2 обеспечиваетнаименьшую эффективность манипулирования.

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

Это объясняется тем же, чем и в случаеанализастепениманипулируемости:правила,построенныенамажоритарном отношении, при малом числе альтернатив даютодинаковый результат.145Подводя итоги анализа эффективности манипулирования, стоитотметить, что это фактически другой взгляд на манипулируемостьправила.Однако,еслирассуждатьоважностипоказателейэффективности и степени манипулируемости, то можно с оговоркамиутверждать, что степень манипулируемости является более важнымпоказателем, так как анализирует саму возможность изменять результатколлективного принятия решений в свою пользу, в то время как индексI 3 измеряет средний максимальный выигрыш.

Разумеется, это приводитк некоторому другому взгляду на проблему. Например, правило, котороедопускает манипулирование в большом числе случаев, но каждый развыигрыш от искажения маленький, может обладать меньшим значениеминдекса I 3 , чем правило, которое допускает манипулирование в оченьмалом числе случаев, однако, с значительным выигрышем. С однойстороны, сложно сказать, какое из правил лучше, но если ставить вопроспоиска именно минимально манипулируемого правила, то значенияиндексовстепениманипулируемостиявляютсяболееважнымпоказателем. На индексы эффективности стоит ориентироваться, восновном, в случае примерно равной степени манипулируемости, чтобывыбрать среди одинаково манипулируемых правил то, которое делаетманипулирование менее выгодным.Такимобразом,вэтихразделахмыизучилиправилаколлективного принятия решений с точки зрения разных показателейстепени и эффективности манипулирования.

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

Слабое манипулированиеКак уже было сказано в главе 2, случай слабого манипулированиясостоит в том, что расширенные предпочтения являются частичнымпорядком - иначе говоря, не все наборы альтернатив сравнимы. В этомслучаеискажениепредпочтенийможет привестикизменениюколлективного выбора на такой, который является несравнимым спервоначальным. Из-за этого появляется новый индекс I 1? - индекснеопределенного перехода, значения которого для некоторых правилпредставлены в Табл. 4.26.Таблица 4.26 – Значения индекса I 1 для 3-х альтернатив и 3-х агентовИндекс ПравилоKellyDA ПринципEUCEPAГэрденфорса0,04440,04440,0444I 1Отн.

Большинство011?11Отн. Большинство0,46670,46670,4667Отн. Большинство0,48890,48890,4889Отн. Большинство0000,05930,05930,05930,37780,37780,37780,47410,47410,56300,08890,08890I 1Одобряющееголосование q=2Одобряющееголосование q=2Одобряющееголосование q=2Одобряющееголосование q=2Правило Блэка0,01110,01110,0111I 10Правило Блэка0,33890,33890,3389I 1Правило Блэка0,54720,60280,6222?1Правило Блэка0,10280,04720,0278IIIII 10I 1I 1?IИз данной таблицы следует интересный факт, который можнообобщить на случай трех альтернатив и большинства правил: значенияиндексов степени манипулируемости совпадают для всех трех слабыхметодов.

Даже если изначально имеются неопределенные переходы, тодля большинства случаев более сильная аксиома определяет этотпереход как ухудшение коллективного выбора, тем самым не влияя на147значение меры манипулируемости. Пользуясь данным наблюдением,представим результаты для порядковых правил на Рис. 4.51.Рисунок 4.51. Индекс Нитцана-Келли для расширения KellyDA3Как видно из рисунка, ситуация похожа на случай сильногоманипулирования. На самом деле, в силу доказанных в главе 2утверждений можно говорить о том, что значения индекса НитцанаКеллидляслабогоманипулированиядаетнижнююоценкуманипулируемости правила принятия решений, так как все сильныеметоды удовлетворяют слабым аксиомам.

Поэтому, если правиломанипулируемо для данного профиля для одной из слабых аксиом, тооно точно манипулируемо для сильных методов. В то же время обратноене обязательно верно.Результаты для порядковых правил можно обобщить в Табл. 4.27.148Таблица 4.27– Минимально манипулируемые правила согласноиндексу Нитцана-Келли для 3-х альтернатив и порядковых правил11N22NKellyDA3,Агенты Gärdenfors3,12H23NEUCEPA313N24H3Pl, H, Bl, IB, N14H25N4Bl, IB, N15N29N5Bl, IB, N16N30H6H17N39N7N18H~~8H19N100N9IB, N20H10N21NПримечание: Bl – Правило Блэка; H – Процедура Хара; IB – Процедураисключения Борда; N – Процедура Нэнсона; Pl – Правило относительногобольшинстваКак видно из Табл. 4.27, для случая слабого манипулированияправило Нэнсона является одним из минимально манипулируемых вбольшинстве случаев. Подобная ситуация наблюдается и для индекса I 1(см.

Рис. 4.52 и Табл. 4.28)Таблица 4.28 – Минимально манипулируемые правила согласно индексуI 1 для 3-х альтернатив и первой группы правилАгенты345 6 7 8 9 10 11 12 13 14 15 16 ~ 100KellyDA3, Pl, H, Bl,Gärdenfors3,Bl,IB,EUCEPA3 IB, N N Bl N Bl N Bl N Bl H Bl N Bl N ~ NПримечание: Bl – Правило Блэка; H – Процедура Хара; IB – Процедура исключенияБорда; N – Процедура Нэнсона; Pl – Правило относительного большинства149Рисунок 4.52. Индекс I 1 для расширения KellyDA3В диссертации мы не будем детально рассматривать случай 4-х и5-и альтернатив.

Стоит лишь отметить, что в них уже наблюдаетсянебольшое различие в значениях индекса Нитцана-Келли для рядаправил при разных слабых аксиомах, поскольку при большем числеальтернатив более сильная аксиома добавляет больше связей врасширенные предпочтения участника голосования.Рассмотрим минимально манипулируемые правила для 3-хальтернатив и всех правил в табл. 4.29.150Таблица 4.29 – Минимально манипулируемые правила согласно индексуНитцана-Келли для 3-х альтернатив и всех правилАгенты3456789101112131415161718нчч899099100KellyDA3Pl, H, IB, Bl, N, *Us-2*Us-2*Us-2*Us-2*Us-2*Us-2*Us-2*Us-2*Us-2*Us-2*Us-2Gärdenfors3Pl, H, IB, Bl, N, *Us-2*Us-2*Us-2*Us-2*Us-2*Us-2*Us-2*Us-2*Us-2*MMF, C-3, S-est*MMF, C-3, S-estEUCEPA3Pl, H, IB, Bl, N, *Us-2*H*H*Us-2*H*H*MMF, C-3, S-est*H*MMF, C-3, S-est*MMF, C-3, S-est*MMF, C-3, S-estПримечание: * - Все правила, построенные на мажоритарном отношении+Сильнейшее q-Паретовское правило простого большинства, Bl – правило Блэка; C-3– Правило Коуплэнда 3; H – Процедура Хара; IB – Процедура исключения Борда;MMF – группа правил: Минимальное недоминируемое множество, минимальноеслабоустойчивое множество, правило Фишбурна; N – Правило Нэнсона; Pl –Правило относительного большинства; S-est – Сильнейшее q-Паретовское правилопростого большинства; Sqpp – Сильное q-Паретовское правило относительногобольшинства; Us-2 – Непокрытое множество 2Интересно то, что за исключением правила Хара и случая 3-хагентов, минимально манипулируемыми правилами являются правила,построенные на мажоритарном отношении.

Правило Нэнсона, котороеявлялось наименее манипулируемым среди порядковых правил дляслабого манипулирования и среди всех для сильного, имеет большеезначениеиндексаНитцана-Келли.Этот,напервыйвзгляд,удивительный факт связан с уже описанной ранее проблемой151разрешимостиправилпринятиярешений.Вусловияхслабогоманипулирования, когда многие наборы из нескольких альтернативнесравнимы, эта проблема встает особенно остро. Непокрытоемножество 2 для 10 агентов в 41,7% случаев дает множественный выбор,в то время как правило Нэнсона – в 32,1%.

Соотношению разрешимостии манипулируемости правил посвящен завершающий раздел даннойглавы.4.5. Разрешимость и манипулируемость.Мы рассматривали до сих пор оценку правила голосования сточки зрения манипулируемости. Однако можно внести и еще один, неменее важный, критерий – разрешимость правила голосования, подкоторой будем понимать средневзешенное количество альтернатив витоговом наборе. Таким образом, меру разрешимости можно записатькакmD     d , 1где d  – доля профилей, для которых результат голосования содержит альтернатив.Таким образом, имеется два критерия и можно решать задачу опоиске Парето-эффективных правил голосования.На Рис. 4.53, 4.54 изображены все правила в пространстверазрешимость – манипулируемость для ста участников голосования, 4-хальтернатив и двух методов расширения.152Рисунок 4.53.

Разрешимость и манипулируемость для расширенияLeximax4 и ста агентовРисунок 4.54. Разрешимость и манипулируемость для расширенияPWorst4 и ста агентовКрасными точками на рисунке отмечены правила, лежащие наПарето-границе. Примечательно, что правило Нэнсона является лучше153большинства правил как по степени манипулируемости, так и поразрешимости выбора. В то же время, пороговое правило, хоть и неявляется ни в одном из случаев наименее манипулируемым правилом,лежит на Парето-границе в силу своей высокой разрешимости.Помимо поиска фиксированной границы для заданных методов иколичества агентов, также представляет интерес и отображениединамики всех показателей при росте числа агентов.