Доказательство теоремы Эрроу

В этой главе мы начнем наши исследования с того, что шаг за шагом пройдем через доказательство теоремы Эрроу ^ХЯ должен преду- предить вас: путешествие, которые мы собираемся предпринять, зай- мет у нас много времени и сил. Теорема Эрроу—это очень значитель- ный результат, и ее доказательство требует усилий и сосредоточенно- сти. Тем не менее, мы в состоянии взять быка за рога и понять дока- зательство, если не будем слишком спешить. Когда мы закончим, вы

¹ Способ, который мы будем использовать для доказательства теоремы Эрроу, мы позаимствовали в адаптированном виде из статьи Геанакоплоса [21].

войдете в число избранных, которые не только знакомы со смыслом одной из самых важных теорем в истории математики, но еще и зна- ют, почему она верна.

Прежде чем приступить к доказательству, мы должны сказать еще об одном обозначении, которым будем пользоваться. Напомним, что мы использовали знак >- чтобы обозначать, что один кандидат пред- почтительней другого, и знак и — что у них равный результат. В этом разделе нам иногда будет нужно говорить, что кандидат А предпочти- тельнее или сравним с другим кандидатом В. Мы будем обозначать этот тип соотношения, записывая Л £ В. (Заметим, что как и раньше, имеется аналогия с символом ^, который используется при сравнива- нии чисел.)

Теперь можно перейти к теореме Эрроу. Как бы странно это ни казалось, в действительности проще доказать более сильный вариант георемы, который мы привели в конце гл. 4 (см. с. 85), чем доказы- вать оригинальную версию, сформулированную раньше в той же гла- ве. Чтобы прояснить стратегию доказательства, мы начнем с того, что приведем новую формулировку сильного варианта теоремы, она бу- дет немного отличаться от той, что была в конце гл. 4.

Теорема Эрроу (сильная форма). Для выборов, в которых учас- твуют больше двух кандидатов, нельзя указать избирательную си- стему, которая бы обладала свойствами универсальности и единогла- I ия, удовлетворяла бы критерию НПА, и не была бы диктатурой.

Вопрос 5.2. Объясните, почему сильная форма теоремы Эрроу, приведенная выше, эквивалентна варианту этой же теоремы, кото- рый был сформулирован в конце гл.4.

Если вы были внимательны, то вы заметили, что наша обновлен- ная версия теоремы Эрроу по стилю очень напоминает утверждение Ш вопроса-разминки 5.1. Точно так же, как и в том случае, мы могли бы попытаться доказать теорему Эрроу, применив грубую силу: т. е. проверить каждую из существующих избирательных систем и убе- диться, что ни одна из них не удовлетворяет всем четырем условиям. 11о трудно даже представить себе, как бы мы могли справиться с про- паркой всех возможных избирательных систем. На самом деле, нет уверенности даже в том, что мы можем найти все возможные изби- |м гельные системы, не говоря уже о проверке свойств каждой из них.

Гораздо лучше было бы попытаться проделать в точности то же, •I го мы делали, отвечая на вопрос-разминку 5.1. Тогда мы просто пред- п ожили, что три из условий (делимость на 2, и и 23) выполнены, .1 потом объяснили, почему четвертое условие (не превышать 500) вы-

подняться не может. Именно при таком подходе наш пересмотренный способ рассуждений оказывается особенно удобным. Мы можем на- чать наше доказательство с предположения о том, что мы рассматри- ваем выборы, в которых участвуют больше двух кандидатов, а изби- рательная система удовлетворяет свойствам универсальности, НПА и единогласия. Чтобы завершить доказательство, нам надо будет объ- яснить, почему эта избирательная система должна быть эквивалент- на диктатуре. Иначе говоря, мы должны будем показать, что в этой системе найдется некоторый избиратель v такой, что если для произ- вольной пары кандидатов А и В для избирателя v кандидат А предпо- чтительней В, то и для общества А предпочтительней В.

В связи с этим полезно указать на аналогии между последним ша- гом в нашем методе доказательства и тем, чем мы занимались в гл. i, когда доказывали теорему 1.22. В этой теореме мы предполагали, что у нас есть анонимная, нейтральная и монотонная избирательная си- стема, и нам нужно было доказать, что это избирательная система с квотой. С этой целью мы строили процедуру, которая позволила нам найти потенциальную величину квоты. После этого мы доказали, что эта потенциальная квота в действительности работает так, как долж- на работать квота в системе с квотой.

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

Чтобы добиться этого, сначала нам нужно будет рассмотреть очень полезную лемму. (Собственно говоря, слово «лемма» означает «вспомогательный результат». В математике леммой обычно называ- ют результат, главное назначение которого — быть использованным при доказательстве другого, более важного результата). Хотя прямо сейчас вам может быть неясно, как мы будем использовать эту лемму, знайте, что она сыграет решающую роль при доказательстве теоремы Эрроу.

Лемма 5.3. Предположим, что мы рассматриваем выборы, в ко- торых участвуют более двух кандидатов и используется избиратель- ная система V, обладающая свойствами универсальности и единогла- сия и удовлетворяющая критерию НПА. Предположим, что В — один из кандидатов на выборах и каждый избиратель помещает его ли- бо первым, либо последним в своем индивидуальном списке предпочте- ний. Тогда в итоговом общественном порядке предпочтений, к кото- рому приводит V, В тоже должен оказаться либо первым, либо по-

следним (даже если половина избирателей ставят В на первое место, а другая половина —на последнее).

Важно заметить, что когда в лемме 5.3 мы говорим, что кандидат стоит на первом или на последнем месте в индивидуальном или обще- ственном порядке предпочтений, мы исключаем возможность того, что этот кандидат может разделить свой порядок с другим кандида- том. Вам будет полезно помнить об этом, когда вы будете отвечать на вопросы из оставшейся части этого раздела.

