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

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

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

После этого останется только одна альтернатива, котораяи будет выбрана.В-третьих, стоит отметить, что на Рис. 4.12 и 4.13 мерыманипулируемости для процедуры исключения Борда и правилаНэнсона почти неотличимы – различие становится видно лишь длябольшого числа агентов. В то же время процедура Нэнсона являетсяменее манипулируемой при сопоставлении значений индекса НитцанаКелли. Наименее манипулируемые правила, с точки зрения данногоиндекса, представлены в Табл.

4.8. Для удобства в Табл. 4.8 процедураХара выделена полужирным.Рассмотрим подробнее полученные результаты. Во-первых, стоитзаметить, что в "консервативных" методах: Leximin3 и PWorst3наилучшим образом проявили себя правила Нэнсона и исключенияБорда. Их тоже можно отнести к разряду "консервативных", так как впервую очередь выкидываются те альтернативы, которые имеютнаименьший ранг Борда, т.е. в среднем стоят низко в предпочтениях умногих агентов.

В то же время, процедура Хара «смотрит» в первуюочередь на лучшие альтернативы, что показывает её больший успех для"неконсервативных" методов. Процедура Кумбса, которая смешивает всебе"консервативные"практическинивиодном"неконсервативные"изслучаевманипулируемой.92нехарактеристики,являетсянаименееPWorst3PBest3АгентыLeximin3Leximax3PWorst3PBest3456789101112131415161718Bl,IB, NBl,IB, NIB, NHIB, NHIB, NNNHNHNNNNLeximax33Leximin3АгентыТаблица 4.8 – Минимально манипулируемые правила согласноиндексу Нитцана-Келли для 3-х альтернатив и второй группы правилPl, HBl, IB,N, CHBlHHHBlHBlHHHNHNBl, IB,NBl, IB,N, CIB, N2-A, APIB, NHIB, NNNNNHNNNNPl, HBl,IB, NHHHHHBlHHHHHNHH19202122232425293039404950596069~100NHNNNNNNNNNNNNNN~NHHHNHNHHNNNNHHNN~NNHNNNNNNNNNNNNNN~NHHHNHHHHHNNNHHHN~NПримечание: 2-A – Одобряющее голосование q=2; Bl – Правило Блэка; C –Процедура Кумбса; IB – Правило исключения Борда; AP - Обратное правилоотносительного большинства; H – Процедура Хара; N – Процедура Нэнсона; Pl –Правило относительного большинстваВо-вторых, отметим совпадение мер манипулируемости длямалого количества агентов.

Наиболее интересно, как уже говорилосьвыше, совпадение значений индексов для процедуры исключения Бордаи правила Нэнсона. Если агентов не больше 9 (за исключением 8), тоони совпадают, однако для большего числа начинаются отличия, причемпроцедура Нэнсона менее манипулируема. Стоит отметить, что длячетного числа агентов разница в значениях значима, начиная с 8-миагентов, в то время как для нечетного числа агентов различие становитсязначимым на 95%, начиная с 25 агентов включительно.93В-третьих, отметим, что процедура Блэка, которая была наименееманипулируемой среди первой группы правил, в большинстве случаевне является таковой среди всех рассматриваемых порядковых правил.Рассмотрим результаты для порядковых правил в случае 4-хальтернатив. В этом случае среди 10 методов можно выделить 8различных ситуаций.

Несмотря на отличия, из этих ситуаций можновыделить 3 принципиально отличающихся с точки зрения результатовметодов, которые представлены на Рис. 4.14 - 4.16.Рисунок 4.14. Индекс Нитцана-Келли для расширения Leximax494Рисунок 4.15. Индекс Нитцана-Келли для расширения PWorst4Рисунок 4.16. Индекс Нитцана-Келли для расширения AR-RA495Во-первых, отметим, что, несмотря на увеличение количестваальтернатив, период в изменении индекса Нитцана-Келли для процедурХара и Кумбса остался равен шести.

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

Однакотаких альтернатив может быть несколько, поэтому множественныйвыбор возникает также и на стадии выбрасывания альтернатив.Возможно, именно это влияет на длину периода.Во-вторых, заметим, что индексы для процедуры Хара и правилаотносительного большинства совпадают для 3-х и 4-х агентов.Рассуждения остаются верными для трех агентов: объяснение остаетсянеизменным и применяется для любого подмножества из трехальтернатив. Рассмотрим случай 4-х агентов и 4-х альтернатив.

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

Помимо неёкакие-то две другие альтернативы имеют по одному голосу, и одна –ноль голосов. Согласно процедуре Хара, сначала будет исключенаальтернатива с нулем голосов, таким образом, задача будет сведена кслучаю трех альтернатив, где, как уже было показано, правила даютодинаковый результат. Для профилей последнего типа для обоих правилрезультатом голосования будет все множество альтернатив.В-третьих,рассмотримсоотношениемеждуоценкамиманипулируемости для процедур Нэнсона и исключения Борда. На Рис.4.14 и 4.16 заметно, что манипулируемость правила Нэнсона меньше,чем правила исключения Борда.

