Эффективные и оптимальные механизмы

Введение

К примеру, в парадоксе Браесса, который мы рассматривали в лекции 2, "хорошесть" можно было признать самоочевидной: каждому водителю хочется доехать до цели побыстрее, и это совершенно естественным образом совпадает с чаяниями организаторов траспортной развязки — максимально увеличить общую пропускную способность конструкцииМожет показаться, что водитель хочет побыстрее проехать сам, а организаторы хотят уменьшить среднее время проезда, и здесь кроется конфликт. На самом деле, конечно, конфликта нет, потому что в любом равновесии все водители проходят маршрут за одно и то же время.

Но что такое "хороший аукцион"? С одной стороны, "хороший" аукцион должен наиболее эффективно распорядиться лотами, на него выставленными: хотелось бы, чтобы вещь досталась тому, кому она действительно более всех нужна. С другой стороны, аукционера тоже забывать не следует: в конце концов, именно он устраивает аукцион так, как ему удобнее, и вполне возможно, что он захочет максимизировать свою прибыль, а вовсе не эфемерное "всеобщее счастье" (это понятие мы чуть ниже конкретизируем).

В этой лекции мы будем рассматривать прямые механизмы, в которых у каждого агента просто спрашивают его тип. Более того, интуиция этой главы полностью ограничивается ситуацией аукциона, в котором продают одну вещь (один лот аукциона). Множество типов агента в такой постановке — это просто множество $$[0,\omega_i]$$ возможных ценностей, которые агент может приписать продаваемой вещи. Ценность агента $$x_i$$, взятая (предположим) по распределению $$X_i$$, остается скрытой, известной только ему. При начале аукциона агент подает некоторую ставку $$b_i$$ ; в прямом механизме у агента спрашивают его тип, но агент не обязан сообщать свою истинную ценность — если ему это выгодно, он может соврать. А в результате аукциона один из агентов приобретет желаемую вещь и тем самым получит свою внутреннюю ценность $$x_i$$, заплатив за это, конечно, некоторую цену.

Прямой механизм реализует эту идеологию. Он полностью описывается двумя параметрами: правилом распределения $$\mathbf Q$$ и правилом выплаты $$\mathcal M$$. В случае аукциона с одной вещью $$\mathbf Q:\mathcal B\to 1..N$$, а $$\mathcal M:\mathcal B\to\mathbb R^N$$, где $$\mathcal B=B_1\times\ldots\times B_N$$ — множество возможных векторов ставок агентов. Иначе говоря, правило $$\mathbf Q$$ определяет, какой из $$N$$ агентов получит продаваемую вещь, а правило $$\mathcal M$$ определяет, сколько каждый агент при этом заплатит аукционеру ( $$M_i$$, кстати говоря, вполне может быть и отрицательным).

Теперь можно определить два понятия "хорошего аукциона", на которые мы уже намекали выше. Эффективный аукцион хорош для агентов — для участников аукциона.

Определение 5.1. Правило распределения $$\mathbf Q:\B\to 1..N$$ называется эффективным, если оно при эгоистичных действиях агентов максимизирует общественное благосостояние (social welfare) — суммарную внутреннюю полезность всех агентов:

$$\forall\mathbf x\ \mathbf Q(\mathbf x)\in argmax_{\mathbf Q}\sum_{j=1}^NQ_jx_j.$$

Прямой механизм $$(\mathbf Q,\mathcal M)$$ называется эффективным, если у него эффективное правило распределения.

Отметим, что свойство эффективности имеет отношение только к $$\mathbf Q$$. Правило выплаты на эффективность вообще не влияет. В простейшем случае аукциона с одним лотом механизм эффективен, если объект достается тому, кому он действительно больше всего нужен, то есть тому агенту, у которого внутренняя ценность $$x_j$$ максимальна.

А вот оптимальный механизм, в отличие от эффективного, хорош не для покупателей, а для продавца.

От слова revenue.:

$$\mathbf E(R) = \sum\limits_{i=1}^N\mathbf E[m_i(X_i)],$$

где $$m_i(X_i)$$ — выплата агента $$i$$, $$X_i$$ — его распределение ценностей, а $$x_i$$ — конкретное значение ценности агента.

Математическое ожидание здесь берется исключительно по возможным типам агентов $$X_i$$, ведь дальнейший ход аукциона строго предопределен: каждый агент рассчитает наиболее выгодную для себя ставку $$b_i$$, правило распределения получит все эти ставки и выдаст вещь одному из агентов, правило выплат по тем же ставкам рассчитает выплаты.

Аукцион второй цены с резервной ценой

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

Рассмотрим аукцион второй цены (он же аукцион Викри). Напомним, что в этом аукционе победитель платит вторую по величине ставку. Простое рассуждение в теореме 2.1 уже убедило нас, что аукцион второй цены правдив: агентам в нем невыгодно врать. Следовательно, аукцион второй цены эффективен в смысле определения 5.1: так как каждый агент сообщает свою истинную внутреннюю ценность, и аукцион распределяет вещь агенту с наивысшей ставкой, то, следовательно, вещь достанется агенту с наивысшей внутренней ценностью: $$Q_i=1$$ тогда и только тогда, когда $$Q_i\in argmax_{i=1..N}x_i$$. А это и означает, что $$\mathbf Q(\mathbf x)\in argmax_{\mathbf Q}\sum_{j=1..N}Q_jx_j$$, ведь вещь всего одна.

Сделаем теперь одну модификацию в нашем (уже эффективном) аукционе: добавим в него резервную цену $$r$$. Резервная цена - это такая сумма, что:

выигравший агент платит максимум между второй ставкой и $$r$$, то есть выплата победителя не может быть меньше $$r$$ ;

если все ставки окажутся ниже $$r$$, продавец оставит товар себе.

Иначе говоря, резервная цена — минимальная, по которой продавец согласен расстаться с товаром. Поэтому агенты, внутренние ценности которых меньше $$r$$, могут просто не участвовать в аукционе — у них все равно нет ни малейшего шанса получить от него доход. А по выплатам данный аукцион будет отличаться от аукциона Викри только в том случае, когда ровно один агент объявит ставку выше резервной цены; если таковых будет хотя бы двое, победитель просто заплатит вторую цену.

Исследуем теперь вопрос о том, каковы будут стратегии и, как следствие, выплаты агентов в новом модифицированном аукционе по сравнению с обычным аукционом Викри.

