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

Начиная с определенногоm,появляютсямножества, не поддающиеся сравнению. Например, для пункта 2 приm4появляются несравнимые для данного дополнения множества  a, d  иb, c . Для рискофил/рискофоб-дополнений несравнимы наборы  a, e, f  иb, c, g приm  7.Нетрудно показать, что если принесравнимые наборы, то и приm  m 1mmпоявляютсяэти наборы также будутнесравнимы. Таким образом, лемма доказана.Стоит упомянуть, что часть алгоритмов расширения предпочтенийпри малом числе альтернатив дают одинаковые результаты. Вчастности, для 3, 4 и 5 альтернатив можно построить 4, 10 и 12 способоврасширения предпочтений, соответственно. Однако количество способов46при большем числе альтернатив неизвестно. Основываясь на результатахлеммы 4, можно лишь утверждать, что при достаточно большихmдляодних и тех же обычных предпочтений может быть построено не более56различныхрасширенныхпредпочтенийвсоответствииспредложенными нами методами.

Более подробную информацию овозможных совпадениях способов можно получить только путемпоследовательного применения всех алгоритмов для разныхm.2.4. Значение расширенных предпочтенийПокажем на примере, как может влиять выбранный методрасширения предпочтений на результат оценки манипулируемости схемголосования. Рассмотрим случай, когда имеется пять участниковголосования и четыре альтернативы. Пусть предпочтения являютсялинейными порядками и выглядят следующим образом:P1acP2bcP3dbP4acP5bddbadacdbca.Пусть выбор производится в соответствии с правилом Борда(каждой альтернативе присваивается ранг в соответствии с её местом впредпочтениях участника: чем выше, тем лучше. Ранги суммируются повсем участникам для каждой альтернативы, и лучшей альтернативойпризнается та, которая набрала наибольший суммарный ранг), тогдарезультатомголосованиябудетнабор  a,b.

Рассмотримпятогоучастника голосования. Указанные альтернативы стоят в его обычныхпредпочтениях на четвертом и первом местах, соответственно. То естьдля пятого участника этот выбор мы можем представить в виде  x1 , x4 ,что говорит о наличии в итоговом выборе альтернатив, стоящих насоответствующих местах. Заметим, что пятый участник может исказитьпредпочтения, например, поменяв альтернативы47dиcместами. В этомслучае коллективный выбор примет вид набора  a, b, c или, с точкизрения упорядоченных искренних предпочтений манипулирующегоучастника,  x1 , x3 , x4 . Будет ли в данном случае происходить именно такоеманипулирование, зависит от того, как предпочитаются наборы  x1 , x3 , x4  и x1 , x4  .

В разных расширенных предпочтениях их отношение различно.Например, в случае предпочтений по принципу лексимакс и повозрастаниювероятностинаихудшейальтернативыимеетместо x1, x3 , x4 EPi  x1, x4  , что говорит о том, что пятому участнику будет выгодноисказить предпочтения указанным выше способом. При всех остальныхметодах такое искажение невыгодно.Все предложенные выше способы построения предпочтений намножествах альтернатив можно условно разделить на два вида: слабые исильные аксиомы. Среди слабых аксиом решено рассматривать три:Сильную аксиому доминирования Келли, принцип Гэрденфорса иEUCEPA.

Согласно Лемме 2 каждая последующая аксиома сильнеепредыдущей.Рисунок 2.1. Граф расширенных предпочтений для слабыхметодов.48Для трех альтернатив и лексикографических предпочтений графрасширенных предпочтений для слабых аксиом представлен на Рис. 2.1.Сплошными стрелками представлены связи, описываемые аксиомойКелли.

Пунктирные стрелки показывают связи, которые добавляются,если используется Принцип Гэрденфорса, а точечные – если EUCEPA.Заметим, что наборы  a, b, c,  a, c и  b несравнимы в условиях слабыхаксиом.Сильные аксиомы по определению позволяют упорядочить всевозможные наборы альтернатив.

Все сильные методы, описанные в этойглаве,рассматриваютсяприизучениимножественном выборе.49манипулированияприГлава 3. Формулировка моделиГлава с формулировкой модели имеет следующую структуру. Сначаладано формальное определение манипулирования, которое опирается напонятие расширенных предпочтений, введенное в предыдущей главе.Затемданыопределенияправил,манипулируемостькоторыхисследуется в данной работе. В последнем разделе описаны индексыстепени и эффективности манипулирования, а также методика ихрасчета.3.1. Определение манипулированияДадим определение манипулирования для случая множественноговыбора.

