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

Согласно правилам штата, вэтом случае каждый из участников выбирает игру, затем подкидываниеммонетки решается, в какую из выбранных участниками игр будут игратькандидаты. В той ситуации один из участников выбрал покер, а другой –игру в кости. Подкидывание монетки указало на покер, а победивший внего игрок (который, кстати, и загадал эту игру) и стал мэром данногогорода.Бросание жребия – это один из распространенных методовразрешениямножественноговыбора,однакотакже сложныйвиспользовании, так как неопределенность итогового выбора порождаетиспользование дополнительных предпосылок о поведении участникаголосования в условиях неопределенности. Так называемое случайноеправило устранения несравнимости рассматривалось Притчардом иУилсоном [90] и подробнее будет описано в следующей главе.Таким образом, можно выделить два описанных выше критерия,по которым отличаются работы в данной области:1) Модель взаимозависимости предпочтений участников;2) Отношение к множественному выбору.Также можно разделить работы по анализируемым правилам иметодамоценкиправиламманипулируемости.достаточномногоЕслиотличий,топорассматриваемымизметодовоценкиманипулируемости почти всеми исследователями используется долявсех манипулируемых профилей, предложенная, как уже было сказановыше,Нитцаном.Использованиеодинаковоймерыпозволяетсравнивать результаты разных работ.

Другие интересные меры иподходы также предложены в работах [18, 19, 20, 21, 35, 98, 100].Основныеработыпооценкеманипулируемостиклассифицированы в Таблице 2.5The New York Times, March 08, 1998 http://www.nytimes.com/1998/03/08/us/nationalnews-briefs-a-coin-then-cards-and-finally-a-mayor.html27Таблица2-Классификацияработпооценкестепениманипулируемости.СтатьяВероятностнаяОтношение кмодельмножественномуРассматриваемые правилавыборуЧемберлен,IC1985 [38]Алфавитное правилоБорда, Кумбс, Хара, Отн.устранениябольшинствонесравнимостиНитцан,IC1985 [80]Алфавитное правилоОтн.

большинство, Борда,устраненияПроизвольная балльнаянесравнимости + голоссхемапредседателяКелли, 1993 ICАлфавитное правилоПроизвольная балльная[65]устранениясхеманесравнимостиАлескеров,Алфавитное правило26 различных правилКурбанов,устраненияпринятия решений1999 [21]несравнимостиICЛеппелье,IC, IAC,Алфавитное правило8 правил: отн.Валонь,модель Пойа-устранениябольшинство, Хара,2003 [69]ЕггенбергеранесравнимостиБорда, обратное отн.большинство, Кумбс и др.Фавардин,IACАлфавитное правилоЛепелье,устранения2006 [48]несравнимостиПричард,IC, IACСлучайное правилоУилсон,устранения2007 [90]несравнимости10 правил8 правилЗа пределами данной классификации осталась часть работ,посвященная коалиционному манипулированию [см. например, 39, 47,48, 90, 93]. Заметим, что это более широкий поход, который ведет кувеличениюзначениймерманипулируемости28правилпринятиярешений, так как индивидуальное манипулирование является частнымслучаем коалиционного при размере коалиции равном 1.

Иначе говоря,еслиправилоиндивидуальноманипулируемо,тооноявляетсякоалиционно манипулируемым. Как известно из упомянутых вышерезультатов,практическивсеправилаявляютсяиндивидуальноманипулируемыми, то есть существуют такие профили, в которыхучастникам голосования выгодно искажать свои предпочтения. Этипрофили заведомо манипулируемы, однако другие профили, которые неявляютсяиндивидуальноманипулируемыми,могутбытьманипулируемы, если мы разрешим участникам вступать в коалиции иодновременно менять свои предпочтения.Важнымманипулированиямоментомявляетсяприрассмотрениимеханизмкоалиционногоформированиякоалиций.Фавардин и Леппелье [48], в частности, использовали два подхода:объединяться в коалиции могут только участники с одинаковымипредпочтениями и объединяться могут любые участники.