Во-первых, стратегии не изменятся — по-прежнему доминантная стратегия в том, чтобы говорить правду (напомним, что доминантная стратегия — это такая стратегия, которая выгоднее любой другой вне зависимости от стратегий других агентов). По-прежнему, если агент делает ставку большую, чем его внутренняя ценность, то может случиться так, что ему придется заплатить больше его внутренней ценности, потерпев тем самым убыток. А если он ставит меньше, чем его настоящая цена, то он может не получить объект, несмотря на то, что при правдивой ставке мог заплатить меньше настоящей цены. Рассуждения теоремы 2.1 останутся справедливыми практически без изменений. Таким образом, наличие резервной цены никак не повлияет на то, что аукцион будет правдивым.

Однако изменятся выплаты агентов. В аукционе Викри ожидаемая выплата агента составляла

$$m(x)=\int_0^xyg(y)dy,$$

где $$g(x)=(N-1)f(x)F(x)^{N-2}$$ — плотность второй порядковой статистики. Проще говоря, ожидаемая выплата в аукционе второй цены составляет (что вполне логично) ожидание второй сверху ставки.

Теперь рассмотрим выплату агента в аукционе с резервной ценой. Он, который ставит ровно $$r$$, ожидает заплатить просто $$rG(r)$$, поскольку вероятность того, что агент выиграет, заплатив $$r$$, составляет $$G(r)$$ (функция распределения второй порядковой статистики, первообразная $$g(r)$$ ). Если же агент ставит больше $$r$$, то он ожидает заплатить

$$m(x,r) = rG(r) + \int_r^xyg(y)dy,$$

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

Проверим теперь, что принцип эквивалентности доходности работает и с резервной ценой. В аукционе первой цены анализ будет точно таким же, как раньше, только теперь участник с ценностью $$x<r$$ вообще не будет участвовать, и оптимальная ставка агента станет равной

$$\beta(x)=\mathbf E[\max\{Y_1,r\}|Y_1<x].$$

Раньше это было просто ожидание $$Y_1$$, а теперь стал максимум из $$Y_1$$ и $$r$$, поскольку ставка не может быть меньше $$r$$. Получаем, что

$$\beta(x)=\mathbf E[\max\{Y_1,r\}|Y_1<x] = r\frac{G(r)}{G(x)}+\frac1{G(x)}\int_r^xyg(y)dy.$$

Здесь первое слагаемое относится к случаю, когда $$Y_1<r$$, а второе — к случаю, когда $$Y_1>r$$. Так как $$G(x)$$ — вероятность того, что $$Y_1<x$$, то ожидаемая выплата агента составит $$m(x,r)=\beta(x)G(x)$$. Умножая выражение справа на $$G(x)$$, получим ту же самую выплату для агента $$i$$, что и в аукционе второй цены:

$$m(x,r) = rG(r) + \int_r^xyg(y)dy.$$

Итак, доходность у аукционов первой и второй цены одинаковая. Найдем ожидаемую доходность продавца от одного агента:

$$\mathbf E[m(X,r)] = \int_r^{\omega} m(x,r)f(x)dx =...$$

Подставим значение $$m$$:

$$...= \int_r^{\omega} \left(rG(r) + \int_r^xyg(y)dy\right)f(x)dx =...$$

Во втором из этих интегралов, $$\int_r^{\omega}\int_r^x f(x)yg(y)dydx$$, нам нужно изменить порядок интегрирования. Напомним, что это можно делать без каких-либо проблем и дополнительных условий, если подынтегральная функция ограничена, а область интегрирования компактна. В нашем случае все условия очевидно выполнены, и остается только рассмотреть, по какой именно области мы интегрируем; она изображена на рис. 5.1.

(рис 5.1) Область интегрирования интеграла

В итоге получается

$$...= rG(r)\int_r^{\omega} f(x)dx + \int_r^{\omega} \left(\int_y^{\omega} f(x)dx\right)yg(y)dy.$$

Суммарно мы получили формулу

$$\begin{equation}\label{eq3:respay} \mathbf E[m(X,r)] = rG(r)(1-F(r)) + \int_r^\omega y(1-F(y))g(y)dy. \end{equation}$$

Ранее мы уже доказывали, что аукцион с резервной ценой будет эффективным. Теперь давайте попробуем, не меняя его вид, сделать его настолько оптимальным, насколько это возможно: максимизируем доходность продавца. Обозначим через $$x_0$$ его собственную внутреннюю ценность объекта (сумму, в которую он оценивает тот факт, что объект останется у него). Заметим, что раньше мы все время рассматривали частный случай при $$x_0=0$$. Тогда общий доход продавца от установки резервной цены $$r$$ вычисляется как

$$\Pi_0 = N\mathbf E[m(X,r)] + F(r)^Nx_0,$$

где первое слагаемое нам уже знакомо, а второе относится к случаю, когда никто не получит объект, то есть все $$N$$ ставок меньше $$r$$.

Чтобы максимизировать, продифференцируем по $$r$$, подставив вместо $$\mathbf E[m(X,r)]$$ выражение (5.1) и не забывая, что $$G(x)=F(x)^N$$:

$$\frac{d\Pi_0}{dr}=\frac{d}{dr}\left(rG(r)\left(\vphantom{1^2}1-F(r)\right) + \int_r^\omega y\left(\vphantom{1^2}1-F(y)\right)g(y)dy + F(r)^Nx_0\right) = \\ = G(r)\left(\vphantom{1^2}1-F(r)\right) + rg(r)\left(\vphantom{1^2}1-F(r)\right) - \\ - rG(r)f(r) - r\left(\vphantom{1^2}1-F(r)\right)g(r) + Nf(r)F(r)^{N-1}x_0 = \\ = N\left(\vphantom{1^2}1-F(r)-rf(r)\right)G(r) + NG(r)f(r)x_0.$$

Введем (точнее, вспомним из статистики) новое обозначение — так называемую функцию риска. Эта часто встречающаяся в статистике функция показывает, грубо говоря, мгновенную вероятность "выжить", если считать $$F(x)$$ распределением вероятности "смерти":

$$\lambda(x) = \frac{f(x)}{1-F(x)}.$$

Пример 5.1. Рассмотрим ситуацию, которая очень часто возникает в медицинской статистике. Предположим, что у нас есть некая выборка людей, которые либо выжили, либо умерли после того или иного заболевания или лечения. Для каждого человека дано время его жизни после начала заболевания. Как описать получающееся распределение вероятностей?

