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

О возможности ослабления этой предпосылки говорил иГиббард в своей основополагающей работе 1973-го года [52]. Онпонимал под этим введение дополнительного условия устранениянесравнимости, которое наиболее естественным он видел в случайномвыборе альтернативы в случае множественного выбора. Это привело егок предпочтениям на лотереях и работам, описанным в последней частипредыдущего раздела. Эта идея была развита Барбера [24]. Используяусловия монотонности (позитивного отклика 2 ) и единогласия 3 , онпоказал, что как минимум для четырех альтернатив не существуетнедиктаторского неманипулируемого правила, удовлетворяющего этимпредпосылкам. Стоит отметить, что для случая трех альтернатив этоправило существует.Другие работы в этой области использовали разные понятияманипулируемости.

Чинг и Чжоу [40] считали, что манипулированиебудет происходить, если существуют любые две лотереи, при которыхнабор при неискренних предпочтениях лучше, с точки зренияожидаемой полезности, чем набор при искренних. В этих условиях они2Если альтернатива a была выбрана среди других альтернатив, а потом еёположение в профиле улучшилось, при этом относительное положение остальныхвыбранных альтернатив не изменилось, то альтернатива a должна статьединственной выбранной альтернативой.3Если альтернатива предпочитается всем остальным для каждого участника, то этаальтернатива должна присутствовать в итоговом выборе20доказали теорему, что любое недиктаторское правило принятия решенийявляется манипулируемым для случая трех альтернатив и более.

Стоитотметить, что они рассматривали только правила, удовлетворяющиеаксиоме единогласия, так как в рамках их концепции манипулируемостинеединогласные правила заведомо являются манипулируемыми.Большим вкладом в исследование неманипулируемости вусловиях множественного выбора является работа Дуггана и Шварца[43]. В отличие от Чинга и Чжоу они считают, что манипулированиебудет происходить, если для любых пар лотерей набор при неискреннихпредпочтениях лучше, чем набор при искренних. Добавляя условиеостаточной разрешимости, они показали, что любое недиктаторскоеправило принятия решений является манипулируемым для случая трехальтернатив и более. Остаточная разрешимость предполагает, что если увсех, кроме одного, альтернатива a стоит на первом месте, аальтернатива b на втором, а у оставшегося участника либо такая жеситуация, либо, наоборот, b стоит на первом месте, то итоговый выбордолжен состоять из одной альтернативы [см.

также 91, 95].Другое направление исследований было предложено Келли [64] –рассматривать процедуры, которые имеют в основе не предпочтения наальтернативах, а предпочтения на множествах альтернатив. Эта идеябыла развита Бенуа [29]. Он показал, что как минимум для трехальтернатив и некоторых требований на расширенные предпочтения несуществует почти единогласного неманипулируемого правила принятиярешений.

Понятие почти единогласного правила очень похоже наусловие остаточной разрешимости Дуггана и Шварца и заключается втом, что если все участники голосования, кроме одного, предпочитаютнекоторую альтернативу всем остальным, то эта альтернатива должнабыть единственным выбором (то есть в данном случае не может бытьмножественного выбора).21В рамках этого направления можно также выделить работуБарбера и др. [27], которая также предполагает, что функцииколлективного выбора могут строиться на основе предпочтений намножествах альтернатив. Авторы показывают, что, в зависимости отусловий,единственнойнеманипулируемойпроцедуройявляетсядиктаторская или бидиктаторская 4 процедура.

Основным отличием отработы Бенуа является то, что здесь предпочтения представимыфункцией ожидаемой полезности, тем самым исключается класслексикографических предпочтений на множествах альтернатив.Какбудет показано ниже, данные предпочтения широко используются прианализе степени манипулируемости известных процедур.1.3. Оценка манипулируемостиОтрицательный результат теоремы Гиббарда-Саттертуэйта, атакже спектра работ, описанных выше, породил вопрос об оценкеманипулируемости существующих схем принятия решений.

Впервыеданный вопрос был поднят Чемберленом [38] и Нитцаном [80]. Вкаждой работе рассматривалась определенная группа правил, которыесравнивались с точки зрения их манипулируемости. Важным вопросомстановилось понятие меры манипулируемости, наиболее естественная изкоторых – доля всех манипулируемых профилей – была предложенаНитцаном.Когда рассматривается вопрос поиска неманипулируемых правилпринятиярешений,неподверженоважно,чтобынайденноеправиловыгодному искажению предпочтений длябылолюбогопрофиля (любой комбинации предпочтений участников).

ТеоремаГиббарда-Саттертуэйта и работы, следующие за ней, фактическипоказали, что обязательно существуют профили, где возможно4Бидиктаторской называется процедура, при которой итоговый выбор являетсяобъединением лучших альтернатив двух агентов-диктаторов.22манипулирование. Если мы хотим понять, насколько манипулируемоправило, важно ответить на вопрос – какова вероятность появленияманипулируемого профиля. Очевидно, что ответ на этот вопрос зависитот взаимозависимости предпочтений.

Существуют три основныхпредположения:1) о независимости индивидуальных предпочтений участников(Impartial Culture),2) о произвольном распределении вероятности итоговых профилейпредпочтений [см. например, 12],3)оравнойвероятностианонимныхпрофилей(ImpartialAnonymous Culture).Фактически 1-й и 3-й подходы являются частным случаем второго,описываемогоспомощьюмоделиПойа-Еггенбергера[45].Действительно, задачу создания профиля предпочтений можно свести кизвестной в теории вероятности задаче вытаскивания шаров из урны.