Очевиднымрезультатом является то, что чем меньше ограничений мы вводим на видкоалиции и чем больше мы устанавливаем максимальный размеркоалиции, тем выше степень манипулируемости.Подводя итог главы, очертим ту нишу, которую занимает данноеисследование. В диссертации рассматривается случай индивидуальногоманипулирования в предпосылках равной вероятности профилей (IC) имножественного выбора. Исследование проводится для 22-х правил.29Глава 2. Методы построения предпочтений намножествах альтернативДанная глава имеет следующую структуру. В первом разделе данобзор основных слабых аксиом расширения предпочтений.

Во второмразделе описаны имеющиеся в литературе сильные методы расширенияпредпочтений, а также предложены новые сильные методы. В третьемразделе изучены их свойства. В итоговом разделе описано, какие методырасширения будут использоваться при анализе манипулируемости вусловиях множественного выбора.Врамкахдиссертациибудутиспользоватьсяследующиеобозначения, основанные на работах [1, 18, 19, 20, 21]. Имеетсямножество A , состоящее из m альтернатив (m  2) . Множество всехнепустых подмножеств множества A мы будем обозначать A  2 A \  .Каждый участник i из конечного множества N  1,..., n, (n  1) , имеетпредпочтение Pi на множестве альтернатив из A и расширенноепредпочтение EPi на множестве A .

Предполагается, что предпочтение Piявляется линейным порядком, то есть удовлетворяет следующимусловиям:антирефлексивности ( x  A , x Px );транзитивности ( x, y, z  A xPy и yPz  xPz );связности ( x, y  A x  y либо xPy , либо yPx ).Вектор P , состоящий из предпочтений n участников, называетсяпрофилем. Коллективный выбор формируется с помощью функцииколлективного выбора в соответствии с профилем P и являетсяэлементом множества A .

Обозначим множество всех линейныхпорядков на A как L . Таким образом, функцию коллективного выбораможно представить как отображение C : Ln  A .30Также в главе будут использоваться в качестве примералексикографические предпочтения, под которыми будут пониматьсяпредпочтения Pi вида x1 Pi x 2 Pi x3 Pi  Pi x n или aPi bPi cPi  Pi z. Предпочтениянамножествахальтернативбудутназыватьсярасширеннымипредпочтениями. Глава построена на статье Карабекяна [5].2.1 Слабые аксиомы расширения предпочтенийВ этой части исследования будут сформулированы основныепредпосылки, описывающие, как взаимосвязаны предпочтения намножестве альтернатив с расширенными предпочтениями на множествеколлективных выборов.

Первое условие основано на работе [24].Условие 1. ПустьC ( P)  xP, P  Ln ,еслиC ( P)   y,тогдаиi  N.ПустьC ( P)  x, y,C ( P) EPi C ( P);еслиxPi yтогдаC ( P)  xидля каких-либоC ( P) EPi C ( P);C ( P)   y,x, y  A.еслитогдадля каких-либоx, y  A.ТогдаP, P  Ln ,C ( P)  x, yиC ( P) EPi C ( P).Это условие можно свести к более простому виду. ПустьxPi yТогдаi  N.ПустьxEPi x, yEPi  y и xEPi  y.Данное предположение вполне логично, так как переход, например, отx, y к x не ухудшит положение индивида. При этом в наборе x, yсуществует такой результатy,который в случае выбора ухудшитположение индивида по сравнению с x.

Аналогично можно описать иоставшиеся отношения.Следующее условие было представлено в работе Келли [63] иизвестно как аксиома доминирования.Аксиома доминирования Келлиi  NиP, P  Ln ,если ( x  C (P) иy  C ( P)  xPi y ), тогда C ( P) EPi C ( P).Если все элементы первого коллективного выбора строгопредпочитаются всем элементам второго, то и сам первый коллективныйвыбор будет предпочитаться второму. Нет сомнений в том, что данное31условие должно быть выполнено, если мы сравниваем множестваальтернатив.Условие 2.i  NиеслиP, P  Ln , x  C ( P) иy  C ( P)  xPi y или x  y и z  C ( P), что y  C ( P)  zP y или z  C ( P), что x  C ( P)  xP ziiтогда,C ( P) EPi C ( P).Данное условие было представлено в [84].