Введем функцию, которая показывает вероятность человека выжить после времени $$T$$ (буква $$S$$ — от слова "survival"):

$$S(t) = p(T > t),$$

где $$T$$ — случайная величина, показывающая время до смерти. Соответственно,

$$S(t) = p(T>t) = 1-p(t\le T) = 1-F(t),$$

где $$F$$ — функция распределения величины $$T$$. А функция риска тогда показывает, какова плотность вероятности умереть в данный момент времени:

$$\lambda(t)dt = p(T\le t+dt\mid T>t) = \frac{p(t < T\le t+dt)}{p(t < T)}=\frac{f(t)dt}{S(t)},\\ \lambda(t) = \frac{f(t)}{1-F(t)}.$$

Конец примера 5.1.

Тогда в терминах функции риска производная общего дохода продавца выражается как

$$\frac{d\Pi_0}{dr}=N\left(\vphantom{1^2}1-(r-x_0)\lambda(r)\right)\left(\vphantom{1^2}1-F(r)\right)G(r).$$

При $$x_0>0$$ производная

$$\frac{d\Pi_0}{dr}(x_0)=N\left(\vphantom{1^2}1-F(x_0)\right)G(x_0)$$

положительна, то есть продавцу выгодно установить резервную цену $$r>x_0$$. Производная обнуляется только в точке $$x_0=0$$, но при этом тоже выгодно установить резервную цену $$r>0$$, что подтвердится в примере ниже. Иначе говоря, резервная цена должна быть выше ценности продукта для продавца.

А максимум доходности продавца получится, если

$$(r^*-x_0)\lambda(r^*)=1,\text{ что эквивалентно }r^*-\frac{1}{\lambda(r^*)} = x_0.$$

Пример 5.2. Подсчитаем оптимальную резервную цену для равномерного распределения ценностей агентов на $$[0,1]$$. Найдем ожидаемый доход у продавца в общем случае и в случае аукциона без резервной цены. Во-первых, поскольку ценности равномерно распределены на $$[0,1]$$,

$$F(x)=x,\quad f(x)=1.$$

Это значит, что

$$\lambda(x)=\frac{f(x)}{1-F(x)}=\frac{1}{1-x}.$$

Подсчитаем оптимальную резервную цену $$r^*$$:

$$x_0=r^*-\frac{1}{\lambda(r^*)}=2r^*-1.$$

Пусть $$x_0=0$$, тогда $$r^*=\frac{1}{2}$$ — искомая резервная цена.

Найдем теперь ожидаемый доход продавца:

$$\Pi_0=NrG(r)\left(\vphantom{1^2}1-F(r)\right) + \int_r^1 y\left(\vphantom{1^2}1-F(y)\right)g(y)dy + F(r)^Nx_0.$$

Зная, что $$G(x)=x^N$$, а значит, $$g(x)=Nx^{N-1}$$, после упрощения получаем

$$\Pi_0=\frac{N^2}{(N+1)(N+2)}+\frac{Nr^{N+1}}{N+1}-\frac{2Nr^{N+2}}{N+2}.$$

Следовательно, ожидаемый доход продавца без резервной цены (в случае $$r=0$$ ) равен первому слагаемому $$\frac{N^2}{(N+1)(N+2)}$$. А при росте резервной цены ожидаемые доходы понемногу растут, достигая максимума при $$r=\frac12$$.

Конец примера 5.2.

Последнее замечание, которое хочется высказать в этом параграфе, заключается в том, что вместо резервной цены аукционер может с совершенно тем же эффектом ввести плату за участие. Резервная цена $$r$$ отсекает участников с ценностями $$x<r$$. То же самое получится, если заставить каждого агента заплатить "за вход"

$$e = \int_0^rG(y)dy,$$

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

Здесь, правда, нужно оговориться, что резервная цена и плата за вход эквивалентны так, как указано выше, только в одном важном предположении: о том, что участвующие в аукционе агенты нейтральны к риску (см. лекцию 4). Если же агенты осторожны(risk-averse), не любят риск, как часто бывает на практике, то плата за участие окажется для них более серьезным барьером, чем резервная цена, и тогда эквивалентность нарушится в сторону уменьшения платы за вход [35].

Оптимальные механизмы

Теперь вернемся к более общей ситуации и начнем наши рассуждения с оптимальных механизмов. Чтобы построить оптимальный механизм, нужно для прямого механизма $$(\mathbf Q, \mathcal M)$$ максимизировать ожидание дохода продавца:

$$\mathbf E(R) = \sum\limits_{i=1}^N\mathbf E[m_i(X_i)],$$

где $$X_i$$ — распределение ценностей агента $$i$$, а $$m_i(X_i)$$ — его выплата. Далее мы подсчитаем это ожидание явно, но сначала вспомним обозначения доходности и выплаты агентов. Через $$q_i(z_i)$$ мы обозначаем ожидаемую доходность агента $$i$$, когда он говорит $$z_i$$, а остальные говорят правду:

$$q_i(z_i) = \int_{\mathcal X_{-i}}Q_i(z_i,\mathbf x_{-i})f_{-i}(\mathbf x_{-i})d\mathbf x_{-i}.$$

А через $$m_i(z_i)$$ — ожидаемую выплату агента $$i$$ в той же ситуации:

$$m_i(z_i) = \int_{\mathcal X_{-i}}M_i(z_i,\mathbf x_{-i})f_{-i}(\mathbf x_{-i})d\mathbf x_{-i}.$$

Напомним, что отрицательные индексы означают "все, кроме"; например, $$f_{-i}(\mathbf x_{-i})$$ означает распределение ценностей всех агентов, кроме агента $$i$$.

Для вывода ожидаемого дохода продавца будем использовать формулу для ожидаемой выплаты $$m_i(x_i)$$ агента $$i$$, которую мы получали в теореме об эквивалентности доходности (теорема 4.1):

$$\mathbf E[m_i(X_i)] = \int_0^{\omega_i}m_i(x_i)f_i(x_i)dx_i = \\ = m_i(0) + \int_0^{\omega_i}q_i(x_i)x_if_i(x_i)dx_i - \int_0^{\omega_i}\int_0^{x_i}q_i(t_i)f_i(x_i)dt_idx_i.$$

