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

Федеральное государственное автономное образовательное учреждениевысшего профессионального образованияНациональный исследовательский университет«Высшая школа экономики»На правах рукописиКарабекян Даниел СамвеловичМанипулирование в задачеколлективного принятия решенийСпециальность 08.00.13 –Математические и инструментальные методы в экономикеДИССЕРТАЦИЯна соискание ученой степени кандидата экономических наукНаучный руководитель:доктор технических наукАлескеров Фуад ТагиевичМосква — 2012ОглавлениеВведение ................................................................................................................3Глава 1.

Обзор исследований ............................................................................161.1. Ограничения на область определения ...................................................161.2. Множественный выбор и неманипулируемость ..................................201.3. Оценка манипулируемости .....................................................................22Глава 2. Методы построения предпочтений на множествах альтернатив ...302.1. Слабые аксиомы расширения предпочтений........................................312.2.

Сильные методы расширения предпочтений .......................................362.2.1. Лексикографические методы ...........................................................362.2.2. Вероятностные методы.....................................................................382.2.3. Метод усреднения рангов с дополнительными ограничениями ..412.3. Исследование различных способов расширения предпочтений ........452.4. Значение расширенных предпочтений ..................................................47Глава 3.

Формулировка модели ........................................................................503.1. Определение манипулирования .............................................................503.2. Правила коллективного принятия решений .........................................513.2.1. Позиционные (порядковые) правила ..............................................513.2.2. Правила, использующие мажоритарное отношение .....................563.2.3.

q-Паретовские правила .....................................................................613.3. Индексы манипулируемости и методика расчета ................................63Глава 4. Манипулируемость правил голосования ..........................................694.1. Степень манипулируемости.

..................................................................694.1.1. Позиционные (порядковые) правила: 1-я часть .............................704.1.2. Позиционные (порядковые) правила: 2-я часть .............................894.1.3. Правила, использующие мажоритарное отношение ...................1034.1.4. q-Паретовские правила ...................................................................1134.1.5.

Минимально манипулируемые правила .......................................1224.2. Свобода манипулирования ...................................................................1324.3. Эффективность манипулирования .......................................................1394.4. Слабое манипулирование .....................................................................1474.5. Разрешимость и манипулируемость. ...................................................152Заключение .......................................................................................................156Литература ........................................................................................................158Приложения ......................................................................................................167Приложение А ...............................................................................................167Возможные расширенные предпочтения для 3-х альтернатив илексикографических предпочтений ........................................................167Возможные расширенные предпочтения для 4-х альтернатив илексикографических предпочтений ........................................................167Возможные расширенные предпочтения для 5-и альтернатив илексикографических предпочтений ........................................................1692ВведениеОдним из главных результатов теории благосостояния являетсяфундаментальная работа Эрроу [11, 22].

В известной теореме онпоказал,чтоневозможноблагосостояния,котораяпостроитьудовлетворялафункциюбыобщественногонекоторомунаборуразумных предпосылок. Данная работа обрисовала серьезную проблемув теории благосостояния, над решением которой в разное времяработали Айзерман [13], Алескеров [13, 16], Браун [34], Викри [101],Инада [59], Кэмп [66], Маскин [73], Плотт [88], Сен [96] и другие.Ослабляяипереформулируяпредпосылки,ониполучалилибоаналогичные результаты в других условиях, либо возможностьпостроить функцию общественного благосостояния для определенногонабора условий. Обзор основных направлений развития теориипредставлен в работах Алескерова [17], ле Бретона и Веймарка [68],Кэмпбела [36] .В работе Эрроу [11] говорится, что существует два способапринятия коллективных решений: голосование и рыночный механизм.Сходство этих способов было показано еще Блэком [30], так как в обоихслучаях речь идет о некотором равновесии при определенном наборе(профиле) предпочтений индивидуальных участников.

В частности,Самуэльсон [9] в описании модели потребителя формулирует рыночныйобмен как голосование, в котором деньги потребителя являютсяголосами.Однако важно помнить, что неотъемлемой частью любогопроцесса коллективного принятия решений является стратегическоеповедение участников. Под стратегическим поведением понимаетсястремление игроков добиться лучшего для себя исхода коллективноговзаимодействия.3Очевидно, что на практике участник может действоватьстратегически–унегоестьвозможностьзаявитьискренниепредпочтения или намеренно их исказить, чтобы добиться лучшего длясебя результата.

Это дополняет проблему, поставленную в работе Эрроу,так как, даже если можно построить функцию, соответствующуюискреннимпредпочтениямучастников,мыможемникогданедостигнуть заданного исхода, поскольку нет механизма, который мог бызаставить участников высказывать искренние предпочтения.Поставленная проблема получила сразу несколько направленийразвития, одним из которых стала теория дизайна механизмов,разработанная Викри [102], Гурвицем [58], Майерсоном [78], Маскиным[74] и др.