ПустьP  P1 ,, Pi ,, Pn является профилем истинных предпочтений участников, тогда какPi  P1 ,, Pi 1 , Pi  , Pi 1 ,, Pnбудет профилем, в котором все участники, кроме i -го, заявляют своиистинные предпочтения. Обозначим сформированные выборы для этихпрофилей P и Pi через C (P) и C ( Pi ) , соответственно. Будем говорить,что имеет место манипулирование, если для i -го участника выполняетсяC ( Pi ) EPi C ( P) , где EPi – это расширенные предпочтения участника i .Другими словами, предполагается, что коллективный выбор в условияхискаженных предпочтений лучше с точки зрения участника i , чем выборпри истинных предпочтениях.Вкачестверасширенныхпредпочтенийберутсяметоды,описанные в главе 2.

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

За основу взяты правила, рассматриваемые в [21].3.2. Правила коллективного принятия решенийВ данном разделе будут описаны правила коллективногопринятия решений, и для удобства сопоставления, все они будутприменены к следующему профилю предпочтений.Таблица 3.1. – Профиль предпочтенийАгент 1Агент 2Агент 3Агент 4Агент 5Агент 6aaaddbbdcbbcccdccddbbaaa3.2.1 Позиционные (порядковые) правила1. Правило относительного большинстваВ выбор входят альтернативы, которые являются лучшими длянаибольшего числа участников голосования, т.е.:a  C ( P)  [x  A n  (a, P)  n  ( x, P)],где n  (a, P) = card{i  N | y  A aPi y} .Для примера в таблице 3.1 за альтернативу "a" подано 3 голоса, заальтернативу "d" – 2 голоса, за альтернативу "b" – 1 голос, заальтернативу "с" – 0 голосов.

Альтернатива "a" получает относительнобольшее число голосов, поэтому будет единственным выбором:C ( P)  a2. Одобряющее голосованиеВведемn  (a, P, q) = card{i  N | card{Di (a)}  q  1},51т.е., n  (a, P, q) означает число участников, у которых альтернатива aстоит не ниже q -го места в их предпочтениях. Таким образом, если q = 1 ,тогда a – это лучшая альтенатива для участника i ; если q = 2 , тогда a –либо первая, либо вторая наилучшая альтенативы, и.т.д. Число q будемназывать уровнем процедуры.Одобряющее голосование уровня q определяется следующимобразом:a  C ( P)  [x  A n  (a, P, q)  n  ( x, P, q)] ,т.е., выбираются альтернативы, которые находятся среди q лучших длямаксимального числа участников голосования.Очевидно, что одобряющее голосование – это обобщениеправила относительного большинства (случай q = 1 ).Применим правило одобряющего голосования для q=2 дляпрофиля из таблицы 3.1.

За альтернативу "a" подано 3 голоса, заальтернативу "b" - 4 голоса, за альтернативу "c" - 2 голоса, заальтернативу "d" - 3 голоса. Таким образом, у альтернативы "b" имеетсяотносительное большинство, и она является итоговым выбором:C ( P)  b.Стоит отметить, что данное правило является частным случаемболее общего правила одобряющего голосования, при которомучастнику голосования разрешается выбрать не более q альтернатив, закоторые он хочет проголосовать [см. например, 33].3. Обратное правило относительного большинства.В выбор входят альтернативы, которые считает худшиминаименьшее число агентов, т.е.:a  C ( P)  [x  A n  (a, P)  n  ( x, P)],где n  (a, P) = card{i  N | y  A yPi a} .52Заметим, что обратное правило относительного большинствадает такой же результат как одобряющее голосование при q  m  1 , таккак голосование "за" все альтернативы кроме одной, равносильноголосованию "против" одной альтернативы.Для рассматриемого примера в таблице 3.1.

против альтернативы"a" подано 3 голоса, против альтернативы "b" – 2 голоса, противальтернативы "с" – 0 голосов, против альтернативы "d" – 1 голос. Такимобразом, против альтернативы "c" подано наименьшее число голосов,поэтому она будет являться итоговым выбором: C ( P)  c .4. Пороговое правило [3, 4]Пусть v1 ( x) –число участников, для которых альтернатива xявляется наихудшей в их предпочтениях, v2 ( x) – число участников, длякоторых альтернатива x является второй наихудшей, и так далее, vm (x) –число участников, для которых альтернатива x является наилучшей.Затем альтернативы упорядочиваются лексикографически.

Говорят, чтоальтернатива x V-доминирует альтернативу y , если v1 ( x) < v1 ( y) или еслисуществует k  m такое, что vi ( x) = vi ( y) , i = 1,..., k 1 , и vk ( x) < vk ( y) .Другимисловами, впервуюочередьсравниваютсяколичествапоследних мест в упорядочениях для каждой альтернативы; в случае,когда они равны, идет сравнение количества предпоследних мест и такдалее.