Преобразуем двойной интеграл, поменяв в нем порядок интегрирования. Здесь снова никаких теоретических проблем с изменением порядка не возникает; область интегрирования показана на рис. 5.2.

(рис 5.2) Область интегрирования интеграла$$\int_0^{\omega_i}\int_0^{x_i}q_i(t_i)f_i(x_i)dt_idx_i = \int_0^{\omega_i}\int_{t_i}^{\omega_i}q_i(t_i)f_i(x_i)dx_idt_i = \\ = \int_0^{\omega_i}(1-F_i(t_i))q_i(t_i)dt_i.$$

Запишем снова ожидаемую выплату агента $$i$$ и вспомним, что $$q_i$$ по определению — интеграл по $$\mathbf x_{-i}$$. Тогда интегралы по $$x_i$$ и $$\mathbf x_{-i}$$ весьма удобно объединятся:

$$\mathbf E[m_i(X_i)] = m_i(0) + \int_0^{\omega_i}\left(x_i - \frac{1-F_i(x_i)}{f_i(x_i)}\right)q_i(x_i)f_i(x_i)dx_i = \\ = \int_\mathcal X\left(x_i - \frac{1-F_i(x_i)}{f_i(x_i)}\right)Q_i(\mathbf x)f(\mathbf x)d\mathbf x.$$

В итоге, просуммировав по всем агентам, получаем ожидаемый доход продавца:

$$\mathbf E[R] = \sum_{i=1}^N\mathbf E[m_i(X_i)] =\sum_{i=1}^Nm_i(0)+\sum_{i=1}^N\int_{\mathcal X}\left(x_i - \frac{1-F_i(x_i)}{f_i(x_i)}\right)Q_i(\mathbf x)f(\mathbf x)d\mathbf x.$$

Осталось максимизировать это выражение при следующих условиях:

правдивость, что равносильно неубыванию $$q_i$$ ;

рациональность, что равносильно $$m_i(0)\le 0$$, то есть если у агента собственная ценность $$0$$, то он должен заплатить не больше $$0$$, чтобы не быть в убытке.

Все эти равносильности уже объяснялись в лекции 4.

Введем для упрощения записи понятие виртуальной ценности предмета для агента $$i$$:

$$\psi_i(x_i)=x_i - \frac{1-F_i(x_i)}{f_i(x_i)}.$$

Смысл виртуальной ценности в том, что продавец должен максимизировать $$\psi_i(x_i)$$, если хочет быть оптимальным. Заметим, что если максимизировать $$x_i$$, то он будет эффективным — вот и вся разница между эффективностью и оптимальностью.

Докажем, что $$\mathbf E[\psi_i(X_i)] = 0$$:

$$\mathbf E[\psi_i(X_i)]=\mathbf E(X_i)-\int_{X_i} \frac{1-F_i(x_i)}{f_i(x_i)}f(x_i)dx_i=\mathbf E(X_i)-\int_{X_i}\left(1-F_i(x_i)\right)dx_i.$$

Рассмотрим теперь отдельно интеграл справа. Поменяем порядок интегрирования, как уже было сделано в показанном на рис. 5.2 случае:

$$\int_0^{\omega_i}\left(1-F_i(x_i)\right)dx_i = \int_0^{\omega_i}\left(\int_{x_i}^{\omega_i} f(y)dy\right)dx_i = \\ = \int_0^{\omega_i}\left(\int_0^y dx_i\right)f(y)dy = \int_0^{\omega_i} f(y)ydy = \mathbf E(X_i).$$

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

Будем называть задачу дизайна механизмов регулярной, если $$\psi_i$$ является возрастающей функцией от $$x_i$$ для любого $$i$$ . Это эквивалентно тому, что функция риска $$\lambda_i$$ возрастает, так как

$$\psi_i(x_i) = x_i - \frac1{\lambda_i(x_i)}.$$

В дальнейшем мы будем рассматривать только регулярные задачи.

Запишем ожидаемый доход продавца в терминах виртуальных ценностей:

$$\mathbf E[R]=\sum_{i=1}^Nm_i(0)+\sum_{i=1}^N\int_{\mathcal X}\psi_i(x_i)Q_i(\mathbf x)f(\mathbf x)d\mathbf x.$$

Рассмотрим подынтегральное выражение $$\sum_{i=1}^N\psi_i(x_i)Q_i(\mathbf x)$$. $$\mathbf Q$$ похожа на весовую функцию, взвешивающую $$\psi_i$$. Резонно было бы дать максимальный вес максимальному $$\psi_i$$ (если он положительный), а про остальные забыть. Это максимизировало бы функцию в каждой точке, а значит, и интеграл тоже. Это и будет идеей конструкции, но нам еще придется учесть ограничения (правдивость и рациональность).

Итак, рассмотрим прямой механизм $$(\mathbf Q, \mathcal M)$$, у которого выполняются следующие свойства:

Функция распределения $$\mathbf Q$$ распределяет объект покупателю $$i$$ с положительной вероятностью тогда и только тогда, когда у него максимальная и неотрицательная виртуальная ценность:

$$Q_i(\mathbf x)>0\quad \Leftrightarrow\quad \psi_i(x_i)=\max_{j=1..N}\psi_j(x_j)\ge 0$$.

Если покупателей с максимальным $$\psi_i(x_i)$$ несколько, то на них может быть любое положительное распределение $$\mathbf Q$$, то есть просто не важно, кому именно из них достанется объект.

Плата $$\mathcal M$$ определяется следующим образом:

$$M_i(\mathbf x)=Q_i(\mathbf x)x_i - \int_0^{x_i}Q_i(z_i,\mathbf x_{-i})dz_i$$.

Такая функция платы нужна для того, чтобы выполнялось условия рациональности.

Оказывается, что (при условии регулярности) это и есть оптимальный механизм.

Теорема 5.1. Для регулярной задачи дизайна механизмов механизм $$(\mathbf Q,\mathcal M)$$, где

$$Q_i(\mathbf x)=\begin{cases} 1, \psi_i(x_i)\ge\max_{j\neq i}\psi_j(x_j)\text{ и }\psi_i(x_i)\ge 0,\\ 0, \text{в противном случае},\end{cases} \\ M_i(\mathbf x)=Q_i(\mathbf x)x_i - \int_0^{x_i}Q_i(z_i,\mathbf x_{-i})dz_i,$$

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

