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

Их сравнение для случая трех альтернатив и некоторыхрасширений представлено на Рис. 4.35, 4.36.122Рисунок 4.35. Индекс Нитцана-Келли для расширения PBest3Рисунок 4.36. Индекс Нитцана-Келли для расширения PWorst3123Отметим, что ряд правил дают одинаковый результат для случаятрех альтернатив. Среди рассматриваемых в данном разделе правил этоМинимальное недоминируемое множество, правила Коупленда 3 иФишбурна, а также Сильнейшее q-Паретовское правило простогобольшинства. Еще больше правил дают одинаковые результаты прималом числе участников голосования.Обобщим результаты в Табл. 4.17.Таблица 4.17 – Минимально манипулируемые правила согласно индексуНитцана-Келли для 3-х альтернатив и всех правилАгенты34Leximin3Bl, IB, N, MMM,FUUR, CCC, Sqpp,S-est56789Us-2IB, N, MMM,FUUR, CCC, S-estHIB, NHIB, N1011Us-2N12131415HNHN1617NN18192021NNHN22NLeximax3Pl, HMdsHUs-2HHHMMF, C-3,S-estHMMF, C-3,S-estHHHMMF, C-3,S-estHMMF, C-3,S-estHHHMMF, C-3,S-est124PWorst3Bl, IB, N, MMM,FUUR, CCC, Sqpp,S-estBl, IB, N, C, MMF,Us-2, C-3, S-estIB, N, MMM,FUUR, CCC, S-est2-AIB, NHIB, NPBest3Pl, HUs-2HHHHHMMF, C-3, S-estNUs-2HNNHNHHHHMMF, C-3,S-estHNNNNHNNHHHHMMF, C-3,S-est23N2425293039404950596069~100NNNNNNNNNNN~NТакимобразом,HMMF, C-3,S-estHHNNNNHHNN~NвNHNNNNNNNNNNN~NHHHHNNNHHHN~Nбольшинствеслучаевнаименееманипулируемыми являются порядковые правила: Процедуры Хара иНэнсона.Рассмотрим случай 4-х альтернатив на Рис.

4.37-4.39Рисунок 4.37. Индекс Нитцана-Келли для расширения AR-RA4125Рисунок 4.38. Индекс Нитцана-Келли для расширения PBest4Рисунок 4.39. Индекс Нитцана-Келли для расширения PWorst4126Отметим, что подчеркнутая выше особенность Сильнейшего qПаретовского правила простого большинства приводит к интересномурезультату для случая AR-RA4. Если сначала число агентов, прикотором достигается наименьшая манипулируемость для правилаНэнсона и других правил с периодом равным 2 совпадает с таким же дляСильнейшего q-Паретовского правила простого большинства, то после14-16 агентов ситуация меняется и там, где для Сильнейшего qПаретовского правила простого большинства достигается минимум, дляправила Нэнсона наблюдается максимум.

Результаты обобщены в Табл.4.18.Как видно из Табл. 4.18, в случае 4-х альтернатив результатыболее разнородны, чем в случае трех. Можно отметить два факта: вопервых,вероятностныеилексикографическиеметодысильноотличаются от метода усреднения рангов. Если для первых минимальнаяманипулируемость на начальном этапе достигается для правил,построенных на мажоритарном отношении, то для метода усреднениярангов минимально манипулируемыми являются порядковые правила.Также стоит отметить, что для вероятностных и лексикографическихметодов Сильнейшее q-Паретовское правило простого большинствастановится минимально манипулируемым для четного числа участниковпо описанным выше причинам.Рассмотрим случай пяти альтернатив на Рис.

4.40-4.42 и в Табл.4.19127Pl,HUs-2FUURUs-2Pl, H,MMM2-AFUURS-estPl, H,MMMUs-2HHHHHUs-2HHHHHMusHHHHNNHHNNHNS-estNS-estNS-estNS-estHUs-2NHNFHFNHNNNNNNNNNNNNNNNNNNNNNHUs-2HHNS-estHNHHNNHNHNNNHNNNNNNNNNNNNPBest4AR-RL4S-estHS-estHHHS-estHS-estHHNS-estHS-estNNS-estNS-estNS-estNS-estNS-estAR-RA4HMdsHHHPWorst4Leximax4Pl,HMdsMMM,FUURIPMMM,FUURS-estMMMHMMMMusMMMMusMMMMusFUURMusFUURMusFUURMusMMMMusMMMMusMMMIBS-estIBS-estNS-estIBS-estNS-estAR-Lmax4,AR-DCRA456789101112131415161718192021222324252930нчч697079чнч100MMM,FUURUs-2MMM,FUURUs-2MMMHMMMUs-2MMMHFUURHFUURMusMMMMusFUURMusFUURMusFUURMusFUURIBMusIBS-estNS-estIBS-estNS-estAR-Lmin4,AR-IC-RL434Leximin4АгентыТаблица 4.18 – Минимально манипулируемые правила согласно индексуНитцана-Келли для 4-х альтернатив и всех правилHUs-2NHNFHFNHNNNNNNNNNNNNNNNNNNNNNHUs-2HHNUs-2HNHHNNHNHHNNHNNNNNNNNNNNNПримечание: 2-A – Approval q=2; FUUR – Fishburn, Uncovered Set I, Uncovered Set II,Richelson; IB – Inverse Borda; H – Hare; Mds – Minimal Dominant Set; MMM – Minimal128Dominant Set, Minimal Undominated Set, Minimal Weakly Stable Set; N – Nanson; Pl –Plurality; S-est – Strongest q-Pareto Simple Majority; Us-2 – Uncovered Set IIРисунок 4.40.

