На самом деле, конечно, это частный, но вместе с тем одновременно и наиболее общий случай тех самых задач, которые мы решаем в этом курсе. Голосование — очень простой и естественный частный случай экономического механизма. У голосования есть множество возможных исходов, из которых участники должны выбрать; например, это кандидаты $$A$$, $$B$$ и $$C$$, из которых один должен стать президентом. У каждого участника голосования (агента) есть определенный порядок на этих исходах (нам будет достаточно случая, когда этот порядок линейный, то есть каждый исход сравним с каждым), который отражает его предпочтения. Например, кандидат $$A$$ мне нравится больше, чем $$B$$, а $$B$$ — больше, чем $$C$$ ; мы это будем обозначать через $$A\succ B\succ C$$. Этот порядок можно рассматривать как скрытую функцию предпочтений агента. И, наконец, есть некоторая функция социального выбора, которая определяет, какой кандидат должен бы победить при том или ином соотношении голосов.
Заметим, что этот частный случай вместе с тем оказывается и наиболее общим. Мы не предполагаем вообще никаких ограничений, никакой структуры на множестве предпочтений каждого из агентов; любой исход может оказаться на любом месте в его внутренней функции предпочтения. Поэтому результаты о невозможности, которые мы получим в этой лекции, окажутся весьма полезными в доказательстве результатов о невозможности в теории экономических механизмов, которыми мы будем заниматься в течение следующих трех лекций. Основным результатом станет теорема Эрроу, которая была доказана Кеннетом Эрроу в 1963 году [3].
Однако прежде всего нужно понять, что бы мы хотели получить от системы голосования. Каковы цели, которых мы будем (безуспешно) пытаться достигнуть?
Для этого рассмотрим достаточно простой и понятный случай голосования: случай, когда в нем участвует ровно один агент. Какими самыми базовыми, самыми естественными свойствами будет обладать множество предпочтений одного агента? Давайте сформулируем три основных свойства, три в высшей степени естественных предположения.
Наконец, четвертое свойство является по сути свойством функции социального выбора, а не свойством одного-единственного агента, как первые три. Мы его уже рассматривали в предыдущих лекциях.
Согласитесь, все эти свойства звучат абсолютно естественно, правда? Было бы очень странно, если бы система голосования не удовлетворяла этим свойствам. Один пример хорошей системы мы уже привели: система, в которой ровно один агент, удовлетворяет всем четырем свойствам.
Можно провести и менее тривиальный пример. Предположим, что возможных исходов всего два, то есть голосование превратилось в референдум. Тогда можно предложить простейшую систему голосования: выбирать нужную альтернативу большинством голосов. Рекомендуем читателю проверить, что выбор простым большинством из двух исходов удовлетворяет всем четырем интересующим нас свойствам.
Однако оказывается, что для трех и более возможных исходов голосования такую систему построить непросто. Подходящих механизмов голосования мало, и вряд ли существующие механизмы смогут удовлетворить поборников демократической процедуры, потому что непременно окажутся диктаторскими: результат голосования будет просто совпадать с предпочтениями какого-то одного его участника. Это и будет теорема Эрроу.
Но начнем мы с того, что продемонстрируем, почему естественные системы голосований оказываются беспомощными перед столь простыми условиями. Наше изложение будет в основном следовать [75].
В этом параграфе мы будем приводить примеры разного рода странных конструкций, которые, философски говоря, доказывают одну простую вещь: на свете не существует рационального "общего мнения группы людей". Есть мнение каждого конкретного человека. Но общее мнение, если пытаться его как-то более или менее "равномерно" вычислять из множества мнений членов интересующей нас группы, вообще никакими разумными свойствами обладать не будет. Формализуем мы это в теореме Эрроу, а в этом параграфе дадим важную интуицию.
Первый пример восходит аж к XVIII веку. В $$1785$$ году маркиз де Кондорсе придумал конструкцию парадокса, который под его именем вошел в политическую и экономическую теорию. Идея парадокса Кондорсе проста: рассмотрим три возможных исхода $$A$$, $$B$$ и $$C$$ и трех участников $$x$$, $$y$$ и $$z$$. Предположим, что их предпочтения распределены так:
$$\begin{array}{lll} A \succ_x B \succ_x C,\\ B \succ_y C \succ_y A,\\ C \succ_z A \succ_z B. \end{array}$$Иначе говоря, предпочтения трех участников получаются циклическим сдвигом одного линейного порядка.
Что будет происходить при голосованиях? Если на выбор предложат $$A$$ и $$B$$, то $$x$$ и $$z$$ проголосуют за $$A$$, и будет избран $$A$$: $$A\succ B$$. Если референдум пройдет между $$B$$ и $$C$$, то победа альтернативы $$B$$ будет обеспечена голосованием агентов $$x$$ и $$y$$: $$B\succ C$$. Но если предложат выбор между $$A$$ и $$C$$, то $$y$$ и $$z$$ проголосуют за $$C$$, и окажется, что $$C\succ A$$! В парадоксе Кондорсе нарушается
Давайте посмотрим на это с точки зрения дизайна механизмов. Как построить механизм голосования, который примет верное решение? Да и что вообще такое в данном случае "верное решение"? Вполне естественным может показаться механизм, который последовательно осуществляет референдумы, голосования с двумя исходами, до тех пор, пока (в предположении
Но этим дело не ограничивается. Здесь пока кажется, что вообще все равно, какой выбор делать: все три варианта абсолютно симметричны, так что какая разница функции социального выбора, какой из них предпочесть. Давайте рассмотрим небольшую модификацию парадокса Кондорсе, на которой результаты алгоритма попарного голосования окажутся еще интереснее. Для примера нам потребуются аж семь альтернатив, поэтому давайте назовем их как-нибудь поинтереснее, не просто буквами латинского алфавита.
Пример 6.1. Семеро великих вождей собираются в поход на семивратные Фивы. Собираются в поход двое изгнанников — Тидей и Полиник, собирается царь Адраст, двое аргивских вождей — Капаней и Гиппомедонт, ясновидец Амфиарай и аркадец
А в это время на Олимпе Гера, Афина и Артемида решают, кого из семи вождей сделать своим любимцем, кому больше других поспособствовать при осаде Фив. Предпочтения богинь весьма замысловаты. Вот они (в таблице сверху вниз степень предпочтения убывает).
| Гера | Афина | Артемида |
|---|---|---|
| Тидей | Капаней | Гиппомедонт |
| Полиник | Гиппомедонт | Тидей |
| Капаней | Тидей | Парфенопей |
| Гиппомедонт | Амфиарай | Полиник |
| Адраст | Парфенопей | Капаней |
| Амфиарай | Полиник | Адраст |
| Парфенопей | Адраст | Амфиарай |
В лучших традициях древнегреческой демократии богини согласились решить дело голосованием. Они начали устанавливать общий порядок поочередными голосованиями. И вот что у них получилось...
В результате не просто Афина оказалась в меньшинстве в последнем голосовании, а как будто мудрость в этом голосовании и вовсе не ночевала. Богини медленно, но верно спускались вниз по таблице, хотя на каждом шаге делали выбор большинством (можно сказать, конституционным большинством — две трети набиралось). В результате победил царь Адраст, хотя в изначальных предпочтениях и Тидей, и Полиник, и Капаней, и Гиппомедонт у всех трех богинь стояли выше Адраста.
Таким образом, в этом примере голосование привело к тому, что нарушился принцип единогласия; вполне честным и естественным протоколом мы выбрали вариант, не оптимальный по Парето (причем ну совсем далеко не оптимальный).
Конец примера 6.1.
Но и на этом интересные следствия парадокса Кондорсе не заканчиваются. Давайте подумаем: какие вообще были варианты у наших голосований? Предположим, что мы хотим пока ограничиться выбором между двумя альтернативами. Таким образом, голосование получается двухступенчатым: сначала две альтернативы сражаются друг с другом, потом победитель с третьей. Рассмотрим возможные варианты для классического парадокса Кондорсе (см. рис. 6.1).
(рис 6.1) Парадокс Кондорсе: как результат зависит от порядкаПолучается, что результат при одних и тех же предпочтениях кардинально зависит от формата голосования! А значит, тот, кто контролирует формат голосования (а в реальных ситуациях его обычно кто-то контролирует), имеет существенное преимущество и может победить, даже оказавшись в меньшинстве.
Более того, эта зависимость от формата приводит к тому, что
Пример 6.2. В политике такие ситуации редко, но действительно возникают на практике. Они называются "поправки-убийцы" (
В США сенаторов поначалу выбирали не прямым всенародным голосованием, а законодательными органами соответствующего штата. В том, чтобы ввести голосования на пост сенатора, заключалась 17-я поправка к Конституции США, которая в конце концов все же была принята в 1913. Но на пути к ее принятию был один любопытный случай.
Проблема заключалась в том, что в те годы в США Юг и Север все еще не слишком любили друг друга, и южные сенаторы беспокоились, что если федеральное ("северное") государство возьмет выборы сенаторов под свой контроль, то северяне-республиканцы сделают что-нибудь ужасное, например допустят на выборы чернокожих — и действительно, некоторые республиканцы так и собирались сделать.
Был достигнут компромисс: билль, который вводил прямые выборы сенаторов, но содержал поправки, ограничивающие контроль федерального правительства над выборами в южных штатах. Его поддерживало большинство (это была возможность $$A$$ ), и на прямом голосовании между этим биллем и тем, чтобы вообще не вводить прямые выборы (возможность $$B$$ ), билль бы прошел.
Однако сенатор Сазерленд, лидер меньшинства, которое было против выборов сенаторов как таковых, сумел придумать поправку-убийцу $$C$$. Таковой стало предложение о прямых выборах сенаторов без каких-либо поправок про южные штаты. Сазерленд устроил дело так, что сначала голосование шло между $$A$$ и $$C$$. Меньшинство Сазерленда проголосовало за $$C$$, северяне-республиканцы тоже проголосовали за $$C$$, и $$C$$ победило $$A$$. Но на этом дело не закончилось: затем встал выбор между $$C$$ и $$B$$. Сазерленд внезапно "изменил свою точку зрения" и стал голосовать не за $$C$$, а за $$B$$, то есть против выборов совсем. В результате билль $$C$$ сначала выполнил свою функцию и выбил поддерживаемый большинством билль $$A$$, а затем не прошел на следующих выборах. Получилась ситуация, изображенная на рис. 6.2 сплошными линиями, вместо ситуации, изображенной там же пунктиром.
(рис 6.2) Поправка сенатора СазерлендаКонец примера 6.2.
Этот же пример демонстрирует, что правдивости при таких выборах тоже лучше не ждать: меньшинство, стоявшее против выборов вообще, здесь было вынуждено сначала голосовать за них, чтобы затем иметь возможность провалить этот исход на следующих выборах. И он же показывает, что попарная независимость тоже недоступна: ведь по этому свойству выбор между $$A$$ и $$B$$ не должен зависеть от наличия или отсутствия третьей альтернативы $$C$$.
Но отсутствие попарной независимости, а также еще более интересный эффект, можно проиллюстрировать и более наглядно.
Пример 6.3. В этом примере мы попробуем "повыбирать" президента Российской Федерации. Делать это мы будем так, как это и делается в реальности: в первом туре участвуют все кандидаты, и если никто не набирает больше 50%, то двое лидеров выходят во второй тур. Предположим, что у нас есть три кандидата на высокий пост и 27 избирателей, чьи предпочтения распределены следующим образом. Цифры в таблице показывают, на какое место ставят данного кандидата эти избиратели, а число в первой строке — сколько избирателей так думают.
| К-во избирателей | 6 | 6 | 6 | 4 | 2 | 3 |
|---|---|---|---|---|---|---|
| Барсуков | 1 | 2 | 3 | 2 | 3 | 1 |
| Гризлев | 2 | 3 | 1 | 1 | 2 | 3 |
| Углеводский | 3 | 1 | 2 | 3 | 1 | 2 |
В первом туре Барсуков наберет 9 голосов, Углеводский — 8, а Гризлев — 10. Однако во втором туре ситуация изменится, и победит Барсуков, набрав 15 голосов против 12 у Гризлева. Пока все нормально.
Предположим, однако, что Барсуков, пытаясь победить Гризлева в первом туре, сумел воздействовать на сердца некоторых избирателей, и они изменили свои предпочтения между Гризлевым и Барсуковым в пользу последнего: трое из четырех с распределением $$2\succ 1\succ 3$$ переместили Барсукова на первое место, а двое с распределением $$3\succ 2\succ 1$$ изменили его на $$2\succ 3\succ 1$$. Итого получается следующая таблица:
| К-во избирателей | 9 | 8 | 6 | 1 | 3 |
|---|---|---|---|---|---|
| Барсуков | 1 | 2 | 3 | 2 | 1 |
| Гризлев | 2 | 3 | 1 | 1 | 3 |
| Углеводский | 3 | 1 | 2 | 3 | 2 |
Согласитесь, что все это, казалось бы, может быть только в пользу Барсукова. Но... В первом туре Барсуков действительно выигрывает с большим отрывом, получив 12 голосов. Однако во второй тур теперь выходит не Гризлев, а Углеводский, который в итоге побеждает Барсукова с счетом $$14:13$$.
Иначе говоря, Барсуков сделал распределение строго лучше для себя, но в итоге сменил победу на поражение. И все это во вполне естественной системе голосования, по которой действительно выбирают президента РФ... \
Конец примера 6.3.
Итак, мы показали, что если пытаться сформулировать более или менее естественную систему голосования, совершенно ничего не получается, вообще ни одного естественного и крайне желательного свойства. Конечно, это еще не доказательство: возможно, мы просто не смогли придумать правильную систему голосования?
Доказательство будет в следующем параграфе.
В этом параграфе мы перейдем к чуть более общей формулировке и докажем, что все равно ничего не получается. Как и прежде, через $$\mathcal O$$ мы будем обозначать множество возможных исходов. На этом множестве у каждого из агентов $$i$$ есть некоторый профиль предпочтений, который мы будем обозначать через $$\succeq_i$$: для двух исходов $$x$$ и $$y$$ будем писать, что $$x\succeq_i y$$, если агент $$i$$ предпочитает исход $$x$$ перед $$y$$.
Определение 6.1.
Мы будем предполагать, что профили предпочтений бывают всякие. Например, всякие рациональные — их множество мы обозначим через $$\mathcal R$$. Или вообще всякие профили, лишь бы любые два исхода были различимы: множество таких исходов мы обозначим через $$\mathcal P$$. Если агентов $$N$$, то, значит, множество всевозможных предпочтений будет в этих обозначениях $$\mathcal R^N$$ или $$\mathcal P^N$$.
Функция социального выбора в данном контексте — это некоторая функция $$f$$ с областью определения $$\mathcal R^N$$ или $$\mathcal P^N$$ и областью значений $$\mathcal O$$, которая по данным предпочтениям агентов выбирает исход. Мы чуть обобщим это определение и будем считать, что функция социального выбора выдает не один исход, а слабый линейный порядок на имеющихся исходах (то есть $$f:\mathcal R^N\to \mathbb R$$ ); этот порядок мы будем обозначать через $$\succeq_{f(\succeq_1,\ldots,\succeq_N)}$$ или, когда ясно, на каком входе берется функция, просто $$\succeq_f$$.
Мы бы хотели, чтобы функция социального выбора удовлетворяла тем естественным условиям, которые мы сформулировали в 6.1. Сначала — принцип единогласия, он же эффективность по Парето.
Определение 6.2. Пусть пара исходов $$x,y\in\mathcal O$$ такова, что для каждого агента $$i$$ исход $$x$$ не хуже, и при этом для какого-нибудь агента он строго лучше: для всех $$i$$ $$x\succeq_i y$$, и существует такое $$j$$, что $$x\succ_j y$$. Тогда функция социального выбора $$f$$ называется эффективной по Парето, если для каждой такой пары исходов результат функции социального выбора $$f(\succeq_1,\ldots,\succeq_N)$$ ставит $$x$$ перед $$y$$: $$x\succeq_f y$$.
Затем сформулируем формально свойство
Определение 6.3. Функция социального выбора $$f$$ удовлетворяет свойству
то в результате $$x \succeq_{f(\succeq_1,\ldots,\succeq_N)} y$$ тогда и только тогда, когда $$x\succeq_{f(\succeq^\prime_1,\ldots,\succeq^\prime_N)} y$$:
$$\forall i\quad x \succeq_{f(\succeq_1,\ldots,\succeq_N)} y \Leftrightarrow x\succeq_{f(\succeq^\prime_1,\ldots,\succeq^\prime_N)} y.$$Наконец, последнее определение будет касаться уже не того, чего бы нам хотелось, а того, что у нас в итоге получится.
Определение 6.4.
Проще говоря, диктаторская функция социального выбора делает точно такой же выбор, как один из представленных агентов. Конечно, у диктаторской функции получится соответствовать нужным свойствам, точно так же как у предпочтений одного агента это получается (проверьте это формально!). А беда в том, что ничего другого-то и не получится. Мы наконец готовы к тому, чтобы сформулировать и доказать теорему Эрроу [3].
Теорема 6.1. (Эрроу) Пусть множество возможных исходов $$\mathcal O$$ состоит из не менее чем трех элементов, и возможны все рациональные профили ( $$\mathcal R$$ ) или все профили, в которых любые две альтернативы различимы ( $$\mathcal P$$ ). Тогда всякая функция социального выбора $$f$$, которая оптимальна по Парето и удовлетворяет условию попарной независимости, является диктаторской.
Доказательство.
Начнем доказательство с определения, простите за
Определение 6.5. Для данного $$f$$ будем говорить, что набор агентов $$S\subset [N]$$ (через $$[N]$$ мы обозначим множество индексов от $$1$$ до $$N$$ ):
Важное замечание: первое из этих определений достаточно слабое, оно касается только ситуаций, когда агенты из $$S$$ голосуют за $$x$$, а все агенты не из $$S$$ голосуют за $$y$$ ; но из него мы быстро перейдем и к более сильным ситуациям.
Доказательство мы проведем в... десять этапов. Не будем, пожалуй, оформлять каждый из этих этапов в отдельную лемму, а просто последовательно их приведем. В каждом пункте ниже выделенное курсивом утверждение — то, что хочется доказать, а в следующем абзаце идет его доказательство. Большинство доказательств однотипны: мы пользуемся тем, что множество возможных предпочтений достаточно богато, и строим такой профиль предпочтений, из которого будет следовать нужный результат.
Если $$z=y$$, доказывать нечего. Если $$z\neq y$$, то рассмотрим такой профиль $$(\succeq_1,\ldots,\succeq_N)$$, что
$$\begin{array}{rl} x\succ_i y\succ_i z \forall i\in S,\\ y\succ_i z\succ_i x \forall i\in [N]\setminus S.\end{array}$$
Тогда, значит, по свойству определяющего набора $$f$$ должна предпочесть $$x$$ перед $$y$$. А по оптимальности по Парето $$f$$ предпочитает $$y$$ перед $$z$$. Значит, $$f$$ предпочитает $$x$$ перед $$z$$. Осталось сослаться на попарную независимость.
По шагу 1, $$S$$ определяющий для $$z$$ перед $$y$$ и для $$x$$ перед $$z$$. Применим снова шаг 1 для пары $$\{x,z\}$$ и альтернативы $$w$$ ; из шага 1 видно, что $$S$$ будет определяющим и для $$w$$ перед $$z$$. Аналогичное рассуждение проходит и для пары $$\{z,y\}$$.
Доказательство сразу следует из шага 2 и из того, что третья альтернатива существует (здесь это важно!).
Рассмотрим тройку альтернатив $$\{x,y,z\}\subset\mathcal O$$ и такой профиль $$(\succeq_1,\ldots,\succeq_N)$$, что
$$\begin{array}{ll} z \succ_i y \succ_i x \quad \forall i\in S\setminus(S\cap T), \\ x \succ_i z \succ_i y \quad \forall i\in S\cap T, \\ y \succ_i x \succ_i z \quad \forall i\in T\setminus(S\cap T), \\ y \succ_i z \succ_i x \quad \forall i\in [N]\setminus(S\cup T). \end{array}$$
Тогда $$z\succ_f y$$, потому что $$S=(S\cap T)\cup(S\setminus(S\cap T))$$ — определяющий, и $$x\succ_f z$$, потому что $$T$$ — определяющий. Значит, $$x\succ_f y$$, и по попарной независимости $$S\cap T$$ тоже является определяющим для $$x$$ перед $$y$$. Значит, он и вообще определяющий.
$$\begin{array}{ll} x \succ_i z \succ_i y \forall i\in S, \\ y \succ_i x \succ_i z \forall i\in [N]\setminus S. \end{array}$$
Тогда либо $$x\succ_f y$$, и $$S$$ определяющий для $$x$$ перед $$y$$, либо $$y\succ_f x$$. Если $$y\succ_f x$$, то по свойству оптимальности по Парето $$x\succ_f z$$, и, значит, $$y\succ_f z$$ ; значит, $$[N]\setminus S$$ является определяющим набором для $$y$$ перед $$z$$
.Пустой набор не может быть определяющим из-за свойства оптимальности по Парето. Значит, $$[N]\setminus T$$ не может быть определяющим, потому что тогда и $$\emptyset = S\cap ([N]\setminus T)$$ будет определяющим. Значит, по пункту $$5$$, $$T$$ определяющий.
Рассмотрим $$h\in S$$. Если $$S\setminus\{h\}$$ определяющий, то утверждение доказано. Если нет, то $$[N]\setminus(S\setminus\{h\})$$ определяющий, и
$$\{h\} = S\cap ([N]\setminus(S\setminus\{h\}))$$
определяющий.
Нужно просто несколько раз применить шаг 7.
Нужно получить, что для всех $$T\subset [N]\setminus S$$ $$x\succ_f y$$, если все агенты из $$S$$ предпочитают $$x\succ y$$, все агенты из $$T$$ предпочитают $$x\succeq y$$, а остальные — $$y\succ x$$.
Рассмотрим третью альтернативу и такой профиль $$(\succeq_1,\ldots,\succeq_N)$$, что
$$\begin{align*} x \succ_i z \succ_i y \quad \forall i\in S, \\ x \succ_i y \succ_i z \quad \forall i\in T, \\ y \succ_i z \succ_i x \quad \forall i\in [N]\setminus (S\cup T). \end{align*}$$
Тогда $$x\succ_f z$$, потому что $$S\cup T$$ определяющий, и $$z\succ_f y$$, потому что $$S$$ определяющий. Значит, $$x\succ_f y$$, что и требовалось.
Это в точности следует из определения полностью определяющего набора.
Как видите, мы неоднократно и по делу пользовались тем, что $$|\mathcal O|\ge 3$$. В самом деле, если $$|\mathcal O|=2$$, то теорема неверна: функция социального выбора "большинство голосов", как мы уже отмечали в предыдущем параграфе, и недиктаторская, и оптимальная по Парето, и обладает свойством
Доказательство теоремы 6.1 получилось довольно громоздким и техническим. Конечно, на самом деле это идейное доказательство: мы постепенно получали все более и более сильные свойства определяющих наборов, пока не выяснили, что на самом деле среди них есть одноэлементные множества.
Но можно предложить и другие идейные доказательства, например [7]. В этом параграфе, основанном на работе [21], мы рассмотрим три альтернативных (и достаточно коротких) доказательства теоремы Эрроу. Надеемся, их идеи окажутся достаточно различными, чтобы оправдать такой подход. %Рекомендуем читателю по мере разбора этих доказательств по крайней мере отмечать, %где в каждом из них используется, что альтернатив по меньшей мере три.
Первое доказательство теоремы 6.1. Это доказательство тоже будет проведено в несколько шагов, но на этот раз шаги куда быстрее приведут к цели. Правда, по сравнению с исходным доказательством они могут показаться менее очевидными. Основным для доказательства здесь станет доказательство существования
Доказательство очень простое. Предположим, что это не так, то есть $$y\succ_f x\succ_f z$$ для некоторых $$y\neq x$$, $$z\neq x$$. Поскольку $$x$$ у каждого находится в одной из крайних позиций, мы можем, не нарушая никаких индивидуальных предпочтений, переместить в предпочтениях каждого агента $$z$$ над $$y$$ (проверьте, что это возможно!). Тогда по
Пусть каждый агент поставит $$x$$ в самый низ. По анонимности, $$x$$ должен занимать последнюю позицию. Теперь пусть агенты по одному перемещают $$x$$ с самого низа на самый верх. Рано или поздно $$x$$ переместится и, по пункту $$1$$, $$x$$ переместится сразу на самую верхнюю позицию. Вот последний перед этим профиль предпочтений и соответствующего агента мы и выберем.
Выберем элемент $$y$$ — один из этой пары — и рассмотрим профиль из пункта $$2$$, для которого агент $$i^*$$ может переместить $$x$$ снизу вверх. Пусть теперь $$i^*$$ изменит свой профиль, переместив $$y$$ на самый верх: $$y\succ_{i^*} x\succ_{i^*} z$$. Рассмотрим всевозможные профили других агентов, в которых $$y$$ и $$z$$ меняются местами произвольно, но $$x$$ остается на своих крайних позициях. По свойству попарной независимости, результат на этих профилях должен быть $$y\succ_f x$$, потому что относительные позиции $$y$$ и $$x$$ такие же, как в том профиле, когда $$x$$ у $$i^*$$ был в самом низу, и в результате $$x$$ тоже был в самом низу. Аналогично, в результате должно быть $$x\succ_{f} z$$. Соответственно, по
Рассмотрим третью возможность $$z$$, не входящую в эту пару. Для нее должен быть какой-нибудь диктатор $$j^*$$. Он должен быть диктатором для каждой пары, не содержащей $$z$$, например для $$x,y$$. Но $$i^*$$ может изменить судьбу пары $$x,y$$, потому что он может при определенных обстоятельствах переместить $$x$$ с самого низа на самый верх. Значит, $$j^*$$ и $$i^*$$ — одно лицо.
Второе доказательство теоремы 6.1. Второе доказательство (как, собственно, и третье) тоже будет строить агента-диктатора. Но делать это мы будем уже другим способом. Давайте рассмотрим парадокс Кондорсе и впишем его в профили агентов. Обозначим возможные исходы в алфавитном порядке через $$\mathcal O=\{x,y,\ldots, z\}$$. Все агенты в так называемых профилях Кондорсе будут иметь профили одного из $$|\mathcal O|$$ типов: $$\theta_x,\theta_y,\ldots,\theta_z$$. Предпочтения этих типов будут выглядеть так:
$$\begin{array}{rcccccccc} \theta_x: x \succ y \succ \ldots \ldots \succ z,\\ \theta_y: y \succ z \succ \ldots \ldots \succ x,\\ \vdots \vdots \vdots \vdots \\ \theta_z: z \succ x \succ y \succ \ldots \ldots.\\ \end{array}$$То есть это просто упорядоченная в алфавитном порядке последовательность исходов, сдвинутая циклически так, чтобы в профиле типа $$\theta_\alpha$$ исход $$\alpha$$ оказался бы на первом месте.
Если все агенты имеют тип $$\theta_x$$, то, по принципу единогласия, $$x\succ_f y\succ_f z$$. Рассмотрим все возможные векторы профилей агентов и выберем из них тот, где число агентов типа $$\theta_x$$ минимально, но результат все равно имеет тип $$\theta_x$$. Обозначим этот профиль через $$\pi_x$$. Хотя бы один агент $$i^*$$, имеющий тип $$\theta_x$$, должен существовать в $$\pi_x$$, т. к. если никто из агентов не этого типа, то по принципу единогласия $$z\succ_f x$$.
Теперь докажем, что $$i^*$$ может в профиле $$\pi_x$$ творить вообще все что хочет. Предположим, что исход $$\beta$$ следует по алфавиту сразу за исходом $$\alpha$$, и в профиле $$\pi_x$$ агент $$i^*$$ меняет свой тип на $$\theta_\beta$$, и в результате получается профиль Кондорсе $$\pi_\beta$$. По свойству попарной независимости, все равно в новом профиле $$x\succ_f \alpha$$ и $$\beta\succ_f z$$. Значит, чтобы порядок изменился (а он должен измениться, ведь мы взяли минимальное возможное число агентов типа $$\theta_x$$ ), нужно, чтобы в результате было верно $$\beta \succeq_f \alpha$$ (а если $$\beta=_f\alpha$$, то по
Пусть $$i^*$$ изменит свой профиль на $$-\theta_x$$, то есть на профиль вида
$$z\succ \ldots \succ y \succ x.$$Получится уже не профиль Кондорсе $$\pi_{-x}$$. Рассмотрим любые два исхода $$\alpha,\beta$$, идущие друг за другом по алфавиту. Тогда $$\theta_\beta$$ и $$\theta_{-\alpha}$$ совпадают на паре $$\{\beta,\alpha\}$$ (в обоих $$\beta\succ\alpha$$ ) и на паре $$\{x,z\}$$ (в обоих $$z\succ x$$ ). Значит, по независимости, на профиле $$\pi_{-x}$$ $$\beta\succeq_f \alpha$$, потому что так было в профиле $$\pi_x$$. Но поскольку $$\alpha$$ и $$\beta$$ произвольные, то, значит, в профиле $$\pi_{-x}$$
$$z\succeq_f\ldots\succeq_f x.$$Более того, если бы было верно, что $$\alpha=_f\beta$$ в профиле $$\pi_{-x}$$, то они были бы равны и в профиле $$\pi_x$$, и, значит, было бы верно, что $$x\succ_f z$$ в профиле $$\pi_\beta$$, а значит, и в профиле $$\pi_{-x}$$, что приводит к противоречию. Значит, все неравенства строгие:
$$z\succ_f y\succ_f\ldots\succ_f x.$$Теперь покажем, что $$i^*$$ — диктатор в каждом профиле, не только в $$\pi_x$$. Предположим, что в некотором профиле $$\pi$$ агент $$i^*$$ является диктатором, то есть при условии, что предпочтения остальных соответствуют профилю $$\pi$$, агент $$i^*$$ может добиться любого желаемого решения. Мы это про агента $$i^*$$ уже доказали для профиля $$\pi_x$$. Изменим тогда $$\pi$$ на $$\pi^\prime$$, позволив ровно одному агенту $$i\neq i^*$$ поднять ровно одну альтернативу на полшага выше: либо разрешить ничью между $$\alpha$$ и $$\beta$$, либо ее создать, но не то и другое вместе, и других альтернатив менять тоже не позволим. Предположим, что для $$i^*$$ $$\alpha\succ_{i^*} \gamma\succ_{i^*} \beta$$ в профиле $$\pi$$. Тогда, значит, и в результате профиля $$\pi$$ $$\alpha\succ_f\gamma\succ_f\beta$$ (ведь $$i^*$$ там диктатор). Следовательно, и в $$\pi^\prime$$ $$\alpha\succ_f \gamma$$ и $$\gamma\succ_f\beta$$, а это значит, что по
А по принципу единогласия это значит, что те полшага, которые сделал агент $$i$$ в профиле $$\pi^\prime$$, ничего для $$f$$ изменить не смогли: в $$\pi^\prime$$ агент $$i^*$$ является таким же диктатором, каким был и в профиле $$\pi$$. Но это значит, что $$i^*$$ — диктатор везде, ведь из любого профиля в любой другой можно придти последовательностью таких шажков (проверьте!).
Итак, второе доказательство использовало специальный вид профилей предпочтений агентов — обобщение парадокса Кондорсе. Третье, самое короткое, будет весьма интересным — мы докажем лемму о том, как должны соотноситься между собой разные предпочтения.
Лемма 6.1. (о строгой нейтральности) Рассмотрим две пары альтернатив $$(x,y)$$ и $$(\alpha,\beta)$$. Предположим, что предпочтения каждого агента на этих парах совпадают, и все такие предпочтения являются строгими. Тогда предпочтения на выходе функции социального выбора на этих парах тоже будут совпадать и тоже будут строгими. Это выполняется для каждой функции социального выбора.
Доказательство. Если пары $$(x,y)$$ и $$(\alpha, \beta)$$ идентичны, то утверждение очевидно. Рассмотрим случай, когда они не совпадают. Предположим без потери общности, что $$x\ge y$$. Переместим $$\alpha$$ (если оно не равно $$x$$ ) в позицию непосредственно сверху $$x$$ для каждого агента, а $$\beta$$ — в позицию непосредственно снизу $$y$$ для каждого агента (если, конечно, $$\beta\neq y$$ ). Поскольку все предпочтения строгие, это можно сделать, не нарушив относительного расположения пар $$(x,y)$$ и $$(\alpha,\beta)$$:
$$\begin{array}{cc} \alpha y\\ x \beta \\ y \alpha \\ \beta x\\ \end{array}$$Тогда, по принципу единогласия, $$\alpha \succ x$$ и $$y\succ\beta$$, если они не равны. По
Третье доказательство теоремы 6.1. Третье доказательство, опирающееся на лемму 6.1, будет совсем коротким. Рассмотрим два исхода $$x\neq y$$ и начнем с $$y\succ_i x$$ для всех $$i$$.i Пусть теперь, начиная с $$i=1$$, каждый агент по очереди перемещает $$x$$ наверх $$y$$. По единогласию и лемме 6.1, будет существовать агент $$i^*$$, при изменении предпочтения которого $$x$$ перемещается наверх относительно $$y$$ и после применения функции социального выбора. Докажем, что $$i^*$$ — диктатор. Рассмотрим произвольную пару исходов $$(\alpha,\beta)$$, для которой $$\alpha\succ_{i^*}\beta$$. Пусть ранжирование этой пары у других агентов будет совершенно произвольным.
Рассмотрим теперь третий исход $$z\notin\{\alpha,\beta\}$$ и переместим $$z$$ выше всех остальных исходов для агентов от $$1$$ до $$i^*-1$$, ниже всех остальных для агентов от $$i^*+1$$ до $$N$$, а для самого $$i^*$$ поместим $$z$$ между $$\alpha$$ и $$\beta$$: $$\alpha\succ_{i^*} z\succ_{i^*}\beta$$. Тогда, по попарной независимости и лемме 6.1, в предпочтениях социальной функции $$\alpha\succ_f z$$ и $$z\succ_f \beta$$, а это значит, по
В предыдущих лекциях мы уже рассмотрели примеры, в которых были получены правдивые механизмы, успешно реализующие социальную функцию в
Однако теорема Эрроу заставляет задуматься, всегда ли это возможно. К сожалению, ответ совсем не положительный: возможно это далеко не всегда. Теперь мы рассмотрим один из самых больших подвохов всей теории экономических механизмов.
Оказывается, что все-таки не любые механизмы существуют. Сейчас мы сформулируем определение довольно узкого и "нечестного" класса функций социального выбора — так называемых диктаторских функций, которые выгодны ровно одному конкретному участнику (полный аналог диктаторских функций в теореме Эрроу). А потом, как и в теореме Эрроу, докажем, что никаких других реализовать в
Этот результат — одна из классических теорем теории экономических механизмов. Она была независимо доказана Аланом Гиббардом и Марком Саттертуэйтом и в их честь и называется [22,74].
Теорема Гиббарда-Саттертуэйта крайне похожа на теорему Эрроу. Она, собственно, из теоремы Эрроу будет следовать (а есть и примеры единого доказательства этих двух результатов [68]). Мы начнем с формулировки того, кто же такие диктаторы в контексте теории экономических механизмов.
Определение 6.7. Функция социального выбора $$f$$ называется диктаторской, если существует такой агент $$i$$, что для всех возможных векторов типов агентов $$\mathbf\theta=(\theta_1,\ldots,\theta_N)\in\mathbf\Theta$$
$$f(\mathbf\theta)\in\left\{\vphantom{1^2_3}x\in\mathcal O\mid u_i(x,\theta_i)\ge u_i(y,\theta_i)\text{ для всех }y\in\mathcal O\right\}.$$Проще говоря, функция социального выбора всегда выбирает один из вариантов, оптимальных для $$i$$ -го агента.
Вспомним теперь определение 3.9: множеством нижнего контура возможного исхода $$x$$ при агенте $$i$$ типа $$\theta_i$$ называется множество
$$L_i(x,\theta_i)=\left\{\vphantom{1^2}x^\prime\in\mathcal O:u_i(x,\theta_i)\ge u_i(x^\prime,\theta_i)\right\}.$$Это определение позволит нам сформулировать понятие монотонной функции социального выбора.
Определение 6.7.
следует, что $$f(\mathbf\theta)=f(\mathbf\theta^\prime)$$.
То есть если $$f(\mathbf\theta)=x$$, и при переходе к $$\mathbf\theta^\prime$$ ни у одного агента ни один исход, который раньше был хуже $$x$$, не стал строго лучше $$x$$, то $$x$$ должен остаться его социальным выбором.
Кроме того, важным для нас понятием будут порядки на возможных исходах $$\mathcal O$$, которые для каждого агента задают, что именно ему больше нравится (это те самые порядки предпочтений, которые играли главную роль в доказательствах теоремы Эрроу). Нам не так важно, сколько именно агент получит (конкретное значение $$u_i$$ ). Важно то, что он исход $$o_1$$ ценит выше, чем $$o_2$$, но ниже, чем $$o_3$$. Обозначим через $$\mathcal P$$ множество всех линейных порядков на $$\mathcal O$$, а через $$\mathcal R_i$$ — множество порядков, которые может реализовывать агент $$i$$.
Теперь уже можно сформулировать и доказать основной результат.
Теорема 6.2. (Гиббарда-Саттертуэйта) Предположим, что:
Тогда функция социального выбора $$f$$ правдиво реализуема в
Доказательство. Доказательство следствия справа налево тривиально: совершенно очевидно, что диктаторская $$f$$ правдиво реализуема в
Доказывать будем в три приема, тремя леммами.
Лемма 6.2. Если $$\mathcal R_i=\mathcal P$$ для всех $$i$$, и $$f$$ правдиво реализуема в
Доказательство. Рассмотрим два профиля типов $$\mathbf\theta$$ и $$\mathbf\theta^\prime$$, для которых
$$L_i\left(\vphantom{1^2}f(\mathbf\theta),\theta_i\right)\subseteq L_i\left(\vphantom{1^2}f(\mathbf\theta),\theta^\prime_i\right).$$Мы хотим показать, что $$f(\mathbf\theta)=f(\mathbf\theta^\prime)$$.
Доказательство будет следовать классической схеме: взять один вектор (профиль типов) и менять его покомпонентно, пока он не станет совпадать со вторым. Поскольку $$f$$ правдиво реализуема, то
$$f(\theta^\prime_1,\theta_2,\ldots,\theta_N)\in L_1\left(f(\mathbf\theta),\theta_1\right)\subseteq L_1\left(f(\mathbf\theta),\theta^\prime_1\right)$$и, с другой стороны, $$f(\mathbf\theta)\in L_1\left(\vphantom{1^2}f(\theta^\prime_1,\theta_2,\ldots,\theta_N),\theta^\prime_1\right)$$. Так как порядки линейные, и все сравнимо (это то же самое условие, которое в теореме Эрроу называлось "строгими предпочтениями"), из этого следует, что
$$f(\theta^\prime_1,\theta_2,\ldots,\theta_N) = f(\mathbf\theta).$$Теперь можно доказать, что
$$f(\theta^\prime_1,\theta^\prime_2,\theta_3,\ldots,\theta_N) = f(\theta^\prime_1,\theta_2,\ldots,\theta_N) = f(\mathbf\theta).$$И так далее, и тому подобное. В общем, $$f(\mathbf\theta)=f(\mathbf\theta^\prime)$$.
Лемма 6.3. Если $$\mathcal R_i=\mathcal P$$ для всех $$i$$, $$f$$ монотонна, и $$f(\mathbf\theta)=\mathcal O$$, то $$f$$ эффективна ex post.
Доказательство. Если $$\mathcal R_i=\mathcal P$$ для всех $$i$$, $$f$$ монотонна и $$f(\mathbf\theta)=\mathcal O$$, то $$f$$ эффективна ex post. Напомним, что "эффективна ex post" означает, что уже после того, как агенты сыграют по своим стратегиям, для каждого возможного значения $$\mathbf\theta$$ нельзя сместить равновесие туда, где всем будет лучше.
Предположим противное. Пусть существуют такие $$\theta\in\mathbf\Theta$$ и $$b\in\mathcal O$$, что
$$u_i(b,\theta_i) > u_i(f(\mathbf\theta), \theta_i)$$(равенство невозможно, потому что нет несравнимых исходов). Воспользуемся тем, что $$f(\mathbf\theta)=\mathcal O$$ (сюръективностью). Это значит, что есть такой $$\mathbf\theta^\prime\in\mathbf\Theta$$, что $$f(\mathbf\theta^\prime)=y$$.
А теперь воспользуемся тем, что все предпочтения в $$\mathcal P$$ возможны. Выберем такой вектор $$\mathbf\theta^{\prime\prime}\in\mathbf\Theta$$, что
$$\forall i\ \forall x\neq f(\mathbf\theta),y\quad u_i(y,\mathbf\theta^{\prime\prime}_i)>u_i(f(\mathbf\theta),\mathbf\theta^{\prime\prime}_i)>u_i(z,\mathbf\theta^{\prime\prime}_i).$$Поскольку
$$L_i(y,\mathbf\theta^\prime_i)\subset L_i(y,\mathbf\theta^{\prime\prime}_i)$$для всех $$i$$, то, по монотонности, $$f(\mathbf\theta^{\prime\prime})=f(\mathbf\theta)$$. А это приводит к противоречию, так как $$y\neq f(\mathbf\theta)$$.
Итак, теперь мы все подготовили к тому, чтобы напрямую применить теорему Эрроу.
Лемма 6.4. Если $$f$$ монотонна и эффективна ex post, то она диктаторская.
Доказательство. Эта лемма является прямым следствием из теоремы Эрроу о невозможности (теоремы 6.1).
Суммарно эти три леммы и доказывают теорему Гиббарда-Саттертуэйта.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.