Доказательство. Во-первых, покажем правдивость построенного нами механизма. Пусть $$z_i<x_i$$. Тогда, по регулярности, $$\psi_i(z_i)<\psi_i(x_i)$$, и, значит,

$$\forall\mathbf x_{-i}\quad Q_i(z_i,\mathbf x_{-i})\le Q_i(x_i,\mathbf x_{-i}).$$

Значит, $$q_i$$ неубывающая, то есть механизм правдивый.

Во-вторых, покажем рациональность. Очевидно, что

$$M_i(0,\mathbf x_{-i})=0.$$

Значит, $$m_i(0)=0$$, и механизм рациональный. Заметим, что форма платы $$\mathcal M$$ в данном случае полностью задана распределением $$\mathbf Q$$ ; $$\mathcal M$$ определена с точностью до константы, которую мы изначально приняли такой, чтобы выполнялось $$m_i(0)=0$$.

Таким образом, это рациональный и правдивый механизм. Кроме того, он оптимален, так как максимизирует каждое из двух слагаемых формулы дохода продавца по отдельности. Во-первых, он максимизирует $$\sum_{i=1}^Nm_i(0)$$, потому что $$m_i(0)\le 0$$ для всех рациональных механизмов, а в нашем $$m_i(0)=0$$. Во-вторых, он максимизирует $$\sum_{i=1}^N\psi_i(x_i)Q_i(\mathbf x)$$ в каждой точке, потому что дает весь имеющийся вес $$Q_i=1$$ агенту с максимальной виртуальной ценностью $$\psi_i(x_i)$$. Значит, он максимизирует и

$$\mathbf E[R]=\sum\limits_{i=1}^Nm_i(0)+\sum\limits_{i=1}^N\int_{\mathcal X}\psi_i(x_i)Q_i(\mathbf x)f(\mathbf x)d\mathbf x$$

Давайте теперь изучим то, что у нас получилось. Максимальный доход нашего оптимального аукциона получается по простой формуле:

$$\max\mathbf E[R] = \mathbf E\left[\vphantom{1^2}\max\{\psi_1(X_1),\ldots,\psi_N(X_N),0\}\right].$$

Ноль добавляется на случай, если все виртуальные ценности окажутся отрицательными.

Проанализируем теперь, сколько придется заплатить победителю такого аукциона. Рассмотрим новые функции

$$y_i(\mathbf x_{-i}) = \inf\{z_i\mid \psi_i(z_i)>0\ \text{и}\ \forall j\neq i\ \psi_i(z_i)\ge \psi_j(x_j)\}.$$

Это минимальное значение ставки игрока $$i$$, которое позволит ему выиграть аукцион (даст ему положительную виртуальную ценность, которая окажется больше, чем виртуальные ценности всех других участников). Тогда определение правила распределения $$\mathbf Q$$ можно переписать как

$$Q_i(z_i,\mathbf x_{-i})=\begin{cases} 1, z_i>y_i(\mathbf x_{-i}),\\ 0, z_i<y_i(\mathbf x_{-i}).\end{cases}$$

Подсчитаем интеграл:

$$\int_0^{x_i}Q_i(z_i,\mathbf x_{-i})dz_i = \begin{cases} x_i-y_i(\mathbf x_{-i}), x_i>y_i(\mathbf x_{-i}),\\ 0, x_i<y_i(\mathbf x_{-i}).\end{cases}$$

Значит, правило выплаты $$\mathcal M$$ можно с использованием функций $$y_i$$ переписать как

$$M_i(\mathbf x) = \begin{cases} y_i(\mathbf x_{-i}), x_i>y_i(\mathbf x_{-i}),\\ 0, x_i<y_i(\mathbf x_{-i}).\end{cases}$$

Иначе говоря, только победитель что-то платит, и он платит минимальную ставку $$y_i(\mathbf x_{-i})$$, достаточную, чтобы обеспечить ему выигрыш. Но это в точности основной принцип аукциона второй цены! Значит, выше мы доказали, что оптимальный аукцион при продаже одной вещи нейтральным к риску агентам — это аукцион Викри с резервной ценой. Более того, из теоремы 5.1 можно извлечь и оптимальную резервную цену.

Рассмотрим для простоты симметричный случай: пусть все агенты симметричны, то есть плотности распределения ценностей $$f_i$$ равны. Тогда все виртуальные ценности $$\psi_i=\psi$$. Тогда получаем, что

$$y_i(\mathbf x_{-i}) = \max\left\{\max\limits_{j\neq i}x_j, \psi^{-1}(0)\right\}.$$

Таким образом, победитель платит максимум из всех остальных ставок или резервную цену, если все остальные ставки меньше. Проще говоря, мы получили в точности аукцион второй цены с резервной ценой

$$r = \psi^{-1}(0).$$

Пример 5.3. Подсчитаем $$\psi^{-1}(0)$$ для равномерных распределений на $$[0,1]$$. Поскольку

$$\psi(x) = x - \frac1{\lambda(x)},$$

то $$\psi^{-1}(0)$$ является корнем уравнения

$$x=\frac1{\lambda(x)}.$$

Решим это уравнение, используя определение функции риска:

$$x=\frac1{\lambda(x)}=\frac{1-F(x)}{f(x)}.$$

Поскольку ценности распределены на $$[0,1]$$, то $$F(x)=x$$, $$f(x)=1$$. Тогда получаем, что $$\psi^{-1}(0)=\frac{1}{2}$$. Иначе говоря, продавцу будет выгодно установить резервную цену в $$\frac{1}{2}$$. Здесь мы, конечно, предполагали, что упоминавшийся в предыдущем параграфе доход продавца от удержания вещи у себя (величина $$x_0$$ ) равен нулю.

Конец примера 5.3.

Эффективные механизмы: VCG

Итак, мы научились максимизировать доход продавца. Теперь попытаемся решить более альтруистическую задачу: максимизируем общественное благосостояние (social welfare). Это значит, что мы будем пытаться распределить вещь тому, кому она больше всего нравится.

Мы уже знаем, что аукцион второй цены (без резервной цены) эффективен. А вот, например, оптимальный аукцион, который мы только что рассматривали, может оказаться и неэффективным. Во-первых, резервная цена автоматически предполагает, что иногда объект никому не достанется, даже если есть положительные ставки. Во-вторых, максимизируется виртуальная ценность: если распределения несимметричные, то это вовсе не эквивалентно максимизации самих $$x_i$$.