Индекс Нитцана-Келли для расширения AR-RA5Рисунок 4.41. Индекс Нитцана-Келли для расширения PBest5129Рисунок 4.42. Индекс Нитцана-Келли для расширения PWorst5Из Рис. 4.40-4.42 и в Табл. 4.19 видно, что сохраняется ситуация,соответствующая случаю четырех альтернатив: имеется разделениевероятностных, лексикографических методов и метода усреднениярангов.

Также как и для предыдущего случая для вероятностных илексикографических методов при малом числе участников лучшепроявляют себя правила, основанные на мажоритарном отношении. Приросте числа участников наименее манипулируемыми становятсяправило Нэнсона и Сильнейшее q-Паретовское правило простогобольшинства.Дляметодовусредненияранговманипулируемыми становятся правило Нэнсона и Хара.130наименееMMM, FUUR2-AMMM, FUURIPMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusIBS-estS-estS-estS-estS-estS-estS-estPl, HPl, HHHHHHUs-2HHHHHNHHHHNNHHNNS-estNS-estNS-estNS-estFUUR2-AHSqppHHNMusHMusNHNNNNNNNNNNNNNNNNNNNPl, HMdsHMusHHNMusHNHHNNHNHNNNHNNNNNNNNNNAR-RL5PBest5Pl, HMdsHMdsHHHS-estHS-estHHHS-estHS-estHS-estNS-estHS-estNNS-estNS-estNS-estNS-estAR-Lmin5,AR-IC-RA5,AR-IC-RL5,AR-RA5AR-Lmax5,AR-DC-RA5,AR-DC-RL5PWorst53 MMM, FUUR4Us-25 MMM, FUUR6Us-27Mds,Mus8H9FUUR10Mwss11Mds,Mus12Mus13FUUR14Mus15FUUR16Mus17FUUR18Mus19Mds,Mus20Mus21Mds,Mus22Mus23Mds,Mus24Mus25Mds,Mus29IB30Mus39N40S-est49NчS-estнчS-est100S-estLeximax5Leximin5АгентыТаблица 4.19 – Минимально манипулируемые правила согласно индексуНитцана-Келли для 5-и альтернатив и всех правилPl, HUs-2HUs-2HHNMusHNHHNNHNHNNNHNNNNNNNNNNПримечание: 2-A – Approval q=2; FUUR – Fishburn, Uncovered Set I, Uncovered Set II,Richelson; IB – Inverse Borda; H – Hare; Mds – Minimal Dominant Set; Mus – MinimalUndominated Set; Mwss – Minimal Weakly Stable Set; MMM – Minimal Dominant Set,Minimal Undominated Set, Minimal Weakly Stable Set; N – Nanson; Pl – Plurality; S-est– Strongest q-Pareto Simple Majority; Sqpp – Strong q-Pareto Plurality; Us-2 – UncoveredSet II131Таким образом, подводя итоги, стоит отметить несколько важныхмоментов.

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

Среди этих правил стоит отдельно отметитьпроцедуры Нэнсона и Хара – именно они дают чаще всего лучшийрезультат с точки зрения индекса Нитцана-Келли.В следующем разделе данные правила будут сопоставлены с точкизрения другой меры манипулируемости: группы индексов I 1–показателей свободы манипулирования.4.2. Свобода манипулированияВ данном разделе мы сопоставим правила с точки зрения значенияиндекса I 1 , то есть свободы манипулирования.

Как уже было сказано вглаве 3, группа индексов I 1 включает в себя 3 индекса: I 1 - индекссвободыманипулирования,I 10-индекснечувствительностикизменениям предпочтений и I 1 - индекс возможного ухудшениярезультата. В сумме для случая сильного манипулирования индексы I 1дают 1, так как описывают все возможные последствия искаженияпредпочтений.Рассмотримзначенияиндексовдлянаименееманипулируемых правил согласно индексу Нитцана-Келли, описанных впредыдущем разделе.

Для сопоставления результатов, также рассмотримряд классических правил. Значения индексов для случая 3-х альтернативи одного из методов представлено на Рис. 4.43 и 4.44.132Рисунок 4.43. Индексы I 1 для расширения PWorst3 и пяти агентовРисунок 4.44. Индексы I 1 для расширения PWorst3 и ста агентовЗеленым цветом отражено значение индекса I 1 , желтым - I 10 икрасным I 1 . Отметим несколько важных фактов. Во-первых, очевидно,что при увеличении числа агентов растет значение индекса I 10 – т.е. чем133больше участников голосования, то тем меньше возможностей изменитьрезультатголосованияпутеминдивидуальногоискаженияпредпочтений.

В то же время значение индекса I 1 достаточно высокодаже при большом числе участников - порядка 13 процентовпотенциальных искажений могут привести к ухудшению результата.Во-вторых, отметим, что сама по себе свобода манипулирования( I 1 ) изначально не велика, иначе говоря, возможности индивидуальногоулучшения результата имеются, но их не так много. При росте числаучастников голосования до 100 падение значения индекса в абсолютномвыражении не превышает в среднем 1,5 процентных пункта.В-третьих, отметим, что из представленных результатов видно,что те правила, которые были наименее манипулируемы с точки зрениястепени манипулируемости, в среднем обладают меньшей свободойманипулирования. Рассмотрим, как изменяются индексы в динамике.Рисунок 4.45.