Используя аксиомудоминирования Келли, условие 2 можно представить в более простомвиде.Условие 2' (сильная версия аксиомы Келли).x  C(P) иy  C(P) тогдаi  NиP, P  Ln , еслиxPi y или x  y и z  C ( P) и w  C ( P)  zPi wC ( P) EPiC ( P) .Как видно из определений, из выполнения условия 2 следуетвыполнение условия 1.

Стоит заметить, что данная предпосылка позволяетсравнивать общественные выборы, имеющие не более одного пересеченияв терминах упорядоченных наборов, так как у нас рассматриваютсястрогие предпочтения. Например, для лексикографических предпочтенийэто условие позволяет сделать вывод, что x1, x6 EPi x6 , x9 , но не позволяетсравнить множества x1 , x6 , x7  и x6 , x7 , x9 .Условие 3.i  NиеслиP, P  Ln ,C ( P)  C ( P)x  C(P)  C(P) и y  C(P)  xP y или x  yи z  C( P)  C( P), что y  C( P)  zP y  , то C( P) EP C(P).и еслиiiiУсловие 4.i  NиеслиP, P  Ln ,C ( P)  C ( P)и еслиx  C(P) и y  C(P)  C(P) xP y или x  yи z  C(P)  C(P), что x  C(P)  xP z , то C( P) EP C(P).iiiПоследние два условия позволяют сравнивать наборы следующеговида: x1, x6 , x7 EPi x6 , x7  (по условию 3) и x6 , x7 EPi x6 , x7 , x9  (по условию 4). Вслучае, когда расширенные предпочтения удовлетворяют условию32транзитивности,можносравнитьx1, x6 , x7 EPi x6 , x7 , x9 ,наборыт.е.множества, содержащие в пересечении более чем одну альтернативу.Таким образом, условия 3 и 4 при наличии транзитивности являютсяболее сильными по сравнению с условиями 1 и 2.

Сформулируем лемму.Лемма 1. Из выполнения условия 2 следует выполнение условия 1 иаксиомы доминирования Келли. Из выполнения условий 3 и 4, а такжеусловиятранзитивностирасширенныхпредпочтенийследуетвыполнение условия 2. То есть:условия 3 и 4  транзитивность EPi  условие 2  условие 1 и аксиома Келли .Доказательство леммы следует из определения самих условий,поэтому будет опущено.Следующее условие было представлено в разных видах в работах[62, 92] как аксиома монотонности.Аксиома монотонности.i  N , P  Lnиx, y  A \ C ( P)C(P)  x EP C(P)  y, если и только если xP y.iiДругими словами, если два коллективных выбора отличаютсятолько одной альтернативой, то тот набор, который содержит болеепредпочитаемую альтернативу, должен быть более предпочтительным всмысле расширенных предпочтений.Принцип Гэрденфорса.i  N , P  Lnиy  A \ C ( P)C(P) EP C(P)  y, когда x  C(P) выполнено xP y;2.

C( P)  y EP C( P), когда x  C (P) выполнено yP x.1.iiiiМожно заметить, что первая часть этого определения являетсячастным случаем условия 3, а вторая часть – частным случаем условия4. Данный принцип, впервые сформулированный в работе [50], известенкак принцип Гэрденфорса. Его можно проинтерпретировать следующимобразом. Если мы добавляем к некоторому набору альтернативу, котораяболее (менее) предпочтительна, чем все альтернативы в изначальном33наборе, то итоговый набор должен быть более (менее) предпочтительнымв смысле расширенных предпочтений.Опишем еще одну, более сильную аксиому: метод ожидаемойполезности с предположением о равной вероятности альтернатив(EUCEPA): EUCEPA : i  N , P, P'  Ln , U () : U ( x)  U ( y)  x  yC ( P) EPi C ( P' ) xC ( P )U x  >C ( P)yC ( P' )U yC ( P' )Данный метод под разными названиями использовался в работах[27, 37, 49].Это условие позволяет сравнить наборы, которые неподдаются сравнению предыдущими методами, например, x1 , x6  иx 2 , x7 .