История создания эффективных механизмов восходит к самым истокам теории экономических механизмов. Собственно, мотивацией первой работы Уильяма Викри стал именно поиск эффективного (и правдивого) механизма: его аукцион второй цены, предложенный в [76], стал первым примером нетривиального дизайна экономических механизмов и фактически основал науку, которой мы сейчас занимаемся. Затем Кларк обобщил идею Викри и применил аналогичный механизм в контексте распределения вещей общего пользования (так называемых public goods) [13]. Наконец, в своем современном виде эффективные механизмы, которые мы сейчас будем рассматривать, появляются у Т.Гровса [24].

Для начала немного обобщим постановку задачи. Расширим возможные значения ценностей агентов, то есть обобщим $$\mathcal X$$: теперь значения ценностей агентов будут $$x_i\in[\alpha_i,\omega_i]$$. Это нужно для того, чтобы разрешить отрицательные ценности. Напоминаем, что, по определению 5.1, функция распределения $$\mathbf Q^*$$ называется эффективной }, если она максимизирует общественное благосостояние, то есть

$$\forall \mathbf x\in\mathcal X\quad \mathbf Q^*(\mathbf x)\in argmax_{\mathbf Q} \sum_{j=1}^NQ_jx_j.$$

Проще говоря, мы даем вещь агенту с максимальной ценностью, либо одному из таких агентов, если их несколько. Введем теперь еще одно обозначение — если $$\mathbf Q^*$$ уже эффективна, то мы обозначим через $$W$$ значение этого самого общественного благосостояния. Суммарное благосостояние всех агентов мы обозначим через

$$W(\mathbf x) = \sum_{j=1}^NQ^*_j(\mathbf x)x_j,$$

а суммарное благосостояние всех агентов без $$i$$ -го — через

$$W_{-i}(\mathbf x) = \sum_{j\neq i}Q^*_j(\mathbf x)x_j.$$

Теперь можно переходить к определению.

Определение 5.3. Механизм Викри-Кларка-Гровса, он же механизм VCG (Vickrey-Clarke-Groves) — это эффективный механизм с правилом платежа $$\mathcal M^V:\mathcal X\to\mathbb R^N$$, определенным следующим образом:

$$M^V_i(\mathbf x) = W(\alpha_i,\mathbf x_{-i}) - W_{-i}(\mathbf x).$$

Напомним, что слово эффективный в определении означает, что правило распределения $$\mathbf Q$$ уже задано:

$$\mathbf Q^*(\mathbf x)\in argmax_{\mathbf Q} \sum_{j=1}^NQ_jx_j.$$

Рассмотрим повнимательнее функцию платы $$\mathcal M^V$$. Цена $$M^V_i(\mathbf x)$$, которую придется заплатить агенту $$i$$ — это разница между общественным благосостоянием при наименьшей возможной ставке агента $$i$$ и благосостоянием всех остальных агентов при текущей ставке. То есть агент должен заплатить ровно столько, насколько он суммарно сделал хуже другим от того, что сделал ставку, а не ограничился минимумом (как правило, равносильным неучастию). В контексте аукционов $$\alpha_i=0$$, и получается в точности аукцион второй цены.

Если другие агенты делают ставки $$\mathbf x_{-i}$$, то прибыль агента $$i$$ от ставки $$z_i$$ вычисляется как

$$Q^*(z_i,\mathbf x_{-i})x_i - M^V_i(z_i,\mathbf x_{-i}) = Q^*(z_i,\mathbf x_{-i})x_i - W(\alpha_i,\mathbf x_{-i}) + W_{-i}(\mathbf x) = \\ = Q^*(z_i,\mathbf x_{-i})x_i - W(\alpha_i,\mathbf x_{-i}) + \sum\limits_{j\neq i}Q^*_j(z_i,\mathbf x_{-i})x_j = \\ = \sum\limits_{j=1}^NQ^*_j(z_i,\mathbf x_{-i})x_j-W(\alpha_i,\mathbf x_{-i}).$$

Здесь $$Q^*(z_i,\mathbf x_{-i})x_i$$ — ожидание дохода агента, а $$M^V_i(z_i,\mathbf x_{-i})$$ — ожидание выплаты агента. Вычитаемое от $$z$$ не зависит, а уменьшаемое по определению $$\mathbf Q^*$$ максимизируется, когда $$i$$ говорит правду. Значит, аукцион VCG правдив.

Из лекции 4 мы знаем уже много свойств правдивых механизмов. В частности, ожидаемая доходность

$$U^V_i(x_i)=\mathbf E[W(x_i,\mathbf X_{-i}) - W(\alpha_i,\mathbf X_{-i})]$$

будет возрастающей и выпуклой функцией. Но $$U^V_i(\alpha_i)=0$$ ; значит, по монотонности, мы получаем, что VCG рационален.

Пусть есть другой механизм, который тоже эффективен, правдив и рационален. Тогда, по принципу эквивалентности доходности, его доходность $$U_i$$ отличается от $$U_i^V$$ на константу. Но если

$$U_i(\alpha_i) < U_i^V(\alpha_i)=0,$$

то механизм не будет рациональным (у агента $$i$$ с ценностью $$\alpha_i$$ — отрицательная ожидаемая доходность). Значит, $$U_i(z) > U_i^V(z)$$, то есть другой механизм больше дает агентам; при одинаковом распределении $$\mathbf Q^*$$ это значит, что агенты платят меньше. Таким образом, мы доказали следующую теорему.

Теорема 5.2. Среди всех механизмов, которые распределяют один объект и являются эффективными, правдивыми и рациональными, механизм VCG максимизирует ожидаемые выплаты каждого агента.

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

Кроме того, нужно понимать, что механизм VCG при всех своих замечательных свойствах может оказаться совершенно нереалистичен. Для вычисления функции распределения $$\mathbf Q$$ в механизме VCG приходится решать сложную задачу оптимизации. Если агентов достаточно много, это не всегда можно сделать быстро: задача распределения в ряде ситуаций оказывается NP-трудной, в том числе "совсем" NP-трудной, то есть такой, к оптимальному решению которой даже приблизиться NP-трудно. Задача сделать вычислительно эффективный механизм, то есть механизм, который бы работал полиномиально долго и при этом обладал хорошими свойствами, — это совсем другая задача, в рамках классической теории экономических механизмов удовлетворительно не решенная. Пути ее решения были исследованы только в совсем недавних работах Нисана и Ронена [63]; мы в этом курсе рассматривать их не будем и, возможно, вернемся к ним позже. Совершенно аналогично нелегко сделать и эффективный оптимальный механизм.