Её суть состоит в поиске условий, при которых искренниепредпочтения участников являются равновесием в некоторой игре. Задостижения в развитии данной области Гурвиц, Майерсон и Маскинполучили Нобелевскую премию в 2007-м году.Однако существует достаточно большое число ситуаций, когданельзяпостроитьподобныймеханизмилипринятиерешенийпроисходит другим образом (например, в формате голосования).Мюллер и Саттертуэйт [76] показали, что ни одно правило голосования,с помощью которого выбирают одну альтернативу, нельзя реализоватькак равновесие по Нэшу в какой-то игре. В этом случае у участниковпроцесса принятия решений имеются стимулы заявлять неискренниепредпочтения. Выбор правила, при котором чаще всего участники будутвыражать именно искренние предпочтения, представляет собой важнуюоткрытую научную проблему, исследованию которой и посвященаданная диссертация.

Продемонстрируем манипулирование на примере.Пусть имеется следующая ситуация голосования, которая показана вТабл. 1 [см. 2, 7]:4Таблица 1 – Профиль предпочтений.Группа 1Группа 2Группа 33 агента2 агента2 агентаЛучшая альт.abcСредняя альт.babХудшая альт.ccaРассмотримпрофильпредпочтенийизТабл.1.Пустьиспользуется распространенное правило относительного большинства:альтернатива, за которую подано больше всего голосов, являетсяитоговым выбором.

Для профиля из Табл. 1 выбором будет альтернатива"a", так как за неё подано 3 голоса, а за все остальные по два. Однако,для группы 3, альтернатива "a" не является лучшим выбором. Тогдагруппе 3 выгодно исказить свои предпочтения и проголосовать завторую наилучшую альтернативу, т.е. за "b". В этом случае заальтернативу "b" будет подано 4 голоса и она станет итоговым выбором.Очевидно, что если группа 3 действует стратегически, то для членовэтой группы выгодно исказить свои предпочтения, так как они получатлучшую для себя альтернативу.Следует отметить, что данный пример не является единичным.Понятие манипулируемости тесно связано с теоремой Эрроу оневозможности.

Одной из предпосылок теоремы Эрроу являетсязнаменитая аксиома о независимости от посторонних альтернатив:соотношение между двумя альтернативами с точки зрения коллектива,должно зависеть только от соотношения этих двух альтернатив виндивидуальных предпочтениях, но не от соотношения их с какой-тотретьей альтернативой.

Викри [101] указал, что данная аксиома оченьпохожа на некоторое условие, запрещающее стратегическое поведение.Действительно, если для кого-то a лучше, чем b , и выполняется5аксиома независимости от посторонних альтернатив, то никакиеизменения в порядке альтернатив (в том числе относительно какой-тодругой альтернативы с ) в большинстве случаев не могут повлиять наобщественные предпочтения.Это соображение формализовали Гиббард и Саттертуэйт [52, 94],показав, что в условиях однозначного выбора и как минимум трехальтернатив не существует недиктаторского правила, защищенного отстратегическогоповедения.Эквивалентностьрядапредпосылоктеоремы Эрроу и теоремы Гиббарда-Саттертуэйта позднее показалиБлин и Саттертуэйт [32].Таким образом, проблема стратегического манипулированиянепосредственно вытекает из теоремы Эрроу и является важной частьюэкономикиблагосостояния.Вдальнейшембольшаячастьисследователей занималась ослаблением предпосылок теоремы, восновном в части неограниченной области определения процедур.

Вчастности, стоит выделить работы Блина и Саттертуэйта [31],Паттанаика [83, 84], Дамметта и Факуарсона [44], Барбера и Пелега [28],Кима и Роуша [67], Калаи и Мюллера [61], Келли [64], Барбера и др.[27], Дуггана и Шварца [43], Бенуа [29], Озюрта и Санвера [81],Мюллера и Саттертуэйта [77], Гиббарда [53, 54], Цекхаузера [103] идругих.

Подробнее об этом направлении рассказано в первой главе.Другим направлением развития исследований была оценкастепени манипулируемости. Работы в данной области пытались найтидругой ответ на теорему о невозможности Гиббарда-Саттертуэйта. Еслиизвестно, что не существует неманипулируемых правил принятиярешений, то возникает вопрос: какие из существующих правил являютсянаименее манипулируемыми? В данных работах рассматривалисьразличныегруппыправил,ианалитическииликомбинаторносравнивалась их манипулируемость. Так как большинство реальных6правил дают в некоторых случаях множественный выбор, то дляполучения однозначного выбора во многих правилах использовалисьусловия устранения несравнимости (подробнее см.

Главу 1). Основныеисследования на эту тему содержатся в работах Притчарда и Уилсона[90], Чемберлена [38], Нитцана [80], Келли [65], Алескерова иКурбанова [21], Лепелье и Валоня [69], Фавардина и Лепелье [48] идругих.Заметим,чтохотятеоремаГиббарда-Саттертуэйтасформулирована для однозначного выбора, большинство существующихправил коллективного принятия решений в ряде случаев порождаетнесравнимость или множественный выбор. Проблема стратегическогоповедения в условиях множественного выбора требует решения рядадополнительных вопросов, связанных с построением предпочтений намножествах альтернатив.Продемонстрируемманипулированиевэтихусловияхнапримере.