Диссертация (1137703), страница 15
Текст из файла (страница 15)
Причем последняя даеточень похожие результаты с процедурой Нэнсона. В тех случаях, когдасогласно расчетам процедура исключения Борда превосходит процедуруНэнсона, нельзя отвергнуть гипотезу о равенстве индексов НитцанаКелли. Значимое превосходство этого правила наблюдается лишь в101случае 4-х альтернатив, методов PWorst4 и Leximin4, и нечетном числеучастников не превышающем 49. Таким образом, в большинстве случаевименно два правила: процедура Хара и правило Нэнсона являютсянаименее манипулируемыми. Именно они будут нами рассматриватьсяпри сопоставлении с другими группами.PWorst5PBest5AR-Lmin5,AR-IC-RA5,AR-IC-RL5AR-Lmax5,AR-DC-RA5,AR-DC-RL5AR-RA5AR-RL53 IB, N42-A5N6AP7N8H9N10N11N12N13IB14H15IB16N17IB18N19IB20N21IB22N23IB24N25IB29IB30N~~100NLeximax5Leximin5АгентыТаблица 4.10 – Минимально манипулируемые правила согласно индексуНитцана-Келли для 5-и альтернатив и второй группы правилPl, HPl, HHBlHHHBlHNHHHNHNHNNNHNNNN~NIB, N2-ANAPNHNNNNIBNIBNIBNIBNIBNIBNIBIBN~NPl, HPl, HHHHHHBlHHHHHNHHHHNNHHNNN~NN2-AHHHHNNHNNHNNNNNNNNNNNNN~NPl, H2-AHBlHHNBlHNHHNNHNHNNNHNNNN~NN2-AHBlHHNNHNNHNNNNNNNNNNNNN~NPl, HBlHHHHNBlHNHHNNHNHNNNHNNNN~N102Примечание: 2-A – Одобряющее голосование q=2; Bl – Правило Блэка; IB – Правилоисключения Борда; AP - Обратное правило относительного большинства; H –Процедура Хара; N – Процедура Нэнсона; Pl – Правило относительногобольшинства4.1.3.
Правила, использующие мажоритарное отношениеРассмотримследующуюгруппуправил,построенныхнамажоритарном отношении и описанных в разделе 3.2.2. На Рис. 4.20,4.21 представлены значения индекса Нитцана-Келли для данной группыи двух типовых расширений.Из Рис. 4.20 и 4.21 следует сразу отметить две важныеособенности. Во-первых, все рассматриваемые правила показываютзависимость меры манипулируемости от четности-нечетности числаагентов. Это объясняется тем, что в случае нечетного числа агентов графмажоритарного отношения является связным – то есть имеются всесвязи.Рисунок 4.20.
Индекс Нитцана-Келли для расширения PBest3103Рисунок 4.21. Индекс Нитцана-Келли для расширения PWorst3Во-вторых,принечетномчислеучастниковвсеправилапоказывают одинаковый результат независимо от метода. Это связано стем, что в случаи трех альтернатив и нечетного числа участниковвозможно лишь два вида мажоритарного графа (с точностью допереименования альтернатив):abacbcОчевидно, что в случае левого графа все методы дадут в качествеитогового выбора альтернативу, доминирующую две другие. В случаеправого графа имеется известная ситуация цикла Кондорсе. В этомслучае каждая альтернатива является доминируемой поэтому всеправила дадут результат из всех трех альтернатив в виде итоговоговыбора.104Также из Рис.
4.20, 4.21 видно, что некоторые правила даютодинаковые результаты даже в случае четности числа агентов. Обобщимрезультаты в Табл. 4.11.Таблица 4.11 – Минимально манипулируемые правила согласно индексуНитцана-Келли для 3-х альтернатив и третьей группы правилАгенты34567891011121314нечетноечетное99100Leximin3*Us-2*Us-2*Us-2*Us-2*MMF, C-3*MMF, C-3*MMF, C-3*MMF, C-3Leximax3PWorst3PBest3***MdsMMF, C-3, Us-2Us-2***Us-2Us-2Us-2***Us-2Us-2Us-2***MMF, C-3MMF, C-3Us-2***MMF, C-3MMF, C-3Us-2***MMF, C-3MMF, C-3MMF, C-3***MMF, C-3MMF, C-3MMF, C-3***MMF, C-3MMF, C-3MMF, C-3Примечание: * – все правила группы; C-3 – правило Коупленда 3; Mds –Минимальное доминирующее множество; MMF – группа правил: Минимальноенедоминируемое множество, Минимальное слабоустойчивое множество, правилоФишбурна; Us-2 – Непокрытое множество 2Стоит отметить, что почти все результаты значимы.
Исключениемявляются две ситуации, отмеченные серым цветом в Табл. 4.11. В случаерасширения Leximin3 и 12 агентов наименьшая манипулируемостьнаблюдается для группы правил MMF, C-3, однако мы не можетотвергнуть гипотезу о том, что такое же значение индекса НитцанаКелли наблюдается для Непокрытого множества 2 и минимальногодоминирующегомножества.Второйситуациейявляетсяслучайрасширения Leximax3 и 8 агентов. Хотя наименьшая манипулируемостьв этом случае наблюдается у Непокрытого множества 2, нельзя105отвергнуть гипотезу, что такое же значение индекса наблюдается и длягруппы правил MMF, C-3. Таким образом, наименее манипулируемымиправилами является группа правил MMF, C-3 для большого числаучастников и Непокрытое множество 2 для случая малого числа.Проверим, сохранятся ли эти результаты в случае 4-х альтернатив.Из имеющихся 10 методов только 8 дают различные результаты с точкизрения поиска минимально манипулируемых процедур.
Как и раньше,покажем результаты для трех принципиально отличающихся методов.Заметим, что на Рис. 4.22 - 4.24 видно, что многие правиласовпадают для нечетного числа агентов. Однако, в отличие отпредыдущего случая только часть правил дают одинаковый результат.Это связано с тем, что возможно гораздо большее число видовмажоритарных графов в случае 4-х альтернатив.Рисунок 4.22. Индекс Нитцана-Келли для расширения PBest4106Рисунок 4.23. Индекс Нитцана-Келли для расширения PWorst4Рисунок 4.24.
Индекс Нитцана-Келли для расширения AR-RA4Продемонстрируем результаты в таблице.107Таблица 4.12 – Минимально манипулируемые правила согласно индексуAR-RL4AR-RA4AR-Lmax4,AR-DC-RA4AR-Lmin4,AR-IC-RL4PBest4PWorst4Leximax4Leximin4АгентыНитцана-Келли для 4-х альтернатив и третьей группы правил3 MMM, FUUR MMM MMM, FUUR FUUR FUUR MMM FUUR MMM4Us-2MdsMMFUs-2Us-2Us-2Us-2Us-25 MMM, FUUR FUUR MMM, FUUR FUUR FUUR MMM FUUR MMM6Us-2MdsFUs-2Us-2Us-2Us-2Us-27MMMFUURMMMFUUR FUUR MMM FUUR MMM8Us-2MusFUs-2Us-2MusFUs-29MMMFUURMMMFUUR FUUR MMM FUUR MMM10Us-2MusMusUs-2FMusFUs-211MMMFUURMMMFUUR FUUR MMM FUUR MMM12MwssMusMusUs-2FMusFMus13FUURFUURMMMFUUR FUUR MMM FUUR MMM14MusMusMusMusFMusFMus15FUURFUURFUURFUUR FUUR MMM FUUR MMM16MusMusMusMusFMusFMus17MMMFUURFUURFUUR FUUR MMM FUUR MMM18MusMusMusMusFMusFMus19FUURFUURFUURFUUR FUUR CCC FUUR CCC20MusMusMusMusFMusFMus21FUURFUURMMMFUUR FUUR CCC FUUR CCC22MusMusMusMusFMusFMus23FUURFUURMMMFUUR FUUR CCC FUUR CCC24MusMusMusMusFMusFMus25FUURFUURMMMFUUR FUUR CCC FUUR CCC29FUURFUURMMMFUUR CCCCCCCCCCCC30MusMusMusMusFMusFMus39MMMFUURMMMFUUR CCCCCCCCCCCC40MusMusMusMusFC-3FC-349MMMFUURMMMFUUR CCCCCCCCCCCC50MusMusMusMusC-3C-3C-3C-359MMMFUURMMMFUUR CCCCCCCCCCCCчMusMusMusMusC-3C-3C-3C-3нчMMMMMMMMMFUUR CCCCCCCCCCCC100MusMusMusMusC-3C-3C-3C-3Примечание: CCC – группа правил Коупленда; C-3 – правило Коупленда 3; F –правило Фишбурна; FUUR – группа правил: Фишбурна, Непокрытого множества 1 и2, Ричелсона; Mds – Минимальное доминирующее множество; Mus – Минимальное108недоминируемое множество; Mwss – Минимальное слабоустойчивое множествоMMF – группа правил: Минимальное доминирующее множество, Минимальноенедоминируемое множество, Минимальное слабоустойчивое множество, правилоФишбурна; MMM – группа правил: Минимальное недоминируемое множество,Минимальное слабоустойчивое множество; Us-2 – Непокрытое множество 2Рассмотрим значимость результатов.
Стоит отметить, что вбольшинстве случаев мы не можем отвергнуть гипотезу о равенствезначенийиндексовНитцана-Келлиминимальноманипулируемыхправил, закодированных в Табл. 4.12, и правил, имеющих чуть большуюманипулируемость, чем рассматриваемые. Все подобные случаиотмечены в таблице серым цветом. Опишем типичные случаинезначимости. Самым распространенным типом можно считать случай"переключения", когда после определенного числа агентов меняетсяминимально манипулируемое правило.
В этом случае возможнанезначимость либо только в случае переключения (например, PBest4 и12 агентов или AR-RL4 и 10 агентов), либо в некоторой окрестности отнеё (например, AR-Lmin4 и 10, 12, 14 агентов). Для методов Leximin4 иPWorst4 очень большая доля незначимых результатов: везде, гдеминимально манипулируемой является группа правил MMM, неотвергается гипотеза о таком же значении индекса для группы FUUR инаоборот.
В случае, когда минимально манипулируемым являетсяМинимальное недоминируемое множество, то нельзя отвергнутьгипотезуотакомжезначениииндексадляМинимальногослабоустойчивого множества.Еслиобобщитьимеющиесярезультаты,тонаименьшаяманипулируемость будет наблюдаться для группы правил MMM иFUUR для лексикографических и вероятностных методов и для правилКоупленда для методов усреднения ранга.Рассмотрим случай пяти альтернатив.
По аналогии рассмотримтри метода.109Рисунок 4.25. Индекс Нитцана-Келли для расширения PBest5Рисунок 4.26. Индекс Нитцана-Келли для расширения PWorst5110Рисунок 4.27. Индекс Нитцана-Келли для расширения AR-RL5Заметим, что все замечания, которые были сделаны для случая 4-хальтернатив, верны и для случая 5-ти. Рассмотрим обобщенные данныев Табл. 4.13.Заметим, что в некоторых случаях результаты незначимы.
Этообъясняется в основном переключением с одного правила на другое.Интересно, что во многих случаях данное переключение происходитнесколько раз. Например, для методов усреднения ранга и четного числаагентов наблюдается переключение с Непокрытого множества 2 наМинимальное недоминируемое множество, затем (для некоторыхметодов) на правило Фишбурна и в итоге на правило Коупленда 3.Большое разнообразие результатов связано с тем, что количестворазличных мажоритарных графов для пяти альтернатив достаточновелико, поэтому результаты правил могут сильно отличаться.111Mds, MusMusFUURMusFUURMusFUURMusMds, MusMusMds, MusMusMds, MusMusMds, MusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusFUURUs-2FUURUs-2FUURUs-2FUURUs-2FUURMusFUURMusFUURMusFUURFFUURFFUURFFUURFUURFFUURFFUURFFUURFFUURMusFUURMusFUURUs-2FUURMusFUURMusFUURMusFUURMusFUURMusFUURMusFUURMusFUURMusFUURFFUURCCCFCCCC-3CCCC-3CCCC-3CCCC-3CCCC-3MwssMusMwssMusMwssMusMwssMusCCCMusCCCMusCCCMusCCCMusCCCMusCCCMusCCCCCCC-3CCCC-3CCCC-3CCCC-3CCCC-3CCCC-3PBest5PWorst5Leximax5FUURUs-2112AR-RL5Us-2FUURMwssMds, MusMdsCCCMdsCCCMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusFUURUs-2Mds,MusMdsAR-RA5100Mds, MusMds, MusMdsMMM,FUURFMMM,FUURFMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusMds, MusMusAR-Lmax5,AR-DC-RA5,AR-DC-RL55678910111213141516171819202122232425293039404950596069чнчMMM,FUURUs-2MMM,FUURUs-2AR-Lmin5,AR-IC-RA5,AR-IC-RL534Leximin5АгентыТаблица 4.13 – Минимально манипулируемые правила согласно индексуНитцана-Келли для 5-и альтернатив и третьей группы правилFUURUs-2MwssFUURMusFUURMusFUURMusFUURMusFUURMusFUURMusFUURMusFUURMusFUURMusFUURFFUURCCCFCCCFCCCC-3CCCC-3CCCC-3CCCC-3MwssUs-2Us-2MwssUs-2MwssMusMwssMusCCCMusCCCMusCCCMusCCCMusCCCMusCCCMusCCCCCCC-3CCCC-3CCCC-3CCCC-3CCCC-3CCCC-3Примечание: CCC – группа правил Коупленда; C-3 – правило Коупленда 3; F –правило Фишбурна; FUUR – группа правил: Фишбурна, Непокрытого множества 1 и2, Ричелсона; Mds – Минимальное доминирующее множество; Mus – Минимальноенедоминируемое множество; Mwss – Минимальное слабоустойчивое множествоMMF – группа правил: Минимальное доминирующее множество, Минимальноенедоминируемое множество, Минимальное слабоустойчивое множество, правилоФишбурна; MMM – группа правил: Минимальное недоминируемое множество,Минимальное слабоустойчивое множество; Us-2 – Непокрытое множество 2Таким образом, среди мажоритарных правил сложно выделитьтакие, которые превосходят остальные в большинстве случаев.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