Баланс бюджета и механизм AGV

Механизм VCG позволяет построить эффективную функцию распределения, максимизирующую всеобщее благосостояние. Это весьма общая конструкция, которая может быть применена далеко не только для ситуации аукциона. Но это еще не все, что можно потребовать от хорошего механизма.

Зачастую в задачах дизайна механизмов требуется, чтобы у механизма в результате его деятельности сходился баланс (budget balance property). Это значит, что система "замкнута": деньги перераспределяются между агентами, но никаких вливаний снаружи не требуется (и наружу никаких лишних денег не отдается).

Определение 5.4. Механизм $$(\mathbf Q,\mathcal M)$$ удовлетворяет условию сбалансированности бюджета, если

$$\sum_{i=1}^NM_i(\mathbf x) = 0,$$

то есть сумма выплат всех агентов равна нулю.

Условие сбалансированности бюджета требуется нередко, но механизм VCG в том виде, в котором мы его рассмотрели в предыдущем параграфе, свойства этого не обеспечивает (см., например, раздел 7.2). А нам хотелось бы построить механизм, который и эффективен был бы, и бюджет соблюдал бы нулевой. Эту задачу исполняет механизм AGV, или механизм Эрроу-д'Аспремона-Жерар-Варе (Arrow-d'Aspremont-Gerard-Varet). Как и в случае VCG, это не совместная работа, а две разных, независимых и вышедших в одно время: Эрроу [5] и остальных авторов [16]. Обращаем внимание читателя на то, что "других авторов" не три, а два: Жерар-Варе — это один человек.

Этот механизм тоже эффективен (то есть использует правило распределения $$\mathbf Q^*$$ ). Его выплаты $$\mathcal M^{\mathcal A}$$ определяются как

$$M_i^{\mathcal A}(\mathbf x)=\frac1{N-1}\sum_{j\neq i}\mathbf E_{\mathbf X_{-j}}[W_{-j}(x_j,\mathbf X_{-j})]-\mathbf E_{\mathbf X_{-i}}[W_{-i}(x_i,\mathbf X_{-i})].$$

"Физический смысл" похож на смысл аукциона VCG: можно сказать, что каждый агент компенсирует каждому другому агенту свое присутствие на аукционе. При таких выплатах очевидно, что баланс механизма AGV сходится, поскольку каждое ожидание входит в сумму один раз с плюсом и один раз с минусом:

$$\sum_{i=1}^NM_i^{\mathcal A}(\mathbf x) = 0.$$

Для полного счастья осталось лишь показать, что механизм AGV правдив и рационален. И здесь нас ждет некоторое разочарование. Во-первых, в доминантных стратегиях доказать правдивость не получится. Но равновесие по Нэшу (и даже по Байесу-Нэшу) получится: если другие агенты говорят правду, то есть сообщают $$\mathbf x_{-i}$$, а агент $$i$$ делает ставку $$z_i$$, его ожидаемый итоговый доход равен

$$\mathbf E_{\mathbf X_{-i}}\left[Q^*_i(z_i,\mathbf X_{-i}) - M_i^{\mathcal A}(\mathbf x)\right] = \mathbf E_{\mathbf X_{-i}}[Q^*_i(z_i,\mathbf X_{-i}) + W_{-i}(z_i,\mathbf X_{-i})] - \\ -\mathbf E_{\mathbf X_{-i}}\left[\frac1{N-1}\sum\limits_{j\neq i}\mathbf E_{\mathbf X_{-j}}[W_{-j}(X_j,\mathbf X_{-j})]\right].$$

Первое слагаемое $$Q^*_i(z_i,\mathbf X_{-i})$$ — доход агента, из которого вычитается выплата агента. Вычитаемое ожидание не зависит от $$z_i$$, а первое ожидание максимизируется при $$z_i=x_i$$, поэтому по Нэшу и по Байесу-Нэшу механизм действительно правдив.

А вот рациональности у механизма AGV, вообще говоря, не будет.

Пример 5.4. Рассмотрим ситуацию торговли с двумя участниками, которую мы будем подробно обсуждать в разделе 7.2. В ней участвуют два игрока, один из которых хочет продать вещь, другой — купить. Они должны договориться о цене, подавая механизму свои себестоимость и максимальную приемлемую цену $$v$$ соответственно. Механизм должен решить, происходит ли обмен, и если да, то сколько платит покупатель и сколько получает продавец.

Предположим, что мы пытаемся реализовать механизм AGV в этой ситуации. Эффективность означает, что товар перераспределяется тогда и только тогда, когда $$v > c$$. Выплата покупателя будет равна

$$M_v^{\mathcal A}(c,v) = \mathbf E_{v}[W_{v}(c,v)] - \mathbf E_{c}[W_{c}(c,v)],$$

а продавца —

$$M_c^{\mathcal A}(c,v) = \mathbf E_{c}[W_{c}(c,v)] - \mathbf E_{v}[W_{v}(c,v)],$$

где $$W_{v}(c,v)$$ — благосостояние покупателя, $$W_{c}(c,v)$$ — благосостояние продавца. Предположим, что они равны

$$W_{v}(c,v) = \begin{cases}v, v > c, \\ 0, \text{в противном случае},\end{cases} \\ W_{c}(c,v) = \begin{cases}0, v > c, \\ c, \text{в противном случае},\end{cases} $$

то есть покупатель может увеличить свое благосостояние в случае покупки, а продавец может остаться при своей вещи (это логично: покупатель должен как раз взносом компенсировать продавцу уменьшение его благосостояния на эту вещь). При этом суммарное благосостояние, разумеется, максимизируется в эффективном случае. Предположим, что $$v$$ и $$c$$ распределены равномерно на $$[v_0,v_1]$$ и $$[c_0,c_1]$$ соответственно. Будем предполагать, что $$v_0\ge c_0$$ и $$c_1 \le v_1$$, потому что вне этих условий все равно никакой торговли точно не случится. Тогда

