Теорема Ерроу

Теорема Ерроу (також відома як «Парадокс Ерроу», англ. Arrow's paradox) — теорема про неможливість «колективного вибору». Сформульована американським економістом Кеннетом Ерроу в 1951 році.

Кеннет Ерроу

Зміст цієї теореми полягає в тому, що в рамках ординалістського підходу не існує методу об'єднання індивідуальних вподобань для трьох чи більше альтернатив, який задовольняв би деякі повністю справедливі умови та завжди давав би логічно несуперечливий результат.

Ординалістський підхід базується на тому, що вподобання індивідуума відносно запропонованих для вибору альтернатив не можуть вимірятись кількісно, а тільки якісно, тобто одна альтернатива краща чи гірша за іншу.

У рамках кардиналістського підходу, що пропонує кількісне вимірювання вподобань, теорема Ерроу в загальному випадку не працює.

Формулювання

Формулювання 1951 року

Нехай є N≥2 виборців, які голосують за n≥3 кандидатів (в термінах теорії прийняття рішень кандидатів прийнято називати 'альтернативами' ). У кожного виборця є упорядкований список альтернатив. Система виборів - функція, що перетворює набір з N таких списків (профіль голосування) до загального упорядкованого списку.

Система виборів може мати такі властивості:

Універсальність

Для будь-якого профілю голосування існує результат - впорядкований список з n альтернатив.

Повнота

Система голосування може давати як результат усі n ! перестановок альтернатив.

Монотонність

Якщо у всіх N списках деяка альтернатива x залишиться на місці або підніметься вище, а порядок інших не зміниться, в загальному списку x повинен залишитися на місці або піднятися.

Відсутність диктатор а

Немає виборця, перевагу якого визначав би результат виборів незалежно від уподобань інших виборців.

Незалежність від сторонніх альтернатив

Якщо профіль голосування зміниться так, що альтернативи x і y у всіх N списках залишаться в тому ж порядку, то не зміниться їх порядок і в остаточному результаті.

Для N≥2 і n≥3 не існує системи голосування, яка відповідає всім п'яти умовам.

Формулювання 1963 року

У формулюванні 1963 року умови Ерроу такі:

універсальність

Відсутність диктатора

Незалежність від сторонніх альтернатив

Оптимум Парето, або принцип одноголосності

якщо у кожного виборця альтернатива x в списку стоїть вище y , це ж має бути і в остаточному результаті.

Для N≥2 і n≥3 не існує системи голосування, яка відповідає всім чотирьом умовам.

Доказ теореми Ерроу

• ${\displaystyle O}$ — множина випадків, які кожен агент ранжує відповідно до своїх уподобань.
• ${\displaystyle L_{i}}$ — лінійний порядок вподобань ${\displaystyle i}$-го агента на множині ${\displaystyle O}$ заданий відношенням ${\displaystyle \succ _{i}}$.
• ${\displaystyle [\succ ']}$ — профіль вподобань (кортеж, елементами якого є переваги всіх агентів).
• ${\displaystyle W:L^{N}\to L_{W}}$ — функція суспільного добробуту.
• ${\displaystyle \succ _{W}}$ — колективні вподобання.

Дамо формальні визначення:

• Парето-ефективність: ${\displaystyle W}$ парето-ефективна, якщо для будь-яких випадків ${\displaystyle o_{1},o_{2}\in O,\forall i(o_{1}\succ _{i}o_{2})\Rightarrow (o_{1}\succ _{W}o_{2})}$.
• Незалежність від сторонніх альтернатив:  ${\displaystyle W}$ незалежна від сторонніх альтернатив, якщо для будь-яких випадків ${\displaystyle o_{1},o_{2}\in O}$ і для будь-яких двох профілів вподобань${\displaystyle [\succ ']}$ і ${\displaystyle [\succ '']\in L_{n},\forall i(o_{1}\succ '_{i}o_{2}\Leftrightarrow o_{1}\succ ''_{i}o_{2})\Rightarrow (o_{1}\succ _{W([\succ '])}o_{2}\Leftrightarrow 0_{1}\succ ''_{W([\succ ''])}o_{2})}$.
• Відсутність диктатора: вважаємо, що для ${\displaystyle W}$ відсутній диктатор, якщо не існує такого ${\displaystyle i}$, що ${\displaystyle \forall o_{1},o_{2}\in O(o_{1}\succ _{i}o_{2}\Rightarrow o_{1}\succ _{W}o_{2})}$.
• Теорема Ерроу: якщо ${\displaystyle |O|\geq 3}$, то будь-яка Парето-ефективна, незалежна від сторонніх альтернатив функція суспільного добробуту ${\displaystyle W}$ має диктатора.

Доказ проведемо в 4 етапи.

Етап 1.

Якщо кожен агент розміщує результат ${\displaystyle b}$ нагору або до самого низу свого списку переваг (при цьому не потрібно, щоб все агенти діяли однаково), то і в ${\displaystyle \succ _{W}}$ результат ${\displaystyle b}$ теж буде або вгорі, або внизу списку.

Візьмемо довільний профіль ${\displaystyle [\succ ]}$ такий, що в ньому для всіх агентів ${\displaystyle i}$ результат ${\displaystyle b}$ знаходиться або зверху, або знизу списку вподобань ${\displaystyle \succ _{i}}$. Тепер припустимо, що наше твердження неправильне, тобто існують такі ${\displaystyle a,c\in O}$, що ${\displaystyle a\succ _{W}b}$ и ${\displaystyle b\succ _{W}c}$. Тоді змінимо профіль ${\displaystyle [\succ ]}$ так, щоб для всіх агентів виконувалось ${\displaystyle c\succ _{i}a}$, не змінюючи при цьому ранжування інших результатів. Позначимо отриманий профіль ${\displaystyle [\succ ']}$. Так як після такої модифікації результат b для кожного агента все одно залишиться або на найвищій, або на найнижчій позиції в списку його переваг, то з незалежності W від сторонніх альтернатив можна зробити висновок, що і в новому профілі ${\displaystyle a\succ _{W}b}$ і ${\displaystyle b\succ _{W}c}$. Отже, в силу транзитивності ${\displaystyle \succ _{W}}$ отримаємо ${\displaystyle a\succ _{W}c}$. Але ми припустили, що для всіх агентів ${\displaystyle c\succ _{i}a}$, тоді в силу Парето-ефективності повинно бути ${\displaystyle c\succ _{W}a}$. Отримане протиріччя доводить твердження.

Етап 2.

Для будь-якого результату ${\displaystyle b}$ існує агент, який є центральним у тому сенсі, що, змінивши свій голос, він може перемістити результат ${\displaystyle b}$ з найнижчої позиції в списку ${\displaystyle \succ _{W}}$ до найвищої. Іншими словами, знайдуться два профілі ${\displaystyle [\succ ^{1}]}$ и ${\displaystyle [\succ ^{2}]}$, що відрізняються тільки вподобаннями агента ${\displaystyle i}$, що ${\displaystyle b}$ знаходиться в кінці списку для ${\displaystyle [\succ _{W}^{1}]}$ і на початку списку для ${\displaystyle [\succ _{W}^{2}]}$.

Розглянемо будь-який профіль переваг, у якому все агенти розташували результат ${\displaystyle b}$ унизу свого списка вподобань ${\displaystyle \succ _{i}}$. Зрозуміло, що і в ${\displaystyle \succ _{W}}$ результат ${\displaystyle b}$ знаходиться на найнижчій позиції (в силу Парето-ефективності). Нехай все агенти почали по черзі переставляти результат ${\displaystyle b}$ з найнижчої на найвищу позицію в своїх списках переваг, не змінюючи при цьому ранжування інших результатів. Коли все агенти поставлять результат ${\displaystyle b}$ першим в своєму списку переваг, він буде першим і для ${\displaystyle \succ _{W}}$. Таким чином, у якийсь момент ${\displaystyle \succ _{W}}$ зміниться. Нехай ${\displaystyle n^{*}}$ — агент, який, переставив таким чином ${\displaystyle b}$, змінив ${\displaystyle \succ _{W}}$ (уперше). позначимо ${\displaystyle [\succ ^{1}]}$ — профіль переваг як раз до того, як ${\displaystyle n^{*}}$ переміщень ${\displaystyle b}$, а ${\displaystyle [\succ ^{2}]}$ — профіль переваг відразу ж після того, як ${\displaystyle n^{*}}$ перемістив ${\displaystyle b}$. Таким чином, в ${\displaystyle [\succ ^{2}]}$ результат ${\displaystyle b}$ змінив позицію в ${\displaystyle \succ _{W}}$, при цьому для всіх агентів ${\displaystyle b}$ знаходиться або на самому верхньому, або на найнижчій позиції ${\displaystyle \succ _{i}}$. Отже, в силу твердження, доведеного на Етапі 1, в ${\displaystyle \succ _{W}}$ результат ${\displaystyle b}$ займає найвищу позицію.

Етап 3.

${\displaystyle n^{*}}$ — диктатор над усіма парами ${\displaystyle <a,c>}$, що не включає в себе ${\displaystyle b}$.

Виберемо з пари ${\displaystyle <a,c>}$ будь-який елемент. Без втрати спільності, виберемо a. Далі з профілю ${\displaystyle [\succ ^{2}]}$ побудуємо ${\displaystyle [\succ ^{3}]}$ наступним чином: в ${\displaystyle \succ _{n^{*}}}$,перемістимо результат a на першу позицію, залишивши інше ранжування незмінним; довільним чином для всіх інших агентів поміняємо місцями один з одним ${\displaystyle a}$ і ${\displaystyle c}$. Тоді, як і в ${\displaystyle [\succ ^{1}]}$ отримаємо, що ${\displaystyle a\succ _{W}b}$ (В силу незалежності від сторонніх альтернатив) і, як і в ${\displaystyle [\succ ^{2}]}$ отримаємо, що ${\displaystyle b\succ _{W}c}$. Тоді ${\displaystyle a\succ _{W}c}$. Тепер побудуємо профіль переваг ${\displaystyle [\succ ^{4}]}$ наступним чином: для всіх агентів помістимо результат ${\displaystyle b}$ на довільну позицію в списку вподобань ${\displaystyle \succ _{i}}$, для агента ${\displaystyle n^{*}}$ помістимо результат ${\displaystyle a}$ в довільну позицію до результату ${\displaystyle c}$. Зрозуміло, що в силу незалежності від сторонніх альтернатив ${\displaystyle a\succ _{W}c}$. Ми отримали, що всі агенті, крім ${\displaystyle n^{*}}$ мають абсолютно довільні профілі вподобань, а результат ${\displaystyle a\succ _{W}c}$ вийшов виходячи тільки лише з припущення, що ${\displaystyle a\succ _{n^{*}}c}$.

Етап 4.

${\displaystyle n^{*}}$ — диктатор над усіма парами ${\displaystyle <a,b>}$.

Розглянемо який-небудь результат с. В силу Етапу 2 існує деякий центральний агент ${\displaystyle n^{**}}$ для цього результату, він же є диктатором для всіх пар ${\displaystyle <A,B>}$, де, зокрема, ${\displaystyle A=a,B=b}$. Якби агент ${\displaystyle n^{**}\neq n^{*}}$ був диктатором над ${\displaystyle <a,b>}$, ніяка заміна переваг агента ${\displaystyle n^{*}}$ не могла б поміняти ранжування ${\displaystyle a}$ і ${\displaystyle b}$ в ${\displaystyle \succ _{W}}$. Але на Етапі 2 агент ${\displaystyle n^{*}}$ переставив ${\displaystyle b}$ з останнього місця на перше в ${\displaystyle \succ _{W}}$, і таким чином був зобов'язаний поміняти місцями ${\displaystyle a}$ і ${\displaystyle b}$. Отже, можна зробити висновок, що ${\displaystyle n^{**}}$ Зівпадає з ${\displaystyle n^{*}}$, тобто ${\displaystyle n^{*}}$ і є диктатором.

Доказ завершено.

Див. також

• Парадокс Кондорсе — парадокс виборів, узагальненням якого стала теорема Ерроу.

Посилання

• Теорема о невозможности в задаче пропорционального представительства

Примітки

1. Kenneth J. Arrow, 1951, 2nd ed., 1963. Social Choice and Individual Values, Yale University Press.
2. Cardinal Voting: The Way to Escape the Social Choice Impossibility (англ.)
3. The Possibility of Social Choice, p.189 (англ.)