Однако на Рис. 4.15 видно, что правилоисключения Борда дает меньшую манипулируемость для нечетногочисла агентов. Несмотря на то что правила очень похожи, ввидуразличного механизма исключения альтернатив доля множественноговыбора отличается. Например, для 13 агентов для правила исключенияБорда множественный выбор проявляется в 31,7% случаев, а дляправила Нэнсона в 20,9%. Так как для методов PWorst4 и Leximin4 припрочих равных условиях большие наборы предпочитаются меньшим, уучастниковпримножественномвыбоременьшестимуловманипулировать. Обобщим всю информацию в Табл.

4.9.В Табл. 4.9 заметно чередование процедур Нэнсона и исключенияБорда для четного и нечетного числа агентов для методов PWorst4 иLeximin4. Дело в том, что в случае четного и нечетного числа агентов уданных правил отличаются доли множественного выбора. Если, как ужебыло сказано выше, при нечетном числе участников правило Нэнсонадает значительно меньшую долю множественного выбора, то длячетного числа эти доли практически совпадают. Например, для 16агентов доля множественного выбора для правила Нэнсона равна 28,4%,а для правила исключения Борда равна 28,9%.9798AR-Lmax4,AR-DC-RA4AR-RA4AR-RL43IB, N Pl, H IB, NPl, H4 3-A, AP Pl, H 3-A, AP Bl, IB, N5IBIBHH6BlBlHH7IBIBHH8HHHH9IBIBHH10NNNN11IBIBHH12NNHH13IBIBHH14HHHH15IBIBHH16NNNN17IBIBHH18NNNH19IBIBHH20NNHH21IBNIBN22NNNN23IBIBHH24NNNH25IBNIBN29IBNIBN30NNNH39IBNIBN40NNNN49IBNIBN50NNNN59IBNIBN60NNNN69NNNN70NNNN79IBNIBN80NNNN~~~~~100NNNNAR-Lmin4,AR-IC-RL4PBest4PWorst4Leximax4Leximin4АгентыТаблица 4.9 – Минимально манипулируемые правила согласно индексуНитцана-Келли для 4-х альтернатив и второй группы правилN2-AHHNHNNHNNHNNNNNNNNNNNNNNNNNNNNNNN~NPl, H2-AHBlHHNNHNHHNNHNHNNNHNNNNNNNNNNNNNN~NN2-AHBlNHNNHNNHNNNNNNNNNNNNNNNNNNNNNNN~NPl, H2-AHHHHNNHNHHNNHNHHNNHNNNNNNNNNNNNNN~NПримечание: 2-A – Одобряющее голосование q=2; 3-A – Одобряющее голосованиеq=3; Bl – Правило Блэка; C – Процедура Кумбса; IB – Правило исключения Борда;AP - Обратное правило относительного большинства; H – Процедура Хара; N –Процедура Нэнсона; Pl – Правило относительного большинстваМожно утверждать, что правило Нэнсона менее манипулируемо припрочих равных условиях.

Правило исключения Борда может превзойтиего только для определенных методов и благодаря более низкойразрешимости (доле множественного выбора). Однако видно, чтоначинаяс89участниковманипулируемостьправилаНэнсонастановится ниже для PWorst4 и Leximin4. Это связано с тем, что вабсолютном выражении доля множественного выбора становится оченьмалой. Например, для 69 агентов для процедуры Нэнсона эта долясоставляет 0,4% , а для правила исключения Борда 0,65%.Рассмотрим значимость результатов.

Как показывает расчетдоверительных интервалов, гипотеза о равенстве значений индексовНитцана-Келли для правил Нэнсона и исключения Борда не отвергаетсядля случаев 59, 69, 79, 89 агентов и методов PWorst4 и Leximin4. Во всехостальных случаях результаты значимы.Проверим, сохранится ли такое соотношение между правиламидля случая пяти альтернатив. В этом случае из 12 возможных методовимеется8отличающихсямеждусобойсоставомнаименееманипулируемых правил. Покажем результаты для трех наиболееотличающихся друг от друга методов.Из Рис. 4.17-4.19 видно, что подтверждаются наблюдения дляслучая 3-х и 4-х альтернатив, в частности, относительно совпаденияиндексов для правила относительного большинства и правила Хара(обоснование совпадает со случаем 4-х альтернатив). Также длинапериода для правил Хара и Кумбса остается равной 6.99Рисунок 4.17.

Индекс Нитцана-Келли для расширения Leximax5Рисунок 4.18. Индекс Нитцана-Келли для расширения PWorst5100Рисунок 4.19. Индекс Нитцана-Келли для расширения AR-RA5Стоит отметить, что здесь для случая PWorst5 практически незаметны отличия в значениях индекса для правила Нэнсона иисключенияБорда.Действительно,какпоказываетрасчетдоверительных интервалов, гипотеза о равенстве значений индексовНитцана-Келли для правил Нэнсона и исключения Борда не отвергаетсядля любого нечетного числа агентов от 9 до 69 и методов PWorst5 иLeximin5. Во всех остальных случаях результаты значимы. Агрегируемимеющиеся данные в Табл. 4.10.Таким образом, стоит отметить, что наименее манипулируемымиправилами среди порядковых являются в большинстве случаевпроцедуры Нэнсона, Хара и исключения Борда.