$$\mathbf E_{c}[W_{c}(c,v)] = \int_{c_0}^{c_1}\frac{W_{c}(c,v)}{c_1-c_0}dc = c\frac{c_1 - \min\{v,c_1\}}{c_1-c_0}, \\ \mathbf E_{v}[W_{v}(c,v)] = \int_{v_0}^{v_1}\frac{W_{v}(c,v)}{v_1-v_0}dv = v\frac{v_1 - \max\{c,v_0\}}{v_1-v_0}.$$

Пока все логично: ожидаемое благосостояние покупателя с ценностью $$v$$ — это $$v$$ умножить на долю случаев, когда продажа происходит; с благосостоянием продавца то же самое. Но давайте теперь посмотрим на выплату покупателя (и, соответственно, доход продавца):

$$M_v^{\mathcal A}(c,v) = -M_c^{\mathcal A}(c,v) = \mathbf E_{v}[W_{v}(c,v)] - \mathbf E_{c}[W_{c}(c,v)] = \\ =v\frac{v_1 - \max\{c,v_0\}}{v_1-v_0} - c\frac{c_1 - \min\{v,c_1\}}{c_1-c_0}.$$

Конечно, когда $$c_1 \le v_0$$, сделка происходит всегда, выплата покупателя всегда равна $$v$$, его доход, соответственно, равен $$0$$, доход продавца равен $$v-c$$, и все довольны (хоть это и не очень честно по отношению к покупателю, но все-таки рационально). А что, если $$v_0 \le v \le c \le c_1$$? В такой ситуации $$\max\{c,v_0\} = c$$, $$\min\{v,c_1\} = v$$, и выплата равна

$$M_v^{\mathcal A}(c,v) = -M_c^{\mathcal A}(c,v) = v\frac{v_1 - c}{v_1-v_0} - c\frac{c_1 - v}{c_1-c_0}.$$

Легко убедиться, что она может оказаться не равной нулю — например, для $$[v_0,v_1]=[1,3]$$, $$[c_0,c_1]=[0,2]$$, $$v=1$$, $$c=2$$ получается $$M_v^{\mathcal A}(c,v) = -\frac12$$ и, соответственно, $$M_c^{\mathcal A}(c,v) = \frac12$$. В такой ситуации никакой торговли не происходит, но продавцу приходится доплатить покупателю просто за участие в аукционе! Разумеется, такой аукцион для продавца нерационален.

Конец примера 5.4.

Интересно, почему в данной ситуации не получается добиться рациональности? Оказывается, что это не механизм плохой; есть более глубокая причина того, почему "совсем замечательный" механизм не построить.

Теорема 5.3. (д'Аспремона-Жерар-Варе) Эффективный, правдивый (в доминантных стратегиях) и рациональный механизм, у которого сходится баланс, существует тогда и только тогда, когда механизм VCG дает положительную ожидаемую прибыль аукционеру.

Доказательство. В одну сторону доказательство тривиально: VCG должен давать прибыль, потому что он, как мы видели раньше, дает аукционеру максимальную ожидаемую прибыль из всех эффективных правдивых рациональных механизмов (а все остальные ему эквивалентны по теореме об эквивалентности доходности). Это тривиальное замечание и есть та проблема, из-за которой не всегда получается построить хороший механизм, ведь VCG, как мы увидим в разделе 7.2, порой требует внешних вливаний.

Докажем, однако, и в другую сторону: предъявим конструкцию эффективного правдивого рационального механизма со сходящимся балансом в том случае, когда VCG дает прибыль.

Возьмем за основу механизм AGV. Принцип эквивалентности доходности нам говорит: есть такие константы $$c_i^{\mathcal A}$$, что ожидаемая доходность

$$U^{\mathcal A}_i(x_i) = \mathbf E[W(x_i,\mathbf X_{-i})]-c^{\mathcal A}_i.$$

Для VCG это тоже верно: существуют такие константы $$c^V_i$$, что

$$U^V_i(x_i) = \mathbf E[W(x_i,\mathbf X_{-i})]-c^V_i.$$

Однако механизм AGV пока что не является рациональным; чтобы добиться рациональности, слегка модифицируем его. Дано, что VCG приносит прибыль:

$$\mathbf E\left[\sum\limits_{i=1}^NM^V_i(\mathbf X)\right]\ge 0.$$

Поскольку AGV по определению имеет сходящийся баланс, то его ожидание прибыли равно нулю:

$$\mathbf E\left[\sum\limits_{i=1}^NM^V_i(\mathbf X)\right]\ge \mathbf E\left[\sum\limits_{i=1}^NM^{\mathcal A}_i(\mathbf X)\right]=0.$$

Или, в терминах наших констант,

$$\sum\limits_{i=1}^Nc^V_i\ge\sum_{i=1}^Nc^{\mathcal A}_i.$$

Введем теперь специальные поправки: для $$i=2..N$$

$$d_i = c^{\mathcal A}_i - c^V_i,\quad d_1=-\sum\limits_{i=2}^Nd_i$$

( $$d_1$$ просто выбирается таким образом, чтобы сумма всех $$d_i$$ оказалась равна нулю).

Тогда искомым механизмом будет механизм AGV с нашими поправками:

$$M_i(\mathbf x) = M^{\mathcal A}_i(\mathbf x) + d_i.$$

Очевидно, баланс все так же сходится (поскольку это $$\mathcal M^{\mathcal A}$$, подправленный на константы, которые в сумме дают $$0$$ ). Механизм правдивый, потому что выплаты агента отличаются от выплат правдивого $$\mathcal M^{\mathcal A}$$ на константу.

Осталось только проверить, что он рациональный, то есть ожидание дохода каждого агента больше нуля. Для $$i\neq 1$$

$$U_i(x_i) = U_i^{\mathcal A}(x_i)+d_i = U_i^{\mathcal A}(x_i)+c_i^{\mathcal A}-c_i^V=U_i^V(x)\ge 0.$$

Для первого агента все то же самое, нужно только заметить, что

$$d_1 = -\sum_{i=2}^Nd_i = \sum_{i=2}^N(c^V_i-c^{\mathcal A}_i)\ge c^{\mathcal A}_1-c^V_1,$$

так как общая сумма $$\sum_{i=1}^Nc^V_i\ge\sum_{i=1}^Nc^{\mathcal A}_i$$.

Таким образом, мы сделали такой эффективный правдивый рациональный механизм, у которого сходится баланс. Иначе говоря, выплаты остаются между агентами, участвующими в аукционе, но ни один из них не ожидает остаться в убытке.