Для того, чтобы понять, почему лемма 5.3 справедлива, давайте начнем с предположения, что каждый голосующий на выборах дей- ствительно ставит В либо на первое, либо на последнее место в своем списке предпочтений. Других предположений о предпочтениях изби- рателей мы делать не будем.

Вопрос 5.4*. Предположим, что в общественном порядке пред- почтений, к которому приводит V, кандидат В не оказывается ни на первом, ни на последнем месте. Объясните, почему в таком случае должны найтись два таких других кандидата Л и С, что А £ В и В С.

Вопрос 5.5. Какой вывод позволяет вам сделать транзитивность общественного порядка предпочтений об общественном предпочте- нии между А и С в предположении, что А £ В и В > С?

Вопрос 5.6*. Теперь предположим, что каждый избиратель из- менил свой индивидуальный список предпочтений, передвинув С вы- ше А, и не внося никаких других изменений. Повлияет ли это как- нибудь на итоговые общественные предпочтения между А и В или между В и С? Объясните ваш ответ. (Подсказка. Не забудьте, что все избиратели поставили В на первое или на последнее место в своих индивидуальных списках предпочтений.)

Вопрос 5.7. В вопросе 5.6 мы предположили такое изменение в предпочтениях, что во всех бюллетенях С оказалось выше, чем А. Какой вывод об итоговом общественном предпочтении между А и С при таком изменении нам позволяет сделать единогласие?

Вопрос 5,8*. Объясните, как ваши ответы на вопросы 5-5—5-7 приводят к противоречию. Что вы можете заключить о справед- 1ивости леммы 5.3 на основании этого противоречия? Тщательно • кгьясните ваш ответ.

Теперь, когда справедливость леммы 5.3 доказана, будем про- д< >лжать искать нашего потенциального диктатора. С этих пор и до и «троса 5.16 мы будем считать, что имеют место выборы, в которых участвуют больше двух кандидатов, и что принята избирательная

система V, удовлетворяющая универсальности, критерию НПА и еди- ногласию (так что применима лемма 5.3). Для удобства, мы обозна- чим избирателей v_l3 v₂, v₃,v_n. И по причинам, которые станут ясны позже, мы начнем с рассмотрения специального случая, когда все избиратели в системе поставили В на последнее место, как показано в табл. 5.1.

Таблица 5.1

Кандидат В единогласно ранжирован последним

	Избиратели
Место	Vi	v2
Первое	?	?	...	?
Последнее	В	В		В

Вопрос 5.9. Что вы можете заключить о месте В в итоговом об- щественном порядке предпочтений, к которому приводит V, основы- ваясь на том факте, что все избиратели поместили В на последнее место? Какое свойство позволяет вам сделать такой вывод?

Вопрос 5.10*. (а) Предположим, что все избиратели в своих ин- дивидуальных списках предпочтений передвинули В с последнего на первое место. К какому изменению в общественном порядке предпо- чтений это приведет и почему произойдет это изменение?

(б) Предположим, что только некоторые из избирателей в своих индивидуальных списках предпочтений передвинули В с последнего на первое место. Какие при этом могут произойти изменения в ито- говом общественном порядке предпочтений? (Подсказка. Не забудьте о лемме 5.3.)

(в) Предположим, что начиная с v, и далее один за другим по по- рядку, каждый избиратель в своем индивидуальном списке предпо- чтений передвинет В с последнего на первое место. Объясните, поче- му при этом должен найтись один избиратель, допустим, Vy, для кото- рого это перемещение впервые приведет к соответствующему изме- нению в общественном порядке предпочтений?

Избиратель, которого выше мы обозначили v_;-, — особенный в том смысле, что если даже все избиратели до него в своих индивидуаль- ных списках предпочтений передвинули В с последнего на первое ме- сто (как показано в табл. 5.2), никаких изменений в итоговом обще- ственном порядке предпочтений не происходит. А вот как только v.-

Таблица 5 2

Общество ранжирует В последним

	Избиратели
Место	Vi	v2	...	У/-,
Первое	В	В		в	?	?		?
Последнее	?	?			В	В		В

делает то же самое, (как показано в табл. 5.3), то сразу же в итоговом общественном порядке предпочтений В вдруг переходит с последне- го места на первое. В таком случае мы можем назвать v_; ключевым избирателем.

Таблица 5.3

Общество ранжирует В первым

	Избиратели
Место	Vi	v2			У/		...
Первое	В	В		В	В	?	...	?
Последнее	?	?		?	?	В		В

Оказывается, Vj еще и диктатор. Мы докажем этот факт в два >гапа. Сначала мы покажем, что для любой пары кандидатов, в ко- торую В не входит, скажем Л и С, верно утверждение: если для Vj кандидат А предпочтительнее С, то и для общества А будет предпо- чтительнее С. Затем мы покажем, что то же самое справедливо для побой пары кандидатов, в которую В входит.

Пусть на первом этапе А и С представляют собой любых двух кандидатов, отличных от В. Кроме того, предположим, что для Vj кандидат А предпочтительнее С. Мы хотим придти к выводу, что в итоговом общественном порядке предпочтений А будет предпо- чгительнее С. Так как нам нужно показать, что А будет предпочти- тельнее С, не принимая во внимание предпочтения всех избирате- лей за исключением v_;-, то мы проигнорируем предпочтения всех избирателей, кроме v_;-. Единственное, что мы предположили, — что для Vj кандидат А предпочтительнее С. Для удобства мы обозначим соответствующий профиль предпочтений S.

• I лист, Матем. выборов