Для функций ценности самого общего вида мы в лекции 6 уже говорили о теореме Гиббарда-Саттертуэйта (теорема 6.2). Мы доказывали, что если допустить любые порядки на множестве возможных исходов, то реализовать можно только диктаторские функции социального выбора, выгодные ровно одному участнику.
Результат, конечно, весьма печальный. Но неужели ничего нельзя сделать? В математике обычно, если общий факт никак не доказывается или общая конструкция никак не строится, пытаются рассмотреть ограниченную постановку, которая, однако, продолжает иметь смысл.
Для теоремы Гиббарда-Саттертуэйта аналогичный вопрос разумно было бы задать для квазилинейных предпочтений — для ситуации, когда функция полезности каждого агента представляет собой разность между его внутренней ценностью от наступившего исхода и той ценой, которую он должен в результате этого исхода заплатить. Такие предпочтения — более чем естественное предположение; в самом деле, ну как же еще? Но для этих предпочтений теорема Гиббарда-Саттертуэйта уже не слишком-то применима: такого, как там, произвольного порядка предпочтений на всем множестве исходов уже может не получиться построить. Поэтому и теорема о невозможности — а в этой лекции мы опять будем доказывать теорему о невозможности — здесь уже не такая пессимистичная, как теорема Гиббарда-Саттертуэйта. Я бы даже назвал ее не теоремой о невозможности, а теоремой классификации: да, мы классифицируем все реализуемые функции социального выбора, но их окажется вовсе не так мало, и среди них будут практически все естественные функции.
Теорема Робертса, как нетрудно догадаться, доказана была Кевином Робертсом [71]. Его доказательство было достаточно сложным технически, и за деревьями трудно было рассмотреть лес, то есть основную базовую идею доказательства. Поэтому доказательства, которые мы приводим в этой лекции, отличаются от оригинального доказательства Робертса; мы изложим два (достаточно существенно отличающихся друг от друга) упрощенных доказательства теоремы Робертса, представленных не так давно Лави, Му-алем и Нисаном [40].
Здесь, однако, стоит заметить, что мы докажем теорему Робертса только для случая неограниченного множества типов. В реальной жизни множества типов часто бывают ограничены, и структура этих ограничений бывает довольно прихотливой. Но в общем случае ответа на этот вопрос до сих пор нет, есть только частные результаты [26,40]. Поэтому будем излагать то, что есть.
Для начала напомним основные определения. У механизма есть набор исходов $$\mathcal O$$ (в этой лекции мы их будем обозначать через $$x,y,z,..$$.). Есть $$N$$ игроков, и у каждого есть свой тип $$v_i$$. Этот тип — просто набор ценностей, которые игрок может присвоить каждому исходу. Например, в ситуации аукциона по продаже одного предмета, о которой мы часто говорили, набор исходов $$\mathcal O$$ — это то, кому достается вещь (фактически множество исходов равно множеству агентов), а тип $$v_i$$ — это функции полезности агента от возможного исхода, которые равны нулю, если эту вещь отдали кому-то другому, или самой ценности, если вещь дали данному игроку:
$$v_i(x) = \begin{cases}v_i, x = i, \\ 0, \text{в противном случае}.\end{cases}$$Определение 8.1.Множество типов $$\mathbf V = V_1\times V_2\times\ldots\times V_N$$ называется неограниченным, если $$V_i = \mathbb R^{|\mathcal O|}$$ для каждого $$i$$.
В дальнейшем в этой лекции мы всегда будем рассматривать только неограниченные множества типов. Разумеется, суть здесь не в плюс-минус бесконечностях, подошел бы и любой открытый интервал — важно, что очередной агент имеет возможность выбрать ставку, которая строго больше всех остальных (да и вообще может находиться где угодно относительно других ставок — между любыми двумя вещественными числами найдется изрядное количество других вещественных чисел).
Следующий объект, который нас интересует, — это функция социального выбора $$f:\mathbf V\to\mathcal O$$. Можно без потери общности предположить, что $$f$$ сюръективна; если это не так, мы просто ограничим $$\mathcal O$$ на $$im(f)\subset\mathcal O,$$ не потеряв ни одного реально возможного исхода, то есть не изменив ни стратегий агентов, ни результатов этих стратегий.
Кроме того, механизм берет с игроков платежи $$p_i:\mathbf V\to\mathbb R$$. А игроки квазилинейны, то есть они хотят максимизировать себе функцию дохода (utility function)
$$u_i = v_i\left(\vphantom{1^2}f(\mathbf v)\right) - p_i(\mathbf v).$$В этой лекции мы будем вести речь о реализации функций социального выбора в
Определение 8.2.
От нас в конструкции механизма зависит только $$p_i$$ (потому что распределение исходов задается функцией социального выбора), поэтому задача сводится к следующей: нам нужно так подобрать значения $$p_i,$$ чтобы в конце концов эгоистичные агенты, действуя для максимизации своих $$u_i$$ (которые у них квазилинейные), максимизировали $$f$$.
Формально говоря, для каждого $$i,$$ каждого $$\mathbf v_{-i}\in \mathbf V_{-i}$$ и каждого $$v^\prime\in V_i$$
В лекции 4 мы уже говорили, что все функции социального выбора, оптимизирующие суммарную полезность, она же общественное благосостояние, правдиво реализуемы VCG-платежами (точнее говоря, функция социального выбора, которая оптимизирует общественное благосостояние – она одна, и она реализуема посредством VCG-механизма). Более того, легко видеть, что точно так же реализуемы и функции социального выбора, оптимизирующие взвешенное общественное благосостояние, то есть функции, которые с разными весами учитывают счастье разных агентов.
Задача этой лекции состоит в том, чтобы доказать обратное утверждение. Мы докажем, что оптимизацией таких вот "взвешенно-эффективных" функций социального выбора, собственно, и исчерпываются все возможности, которые у нас есть с квазилинейными агентами.
Теорема 8.1. (Теорема Робертса) Пусть $$|\mathcal O|\ge 3,$$ и множество типов $$\mathbf V$$ — неограниченное. Тогда для каждой
Оба доказательства теоремы Робертса (да и исходное) основаны на условиях монотонности. Мы сначала докажем, что для правдивой реализуемости $$f$$ должна удовлетворять этим условиям, а затем, в доказательстве самой теоремы, докажем, что функция, удовлетворяющая таким условиям, имеет требуемый вид. Начнем со свойства слабой монотонности.
Определение 8.3. W-MON — слабая монотонность (
Иначе говоря, если игрок $$i$$ может изменить свой тип с $$v_i$$ на $$v^\prime_i,$$ при этом изменив исход с $$x$$ на $$y,$$ то разность его значений для $$y$$ должна быть не меньше, чем разность его значений для $$x$$. Вот так, ненавязчиво, здесь появляются разности, которые будут ключевыми объектами в дальнейших рассуждениях. %Стоит также заметить, что разности нужно использовать из-за квазилинейности.
Лемма 8.1. Всякая доминантно реализуемая функция социального выбора $$f$$ удовлетворяет W-MON.
Доказательство. Во-первых, докажем, что $$p_i$$ не зависит от $$v_i$$. Другими словами, если функция правдиво реализуется механизмом, то функция платежа уже не зависит от ставки.
Предположим противное. Что значит, функция платежа зависит от ставки? Это значит, что есть такие $$\mathbf v_{-i},$$ $$x,$$ $$v_i$$ и $$v^\prime_i,$$ что исход один и тот же, но платеж при этом разный:
$$f(v_i, \mathbf v_{-i}) = f(v^\prime_i, \mathbf v_{-i}) = x,\quad p_i(v_i,\mathbf v_{-i}) < p_i(v^\prime_i, \mathbf v_{-i}).$$Тогда очевидно, что при векторе типов $$\mathbf v$$ игроку $$i$$ выгодно солгать. Следовательно, у
Теперь зафиксируем $$\mathbf v_{-i}, v_i, v^\prime_i, x, y$$ так, как было в определении W-MON. Из-за правдивой реализуемости должно быть верно, что
$$v_i(x) - p_i(x, \mathbf v_{-i}) \ge v_i(y) - p_i(y, \mathbf v_{-i}),$$иначе при типе $$v_i$$ игрок $$i$$ сможет улучшить себе доход, солгав $$v^\prime_i$$. Аналогично,
$$v^\prime_i(y) - p_i(y, \mathbf v_{-i}) \ge v^\prime_i(x) - p_i(x, \mathbf v_{-i}).$$Сложив эти два неравенства и сократив $$p_i$$ получим искомое условие W-MON. Таким образом, W-MON необходимо для правдивой реализуемости.
Второе условие монотонности — свойство
Определение 8.4. Функция социального выбора $$f$$ удовлетворяет
для всех $$y\in\mathcal O\setminus x$$ и всех $$i,$$ то $$f(v^\prime)$$ тоже равно $$x$$.
Свойство
Лемма 8.2. Всякая доминантно реализуемая функция социального выбора $$f$$ удовлетворяет
Доказательство. Мы уже доказали, что она удовлетворяет W-MON. Теперь зафиксируем типы $$v$$ и $$v^\prime$$ из определения
Тогда
$$f(\mathbf v^0) = x,\quad \mathbf v^0 = v,\quad \mathbf v^N = v^\prime.$$Предположим теперь противное: пусть $$f(\mathbf v^{i-1}) = x,$$ а $$f(\mathbf v^i) = y\neq x$$. Тогда можно применить W-MON:
$$v^\prime_i(y) - v_i(y) \ge v^\prime_i(x) - v_i(x),$$что противоречит предположению
Мы будем пользоваться
Лемма 8.3. Пусть функция социального выбора $$f$$ удовлетворяет
Доказательство. Так как в каждой компоненте имеет место строгое неравенство, то, следовательно, можно построить вектор $$\delta > \bf 0,$$ равный разности двух векторов из исходного неравенства:
$$\delta = \mathbf v^\prime(y) - \mathbf v(y) - \mathbf v^\prime(x) + \mathbf v^\prime(x)\in\mathbb R^N.$$Кроме того, для каждого $$i$$
$$v_i(x) - v^\prime_i(x) - \frac{\Delta_i}2 = v_i(y) - v^\prime_i(y) + \frac{\Delta_i}2 > v_i(y) - v^\prime_i(y).$$Определим теперь новый тип $$\mathbf v^{\prime\prime}\in\mathbf V$$:
$$v^{\prime\prime}_i(z) = \begin{cases} \min\{v_i(z), v^\prime_i(z) + v_i(x) - v^\prime_i(x)\} - \Delta_i, z\neq x,y,\\ v_i(x) - \frac{\Delta_i}2, z = x,\\ v_i(y), z = y. \end{cases}$$Это сугубо техническая конструкция, которая нужна для того, чтобы придти к противоречию: при такой конструкции из
С одной стороны получаем, что
$$v^{\prime\prime}_i(y) - v_i(y) = 0 > v^{\prime\prime}_i(z) - v_i(z),$$и из
С другой стороны, для $$z\neq x,y$$
$$v^{\prime\prime}_i(z) \le v^\prime_i(z) + v_i(x) - v^\prime_i(x) - \Delta_i,$$и
$$v^{\prime\prime}_i(x) - v^\prime_i(x) = v_i(x) - v^\prime_i(x) - \frac{\Delta_i}2 > v^{\prime\prime}_i(z) - v^\prime_i(z).$$Анналогично для $$z=y$$. Тогда из
Теперь, когда мы изучили все дополнительные леммы об условиях монотонности, можно наконец-то перейти к доказательствам собственно теоремы Робертса.
Чтобы показать, что функция — это аффинный максимизатор, на самом деле нужно изучать разности. Это потому, что аффинная максимизация на самом деле
где $$f(v) = x\neq y$$ (рекомендуем читателю не лениться и проверить эту эквивалентность). Мы будем изучать структуру этих самых разностей.
Главное множество, которое мы будем изучать, — это
$$P(x,y) = \left\{\vphantom{1^2}\alpha\in\mathbb R^N\mid \exists \mathbf v: \mathbf v(x) - \mathbf v(y) = \alpha, f(\mathbf v) = x\right\}.$$Проще говоря, если $$f(\mathbf v) = x,$$ то $$\mathbf v(x) - \mathbf v(y)\in P(x,y)$$.
В течение доказательства мы увидим, какова структура множеств $$P(x,y),$$ и в конце концов покажем, что $$P(x,y)$$ — это полупространство. В частности, мы сделаем два важных замечания о структуре $$P(x,y)$$. Во-первых,
$$\begin{equation} \alpha\in P(x,y)\text{ тогда и только тогда, когда }-\alpha\notin P(y,x), \end{equation}$$причем внутренности $$P(x,y)$$ и $$P(y,x)$$ не пересекаются.
А во-вторых, для внутренних точек упомянутых множеств
$$\begin{equation} P(x,y) + P(y, z) = P(x,z). \end{equation}$$Для чего нужны эти свойства? Предположим, что $$\bf 0\in P(x,y)$$ для всех $$x,y\in\mathcal O$$ (на самом деле это не обязательно так, и нам позже придется сместить множества $$P(x,y)$$ ). Тогда по второму условию все $$P(x,y)$$ равны. Введем новое обозначение – пусть они равны $$C$$. По первому условию $$C\cup -C = \mathbb R^N$$: если $$\alpha\notin C,$$ то $$-\alpha\in C$$. Также из первого условия следует, что $$C$$ —
Таким образом, $$C$$ и $$-C$$ покрывают все пространство, выпуклы, и их внутренности не пересекаются. Это в точности означает, что они являются подпространствами.
Теперь, объяснив идею будущего доказательства, перейдем к нему самому. Начнем с простейших свойств $$P(x,y)$$. Так как $$f$$ — сюръекция, то $$P(x,y)$$ непусто для любых $$x$$ и $$y$$. Также,
$$\begin{equation} \text{если }\alpha\in P(x,y),\text{ то }\forall\ \delta>\bf 0\in\mathbb R^N\quad \alpha+\delta\in P(x,y). \end{equation}$$Чтобы это доказать, рассмотрим $$v$$: $$f(v) = x$$ и $$\mathbf v(x) - \mathbf v(y) = \alpha$$. Увеличим $$\mathbf v(x)$$ на $$\delta$$ (мы можем это сделать, так как множества типов $$\mathbf V$$ у нас неограниченные), и получится, что $$\alpha+\delta$$ тоже будет лежать в $$P(x,y)$$.
Следующая лемма докажет нам свойство 8.1 для внутренних точек множества $$P(x,y)$$.
Лемма 8.4. Рассмотрим произвольные векторы $$\alpha, \epsilon\in P(x,y)$$. Тогда
$$\begin{array}{rlcl} \text{если }\alpha-\epsilon\in P(x,y), \text{ то } -\alpha\notin P(y,x),\\ \text{а если }\alpha\notin P(x,y), \text{ то } -\alpha\in P(y,x). \end{array}$$Доказательство. Сначала докажем первую часть леммы. Предположим противное: пусть, наоборот, $$-\alpha\in P(y,x)$$. Тогда существует такой вектор типов $$\mathbf v,$$ что
$$\mathbf v(y) - \mathbf v(x) = -\alpha,\text{ и }f(\mathbf v) = y.$$Но так как $$\alpha-\epsilon\in P(x,y),$$ то, значит, существует такой вектор типов $$\mathbf v^\prime,$$ что $$\mathbf v^\prime(x) - \mathbf v^\prime(y) = \alpha-\epsilon,$$ и $$f(\mathbf v^\prime) = x$$. Тогда верно, что
$$\mathbf v(x)-\mathbf v(y) = \alpha > \mathbf v^\prime(x) - \mathbf v^\prime(y) = \alpha-\epsilon,$$а это противоречит лемме 8.3. Вторая часть леммы доказывается абсолютно аналогично — ее мы оставим читателю.
Пока что мы доказали, что внутренние области $$P(x,y)$$ и $$P(y,x)$$ не пересекаются, и объединение $$P(x,y)$$ и $$-P(y,x)$$ составляет все пространство.
Отметим еще, что из свойства 8.3 следует, что граница у $$P(x,y)$$ монотонно невозрастающая. Действительно, если граница будет возрастающей, то тогда мы сможем прибавить $$\alpha$$ к $$\delta$$ и попасть вне $$P(x,y)$$.
Осталось только показать, что границы являются гиперплоскостями, и тогда мы докажем все необходимые свойства $$P(x,y)$$. Также стоит показать, что $$P(x,y)=P(y,x)$$.
Следующая лемма — это доказательство свойства 8.2. В ней понятие "внутренней точки" приобретает исконный смысл, по определению: если $$\alpha\in P(x,y)$$ — внутренняя точка, то, значит, для всех достаточно коротких векторов $$\epsilon^\alpha\in\mathbb R^N$$ верно, что $$\alpha-\epsilon^\alpha\in P(x,y)$$.
Лемма 8.5. Рассмотрим некоторые векторы $$\alpha,\beta\in\mathbb R^N$$ и некоторые векторы $$\epsilon^\alpha, \epsilon^\beta\in\mathbb R^N,$$ такие, что $$\epsilon^\alpha,\epsilon^\beta>\bf 0$$. Тогда, если
$$\alpha-\epsilon^\alpha\in P(x,y)\text{ и }\beta - \epsilon^\beta\in P(y, z),$$то
$$\alpha+\beta-\frac{\epsilon^\alpha + \epsilon^\beta}2\in P(x,z).$$Доказательство. Выберем исход $$w\neq x,y,z$$ (обратите внимание — мы по делу пользуемся тем, что $$|\mathcal O|>3$$!) и векторы $$\delta^w\in P(x,w),$$ $$\epsilon>\bf 0\in\mathbb R^N$$. Также выберем такой вектор типов $$\mathbf v,$$ что
$$\mathbf v(x)-\mathbf v(y) = \alpha - \frac{\epsilon^\alpha}2,\quad \mathbf v(y)-\mathbf v(z) = \beta - \frac{\epsilon^\beta}2,\quad \mathbf v(x)-\mathbf v(w) = \delta^w+\epsilon.$$Значит, они лежат в соответствующих множествах:
$$\mathbf v(x)-\mathbf v(y)\in P(x,y),\quad \mathbf v(y)-\mathbf v(z)\in P(y,z),\quad \mathbf v(x)-\mathbf v(w)\in P(x,w).$$Тогда, по лемме 8.3, $$f(v)=x,$$ и, следовательно,
$$\alpha+\beta - \frac{\epsilon^\alpha + \epsilon^\beta}2 = \mathbf v(x) - \mathbf v(z),$$а $$\mathbf v(x) - \mathbf v(z),$$ несомненно, лежит в $$P(x,z)$$.
Вернемся к доказательству теоремы. Если бы было верно, что $$0\in P(x,y),$$ то мы бы уже доказали всю теорему, так как лемма 8.5, примененная к $$\bf 0,$$ доказывала бы, что внутренности всех $$P(x,y)$$ равны. Мы бы доказали, что $$P(x,y) = P(w,w),$$ прибавляя к какому-нибудь $$\alpha$$ нулевые векторы. Но нулевой вектор в $$P(x,y)$$ лежать, конечно, не обязан.
Чтобы обойти эту досадную трудность, давайте возьмем каждое множество $$P(x,y)$$ и сдвинем его на
$$\gamma(x,y) = \inf\{p\in\mathbb R\mid p\cdot 1\in P(x,y)\},$$где $$\bf 1$$ — вектор из всех единиц. Число $$\gamma(x,y)$$ — это нижняя граница множества тех чисел, для которых
Лемма 8.6. Для всех $$x,y,z\in\mathcal O$$:
$$\begin{array}{rcl}\gamma(x,y) = - \gamma(y,x),\\ \gamma(x,z) = \gamma(x,y) + \gamma(y,z).\end{array}$$Доказательство. Доказательство проведем в два этапа. Сначала покажем, что для всякого $$\epsilon>0$$
$$\left(\gamma(x,y) + \frac\epsilon2\right)\cdot\bf 1\in P(x,y).$$Это верно потому, что, начиная с $$\gamma(x,y),$$ векторы $$p\cdot\bf 1$$ уже лежат в $$P(x,y)$$. Значит, по лемме 8.5,
$$(-\gamma(x,y) - \epsilon)\cdot 1\notin P(y,x).$$Но, с другой стороны,
$$(\gamma(x,y) - \epsilon)\cdot 1 \notin P(x,y),$$так как $$\gamma(x,y)$$ не лежит в $$P(x,y)$$. Следовательно, наоборот:
$$(-\gamma(x,y) + \frac\epsilon2)\cdot 1 \in P(y,x).$$Таким образом, у нас получилось, что для любого $$\epsilon$$ $$(-\gamma(x,y) - \epsilon)\notin P(x,y),$$ но при этом
$$(-\gamma(x,y) + \epsilon)\in P(x,y).$$Второй этап: поделим $$\epsilon$$ пополам и рассмотрим векторы
$$\left(\gamma(x,y) + \frac\epsilon2\right)\cdot 1 \in P(x,y)\text{ и }\left(\gamma(y,z) + \frac\epsilon2\right)\cdot 1 \in P(y,z).$$Тогда, по лемме 8.5,
$$(\gamma(x,y) + \gamma(y,z) + \epsilon)\cdot\bf 1\in P(x,z).$$Только что мы доказали, что
$$\gamma(z,x) \le \gamma(z,y) + \gamma(y,x).$$Обратное неравенство легко доказать, если поменять в этом неравенстве буквы $$y$$ и $$z$$ местами:
$$\gamma(y,x) \le \gamma(y,z) + \gamma(z,x),$$а затем заменить $$\gamma(y,z)$$ на $$-\gamma(z,y)$$:
$$\gamma(y,x) \le -\gamma(z,y) + \gamma(z,x).$$Итого мы получили два противоположных неравенства, то есть доказали искомое равенство $$\gamma(x,z) = \gamma(x,y) + \gamma(y,z)$$.
Теперь мы можем сдвинуть множества $$P(x,y)$$. Введем новые множества
$$C(x,y) = P(x,y) - \gamma(x,y)\cdot 1,$$для того чтобы $$\bf 0\in C(x,y)$$. Иначе говоря,
$$C(x,y)=\{\alpha -\gamma(x,y)\cdot 1 \ |\ \alpha \in P(x,y)\}.$$Также обозначим через $$\dot C$$ внутренность $$C$$ ; формально говоря:
$$\dot C = \{\alpha \in C \mid \alpha - \epsilon \in C\text{ для любого }\epsilon > 0 \}.$$Лемма 8.7. Внутренности всех $$C$$ совпадают:
$$\dot C(x,y) = \dot C(w, z)\text{ для любых }x,y,w,z\in\mathcal O,\ x\neq y,\ w\neq z.$$Доказательство. По второму пункту леммы 8.6,
$$\dot P(x,y)\subseteq\dot P(x,z)-\beta$$для любого $$\beta\in\dot P(y,z)$$. Также это верно для $$\beta = (\gamma(y,z) + \epsilon)\cdot 1 $$.
Аналогично,
$$\dot P(x,z)\subseteq\dot P(w,z)-\alpha$$для любого $$\alpha = (\gamma(w,x) + \epsilon)\cdot 1 ,$$ и получается, что
$$\dot P(x,y)\subseteq\dot P(w,z)-(\gamma(y,z) + \gamma(w,x))\cdot 1.$$Также по второму пункту леммы 8.6,
$$\gamma(y,z) + \gamma(w,x) = \gamma(y,z) + \gamma(w,y) + \gamma(y,x) = \gamma(w,z) - \gamma(x,y).$$Перенося вправо $$\gamma(w,z),$$ получаем, что
$$\dot P(x,y) - \gamma(x,y)\cdot 1 \subseteq\dot P(w,z)-\gamma(w,z)\cdot 1.$$Тогда, поскольку $$x,y,w$$ и $$z$$ мы выбирали произвольно, получается, что все $$\dot P(a,b)-\gamma(a,b)\cdot 1 $$ равны, то есть равны все $$\dot C$$.
Cтоит заметить, что для неразличающихся $$x,y,w,z$$ утверждение леммы 8.7 тоже выполняется. Докажем, например, что $$\dot C(x,y)=\dot C(y, x)$$. Для доказательства выберем $$w\in\mathcal O,$$ отличный от $$x$$ и $$y,$$ и используем лемму 8.7 для пар равенств из следующей цепочки
$$\dot C(x,y)=\dot C(w,y)=\dot C(w,x)= \dot C(y,x).$$Оставляем читателю доказательство остальных случаев частичного равенства $$x,y,z,w$$ между собой.
Доказав, что всевозможные $$\dot C(x,y)$$ равны, обозначим их все через $$C$$. Теперь, в полном соответствии с общей идеей доказательства, можно доказать, что $$C$$ выпукло.
Лемма 8.8. $$C$$ выпукло.
Доказательство. Пусть $$\alpha,\beta\in C \subseteq \mathbb R^{n}$$. Для начала покажем, что $$\alpha + \beta \in C$$. Зафиксируем разные $$x,y,z\in\mathcal O$$. Тогда
$$\gamma(x,y)\cdot\bf 1 + \alpha\in\dot P(x,y)\text{ и }\gamma(y,z)\cdot\bf 1+\beta\in\dot P(y,z)$$по определению $$\gamma(a,b)$$. Cложим их:
$$\gamma(x,z)\cdot\bf 1 + \alpha + \beta\in\dot P(x,z),$$и, следовательно, $$\alpha + \beta\in C$$.
Вторая часть выпуклости – покажем, что если $$\alpha \in C,$$ то и $$\frac\alpha2 \in C$$. Предположим противное: пусть $$\alpha\in C,$$ но $$\frac\alpha2\notin C$$. Тогда
$$\frac\alpha2 + \gamma(x,y)\cdot 1 \notin P(x,y),$$а значит,
$$-\frac\alpha2 - \gamma(x,y)\cdot 1 \in P(y,x).$$Следовательно, $$-\frac\alpha2\in C,$$ и $$\frac\alpha2=\alpha+(-\frac\alpha2)\in C$$. Противоречие.
Таким образом, для всех $$\alpha,\beta\in C \frac{\alpha+\beta}2\in C,$$ то есть $$C$$ выпукло.
Теперь, наконец-то, можно завершать доказательство теоремы. Во-первых, $$\bf 0\notin\dot C,$$ так как нулевой вектор должен быть на границе: мы уже видели, что если $$x \in C,$$ то $$-x \notin C$$.
Вспомним теорему о подпирающей
Зафиксируем исход $$x_0\in\mathcal O$$ и константы
$$C_x = \sum_{i=1}^Nk_i\gamma(x_0, x).$$Докажем теперь все необходимые неравенства, то есть
$$\sum_{i=1}^N k_i(v_i(x) - v_i(y)) \ge C_y - C_x,$$где $$f(v) = x\neq y$$. Если $$f(v) = x\neq y,$$ то $$v(x)-v(y)\in P(x,y)$$. Обозначим
$$\alpha = v(x)-v(y)-\gamma(x,y)\cdot\bf 1.$$Тогда, по определению констант $$k_i$$ и $$P(x,y),$$ $$\alpha\in\bar C$$. Значит, $$\bf k\cdot \alpha\ge 0$$.
Так как $$- \gamma(x,y) = \gamma(x_0,x) - \gamma(x_0,y),$$ то
$$\bf k\cdot \mathbf v(x) + C_x \ge \bf k\cdot \mathbf v(y) + C_y.$$Это и есть утверждение теоремы, так как мы его доказали для произвольного $$P=P(x,y)$$. Доказательство теоремы 8.1 тем самым завершено.
Второе доказательство использует другое условие монотонности и, естественно, пользуется при этом иным методом анализа. Мы должны также задействовать одно дополнительное условие [52].
Определение 8.5. Задим функцию социального выбора $$f : \mathbf V\to\mathbb \mathcal O$$. Будем говорить, что игрок $$i$$ принимает решения, если для каждого $$\mathbf v_{-i} \in \mathbf V_{-i}$$ и $$x \in \bA$$ существует такая функция полезности $$v_i \in V_i,$$ что $$f(v_i, \mathbf v_{-i}) = x$$.
Проще говоря, игрок $$i$$ может вынудить выбор любой из альтернатив для любой комбинации типов других игроков (например задавая "достаточно высокое" значение). Мы уже отмечали, что в том случае, когда существуют только две возможные альтернативы, принцип большинства (выбирать альтернативу большинством голосов, где игрок $$i$$ "подает голос" за $$x$$ по сравнению с $$y,$$ выбирая $$v_i(x) > v_i(y)$$ ) реализуем, и при таком подходе нет ни одного игрока, принимающего решения. Однако для трех и более альтернатив, как мы уже знаем из предыдущего доказательства, каждая выполнимая функция социального выбора должна допускать существование как минимум одного принимающего решения игрока. В дальнейшем мы будем пользоваться тем, что такой игрок существует.
Мы снова доказываем теорему Робертса — теорему 8.1.
Теорема 8.2. Пусть $$|\mathcal O|\ge 3,$$ и $$\mathbf V$$ не ограничено. Тогда для каждой
Далее мы без потери общности будем считать, что игрок 1 решающий.
Введем важное обозначение: будем писать
$$\mathbf v^\prime = \mathbf v + \epsilon 1_{i,x},$$или, что то же самое,
$$\mathbf v^\prime = (v_i + \epsilon 1_{x}, \mathbf v_{-i}).$$То есть через $$\mathbf v^\prime$$ мы будем обозначать вектор, совпадающий с $$\mathbf v$$ за исключением того, что компонента $$v_i(x)$$ увеличена на $$\epsilon$$. А через $$e_j$$ мы будем обозначать
Предыдущее доказательство занималось анализом
Определение 8.6. Для каждых двух различных $$x, y \in \mathcal O$$ и для каждого $$\mathbf v_{-i} \in \mathbf V_{-i}$$ определим
$$\delta^{i}_{xy}(\mathbf v_{-i}) = \inf\left\{\vphantom{1^2} v^\prime_i(x) - v^\prime_i(y)\,\mid\, v^\prime_i \in V_i\text{ и }f(v^\prime_i, \mathbf v_{-i}) = x \right\}.$$По определению, если $$f(\mathbf v) = x,$$ то $$v^\prime_i(x) - v^\prime_i(y) < \delta^{i}_{xy}(\mathbf v_{-i})$$ для всех $$y \in \mathcal O$$. Иными словами, если зафиксировать $$\mathbf v_{-i},$$ то $$\delta^{i}_{xy}(\mathbf v_{-i})$$ — это минимальное значение разницы между $$x$$ и $$y$$ всякий раз, когда $$f$$ выбирает $$x$$.
Пример 8.1. Для
Конец примера 8.1.
Теперь мы хотим исследовать структурные характеристики этого определения для случая неограниченной области и в конце концов показать, что $$\delta^{1}_{xy}(\mathbf v_{-i})$$ — это аффинная функция от разницы векторов $$(\bvn 1(x) - \bvn 1(y))$$. Отсюда и воспоследует свойство аффинной максимизации. Но сначала — немного более техническая лемма, которая установит, что сумма значений $$\delta$$ по циклам небольшой длины равна нулю.
Лемма 8.9.
Доказательство. Сначала докажем, что для любого $$\bf v_{-1} \in \bf V_{-1}$$ и любых исходов $$x, y \in O$$ значение $$\delta^{1}_{xy}(\bf v_{-1})$$ определено (конечно), и
$$\delta^{1}_{xy}(\bf v_{-1}) + \delta^{1}_{yx}(\bf v_{-1}) \ge 0.$$Раз агент $$1$$ принимает решения, то, значит, существует такая функция полезности $$v_{1} \in V_{1},$$ что $$f(v_1, \bf v_{-1}) = x$$. Тогда
$$\delta^{1}_{xy}(\mathbf v_{-i}) \le v_1(x) - v_1(y) < \infty.$$Однако, поскольку агент $$1,$$ опять же, принимает решения, существует и такая функция полезности $$v^{*}_1,$$ что $$f(v^{*}_1, \bf v_{-1}) = y$$. Для каждого из тех $$v^\prime_1 \in V_1,$$ для которых $$f(v^\prime_1, \bf v_{-1}) = x,$$ мы по свойству W-MON знаем, что $$v^\prime_1(x) - v^\prime_1(y) \ge v^{*}_1(x) - v^{*}_1(y)$$. Следовательно,
$$\delta^{1}_{xy}(\mathbf v_{-i}) \ge v^{*}_1(x) - v^{*}_1(y) > - \infty.$$Чтобы доказать, что $$\delta^{1}_{xy}(\bf v_{-1}) + \delta^{1}_{yx}(\bf v_{-1})$$ неотрицательно, зафиксируем произвольное $$\epsilon > 0$$ и рассмотрим такую $$v^{*}_1 \in V_1,$$ что
$$f(v^{*}_1, \bf v_{-1}) = y\text{ и }v^{*}_1(x) - v^{*}_1(y) \le \delta^{1}_{xy}(\mathbf v_{-i}) + \epsilon,$$а также такую $$v^\prime_1 \in V_1,$$ что
$$f(v^\prime_1, \bf v_{-1}) = x\text{ и }v^\prime_1(x) - v^\prime_1(y) \le \delta^{1}_{xy}(\mathbf v_{-i}) + \epsilon.$$По свойству W-MON мы имеем $$v^\prime_1(x) - v^\prime_1(y) \ge v^{*}_1(x) - v^{*}_1(y)$$. Тогда, значит,
$$\delta^{1}_{xy}(\mathbf v_{-i}) + \epsilon \ge v^\prime_1(x) - v^\prime_1(y) \ge v^{*}_1(x) - v^{*}_1(y) \ge - \delta^{1}_{yx}(\mathbf v_{-i}) - \epsilon.$$Следовательно, для любого $$\epsilon > 0$$
$$\delta^{1}_{xy}(\mathbf v_{-i}) + \delta^{1}_{yx}(\mathbf v_{-i}) + 2 \epsilon \ge 0,$$откуда и следует искомое неравенство.
Теперь можно доказать собственно утверждения леммы.
$$v^\prime_1 = v_1 + 3\epsilon \cdot 1_y + \epsilon \cdot 1_x$$.
Тогда $$f(v^\prime_1,\bf v_{-1}) \in {x,y}$$ по свойству W-MON. Однако $$f(v^\prime_1,\bf v_{-1})$$ не может быть равно $$x,$$ так как
$$v^\prime_1(x) - v^\prime_1(y) = (v_1(x) + \epsilon) - (v_1(y) + 3\epsilon) < \delta^{1}_{xy}(\bf v_{-1})$$.
Мы получили, что $$f(v^\prime_1,\bf v_{-1}) = y$$. Но тогда
$$\delta^{1}_{yx}(\bf v_{-1}) \le v^\prime_1(x) - v^\prime_1(y) + 2 \epsilon = - \delta^{1}_{xy}(\bf v_{-1}) + \epsilon,$$
и, таким образом, $$\delta^{1}_{xy}(\mathbf v_{-i}) + \delta^{1}_{yx}(\mathbf v_{-i}) \le \epsilon$$ для каждого $$\epsilon \ge 0$$.
$$f(v_1, \bf v_{-1}) = x,\quad f(v^\prime_1, \bf v_{-1}) = y,\quad f(v^{\prime\prime}_1, \bvn 1) = z$$
(они существуют, потому что агент $$1$$ принимает решения). По правдивости,
$$v_1(x) - p_1(x, \bf v_{-1}) \ge v_1(y) - p_1(y, \bf v_{-1}), \\ v^\prime_1(y) - p_1(y, \bf v_{-1}) \ge v^\prime_1(z) - p_1(z, \bf v_{-1}), \\ v^{\prime\prime}_1(z) - p_1(z, \bf v_{-1}) \ge v^{\prime\prime}_1(x) - p_1(x, \bf v_{-1}).$$(обратите внимание — опять вдруг откуда ни возьмись появляется парадокс Кондорсе!). Отсюда следует, что
$$v_1(x) - v_1(y) + v^\prime_1(y) - v^\prime_1(z) + v^{\prime\prime}_1(z) - v^{\prime\prime}_1(x) \ge 0$$.
В частности,
$$\delta^{1}_{xy}(\bf v_{-1}) + \delta^{1}_{yz}(\bf v_{-1}) + \delta^{1}_{zx}(\bf v_{-1}) \ge 0$$.
Теперь предположим, что существуют такая функция полезности $$\bvn 1$$ и такие исходы $$x, y, z,$$ что
$$\delta^{1}_{xy}(\bf v_{-1}) + \delta^{1}_{yz}(\bf v_{-1}) + \delta^{1}_{zx}(\bf v_{-1}) > 0$$.
По первому пункту этой леммы,
$$[\delta^{1}_{xy}(\bf v_{-1}) + \delta^{1}_{yx}(\bf v_{-1})] + [\delta^{1}_{yz}(\bf v_{-1}) + \delta^{1}_{zy}(\bf v_{-1})] + [\delta^{1}_{zx}(\bf v_{-1}) + \delta^{1}_{xz}(\bf v_{-1})] = 0$$.
Таким образом,
$$\delta^{1}_{xz}(\bf v_{-1}) + \delta^{1}_{zy}(\bf v_{-1}) + \delta^{1}_{yx}(\bf v_{-1}) < 0,$$
что приводит нас к противоречию.
Следующая лемма показывает, что значение $$\delta^{1}_{xy}(\bvn i)$$ зависит только от
$$\bf v_{-1}(x)-\bf v_{-1}(y),$$то есть от $$(n-1)$$ -мерного вектора разностей оценок всех агентов, кроме первого. Вспомним введенные ранее обозначения: $$(\mathbf v - \epsilon \cdot 1_{j,z})$$ означает оценку $$\mathbf v,$$ в которой агент $$j$$ уменьшил значение своей функции для альтернативы $$z$$ на $$\epsilon$$.
Лемма 8.10.
$$\delta^{1}_{xy}(\mathbf v_{-i}) = \delta^{1}_{xy}(\bf v_{-1} - L \cdot 1_{j,z})$$.
$$\bvn 1(x)-\bvn 1(y) = \bf v_{-1}^\prime(x) - \bf v_{-1}^\prime(y).$$
Тогда $$\delta^{1}_{xy}(\bf v_{-1}) = \delta^{1}_{xy}(\bf v_{-1}^\prime)$$.
Доказательство.
$$\delta^{1}_{xy}(\bf v_{-1}) \ge \delta^{1}_{xy}(\bf v_{-1}^\prime)$$.
Предположим противное: пусть равенство неверно, а, значит,
$$\delta^{1}_{xy}(\bf v_{-1}) > \delta^{1}_{xy}(\bvn 1^\prime).$$
Сперва заметим, что, как и в предыдущих доказательствах,
$$\delta^{1}_{yx}(\bf v_{-1}) \ge \delta^{1}_{yx}(\bf v_{-1}^\prime)$$Но
$$\delta^{1}_{xy}(\bf v_{-1}) + \delta^{1}_{yx}(\bf v_{-1}) = 0 = \delta^{1}_{xy}(\bf v_{-1}^\prime) + \delta^{1}_{yx}(\bf v_{-1}^\prime)$$.
Но мы предполагали, что левая часть этого равенства больше, чем правая; таким образом, мы пришли к противоречию.
для которых
$$\bvn 1(x) - \bvn 1(y) = \bf v_{-1}^\prime(x) - \bf v_{-1}^\prime(y).$$Для каждого $$j \neq 1$$ и для каждого $$v_j \in V_j$$ условие S-MON подразумевает, что добавление аддитивной константы ко всем координатам $$v_j$$ не изменит выбора $$f$$. Таким образом, мы можем без потери общности предположить, что $$v_j(x) = v^\prime_j(x)$$ и $$v_j(y) = v^\prime_j(y)$$. Теперь определим
$$v^{\prime\prime}_j(w) = \min \left\{\vphantom{1^2} v_j(w), v^\prime_j(w)\right\}$$
для каждого $$w \in \mathcal O$$. Тогда первый пункт этой леммы позволяет сделать вывод о том, что
$$\delta^{1}_{xy}(\bf v_{-1}) = \delta^{1}_{xy}(\bf v_{-1}^\prime) = \delta^{1}_{xy}(v^{\prime\prime}_{-1})$$.
Вот и все, лемма доказана.
Итак, мы доказали, что $$\delta^{1}_{xy}(\mathbf v_{-i})$$ зависит только от $$\bvn 1(x)-\bvn 1(y)$$. Таким образом, отныне мы можем рассматривать $$\delta^{1}_{xy}(\bvn i)$$ как функцию $$\delta^{1}_{xy}(\bvn 1(x)-\bvn 1(y))$$. В этих (слегка измененных) обозначениях можно сформулировать следующее следствие.
Следствие 8.2.1. Для любой пары векторов $$\bf{r}, \bf{t} \in \mathbb R^{n-1}$$ и любой тройки исходов $$x,y,z \in \mathcal O$$ верно, что
$$\delta^{1}_{xy}(\bf{r}) + \delta^{1}_{yx}(-\bf{r}) = 0,\\ \delta^{1}_{xy}(\bf{r}) + \delta^{1}_{yz}(\bf{t}) + \delta^{1}_{zx}(-\bf{r}- \bf{t}) = 0.$$В частности,
$$\delta^{1}_{xy}(\bf{0}) + \delta^{1}_{yx}(\bf{0}) = 0\text{ и } \delta^{1}_{xy}(\bf{0}) + \delta^{1}_{yz}(\bf{0}) + \delta^{1}_{zx}(\bf{0})= 0.$$Лемма 8.11. Для каждого $$\bf{r}, \bf{s}, \bf{t} \in \mathbb R^{n-1}$$ и для любой тройки исходов $$x,y,z \in \mathcal O$$
$$\delta^{1}_{yx}(\bf{r} + \bf{t}) - \delta^{1}_{yx}(\bf{r}) = \delta^{1}_{zx}(\bf{s} + \bf{t}) - \delta^{1}_{zx}(\bf{s}).$$Доказательство. Достаточно показать, что
$$\delta^{1}_{zx}(\bf{s}) - \delta^{1}_{yx}(\bf{r}) = \delta^{1}_{zx}(\bf{s} + \bf{t}) - \delta^{1}_{yx}(\bf{r} + \bf{t}).$$По следствию 8.2.1,
$$\delta^{1}_{zx}(\bf{s}) - \delta^{1}_{yx}(\bf{r}) = \delta^{1}_{zx}(\bf{s}) + \delta^{1}_{xy}(-\bf{r}) = -\delta^{1}_{yz}(\bf{r}-\bf{s}).$$Аналогично,
$$\delta^{1}_{zx}(\bf{s} + \bf{t}) - \delta^{1}_{yx}(\bf{r} + \bf{t}) = -\delta^{1}_{yz}(\bf{r} - \bf{s}).$$Теперь нам придется ненадолго
В формулировке предложения "монотонность" означает следующее: функция $$g : \mathbb R^n \to \mathbb R$$ монотонная, если для любых векторов $$\bf{a}, \bf{b} \in \mathbb R^n$$ из $$\beta_i \ge \alpha_i$$ для каждого $$i$$ следует, что $$g(\bf{b}) \ge g(\bf{a})$$. Иначе говоря, это монотонность относительно частичного порядка на векторах, который мы тут уже неоднократно вводили и использовали.
Предложение 8.1. Зафиксируем
для любого $$\bf r \in \mathbb R^n$$ и любого $$\delta > 0$$ (где $$\bf e_i$$ — это
Доказательство. Доказательство мы для большей наглядности разобьем на две леммы. Первая из них рассматривает одномерный случай.
Лемма 8.12. Предположим, что $$m : \mathbb R_+ \to \mathbb R$$ — монотонно неубывающая функция, и существует такая функция $$h : \mathbb R_+ \to \mathbb R_+,$$ что
$$m(x + \delta)-m(x) = h(\delta)$$для любых $$x,\delta \in \mathbb R_+$$. Тогда существует такое число $$w \in \mathbb R_+,$$ что $$h(\delta) = w \delta$$.
Доказательство. Пусть $$w = h(1)$$ (заметим, что $$w \ge 0,$$ поскольку $$m$$ не убывает). Сначала мы докажем, что для любых двух целых чисел $$p$$ и $$q$$ $$h(p/q) = w (p/q)$$. Заметим, что
$$h(1) = m(1) - m(0) = {\sum_{i=0}^{q-1}m\left(\vphantom{1^2}(i + 1)/q\right)} - m(i/q) = q \cdot h(1/q).$$Таким образом, $$h(1/q) = (1/q) \cdot h(1)$$. Аналогично,
$$h(p/q) = m(p/q)-m(0)= {\sum_{i=0}^{p-1}m\left(\vphantom{1^2}(i + 1)/q\right)} - m(i/q) = \\ = p \cdot (1/q) = (p/q) \cdot h(1) = (p/q) \cdot w.$$Теперь стандартным образом перейдем по полноте от рациональных чисел к вещественным: докажем, что для любого вещественного $$\delta$$ $$h(\delta) = \delta w$$. Заметим, что так как $$m$$ монотонно не убывает, $$h$$ тоже должна быть монотонно неубывающей. Предположим от противного, что $$h(\delta) > w \delta$$. Возьмем некоторое
Лемма 8.13. Рассмотрим подмножество $$X \subseteq \mathbb R^n,$$ обладающее следующим свойством: если $$\bf x \in X$$ и $$\bf y \ge x,$$ то $$\bf y \in X$$. Рассмотрим монотонно неубывающую функцию $$m: X \to \mathbb{R}$$ и предположим, что существуют такие числа $$w_1,\ldots,w_n\in\mathbb R,$$ что
$$m(\bf{x} + \delta \bf{e}_i) - m(x) = w_i \delta$$для любого $$i,$$ любого $$\bf{x} \in X$$ и любого $$\delta > 0$$. Тогда существует такая константа $$\gamma \in \mathbb{R},$$ что
$$m(\bf x) = {\sum\limits_{i=1}^{n}w_i\cdot x_i} + \gamma.$$Доказательство. Сначала мы докажем, что для любых таких $$\bf{x},\bf y \in X,$$ что $$y_i \ge x_i$$ для всех $$i,$$ в этом случае
$$m(\bf y) = m(\bf x) + {\sum\limits_{i=1}^{n}w_i\cdot (y_i - x_i)}.$$Заметим, что $$(y_1, x_2, \ldots, x_n) \in X$$ и
$$m(y_1, x_2, \ldots, x_n) = m(\bf x) + h_1(y_1 - x_1).$$Повторяя этот шаг $$n$$ раз, мы получаем, что
$$m(\bf y) = m(\bf x) + {\sum\limits_{i=1}^{n}w_i\cdot (y_i - x_i)}.$$Теперь зафиксируем любой $$\bf x^* \in X$$. Докажем, что для любого $$\bf x \in X$$
$$m(\bf x) = m(\bf x^*) + \sum\limits_{i=1}^{n}w_i \left(x_i - x^*_i\right).$$Выберем такой вектор $$\bf y,$$ что $$y_i \ge \max \{ x_i, x^*_i\}$$ для всех $$i$$. Таким образом,
$$m(\bf y) = m(\bf x) + {\sum\limits_{i=1}^{n}w_i(y_i - x_i)},$$а также
$$m(\bf y) = m(\bf x^*) + \sum\limits_{i=1}^{n}w_i \left(y_i - x^*_i\right),$$из чего немедленно следует доказываемое утверждение.
Эти две леммы и составляют доказательство предложения 8.1.
Теперь вернемся к доказательству теоремы Робертса. Нам осталось уже буквально одно последнее усилие.
Лемма 8.14. Существуют такие неотрицательные вещественные константы $$k_2,\ldots,k_n,$$ что для каждого $$\bf r \in \mathbb R^{n-1}$$ и для любых исходов $$y,z \in \mathcal O$$
$$\delta^{1}_{yz}(\bf r) = -{\sum_{j=2}^nk_{jrj} + \delta^{1}_{yz}(\bf 0)}.$$Доказательство. Прежде всего заметим, что $$\delta^{1}_{yz}(\cdot)$$ — это монотонно невозрастающая вещественная функция. Если $$f(v_1, \bf v_{-1}) = y,$$ то тогда $$f(v_1, \bf v_{-1} + \epsilon \bf 1_{j,y}) = y$$ по S-MON. Тогда инфимум на $$\bf v_{-1} + \epsilon \cdot 1_{j,y}$$ получается на большем множестве, и, следовательно, он меньше. Значит, $$\delta^{1}_{yz}(\cdot)$$ невозрастает.
По лемме 8.11 и предложению 8.1 получаем, что существуют такие вещественные константы $$k^{yz}_j,$$ что
$$\delta^{1}_{yz}(\bf{r}) = {\sum^n_{j=2}k^{yz}_{jrj} + \delta^{1}_{yz}(\bf{0})}.$$Поскольку $$\delta^{1}_{yz}(\cdot)$$ является монотонно невозрастающей функцией, все $$k^{yz}_j$$ должны быть неположительными. Перепишем для удобства это равенство как
$$\delta^{1}_{yz}(\bf{r}) = -{\sum^n_{j= 2}k^{yz}_{jrj} + \delta^{1}_{yz}(\bf{0})},$$и будем отныне считать, что константы $$k^{yz}_j$$ неотрицательны.
Нам осталось показать, что $$k^{xy}_j = k^{wz}_j$$ для любых $$x,y,z,w \in\mathcal O$$. Выше мы получили, что $$k^{xy}_j = \delta^{1}_{xy}(\bf{0}) - \delta^{1}_{xy}(\bf e_j)$$. По следствию 8.2.1 мы получаем $$k^{xy_j = k^{zx}_j,$$ потому что $$\delta^{1}_{xy}(\bf e_j) + \delta^{1}_{yz}(\bf{0}) + \delta^{1}_{xy}(-\bf e_j) = 0$$. Аналогично, $$k^{zx}_j = k^{wz}_j$$.
Теперь мы легко можем завершить доказательство теоремы. Зафиксируем произвольную альтернативу $$w \in \mathcal O$$ и зададим константы $$C_x = \delta^{1}_{wx}(\bf{0})$$ для всех $$x \neq w,$$ а $$C_w$$ положим равной нулю. Зафиксируем $$\mathbf v \in V$$ и предположим, что $$f(\mathbf v) = x$$. Следовательно, для любого другого исхода $$y \ne x$$
$$v_1(x) - v_1(y) \ge \delta^{1}_{xy}(\bf v_{-1}) = -{\sum_{j\ne 1}k_j\left(\vphantom{1^2}v_j(x) - v_j(y)\right)+ \delta^{1}_{xy}(\bf{0})}.$$Так как $$\delta^{1}_{xy}(\bf{0}) = \delta^{1}_{xw}(\bf{0}) + \delta^{1}_{wy}(\bf{0})$$ и $$\delta^{1}_{xw}(\bf{0}) = - \delta^{1}_{wx}(\bf{0}),$$ мы, переставляя элементы, получаем, что
$$v_1(x) + {\sum_{j\ne 1}k_jv_j(x)} + C_x \ge v_1(y) + {\sum_{j\neq1}k_jv_j(y)} + C_y,$$что и требовалось доказать.
Для функций ценности самого общего вида мы в лекции 6 уже говорили о теореме Гиббарда-Саттертуэйта (теорема 6.2). Мы доказывали, что если допустить любые порядки на множестве возможных исходов, то реализовать можно только диктаторские функции социального выбора, выгодные ровно одному участнику.
Результат, конечно, весьма печальный. Но неужели ничего нельзя сделать? В математике обычно, если общий факт никак не доказывается или общая конструкция никак не строится, пытаются рассмотреть ограниченную постановку, которая, однако, продолжает иметь смысл.
Для теоремы Гиббарда-Саттертуэйта аналогичный вопрос разумно было бы задать для квазилинейных предпочтений — для ситуации, когда функция полезности каждого агента представляет собой разность между его внутренней ценностью от наступившего исхода и той ценой, которую он должен в результате этого исхода заплатить. Такие предпочтения — более чем естественное предположение; в самом деле, ну как же еще? Но для этих предпочтений теорема Гиббарда-Саттертуэйта уже не слишком-то применима: такого, как там, произвольного порядка предпочтений на всем множестве исходов уже может не получиться построить. Поэтому и теорема о невозможности — а в этой лекции мы опять будем доказывать теорему о невозможности — здесь уже не такая пессимистичная, как теорема Гиббарда-Саттертуэйта. Я бы даже назвал ее не теоремой о невозможности, а теоремой классификации: да, мы классифицируем все реализуемые функции социального выбора, но их окажется вовсе не так мало, и среди них будут практически все естественные функции.
Теорема Робертса, как нетрудно догадаться, доказана была Кевином Робертсом [71]. Его доказательство было достаточно сложным технически, и за деревьями трудно было рассмотреть лес, то есть основную базовую идею доказательства. Поэтому доказательства, которые мы приводим в этой лекции, отличаются от оригинального доказательства Робертса; мы изложим два (достаточно существенно отличающихся друг от друга) упрощенных доказательства теоремы Робертса, представленных не так давно Лави, Му-алем и Нисаном [40].
Здесь, однако, стоит заметить, что мы докажем теорему Робертса только для случая неограниченного множества типов. В реальной жизни множества типов часто бывают ограничены, и структура этих ограничений бывает довольно прихотливой. Но в общем случае ответа на этот вопрос до сих пор нет, есть только частные результаты [26,40]. Поэтому будем излагать то, что есть.
Для начала напомним основные определения. У механизма есть набор исходов $$\mathcal O$$ (в этой лекции мы их будем обозначать через $$x,y,z,..$$.). Есть $$N$$ игроков, и у каждого есть свой тип $$v_i$$. Этот тип — просто набор ценностей, которые игрок может присвоить каждому исходу. Например, в ситуации аукциона по продаже одного предмета, о которой мы часто говорили, набор исходов $$\mathcal O$$ — это то, кому достается вещь (фактически множество исходов равно множеству агентов), а тип $$v_i$$ — это функции полезности агента от возможного исхода, которые равны нулю, если эту вещь отдали кому-то другому, или самой ценности, если вещь дали данному игроку:
$$v_i(x) = \begin{cases}v_i, x = i, \\ 0, \text{в противном случае}.\end{cases}$$Определение 8.1.Множество типов $$\mathbf V = V_1\times V_2\times\ldots\times V_N$$ называется неограниченным, если $$V_i = \mathbb R^{|\mathcal O|}$$ для каждого $$i$$.
В дальнейшем в этой лекции мы всегда будем рассматривать только неограниченные множества типов. Разумеется, суть здесь не в плюс-минус бесконечностях, подошел бы и любой открытый интервал — важно, что очередной агент имеет возможность выбрать ставку, которая строго больше всех остальных (да и вообще может находиться где угодно относительно других ставок — между любыми двумя вещественными числами найдется изрядное количество других вещественных чисел).
Следующий объект, который нас интересует, — это функция социального выбора $$f:\mathbf V\to\mathcal O$$. Можно без потери общности предположить, что $$f$$ сюръективна; если это не так, мы просто ограничим $$\mathcal O$$ на $$im(f)\subset\mathcal O,$$ не потеряв ни одного реально возможного исхода, то есть не изменив ни стратегий агентов, ни результатов этих стратегий.
Кроме того, механизм берет с игроков платежи $$p_i:\mathbf V\to\mathbb R$$. А игроки квазилинейны, то есть они хотят максимизировать себе функцию дохода (utility function)
$$u_i = v_i\left(\vphantom{1^2}f(\mathbf v)\right) - p_i(\mathbf v).$$В этой лекции мы будем вести речь о реализации функций социального выбора в
Определение 8.2.
От нас в конструкции механизма зависит только $$p_i$$ (потому что распределение исходов задается функцией социального выбора), поэтому задача сводится к следующей: нам нужно так подобрать значения $$p_i,$$ чтобы в конце концов эгоистичные агенты, действуя для максимизации своих $$u_i$$ (которые у них квазилинейные), максимизировали $$f$$.
Формально говоря, для каждого $$i,$$ каждого $$\mathbf v_{-i}\in \mathbf V_{-i}$$ и каждого $$v^\prime\in V_i$$
В лекции 4 мы уже говорили, что все функции социального выбора, оптимизирующие суммарную полезность, она же общественное благосостояние, правдиво реализуемы VCG-платежами (точнее говоря, функция социального выбора, которая оптимизирует общественное благосостояние – она одна, и она реализуема посредством VCG-механизма). Более того, легко видеть, что точно так же реализуемы и функции социального выбора, оптимизирующие взвешенное общественное благосостояние, то есть функции, которые с разными весами учитывают счастье разных агентов.
Задача этой лекции состоит в том, чтобы доказать обратное утверждение. Мы докажем, что оптимизацией таких вот "взвешенно-эффективных" функций социального выбора, собственно, и исчерпываются все возможности, которые у нас есть с квазилинейными агентами.
Теорема 8.1. (Теорема Робертса) Пусть $$|\mathcal O|\ge 3,$$ и множество типов $$\mathbf V$$ — неограниченное. Тогда для каждой
Оба доказательства теоремы Робертса (да и исходное) основаны на условиях монотонности. Мы сначала докажем, что для правдивой реализуемости $$f$$ должна удовлетворять этим условиям, а затем, в доказательстве самой теоремы, докажем, что функция, удовлетворяющая таким условиям, имеет требуемый вид. Начнем со свойства слабой монотонности.
Определение 8.3. W-MON — слабая монотонность (
Иначе говоря, если игрок $$i$$ может изменить свой тип с $$v_i$$ на $$v^\prime_i,$$ при этом изменив исход с $$x$$ на $$y,$$ то разность его значений для $$y$$ должна быть не меньше, чем разность его значений для $$x$$. Вот так, ненавязчиво, здесь появляются разности, которые будут ключевыми объектами в дальнейших рассуждениях. %Стоит также заметить, что разности нужно использовать из-за квазилинейности.
Лемма 8.1. Всякая доминантно реализуемая функция социального выбора $$f$$ удовлетворяет W-MON.
Доказательство. Во-первых, докажем, что $$p_i$$ не зависит от $$v_i$$. Другими словами, если функция правдиво реализуется механизмом, то функция платежа уже не зависит от ставки.
Предположим противное. Что значит, функция платежа зависит от ставки? Это значит, что есть такие $$\mathbf v_{-i},$$ $$x,$$ $$v_i$$ и $$v^\prime_i,$$ что исход один и тот же, но платеж при этом разный:
$$f(v_i, \mathbf v_{-i}) = f(v^\prime_i, \mathbf v_{-i}) = x,\quad p_i(v_i,\mathbf v_{-i}) < p_i(v^\prime_i, \mathbf v_{-i}).$$Тогда очевидно, что при векторе типов $$\mathbf v$$ игроку $$i$$ выгодно солгать. Следовательно, у
Теперь зафиксируем $$\mathbf v_{-i}, v_i, v^\prime_i, x, y$$ так, как было в определении W-MON. Из-за правдивой реализуемости должно быть верно, что
$$v_i(x) - p_i(x, \mathbf v_{-i}) \ge v_i(y) - p_i(y, \mathbf v_{-i}),$$иначе при типе $$v_i$$ игрок $$i$$ сможет улучшить себе доход, солгав $$v^\prime_i$$. Аналогично,
$$v^\prime_i(y) - p_i(y, \mathbf v_{-i}) \ge v^\prime_i(x) - p_i(x, \mathbf v_{-i}).$$Сложив эти два неравенства и сократив $$p_i$$ получим искомое условие W-MON. Таким образом, W-MON необходимо для правдивой реализуемости.
Второе условие монотонности — свойство
Определение 8.4. Функция социального выбора $$f$$ удовлетворяет
для всех $$y\in\mathcal O\setminus x$$ и всех $$i,$$ то $$f(v^\prime)$$ тоже равно $$x$$.
Свойство
Лемма 8.2. Всякая доминантно реализуемая функция социального выбора $$f$$ удовлетворяет
Доказательство. Мы уже доказали, что она удовлетворяет W-MON. Теперь зафиксируем типы $$v$$ и $$v^\prime$$ из определения
Тогда
$$f(\mathbf v^0) = x,\quad \mathbf v^0 = v,\quad \mathbf v^N = v^\prime.$$Предположим теперь противное: пусть $$f(\mathbf v^{i-1}) = x,$$ а $$f(\mathbf v^i) = y\neq x$$. Тогда можно применить W-MON:
$$v^\prime_i(y) - v_i(y) \ge v^\prime_i(x) - v_i(x),$$что противоречит предположению
Мы будем пользоваться
Лемма 8.3. Пусть функция социального выбора $$f$$ удовлетворяет
Доказательство. Так как в каждой компоненте имеет место строгое неравенство, то, следовательно, можно построить вектор $$\delta > \bf 0,$$ равный разности двух векторов из исходного неравенства:
$$\delta = \mathbf v^\prime(y) - \mathbf v(y) - \mathbf v^\prime(x) + \mathbf v^\prime(x)\in\mathbb R^N.$$Кроме того, для каждого $$i$$
$$v_i(x) - v^\prime_i(x) - \frac{\Delta_i}2 = v_i(y) - v^\prime_i(y) + \frac{\Delta_i}2 > v_i(y) - v^\prime_i(y).$$Определим теперь новый тип $$\mathbf v^{\prime\prime}\in\mathbf V$$:
$$v^{\prime\prime}_i(z) = \begin{cases} \min\{v_i(z), v^\prime_i(z) + v_i(x) - v^\prime_i(x)\} - \Delta_i, z\neq x,y,\\ v_i(x) - \frac{\Delta_i}2, z = x,\\ v_i(y), z = y. \end{cases}$$Это сугубо техническая конструкция, которая нужна для того, чтобы придти к противоречию: при такой конструкции из
С одной стороны получаем, что
$$v^{\prime\prime}_i(y) - v_i(y) = 0 > v^{\prime\prime}_i(z) - v_i(z),$$и из
С другой стороны, для $$z\neq x,y$$
$$v^{\prime\prime}_i(z) \le v^\prime_i(z) + v_i(x) - v^\prime_i(x) - \Delta_i,$$и
$$v^{\prime\prime}_i(x) - v^\prime_i(x) = v_i(x) - v^\prime_i(x) - \frac{\Delta_i}2 > v^{\prime\prime}_i(z) - v^\prime_i(z).$$Анналогично для $$z=y$$. Тогда из
Теперь, когда мы изучили все дополнительные леммы об условиях монотонности, можно наконец-то перейти к доказательствам собственно теоремы Робертса.
Чтобы показать, что функция — это аффинный максимизатор, на самом деле нужно изучать разности. Это потому, что аффинная максимизация на самом деле
где $$f(v) = x\neq y$$ (рекомендуем читателю не лениться и проверить эту эквивалентность). Мы будем изучать структуру этих самых разностей.
Главное множество, которое мы будем изучать, — это
$$P(x,y) = \left\{\vphantom{1^2}\alpha\in\mathbb R^N\mid \exists \mathbf v: \mathbf v(x) - \mathbf v(y) = \alpha, f(\mathbf v) = x\right\}.$$Проще говоря, если $$f(\mathbf v) = x,$$ то $$\mathbf v(x) - \mathbf v(y)\in P(x,y)$$.
В течение доказательства мы увидим, какова структура множеств $$P(x,y),$$ и в конце концов покажем, что $$P(x,y)$$ — это полупространство. В частности, мы сделаем два важных замечания о структуре $$P(x,y)$$. Во-первых,
$$\begin{equation} \alpha\in P(x,y)\text{ тогда и только тогда, когда }-\alpha\notin P(y,x), \end{equation}$$причем внутренности $$P(x,y)$$ и $$P(y,x)$$ не пересекаются.
А во-вторых, для внутренних точек упомянутых множеств
$$\begin{equation} P(x,y) + P(y, z) = P(x,z). \end{equation}$$Для чего нужны эти свойства? Предположим, что $$\bf 0\in P(x,y)$$ для всех $$x,y\in\mathcal O$$ (на самом деле это не обязательно так, и нам позже придется сместить множества $$P(x,y)$$ ). Тогда по второму условию все $$P(x,y)$$ равны. Введем новое обозначение – пусть они равны $$C$$. По первому условию $$C\cup -C = \mathbb R^N$$: если $$\alpha\notin C,$$ то $$-\alpha\in C$$. Также из первого условия следует, что $$C$$ —
Таким образом, $$C$$ и $$-C$$ покрывают все пространство, выпуклы, и их внутренности не пересекаются. Это в точности означает, что они являются подпространствами.
Теперь, объяснив идею будущего доказательства, перейдем к нему самому. Начнем с простейших свойств $$P(x,y)$$. Так как $$f$$ — сюръекция, то $$P(x,y)$$ непусто для любых $$x$$ и $$y$$. Также,
$$\begin{equation} \text{если }\alpha\in P(x,y),\text{ то }\forall\ \delta>\bf 0\in\mathbb R^N\quad \alpha+\delta\in P(x,y). \end{equation}$$Чтобы это доказать, рассмотрим $$v$$: $$f(v) = x$$ и $$\mathbf v(x) - \mathbf v(y) = \alpha$$. Увеличим $$\mathbf v(x)$$ на $$\delta$$ (мы можем это сделать, так как множества типов $$\mathbf V$$ у нас неограниченные), и получится, что $$\alpha+\delta$$ тоже будет лежать в $$P(x,y)$$.
Следующая лемма докажет нам свойство 8.1 для внутренних точек множества $$P(x,y)$$.
Лемма 8.4. Рассмотрим произвольные векторы $$\alpha, \epsilon\in P(x,y)$$. Тогда
$$\begin{array}{rlcl} \text{если }\alpha-\epsilon\in P(x,y), \text{ то } -\alpha\notin P(y,x),\\ \text{а если }\alpha\notin P(x,y), \text{ то } -\alpha\in P(y,x). \end{array}$$Доказательство. Сначала докажем первую часть леммы. Предположим противное: пусть, наоборот, $$-\alpha\in P(y,x)$$. Тогда существует такой вектор типов $$\mathbf v,$$ что
$$\mathbf v(y) - \mathbf v(x) = -\alpha,\text{ и }f(\mathbf v) = y.$$Но так как $$\alpha-\epsilon\in P(x,y),$$ то, значит, существует такой вектор типов $$\mathbf v^\prime,$$ что $$\mathbf v^\prime(x) - \mathbf v^\prime(y) = \alpha-\epsilon,$$ и $$f(\mathbf v^\prime) = x$$. Тогда верно, что
$$\mathbf v(x)-\mathbf v(y) = \alpha > \mathbf v^\prime(x) - \mathbf v^\prime(y) = \alpha-\epsilon,$$а это противоречит лемме 8.3. Вторая часть леммы доказывается абсолютно аналогично — ее мы оставим читателю.
Пока что мы доказали, что внутренние области $$P(x,y)$$ и $$P(y,x)$$ не пересекаются, и объединение $$P(x,y)$$ и $$-P(y,x)$$ составляет все пространство.
Отметим еще, что из свойства 8.3 следует, что граница у $$P(x,y)$$ монотонно невозрастающая. Действительно, если граница будет возрастающей, то тогда мы сможем прибавить $$\alpha$$ к $$\delta$$ и попасть вне $$P(x,y)$$.
Осталось только показать, что границы являются гиперплоскостями, и тогда мы докажем все необходимые свойства $$P(x,y)$$. Также стоит показать, что $$P(x,y)=P(y,x)$$.
Следующая лемма — это доказательство свойства 8.2. В ней понятие "внутренней точки" приобретает исконный смысл, по определению: если $$\alpha\in P(x,y)$$ — внутренняя точка, то, значит, для всех достаточно коротких векторов $$\epsilon^\alpha\in\mathbb R^N$$ верно, что $$\alpha-\epsilon^\alpha\in P(x,y)$$.
Лемма 8.5. Рассмотрим некоторые векторы $$\alpha,\beta\in\mathbb R^N$$ и некоторые векторы $$\epsilon^\alpha, \epsilon^\beta\in\mathbb R^N,$$ такие, что $$\epsilon^\alpha,\epsilon^\beta>\bf 0$$. Тогда, если
$$\alpha-\epsilon^\alpha\in P(x,y)\text{ и }\beta - \epsilon^\beta\in P(y, z),$$то
$$\alpha+\beta-\frac{\epsilon^\alpha + \epsilon^\beta}2\in P(x,z).$$Доказательство. Выберем исход $$w\neq x,y,z$$ (обратите внимание — мы по делу пользуемся тем, что $$|\mathcal O|>3$$!) и векторы $$\delta^w\in P(x,w),$$ $$\epsilon>\bf 0\in\mathbb R^N$$. Также выберем такой вектор типов $$\mathbf v,$$ что
$$\mathbf v(x)-\mathbf v(y) = \alpha - \frac{\epsilon^\alpha}2,\quad \mathbf v(y)-\mathbf v(z) = \beta - \frac{\epsilon^\beta}2,\quad \mathbf v(x)-\mathbf v(w) = \delta^w+\epsilon.$$Значит, они лежат в соответствующих множествах:
$$\mathbf v(x)-\mathbf v(y)\in P(x,y),\quad \mathbf v(y)-\mathbf v(z)\in P(y,z),\quad \mathbf v(x)-\mathbf v(w)\in P(x,w).$$Тогда, по лемме 8.3, $$f(v)=x,$$ и, следовательно,
$$\alpha+\beta - \frac{\epsilon^\alpha + \epsilon^\beta}2 = \mathbf v(x) - \mathbf v(z),$$а $$\mathbf v(x) - \mathbf v(z),$$ несомненно, лежит в $$P(x,z)$$.
Вернемся к доказательству теоремы. Если бы было верно, что $$0\in P(x,y),$$ то мы бы уже доказали всю теорему, так как лемма 8.5, примененная к $$\bf 0,$$ доказывала бы, что внутренности всех $$P(x,y)$$ равны. Мы бы доказали, что $$P(x,y) = P(w,w),$$ прибавляя к какому-нибудь $$\alpha$$ нулевые векторы. Но нулевой вектор в $$P(x,y)$$ лежать, конечно, не обязан.
Чтобы обойти эту досадную трудность, давайте возьмем каждое множество $$P(x,y)$$ и сдвинем его на
$$\gamma(x,y) = \inf\{p\in\mathbb R\mid p\cdot 1\in P(x,y)\},$$где $$\bf 1$$ — вектор из всех единиц. Число $$\gamma(x,y)$$ — это нижняя граница множества тех чисел, для которых
Лемма 8.6. Для всех $$x,y,z\in\mathcal O$$:
$$\begin{array}{rcl}\gamma(x,y) = - \gamma(y,x),\\ \gamma(x,z) = \gamma(x,y) + \gamma(y,z).\end{array}$$Доказательство. Доказательство проведем в два этапа. Сначала покажем, что для всякого $$\epsilon>0$$
$$\left(\gamma(x,y) + \frac\epsilon2\right)\cdot\bf 1\in P(x,y).$$Это верно потому, что, начиная с $$\gamma(x,y),$$ векторы $$p\cdot\bf 1$$ уже лежат в $$P(x,y)$$. Значит, по лемме 8.5,
$$(-\gamma(x,y) - \epsilon)\cdot 1\notin P(y,x).$$Но, с другой стороны,
$$(\gamma(x,y) - \epsilon)\cdot 1 \notin P(x,y),$$так как $$\gamma(x,y)$$ не лежит в $$P(x,y)$$. Следовательно, наоборот:
$$(-\gamma(x,y) + \frac\epsilon2)\cdot 1 \in P(y,x).$$Таким образом, у нас получилось, что для любого $$\epsilon$$ $$(-\gamma(x,y) - \epsilon)\notin P(x,y),$$ но при этом
$$(-\gamma(x,y) + \epsilon)\in P(x,y).$$Второй этап: поделим $$\epsilon$$ пополам и рассмотрим векторы
$$\left(\gamma(x,y) + \frac\epsilon2\right)\cdot 1 \in P(x,y)\text{ и }\left(\gamma(y,z) + \frac\epsilon2\right)\cdot 1 \in P(y,z).$$Тогда, по лемме 8.5,
$$(\gamma(x,y) + \gamma(y,z) + \epsilon)\cdot\bf 1\in P(x,z).$$Только что мы доказали, что
$$\gamma(z,x) \le \gamma(z,y) + \gamma(y,x).$$Обратное неравенство легко доказать, если поменять в этом неравенстве буквы $$y$$ и $$z$$ местами:
$$\gamma(y,x) \le \gamma(y,z) + \gamma(z,x),$$а затем заменить $$\gamma(y,z)$$ на $$-\gamma(z,y)$$:
$$\gamma(y,x) \le -\gamma(z,y) + \gamma(z,x).$$Итого мы получили два противоположных неравенства, то есть доказали искомое равенство $$\gamma(x,z) = \gamma(x,y) + \gamma(y,z)$$.
Теперь мы можем сдвинуть множества $$P(x,y)$$. Введем новые множества
$$C(x,y) = P(x,y) - \gamma(x,y)\cdot 1,$$для того чтобы $$\bf 0\in C(x,y)$$. Иначе говоря,
$$C(x,y)=\{\alpha -\gamma(x,y)\cdot 1 \ |\ \alpha \in P(x,y)\}.$$Также обозначим через $$\dot C$$ внутренность $$C$$ ; формально говоря:
$$\dot C = \{\alpha \in C \mid \alpha - \epsilon \in C\text{ для любого }\epsilon > 0 \}.$$Лемма 8.7. Внутренности всех $$C$$ совпадают:
$$\dot C(x,y) = \dot C(w, z)\text{ для любых }x,y,w,z\in\mathcal O,\ x\neq y,\ w\neq z.$$Доказательство. По второму пункту леммы 8.6,
$$\dot P(x,y)\subseteq\dot P(x,z)-\beta$$для любого $$\beta\in\dot P(y,z)$$. Также это верно для $$\beta = (\gamma(y,z) + \epsilon)\cdot 1 $$.
Аналогично,
$$\dot P(x,z)\subseteq\dot P(w,z)-\alpha$$для любого $$\alpha = (\gamma(w,x) + \epsilon)\cdot 1 ,$$ и получается, что
$$\dot P(x,y)\subseteq\dot P(w,z)-(\gamma(y,z) + \gamma(w,x))\cdot 1.$$Также по второму пункту леммы 8.6,
$$\gamma(y,z) + \gamma(w,x) = \gamma(y,z) + \gamma(w,y) + \gamma(y,x) = \gamma(w,z) - \gamma(x,y).$$Перенося вправо $$\gamma(w,z),$$ получаем, что
$$\dot P(x,y) - \gamma(x,y)\cdot 1 \subseteq\dot P(w,z)-\gamma(w,z)\cdot 1.$$Тогда, поскольку $$x,y,w$$ и $$z$$ мы выбирали произвольно, получается, что все $$\dot P(a,b)-\gamma(a,b)\cdot 1 $$ равны, то есть равны все $$\dot C$$.
Cтоит заметить, что для неразличающихся $$x,y,w,z$$ утверждение леммы 8.7 тоже выполняется. Докажем, например, что $$\dot C(x,y)=\dot C(y, x)$$. Для доказательства выберем $$w\in\mathcal O,$$ отличный от $$x$$ и $$y,$$ и используем лемму 8.7 для пар равенств из следующей цепочки
$$\dot C(x,y)=\dot C(w,y)=\dot C(w,x)= \dot C(y,x).$$Оставляем читателю доказательство остальных случаев частичного равенства $$x,y,z,w$$ между собой.
Доказав, что всевозможные $$\dot C(x,y)$$ равны, обозначим их все через $$C$$. Теперь, в полном соответствии с общей идеей доказательства, можно доказать, что $$C$$ выпукло.
Лемма 8.8. $$C$$ выпукло.
Доказательство. Пусть $$\alpha,\beta\in C \subseteq \mathbb R^{n}$$. Для начала покажем, что $$\alpha + \beta \in C$$. Зафиксируем разные $$x,y,z\in\mathcal O$$. Тогда
$$\gamma(x,y)\cdot\bf 1 + \alpha\in\dot P(x,y)\text{ и }\gamma(y,z)\cdot\bf 1+\beta\in\dot P(y,z)$$по определению $$\gamma(a,b)$$. Cложим их:
$$\gamma(x,z)\cdot\bf 1 + \alpha + \beta\in\dot P(x,z),$$и, следовательно, $$\alpha + \beta\in C$$.
Вторая часть выпуклости – покажем, что если $$\alpha \in C,$$ то и $$\frac\alpha2 \in C$$. Предположим противное: пусть $$\alpha\in C,$$ но $$\frac\alpha2\notin C$$. Тогда
$$\frac\alpha2 + \gamma(x,y)\cdot 1 \notin P(x,y),$$а значит,
$$-\frac\alpha2 - \gamma(x,y)\cdot 1 \in P(y,x).$$Следовательно, $$-\frac\alpha2\in C,$$ и $$\frac\alpha2=\alpha+(-\frac\alpha2)\in C$$. Противоречие.
Таким образом, для всех $$\alpha,\beta\in C \frac{\alpha+\beta}2\in C,$$ то есть $$C$$ выпукло.
Теперь, наконец-то, можно завершать доказательство теоремы. Во-первых, $$\bf 0\notin\dot C,$$ так как нулевой вектор должен быть на границе: мы уже видели, что если $$x \in C,$$ то $$-x \notin C$$.
Вспомним теорему о подпирающей
Зафиксируем исход $$x_0\in\mathcal O$$ и константы
$$C_x = \sum_{i=1}^Nk_i\gamma(x_0, x).$$Докажем теперь все необходимые неравенства, то есть
$$\sum_{i=1}^N k_i(v_i(x) - v_i(y)) \ge C_y - C_x,$$где $$f(v) = x\neq y$$. Если $$f(v) = x\neq y,$$ то $$v(x)-v(y)\in P(x,y)$$. Обозначим
$$\alpha = v(x)-v(y)-\gamma(x,y)\cdot\bf 1.$$Тогда, по определению констант $$k_i$$ и $$P(x,y),$$ $$\alpha\in\bar C$$. Значит, $$\bf k\cdot \alpha\ge 0$$.
Так как $$- \gamma(x,y) = \gamma(x_0,x) - \gamma(x_0,y),$$ то
$$\bf k\cdot \mathbf v(x) + C_x \ge \bf k\cdot \mathbf v(y) + C_y.$$Это и есть утверждение теоремы, так как мы его доказали для произвольного $$P=P(x,y)$$. Доказательство теоремы 8.1 тем самым завершено.
Второе доказательство использует другое условие монотонности и, естественно, пользуется при этом иным методом анализа. Мы должны также задействовать одно дополнительное условие [52].
Определение 8.5. Задим функцию социального выбора $$f : \mathbf V\to\mathbb \mathcal O$$. Будем говорить, что игрок $$i$$ принимает решения, если для каждого $$\mathbf v_{-i} \in \mathbf V_{-i}$$ и $$x \in \bA$$ существует такая функция полезности $$v_i \in V_i,$$ что $$f(v_i, \mathbf v_{-i}) = x$$.
Проще говоря, игрок $$i$$ может вынудить выбор любой из альтернатив для любой комбинации типов других игроков (например задавая "достаточно высокое" значение). Мы уже отмечали, что в том случае, когда существуют только две возможные альтернативы, принцип большинства (выбирать альтернативу большинством голосов, где игрок $$i$$ "подает голос" за $$x$$ по сравнению с $$y,$$ выбирая $$v_i(x) > v_i(y)$$ ) реализуем, и при таком подходе нет ни одного игрока, принимающего решения. Однако для трех и более альтернатив, как мы уже знаем из предыдущего доказательства, каждая выполнимая функция социального выбора должна допускать существование как минимум одного принимающего решения игрока. В дальнейшем мы будем пользоваться тем, что такой игрок существует.
Мы снова доказываем теорему Робертса — теорему 8.1.
Теорема 8.2. Пусть $$|\mathcal O|\ge 3,$$ и $$\mathbf V$$ не ограничено. Тогда для каждой
Далее мы без потери общности будем считать, что игрок 1 решающий.
Введем важное обозначение: будем писать
$$\mathbf v^\prime = \mathbf v + \epsilon 1_{i,x},$$или, что то же самое,
$$\mathbf v^\prime = (v_i + \epsilon 1_{x}, \mathbf v_{-i}).$$То есть через $$\mathbf v^\prime$$ мы будем обозначать вектор, совпадающий с $$\mathbf v$$ за исключением того, что компонента $$v_i(x)$$ увеличена на $$\epsilon$$. А через $$e_j$$ мы будем обозначать
Предыдущее доказательство занималось анализом
Определение 8.6. Для каждых двух различных $$x, y \in \mathcal O$$ и для каждого $$\mathbf v_{-i} \in \mathbf V_{-i}$$ определим
$$\delta^{i}_{xy}(\mathbf v_{-i}) = \inf\left\{\vphantom{1^2} v^\prime_i(x) - v^\prime_i(y)\,\mid\, v^\prime_i \in V_i\text{ и }f(v^\prime_i, \mathbf v_{-i}) = x \right\}.$$По определению, если $$f(\mathbf v) = x,$$ то $$v^\prime_i(x) - v^\prime_i(y) < \delta^{i}_{xy}(\mathbf v_{-i})$$ для всех $$y \in \mathcal O$$. Иными словами, если зафиксировать $$\mathbf v_{-i},$$ то $$\delta^{i}_{xy}(\mathbf v_{-i})$$ — это минимальное значение разницы между $$x$$ и $$y$$ всякий раз, когда $$f$$ выбирает $$x$$.
Пример 8.1. Для
Конец примера 8.1.
Теперь мы хотим исследовать структурные характеристики этого определения для случая неограниченной области и в конце концов показать, что $$\delta^{1}_{xy}(\mathbf v_{-i})$$ — это аффинная функция от разницы векторов $$(\bvn 1(x) - \bvn 1(y))$$. Отсюда и воспоследует свойство аффинной максимизации. Но сначала — немного более техническая лемма, которая установит, что сумма значений $$\delta$$ по циклам небольшой длины равна нулю.
Лемма 8.9.
Доказательство. Сначала докажем, что для любого $$\bf v_{-1} \in \bf V_{-1}$$ и любых исходов $$x, y \in O$$ значение $$\delta^{1}_{xy}(\bf v_{-1})$$ определено (конечно), и
$$\delta^{1}_{xy}(\bf v_{-1}) + \delta^{1}_{yx}(\bf v_{-1}) \ge 0.$$Раз агент $$1$$ принимает решения, то, значит, существует такая функция полезности $$v_{1} \in V_{1},$$ что $$f(v_1, \bf v_{-1}) = x$$. Тогда
$$\delta^{1}_{xy}(\mathbf v_{-i}) \le v_1(x) - v_1(y) < \infty.$$Однако, поскольку агент $$1,$$ опять же, принимает решения, существует и такая функция полезности $$v^{*}_1,$$ что $$f(v^{*}_1, \bf v_{-1}) = y$$. Для каждого из тех $$v^\prime_1 \in V_1,$$ для которых $$f(v^\prime_1, \bf v_{-1}) = x,$$ мы по свойству W-MON знаем, что $$v^\prime_1(x) - v^\prime_1(y) \ge v^{*}_1(x) - v^{*}_1(y)$$. Следовательно,
$$\delta^{1}_{xy}(\mathbf v_{-i}) \ge v^{*}_1(x) - v^{*}_1(y) > - \infty.$$Чтобы доказать, что $$\delta^{1}_{xy}(\bf v_{-1}) + \delta^{1}_{yx}(\bf v_{-1})$$ неотрицательно, зафиксируем произвольное $$\epsilon > 0$$ и рассмотрим такую $$v^{*}_1 \in V_1,$$ что
$$f(v^{*}_1, \bf v_{-1}) = y\text{ и }v^{*}_1(x) - v^{*}_1(y) \le \delta^{1}_{xy}(\mathbf v_{-i}) + \epsilon,$$а также такую $$v^\prime_1 \in V_1,$$ что
$$f(v^\prime_1, \bf v_{-1}) = x\text{ и }v^\prime_1(x) - v^\prime_1(y) \le \delta^{1}_{xy}(\mathbf v_{-i}) + \epsilon.$$По свойству W-MON мы имеем $$v^\prime_1(x) - v^\prime_1(y) \ge v^{*}_1(x) - v^{*}_1(y)$$. Тогда, значит,
$$\delta^{1}_{xy}(\mathbf v_{-i}) + \epsilon \ge v^\prime_1(x) - v^\prime_1(y) \ge v^{*}_1(x) - v^{*}_1(y) \ge - \delta^{1}_{yx}(\mathbf v_{-i}) - \epsilon.$$Следовательно, для любого $$\epsilon > 0$$
$$\delta^{1}_{xy}(\mathbf v_{-i}) + \delta^{1}_{yx}(\mathbf v_{-i}) + 2 \epsilon \ge 0,$$откуда и следует искомое неравенство.
Теперь можно доказать собственно утверждения леммы.
$$v^\prime_1 = v_1 + 3\epsilon \cdot 1_y + \epsilon \cdot 1_x$$.
Тогда $$f(v^\prime_1,\bf v_{-1}) \in {x,y}$$ по свойству W-MON. Однако $$f(v^\prime_1,\bf v_{-1})$$ не может быть равно $$x,$$ так как
$$v^\prime_1(x) - v^\prime_1(y) = (v_1(x) + \epsilon) - (v_1(y) + 3\epsilon) < \delta^{1}_{xy}(\bf v_{-1})$$.
Мы получили, что $$f(v^\prime_1,\bf v_{-1}) = y$$. Но тогда
$$\delta^{1}_{yx}(\bf v_{-1}) \le v^\prime_1(x) - v^\prime_1(y) + 2 \epsilon = - \delta^{1}_{xy}(\bf v_{-1}) + \epsilon,$$
и, таким образом, $$\delta^{1}_{xy}(\mathbf v_{-i}) + \delta^{1}_{yx}(\mathbf v_{-i}) \le \epsilon$$ для каждого $$\epsilon \ge 0$$.
$$f(v_1, \bf v_{-1}) = x,\quad f(v^\prime_1, \bf v_{-1}) = y,\quad f(v^{\prime\prime}_1, \bvn 1) = z$$
(они существуют, потому что агент $$1$$ принимает решения). По правдивости,
$$v_1(x) - p_1(x, \bf v_{-1}) \ge v_1(y) - p_1(y, \bf v_{-1}), \\ v^\prime_1(y) - p_1(y, \bf v_{-1}) \ge v^\prime_1(z) - p_1(z, \bf v_{-1}), \\ v^{\prime\prime}_1(z) - p_1(z, \bf v_{-1}) \ge v^{\prime\prime}_1(x) - p_1(x, \bf v_{-1}).$$(обратите внимание — опять вдруг откуда ни возьмись появляется парадокс Кондорсе!). Отсюда следует, что
$$v_1(x) - v_1(y) + v^\prime_1(y) - v^\prime_1(z) + v^{\prime\prime}_1(z) - v^{\prime\prime}_1(x) \ge 0$$.
В частности,
$$\delta^{1}_{xy}(\bf v_{-1}) + \delta^{1}_{yz}(\bf v_{-1}) + \delta^{1}_{zx}(\bf v_{-1}) \ge 0$$.
Теперь предположим, что существуют такая функция полезности $$\bvn 1$$ и такие исходы $$x, y, z,$$ что
$$\delta^{1}_{xy}(\bf v_{-1}) + \delta^{1}_{yz}(\bf v_{-1}) + \delta^{1}_{zx}(\bf v_{-1}) > 0$$.
По первому пункту этой леммы,
$$[\delta^{1}_{xy}(\bf v_{-1}) + \delta^{1}_{yx}(\bf v_{-1})] + [\delta^{1}_{yz}(\bf v_{-1}) + \delta^{1}_{zy}(\bf v_{-1})] + [\delta^{1}_{zx}(\bf v_{-1}) + \delta^{1}_{xz}(\bf v_{-1})] = 0$$.
Таким образом,
$$\delta^{1}_{xz}(\bf v_{-1}) + \delta^{1}_{zy}(\bf v_{-1}) + \delta^{1}_{yx}(\bf v_{-1}) < 0,$$
что приводит нас к противоречию.
Следующая лемма показывает, что значение $$\delta^{1}_{xy}(\bvn i)$$ зависит только от
$$\bf v_{-1}(x)-\bf v_{-1}(y),$$то есть от $$(n-1)$$ -мерного вектора разностей оценок всех агентов, кроме первого. Вспомним введенные ранее обозначения: $$(\mathbf v - \epsilon \cdot 1_{j,z})$$ означает оценку $$\mathbf v,$$ в которой агент $$j$$ уменьшил значение своей функции для альтернативы $$z$$ на $$\epsilon$$.
Лемма 8.10.
$$\delta^{1}_{xy}(\mathbf v_{-i}) = \delta^{1}_{xy}(\bf v_{-1} - L \cdot 1_{j,z})$$.
$$\bvn 1(x)-\bvn 1(y) = \bf v_{-1}^\prime(x) - \bf v_{-1}^\prime(y).$$
Тогда $$\delta^{1}_{xy}(\bf v_{-1}) = \delta^{1}_{xy}(\bf v_{-1}^\prime)$$.
Доказательство.
$$\delta^{1}_{xy}(\bf v_{-1}) \ge \delta^{1}_{xy}(\bf v_{-1}^\prime)$$.
Предположим противное: пусть равенство неверно, а, значит,
$$\delta^{1}_{xy}(\bf v_{-1}) > \delta^{1}_{xy}(\bvn 1^\prime).$$
Сперва заметим, что, как и в предыдущих доказательствах,
$$\delta^{1}_{yx}(\bf v_{-1}) \ge \delta^{1}_{yx}(\bf v_{-1}^\prime)$$Но
$$\delta^{1}_{xy}(\bf v_{-1}) + \delta^{1}_{yx}(\bf v_{-1}) = 0 = \delta^{1}_{xy}(\bf v_{-1}^\prime) + \delta^{1}_{yx}(\bf v_{-1}^\prime)$$.
Но мы предполагали, что левая часть этого равенства больше, чем правая; таким образом, мы пришли к противоречию.
для которых
$$\bvn 1(x) - \bvn 1(y) = \bf v_{-1}^\prime(x) - \bf v_{-1}^\prime(y).$$Для каждого $$j \neq 1$$ и для каждого $$v_j \in V_j$$ условие S-MON подразумевает, что добавление аддитивной константы ко всем координатам $$v_j$$ не изменит выбора $$f$$. Таким образом, мы можем без потери общности предположить, что $$v_j(x) = v^\prime_j(x)$$ и $$v_j(y) = v^\prime_j(y)$$. Теперь определим
$$v^{\prime\prime}_j(w) = \min \left\{\vphantom{1^2} v_j(w), v^\prime_j(w)\right\}$$
для каждого $$w \in \mathcal O$$. Тогда первый пункт этой леммы позволяет сделать вывод о том, что
$$\delta^{1}_{xy}(\bf v_{-1}) = \delta^{1}_{xy}(\bf v_{-1}^\prime) = \delta^{1}_{xy}(v^{\prime\prime}_{-1})$$.
Вот и все, лемма доказана.
Итак, мы доказали, что $$\delta^{1}_{xy}(\mathbf v_{-i})$$ зависит только от $$\bvn 1(x)-\bvn 1(y)$$. Таким образом, отныне мы можем рассматривать $$\delta^{1}_{xy}(\bvn i)$$ как функцию $$\delta^{1}_{xy}(\bvn 1(x)-\bvn 1(y))$$. В этих (слегка измененных) обозначениях можно сформулировать следующее следствие.
Следствие 8.2.1. Для любой пары векторов $$\bf{r}, \bf{t} \in \mathbb R^{n-1}$$ и любой тройки исходов $$x,y,z \in \mathcal O$$ верно, что
$$\delta^{1}_{xy}(\bf{r}) + \delta^{1}_{yx}(-\bf{r}) = 0,\\ \delta^{1}_{xy}(\bf{r}) + \delta^{1}_{yz}(\bf{t}) + \delta^{1}_{zx}(-\bf{r}- \bf{t}) = 0.$$В частности,
$$\delta^{1}_{xy}(\bf{0}) + \delta^{1}_{yx}(\bf{0}) = 0\text{ и } \delta^{1}_{xy}(\bf{0}) + \delta^{1}_{yz}(\bf{0}) + \delta^{1}_{zx}(\bf{0})= 0.$$Лемма 8.11. Для каждого $$\bf{r}, \bf{s}, \bf{t} \in \mathbb R^{n-1}$$ и для любой тройки исходов $$x,y,z \in \mathcal O$$
$$\delta^{1}_{yx}(\bf{r} + \bf{t}) - \delta^{1}_{yx}(\bf{r}) = \delta^{1}_{zx}(\bf{s} + \bf{t}) - \delta^{1}_{zx}(\bf{s}).$$Доказательство. Достаточно показать, что
$$\delta^{1}_{zx}(\bf{s}) - \delta^{1}_{yx}(\bf{r}) = \delta^{1}_{zx}(\bf{s} + \bf{t}) - \delta^{1}_{yx}(\bf{r} + \bf{t}).$$По следствию 8.2.1,
$$\delta^{1}_{zx}(\bf{s}) - \delta^{1}_{yx}(\bf{r}) = \delta^{1}_{zx}(\bf{s}) + \delta^{1}_{xy}(-\bf{r}) = -\delta^{1}_{yz}(\bf{r}-\bf{s}).$$Аналогично,
$$\delta^{1}_{zx}(\bf{s} + \bf{t}) - \delta^{1}_{yx}(\bf{r} + \bf{t}) = -\delta^{1}_{yz}(\bf{r} - \bf{s}).$$Теперь нам придется ненадолго
В формулировке предложения "монотонность" означает следующее: функция $$g : \mathbb R^n \to \mathbb R$$ монотонная, если для любых векторов $$\bf{a}, \bf{b} \in \mathbb R^n$$ из $$\beta_i \ge \alpha_i$$ для каждого $$i$$ следует, что $$g(\bf{b}) \ge g(\bf{a})$$. Иначе говоря, это монотонность относительно частичного порядка на векторах, который мы тут уже неоднократно вводили и использовали.
Предложение 8.1. Зафиксируем
для любого $$\bf r \in \mathbb R^n$$ и любого $$\delta > 0$$ (где $$\bf e_i$$ — это
Доказательство. Доказательство мы для большей наглядности разобьем на две леммы. Первая из них рассматривает одномерный случай.
Лемма 8.12. Предположим, что $$m : \mathbb R_+ \to \mathbb R$$ — монотонно неубывающая функция, и существует такая функция $$h : \mathbb R_+ \to \mathbb R_+,$$ что
$$m(x + \delta)-m(x) = h(\delta)$$для любых $$x,\delta \in \mathbb R_+$$. Тогда существует такое число $$w \in \mathbb R_+,$$ что $$h(\delta) = w \delta$$.
Доказательство. Пусть $$w = h(1)$$ (заметим, что $$w \ge 0,$$ поскольку $$m$$ не убывает). Сначала мы докажем, что для любых двух целых чисел $$p$$ и $$q$$ $$h(p/q) = w (p/q)$$. Заметим, что
$$h(1) = m(1) - m(0) = {\sum_{i=0}^{q-1}m\left(\vphantom{1^2}(i + 1)/q\right)} - m(i/q) = q \cdot h(1/q).$$Таким образом, $$h(1/q) = (1/q) \cdot h(1)$$. Аналогично,
$$h(p/q) = m(p/q)-m(0)= {\sum_{i=0}^{p-1}m\left(\vphantom{1^2}(i + 1)/q\right)} - m(i/q) = \\ = p \cdot (1/q) = (p/q) \cdot h(1) = (p/q) \cdot w.$$Теперь стандартным образом перейдем по полноте от рациональных чисел к вещественным: докажем, что для любого вещественного $$\delta$$ $$h(\delta) = \delta w$$. Заметим, что так как $$m$$ монотонно не убывает, $$h$$ тоже должна быть монотонно неубывающей. Предположим от противного, что $$h(\delta) > w \delta$$. Возьмем некоторое
Лемма 8.13. Рассмотрим подмножество $$X \subseteq \mathbb R^n,$$ обладающее следующим свойством: если $$\bf x \in X$$ и $$\bf y \ge x,$$ то $$\bf y \in X$$. Рассмотрим монотонно неубывающую функцию $$m: X \to \mathbb{R}$$ и предположим, что существуют такие числа $$w_1,\ldots,w_n\in\mathbb R,$$ что
$$m(\bf{x} + \delta \bf{e}_i) - m(x) = w_i \delta$$для любого $$i,$$ любого $$\bf{x} \in X$$ и любого $$\delta > 0$$. Тогда существует такая константа $$\gamma \in \mathbb{R},$$ что
$$m(\bf x) = {\sum\limits_{i=1}^{n}w_i\cdot x_i} + \gamma.$$Доказательство. Сначала мы докажем, что для любых таких $$\bf{x},\bf y \in X,$$ что $$y_i \ge x_i$$ для всех $$i,$$ в этом случае
$$m(\bf y) = m(\bf x) + {\sum\limits_{i=1}^{n}w_i\cdot (y_i - x_i)}.$$Заметим, что $$(y_1, x_2, \ldots, x_n) \in X$$ и
$$m(y_1, x_2, \ldots, x_n) = m(\bf x) + h_1(y_1 - x_1).$$Повторяя этот шаг $$n$$ раз, мы получаем, что
$$m(\bf y) = m(\bf x) + {\sum\limits_{i=1}^{n}w_i\cdot (y_i - x_i)}.$$Теперь зафиксируем любой $$\bf x^* \in X$$. Докажем, что для любого $$\bf x \in X$$
$$m(\bf x) = m(\bf x^*) + \sum\limits_{i=1}^{n}w_i \left(x_i - x^*_i\right).$$Выберем такой вектор $$\bf y,$$ что $$y_i \ge \max \{ x_i, x^*_i\}$$ для всех $$i$$. Таким образом,
$$m(\bf y) = m(\bf x) + {\sum\limits_{i=1}^{n}w_i(y_i - x_i)},$$а также
$$m(\bf y) = m(\bf x^*) + \sum\limits_{i=1}^{n}w_i \left(y_i - x^*_i\right),$$из чего немедленно следует доказываемое утверждение.
Эти две леммы и составляют доказательство предложения 8.1.
Теперь вернемся к доказательству теоремы Робертса. Нам осталось уже буквально одно последнее усилие.
Лемма 8.14. Существуют такие неотрицательные вещественные константы $$k_2,\ldots,k_n,$$ что для каждого $$\bf r \in \mathbb R^{n-1}$$ и для любых исходов $$y,z \in \mathcal O$$
$$\delta^{1}_{yz}(\bf r) = -{\sum_{j=2}^nk_{jrj} + \delta^{1}_{yz}(\bf 0)}.$$Доказательство. Прежде всего заметим, что $$\delta^{1}_{yz}(\cdot)$$ — это монотонно невозрастающая вещественная функция. Если $$f(v_1, \bf v_{-1}) = y,$$ то тогда $$f(v_1, \bf v_{-1} + \epsilon \bf 1_{j,y}) = y$$ по S-MON. Тогда инфимум на $$\bf v_{-1} + \epsilon \cdot 1_{j,y}$$ получается на большем множестве, и, следовательно, он меньше. Значит, $$\delta^{1}_{yz}(\cdot)$$ невозрастает.
По лемме 8.11 и предложению 8.1 получаем, что существуют такие вещественные константы $$k^{yz}_j,$$ что
$$\delta^{1}_{yz}(\bf{r}) = {\sum^n_{j=2}k^{yz}_{jrj} + \delta^{1}_{yz}(\bf{0})}.$$Поскольку $$\delta^{1}_{yz}(\cdot)$$ является монотонно невозрастающей функцией, все $$k^{yz}_j$$ должны быть неположительными. Перепишем для удобства это равенство как
$$\delta^{1}_{yz}(\bf{r}) = -{\sum^n_{j= 2}k^{yz}_{jrj} + \delta^{1}_{yz}(\bf{0})},$$и будем отныне считать, что константы $$k^{yz}_j$$ неотрицательны.
Нам осталось показать, что $$k^{xy}_j = k^{wz}_j$$ для любых $$x,y,z,w \in\mathcal O$$. Выше мы получили, что $$k^{xy}_j = \delta^{1}_{xy}(\bf{0}) - \delta^{1}_{xy}(\bf e_j)$$. По следствию 8.2.1 мы получаем $$k^{xy_j = k^{zx}_j,$$ потому что $$\delta^{1}_{xy}(\bf e_j) + \delta^{1}_{yz}(\bf{0}) + \delta^{1}_{xy}(-\bf e_j) = 0$$. Аналогично, $$k^{zx}_j = k^{wz}_j$$.
Теперь мы легко можем завершить доказательство теоремы. Зафиксируем произвольную альтернативу $$w \in \mathcal O$$ и зададим константы $$C_x = \delta^{1}_{wx}(\bf{0})$$ для всех $$x \neq w,$$ а $$C_w$$ положим равной нулю. Зафиксируем $$\mathbf v \in V$$ и предположим, что $$f(\mathbf v) = x$$. Следовательно, для любого другого исхода $$y \ne x$$
$$v_1(x) - v_1(y) \ge \delta^{1}_{xy}(\bf v_{-1}) = -{\sum_{j\ne 1}k_j\left(\vphantom{1^2}v_j(x) - v_j(y)\right)+ \delta^{1}_{xy}(\bf{0})}.$$Так как $$\delta^{1}_{xy}(\bf{0}) = \delta^{1}_{xw}(\bf{0}) + \delta^{1}_{wy}(\bf{0})$$ и $$\delta^{1}_{xw}(\bf{0}) = - \delta^{1}_{wx}(\bf{0}),$$ мы, переставляя элементы, получаем, что
$$v_1(x) + {\sum_{j\ne 1}k_jv_j(x)} + C_x \ge v_1(y) + {\sum_{j\neq1}k_jv_j(y)} + C_y,$$что и требовалось доказать.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.