Теорема Эрроу о диктаторе
\[ \newcommand\cN{{\mathcal{N}}} \newcommand\P{{\mathbb{P}}} \newcommand\E{{\mathbb{E}}} \newcommand\Var{{\mathrm{Var}}} \newcommand\Cov{{\mathrm{Cov}}} \newcommand\Corr{{\mathrm{Corr}}} \]
Выбор между альтернативами
В городе Энске живут \(n\) человек.
По каждому вопросу референдума каждый голосует «за» или «против». Будем кодировать ответ «за» как (+1), а ответ «против» — как (-1).
Жители города хотят придумать функцию общественного выбора \(f\). Эта функция должна ответы всех жителей превращать в выбор общества.
Чего мы хотим от функции \(f\)?
Если все жители голосуют «за», то функция должна говорить, что город «за»,
\[ f(1, 1, 1, \ldots, 1) = 1. \]
И, аналогично, если все жители голосуют «против», то функция должна говорить, что город «против»,
\[ f(-1, -1, -1, \ldots, -1) = -1. \]
Плохо, если функция общественного выбора является диктаторской, то есть, если выбор города полностью продиктован выбором единственного человека. Например, функция \(f(x_1, x_2, \ldots, x_n) = x_2\) является диктаторской: житель номер 2 полностью решает всё.
Функция общественного выбора вида
\[ f(x_1, x_2, \ldots, x_n) = x_i \]
называется диктаторской.
Например, функция \(f(x_1, x_2, x_3) = x_1 x_2 x_3\) для городка из трёх человек диктаторской не является.
Рациональность
На референдуме мы хотим выбрать упорядочить три алтернативы: А, Б и В. Поэтому на референдуме каждого жителя ждут три вопроса.
- Правда ли, что \(A\) лучше \(B\)?
- Правда ли, что \(B\) лучше \(C\)?
- Правда ли, что \(C\) лучше \(A\)?
Обозначим ответы горожан на первый вопрос вектором \(x\), на второй — вектором \(y\), на третий — вектором \(z\).
Назовём тройку ответов на вопросы рациональной, если по ней можно однозначно упорядочить альтернативы.
Например, тройка \((1, -1, 1)\) означает порядок \(С>A>B\), а тройка \((1, 1, 1)\) противоречива.
Выбор (тройка чисел) \((a_1, a_2, a_3)\) называется рациональным, если каждое число \(a_i \in \{-1, +1\}\) и не все три числа равны между собой.
От функции общественного выбора \(f\) мы хотим, чтобы при рациональном выборе каждого жителя выбор города был рациональным.
Функция общественного выбора \(f\) называется рациональной, если при рациональном выборе каждого жителя \((x_i, y_i, z_i)\) выбор города \((f(x), f(y), f(z))\) оказывается рациональным.
Например, диктаторская функция \(f\) является рациональной. Действительно, диктаторская функция обращает внимание только на предпочтения одного индивида. И если этот индивид рационален, то и выбор города будет рациональным.
Внезапно оказывается, других-то рациональных функций нет.
Если функция общественного выбора \(f\) удовлетворяет аксиомам рациональности и единогласия, то она является диктаторской.
Для доказательства будем использовать мощь линейной алгебры и теории вероятностей.
Вспоминаем линейную алгебру
Аргументом функции общественного выбора является вектор из (+1) и (-1). Зададим неожиданное скалярное произведение.
Для произвольных функций общественого выбора \(f\) и \(g\) определим
\[ \langle f, g \rangle = \E(f(X)g(X)), \]
где \(X\) — случайный вектор, все компоненты которого независимы и равны (+1) или (-1).
Подчеркнем, что мы не предполагаем, что жители города на самом деле голосуют случайно и независимо друг от друга. Скалярное произведение — это всего лишь инструмент для изучения функций.
Давайте попробуем посчитать пару скалярных произведений.
Например, возьмём две разных диктаторских функции, \(f(x) = x_1\) и \(g(x) = x_2\). В этом случае \(\langle f, g\rangle = \E(X_1 X_2) = \E(X_1) \E(X_2) = 0\).
Рассмотрим ещё один пример, \(f(x)=x_1 x_2 x_3\), \(g(x) = x_2 x_3 x_5\). Получаем \(\langle f, g\rangle = \E(X_1 X_2^2 X_3^2 X_5) = \E(X_1) \E(X_2^2) \E(X_3^2) \E(X_5) = 0\).
И, конечно, для любой функции общественного выбора \(\langle f, f\rangle = \E(1) = 1\). Если случайную величину, принимающую значения (-1) или (+1) домножить на себя, то всегда будет получаться (+1).
Базис в пространстве всех функций
Рассмотрим множество \(V\) всех действительных функций, заданных на векторах из \(n\) чисел, равных \(+1\) или \(-1\). В этом множестве функций \(V\) есть все функции общественного выбора, но также там есть куча бессмысленных для нас функций, которые хотя бы где-то принимают значения отличные от \(+1\) или \(-1\).
Это множество \(V\) является векторным пространством, так как при сложении двух функций между собой или при умножении функции на число мы снова получим функцию.
Найдём размерность пространства \(V\).
Например, если \(n=3\), то размерность пространства \(V\) равна 8. Существует \(2^3\) возможных значений аргумента \(x\), ведь \(x= (x_1, x_2, x_3)\), а каждый \(x_i \in \{-1, +1\}\). Если не требовать от \(f\) никаких аксиом, то при каждом значении вектора \(x\) мы можем определить функцию \(f\) произвольным образом, то есть для полного определения \(f\) потребуется 8 чисел. В общем случае размерность пространства \(V\) равна \(2^n\).
Можно задать в пространстве \(V\) разные базисы.
Например, можно задать базис из индикаторов каждой возможной точки,
\[ A = \{ I[+++], I[++-], I[+-+], \ldots, I[---]\} \]
Функция \(I[+-+]\) равна 1 в точке \(x = (+1, -1, +1)\) и равна 0 в остальных точка.
Можно задать более хитрый базис!
\[ B = \{1, x_1, x_2, x_3, x_1 x_2, x_1 x_3, x_2 x_3, x_1 x_2 x_3\} \]
В множестве \(B\) ровно 8 элементов. Чтобы доказать, что \(B\) — базис осталось доказать только независимость. Заметим, что согласно нашему скалярному произведению все векторы в \(B\) имеют единичную длину и ортогональны друг другу, \(\langle b_i, b_i \rangle =1\), \(\langle b_i, b_j \rangle = 0\) при \(i\neq j\). Из ортогональности следует независимость.
Предположим противное, что одна из функций в множестве \(B\) выражается через другие. К примеру пусть функция \(b_3\) выражается через остальные функции из множества \(B\):
\[ b_3 = \alpha_1 b_1 + \alpha_2 b_2 + \alpha_4 b_4 +\ldots + \alpha_8 b_8. \]
Посчитаем скалярное произведение левой и правой частей с \(b_3\). Слева окажется \(1\), а справа получится сумма нулей. Значит, функция \(b_3\) не выражается через остальные функции из \(B\). Аналогично доказывается, что ни одна из функций не может быть выражена через другие. Таким образом, \(B\) — действительно базис.
Для произвольного количества жителей \(n\) базис \(B\) всех функций, заданных на векторах ответах жителей, состоит из \(2^n\) функций. Каждая функция базиса является перемножений некоторых \(x_i\).
<— TODO: надо ли? —> Для удобства обозначим элементы базиса \(B\) покороче, упомянув перемножаемые номера \(x_i\) в одном общем индексе. Например,
\[ x_{1, 2, 7} = x_1 x_2 x_7. \]
Разложение по базису
Разложим для тренировки пару функций по базису \(B\). Первое разложение нам понадобится для доказательства, а второе — просто неплохое упражнение на понимание.
Индикатор рациональности выбора \(R(a, b, c)\) равна +1 для рационального выбора \((a, b, c)\) и 0 для нерационального выбора из трех одинаковых чисел, \(R(1, 1, 1) = R(-1, -1, -1) =0\).
Разложите функцию \(R\) по базису \(B\).
В силу симметрии нам требуется найти всего лишь четыре константы:
\[ R(x) = \alpha + \beta(x_1 + x_2 + x_3) + \gamma(x_1 x_2 + x_1 x_3 + x_2 x_4) + \delta x_1 x_2 x_3. \]
Составляем четыре уравнения:
\[ \begin{cases} R(1, 1, 1) = \alpha + 3\beta + 3\gamma + \delta = 0 \\ R(-1, -1, -1) = \alpha - 3\beta + 3\gamma - \delta = 0 \\ R(1, 1, -1) = \alpha + \beta - \gamma - \delta = 1 \\ R(-1, -1, 1) = \alpha - \beta - \gamma + \delta = 1 \\ \end{cases} \]
Замечаем, что функция чётная, поэтому \(\beta = \delta = 0\).
\[ \begin{cases} R(1, 1, 1) = \alpha + 3\gamma = 0 \\ R(1, 1, -1) = \alpha - \gamma = 1 \\ \end{cases} \]
Получаем \(\beta = \delta = 0\), \(\gamma = -1/4\), \(\alpha = 3/4\) и
\[ R(x) = 0.75 - 0.25(x_1 x_2 + x_1 x_3 + x_2 x_4). \]
Рассмотрим город из трёх жителей и мажоритарную функцию общественного выбора \(M(x_1, x_2, x_3)\). Мажоритарная функция функция \(M\) выбирает тот ответ, которые выбрало большинство жителей города.
Разложите функцию \(M\) по базису \(B\).
Является ли функция \(M\) рациональной?
В силу симметрии нам требуется найти всего лишь четыре константы:
\[ M(x) = \alpha + \beta(x_1 + x_2 + x_3) + \gamma(x_1 x_2 + x_1 x_3 + x_2 x_4) + \delta x_1 x_2 x_3. \]
Если помножить на (-1) выбор каждого жителя, выбор города множится на (-1). Получается, что функция \(M\) нечётная, поэтому \(\alpha = \gamma = 0\).
Составляем два уравнения:
\[ \begin{cases} M(1, 1, 1) = 3\beta + \delta = 1 \\ M(1, 1, -1) = \beta - \delta = 1 \\ \end{cases} \]
Получаем \(\beta = 0.5\), \(\delta = -0.5\), \(\gamma = 0\), \(\alpha = 0\) и
\[ M(x) = 0.5(x_1 + x_2 + x_3) - 0.5x_1 x_2 x_3. \]
Теперь разложим по базису \(B\) произвольную функцию общественного выбора \(f\). Обозначим коэффициент перед \(x_S\) как \(\hat f_S\).
\[ f = \hat f_{\emptyset} \cdot 1 + \hat f_1 \cdot x_1 + \ldots + \hat f_{1,2,7} x_{1,2,7} + \ldots \]
Если компактно,
\[ f = \sum_S \hat f_S x_S, \]
где подмножество \(S\) — часть множества натуральных чисел от \(1\) до \(n\), \(S \subset \{1, 2, \ldots, n\}\).
Теперь теорему Эрроу можно переформулировать на языке линейной алгебры.
В разложении по базису \(B\) рациональной единогласной функции общественного выбора \(f\) все коэффициенты за одним исключением равны 0. Единственный ненулевой коэффициент это некое \(\hat f_i = 1\).
На охоту за коэффициентами
В теории рядов Фурье известно тождество Парсеваля.
\[ 1=\langle f, f\rangle = \sum_S \hat f_S^2 \]
Вспомним, что скалярное произведение \(\langle f, f\rangle\) считается как ожидание \(\E(f(X)f(X))\) в случайном векторе \(X\), компоненты которого равновероятно равны (-1) и (+1).
Замечаем, что \(f(X)f(X) = 1\), поэтому \(\langle f, f\rangle = 1\).
Разложим внутри скалярного произведения каждую \(f\) по базису
\[ \langle \sum_S \hat f_S x_S, \sum_Q \hat f_Q x_Q \rangle = 1 \]
Раскрываем скобки и вспоминаем, что наш базис — ортонормальный, \(\langle x_S, x_Q \rangle = 0\), если подмножества \(S\) и \(Q\) не совпадают, а \(\langle x_S, x_S \rangle = 1\).
Тем самым,
\[ 1=\langle f, f\rangle = \sum_S \hat f_S^2 \]
Мы доказали, что квадраты коэффициентов \(\hat f_S^2\) в сумме дают единицу. Заметим, что мажоритарная функция из упражнения удовлетворяет этому критерию, \(0.5^2 + 0.5^2 + 0.5^2 + (-0.5)^2=1\).
Почти все коэффициенты разложения — нули
Теперь мы готовы доказать, что все коэффициенты помимо коэффициентов при отдельных \(x_i\) равны нулю, то есть, что функция \(f\) имеет всего лишь вид
\[ f(x) = \alpha_1 x_1 + \alpha_2 x_2 + \ldots +\alpha_n x_n, \]
а более сложные слагаемые вида \(x_1 x_7\), \(x_2 x_5 x_9\) отсутствуют.
… тут дописать …
Ищем диктатора
Итак, мы доказали, что функция \(f\) имеет вид
\[ f(x) = \alpha_1 x_1 + \alpha_2 x_2 + \ldots +\alpha_n x_n. \]
Заметим, что \(f\) принимает только значения \((-1)\) и \((+1)\), поэтому при изменении любого \(x_i\) с (-1) до (+1) функция \(f\) либо не должна измениться совсем, либо должна измениться ровно на 2.
Следовательно, каждое \(\alpha_i\) может принимать только значения \(0\), \(-1\) или \(1\).
Из равенства Парсеваля следует, что \(\sum \alpha_i^2=1\), поэтому ровно одно \(\alpha_i\) отлично от нуля. По аксиоме единигласия это \(\alpha_i = 1\).
Ура, мы доказали, теорему Эрроу. Любая рациональная единогласная функция общественного выбора является диктаторской, и имеет вид
\[ f(x) = x_i. \]
У Джеймса Мерфи в (Murphy III 2015) этот кусок доказательства концептуально сложней, но трюк настолько виртуозен, что его стоит повторить.
Насколько нерационально правило простого большинства?
….
Источники
В основном изложение следует статье (Murphy III 2015). Немного упростил поиск коэффициентов в функции рациональности и участок доказательства с равенством нулю всех \(\alpha_i\) кроме одного, добавил больше примеров.
На Бесконечной салфетке Эвана Чена (Chen 2016) есть похожее доказательство. И это классный повод взглянуть в этот шикарный текст, если читатель его ещё не видел.