Вданном случае в виде шаров выступают предпочтения, и намнеобходимо достать количество шаров, равное n (количество участниковголосования), возвращая каждый раз шар в урну. Модель ПойаЕггенбергера подразумевает, что каждый раз, когда мы кладем шаробратно в урну, мы добавляем в эту урну еще  шаров такого же цвета.Очевидно, что чем больше  , тем больше вероятность появленияпрофилей с одинаковыми предпочтениями внутри профиля.

Леппелье иВалонь [69] показывают, что известная схема Impartial Culture естьчастный случай модели Пойа-Еггенбергера при   0 , а ImpartialAnonymous Culture при   1 .Рассмотрим отличия моделей на примере. Пусть имеются двеальтернативы ( a и b ) и два участника голосования(1 и 2). Тогдавозможны 4 профиля:П1)ababП2)abba23П3)baabП4)babaСогласно подходу Impartial Culture (IC) вероятность того, что улюбого участника голосования будет, например, предпочтение a  b ,равна 1/2, и так как вероятности независимы, то вероятность появлениякаждого профиля равна 1/4.В подходе Impartial Anonymous Culture рассматриваются толькоанонимные профили или, как их называют, ситуации голосования.Иначе говоря, не рассматриваются такие профили, которые можнополучить из других путем переименования участников.

В данномконкретном примере профили П2 и П3 могут быть получены путемперестановки предпочтений участников и отражают одну и ту жеситуацию голосования: одно предпочтение a  b и одно предпочтениеb  a . Все ситуации голосования считаются равновероятными. Такимобразом, вероятность проявления профилей (ситуаций голосования) П1,П2, П4 равны 1/3.В подходе Пойа-Еггенбергера вероятности профилей могутменяться от (1/4, 1/4, 1/4, 1/4), как в случае IC или   0 , до (1/2, 0, 0, 1/2)при  стремящемся к бесконечности.Важно отметить, что сама по себе модель Impartial AnonymousCulture была выдвинута в работе Герляйна и Фишбурна [51].

Главноесвойство, благодаря которому эта модель получила популярность,является то, что в этой модели можно получить точные формулы мерманипулируемости для основных правил принятия решений, тогда какIC и модель Пойа-Еггенбергера этого не позволяют [см. например, 57,99].Заметим, что Герляйн и Фишбурн занимались не оценкойманипулируемости, а смежной темой наличия циклов Кондорсе.

ЦиклКондорсе – это один из классических парадоксов голосования, которыйозначает, что не существует никакой альтернативы, которая побеждаетлюбую другую при попарном сравнении. Классическим примером24является профиль из трех альтернатив и трех участников соследующими предпочтениями:abсbcacabЕсли мы будем попарно выносить на голосование по двеальтернативы, то, согласно мнению большинства, будет наблюдатьсяцикл a  b  с  a . Заметим в то же время, что данная ситуация являетсязаведомо манипулируемой. Например, если мы знаем, что сначала наголосование выносятся альтернативы a и b , а потом с , то участнику 1выгодно на первом шаге исказить свои предпочтения и проголосовать заальтернативу b , чтобы потом гарантировано получить её в итоге. В тоже время, если он будет действовать искренне, то на втором этапеальтернатива с (худшая для него) победит выбранную на первом шагеальтернативуa.Заметим,чтосвязьпарадоксаКондорсеиманипулируемости отчасти отражена в приведенном выше примереКима и Роуша, так как описанное ими множество предпочтений неисключало парадокса Кондорсе.Отметим, что если мы будем рассматривать данный профиль сточкизренияклассическогоконцепцииправиламножественноговыбора и,относительногонапример,большинства,томанипулируемость данного профиля не так очевидна.

Если все триальтернативы будут выноситься на голосование, то итоговым выборомбудет набор, состоящий из всех альтернатив a, b, c, в то время как приманипулировании участник голосования может гарантировано получитьвторую наилучшую альтернативу (например, участник 1, манипулируя,получает b ). Очевидно, что ответ на вопрос – будет ли в данном случаепроисходить манипулирование или нет – зависит от того, какой наборлучше – a, b, c или b – для первого участника.

Существует обширнаялитература,посвященнаясравнению25множествальтернатив.Большинство предпосылок основано на работах [24, 50, 63, 82], а такжеописано в обзоре [27]. Рассмотрению данных предпосылок посвященаотдельная часть диссертации.Множественный выбор – это не такая уж и редкая ситуацияколлективного выбора. Например, в случае трех альтернатив и правилаотносительно большинства для малого числа участников голосованияоколо 20 процентов профилей дают множественный выбор. Несмотря наточтопредпосылкипостроенияпредпочтенийнамножествахальтернатив появились почти одновременно с теоремой ГиббардаСаттертуэйта, при анализе степени манипулируемости они почти неиспользовалисьввидудостаточнойсложностивычислений:каккомпьютерных, так и аналитических. Для борьбы с множественнымвыборомиспользуютсятакназываемыеправилаустранениянесравнимости.Наиболееестественнымипопулярнымизнихявляетсяалфавитное правило: при наличии множественного выбора итоговойвыбирается альтернатива, которая идет первой по алфавиту.

Такжеиногда множественный выбор разрешается согласно предпочтениямнекоторого определенного заранее участника (председателя, голоскоторого имеет преимущество в ситуации равенства голосов). В историиизвестны разные способы разрешения несравнимости: в Испании всредние века при выборах мэра в случае равенства голосов побеждалтот, у кого больше детей, а в Германии при равенстве голосов навыборах мэра кандидатов взвешивали и выбирали самого тяжелого.Некоторые другие интересные методы применяются до сих пор.Например, в 1998 году на выборах мэра маленького городка Эстанция вНью Мексико сложилась ситуация равенства голосов: за каждого из26кандидатов было подано по 68 голосов 5 .