Принцип выявления предпочтений

Введение

Наши аукционы будут проходить с закрытыми ставками (еще говорят — в режиме закрытых торгов; так обычно проводят, например, тендеры). Есть $$N$$ независимых агентов, которые хотят купить один объект. Считается, что участники подают заявки "в конвертах" организаторам, которые на основании всех ставок решают, какому агенту отдать этот объект и за какую цену.

Будем считать, что возможная внутренняя стоимость агента $$i$$ определяется случайной величиной $$X_i$$. Иначе говоря, агент $$i$$ при многократном повторении аукциона будет иметь внутренние стоимости, подчиняющиеся распределению случайной величины $$X_i$$. Предположим также, что $$X_i$$ одинаково распределены на отрезке $$[0, \omega]$$, и каждая из них имеет неубывающую функцию распределения $$F:[0,\omega]\to[0,1]$$. В принципе возможно, что $$\omega=\infty$$, но в любом случае $$\mathbf E[X_i]<\infty$$.

Далее предположим, что агент $$i$$ знает все $$X_j$$, $$j\neq i$$ и знает свою ставку $$x_i$$, которую он поставит. При этом конкретные значения $$x_j$$, $$j\neq i$$, которые поставили другие агенты, агент $$i$$ не знает.

Наконец, сделаем еще одно предположение о природе агентов. Будем считать, что все $$X_i$$ имеют одну и ту же функцию распределения $$F$$, и все агенты осведомлены о том, что у всех одинаковая функция распределения $$F$$. Такая модель называется симметричной }.

Модели аукционов: закрытые и открытые ставки

Когда мы говорим "аукцион", первой, конечно, на ум приходит ситуация, в которой участники один за другим поднимают цену, и когда в результате остается только один, который и покупает разыгрываемый лот.

- Сто сорок пять в пятом ряду справа, раз.
Зал потух. Слишком дорого.
- Сто сорок пять, два.
Остап равнодушно рассматривал лепной карниз. Ипполит Матвеевич сидел, 
опустив голову, и вздрагивал.
- Сто сорок пять, три...
Но, прежде чем черный лакированный молоточек ударился о фанерную кафедру, 
Остап повернулся, выбросил вверх руку и негромко сказал:
- Двести!

Примерно так, правда? Такой аукцион называется английским. На самом же деле, конечно, различных моделей аукционов гораздо больше. Например, другая классическая модель — так называемый голландский аукцион. Он получил такое название потому, что именно по этой модели проводятся классические голландские аукционы, на которых продают цветыhttp://www.floraholland.com/ .. В голландском аукционе аукционер начинает торги с заведомо слишком высокой цены, после чего понижает ее до тех пор, пока не поднимется первая рука (то есть пока первый агент не захочет купить лот по объявленной цене). После этого лот уходит тому, кто захотел его приобрести, и по той цене, которая была объявлена.

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

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

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

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

Для английского аукциона тоже можно найти эквивалентный ему аукцион с закрытыми ставками. Правда, для этого придется предположить, что внутренние ценности агентов независимы, ведь в английском аукционе агент слышит ставки других агентов и теоретически мог бы модифицировать свою собственную ставку в зависимости от услышанного. О том, что происходит в таких случаях, мы начнем говорить в лекции 9; в действительности окажется, что в такой ситуации английский аукцион нужно анализировать по-другому. Но если сделать предположение о независимости внутренних ценностей, то английский аукцион становится эквивалентен аукциону второй цены}с закрытыми ставками. В аукционе второй цены аукционер собирает ставки в конвертах; победителем становится, как и в аукционе первой цены, объявивший максимальную цену, но платит он не то, что объявил, а цену второго сверху участника. Этот аукцион еще называется аукционом Викри; в следующем разделе мы узнаем о нем много интересного. Легко видеть, что эти два аукциона эквивалентны: в английском аукционе победитель определяется в тот момент, когда сдается второй сверху игрок. Соответственно, и платит он не свою внутреннюю ценность, а внутреннюю ценность второго сверху игрока.

О разных моделях аукционов можно подробнее прочитать в [48]; мы же будем в дальнейшем в основном рассматривать аукционы с закрытыми ставками, особенно упирая на аукционы первой и второй цены. Теперь вы знаете, почему они столь важны.

Стратегии и доход аукционов первой и второй цены

Определив в разделе 3.1 аукцион с закрытыми ставками с точки зрения агентов, обратимся теперь к самой реализации этой модели аукциона организаторами — кому отдать единственный продаваемый объект и по какой цене. Сначала рассмотрим механизм аукциона Викри (подробно описанный в предыдущей лекции). Напомним, что если агент $$i$$ подает ставку $$b_i$$, то его прибыль, исходя из механизма аукциона Викри, определяется следующим образом:

$$\Pi_i=\begin{cases} x_i-\max_{j\neq i}b_j, \text{если }b_i>\max_{j\neq i}b_j,\\ 0, \text{если }b_i<\max_{j\neq i}b_j.\end{cases}$$

Если несколько агентов подадут одинаковые ставки, то в качестве победителя аукциона мы просто равновероятно выберем одного из них.

В предыдущей лекции мы обсудили и доказали следующую теорему.

Теорема 3.1. В аукционе второй цены с закрытыми ставками (аукционе Викри) стратегия делать правдивую ставку

$$b_i(x)=x,$$

где $$x$$ — реальная внутренняя стоимость объекта для агента $$i$$, является слабо доминирующей.

Напомним определение слабо доминирующей стратегии.

Определение 3.1. Стратегия агента $$b_i:[0, \omega]\to[0, \omega]$$ называется слабо доминирующей }, если она слабо максимизирует прибыль агента $$i$$ при всех возможных стратегиях других агентов:

$$\forall b^\prime_i\in\Sigma_i,\ \forall\mathbf b_{-i} \in \mathbf \Sigma_{-i}\quad \Pi_i(b_i, \mathbf b_{-i}) \ge \Pi_i({b^\prime}_i, \mathbf b_{-i}),$$

где $$\mathbf \Sigma_{-i}$$ — множество возможных наборов стратегий остальных агентов, $$\mathbf b_{-i}$$ — множество векторов их ставок.

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

Давайте теперь найдем, сколько агент ожидает заплатить в результате аукциона Викри, учитывая его симметричность. Рассмотрим агента 1 и первую порядковую статистику на распределениях всех остальных агентов $$\{X_2, X_3, ..., X_N\}$$:

$$Y_1 = \max\{X_2, X_3, ..., X_N\}.$$

Найдем функцию распределения $$Y_1$$:

$$G(y) = p({\max\{X_2, X_3, ..., X_N\} < y}) = \prod\limits_{i = 2}^{N} p(X_i < y) = {F(y)}^{N-1}.$$

Итого, если $$x$$ — ставка агента 1, то ожидание выигрыша с учетом того, что все агенты ставят свои реальные ценности, будет вычисляться по следующей формуле:

$$m(x) = p[\text{Выигрыш агента }1]\times\mathbf E[2\text{-я ставка}\mid x\text{ — макс. ставка}] = \\ =p[\text{Выигрыш агента }1]\times\mathbf E[2\text{-я ценность}\mid x\text{ — макс. ценность}] = \\ =G(x)\mathbf E[Y_1\mid Y_1<x]=F(x)^{N-1}\mathbf E[Y_1\mid Y_1<x].$$

Запомним эту формулу — она нам еще пригодится. А сами обратимся к анализу другой модели аукциона. Теперь мы будем рассматривать аукцион первой цены с закрытыми ставками. Функция прибыли агента $$i$$ выглядит следующим образом:

$$\Pi_i=\begin{cases} x_i-b_i, \text{если }b_i>\max_{j\neq i}b_j,\\ 0, \text{если }b_i<\max_{j\neq i}b_j.\end{cases}$$

Если несколько агентов подадут одинаковые ставки, то в качестве победителя аукциона выберем одного из них равновероятно.

Самое же первое наблюдение, которое можно произвести над формулой прибыли агента $$i$$, убеждает нас в том, что аукцион первой цены не будет правдивым. Ведь если агент сообщит в качестве ставки свою истинную внутреннюю стоимость ( $$b_i=x_i$$ ), то при любом исходе агент всегда получит нулевую прибыль! Говорить правду в аукционе первой цены — все равно что в нем вообще не участвовать. Поэтому неизбежно, что агенты будут лгать, подавать ставки, меньшие их истинных стоимостей. Наша ближайшая задача — найти их равновесные стратегии.

Рассмотрим стратегии агентов, обозначив через $$\beta (x)$$ ставку агента с внутренней ценностью $$x$$. Мы будем понемногу устанавливать свойства функции $$\beta$$, из которых она потом определится единственным образом. Вот простейшие свойства:

$$\beta(0) = 0$$ и $$\forall x \in [0,\omega] : \beta(x)\le\beta(\omega)$$ ;

$$\beta(x)$$ — неубывающая функция.

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

$$\max\limits_{i\neq 1}\beta(X_i) < b.$$

По монотонности $$\beta$$ получаем, что

$$\max\limits_{i\neq 1}\beta(X_i)=\beta\left(\max\limits_{i\neq 1}X_i\right)=\beta(Y_1).$$

Следовательно, первый игрок выиграет, когда $$Y_1<\beta^{-1}(b)$$. Тогда вероятность того, что агент выиграет, поставив $$b$$, будет равна

$$p[\text{Выигрыш агента 1}] = G\left(\beta^{-1}(b)\right),$$

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

$$\Pi(b,x)=G\left(\beta^{-1}(b)\right)(x-b).$$

Получив такую формулу для ожидаемого выигрыша, осталось максимизировать ее по $$b$$ стандартным способом: продифференцировать по $$b$$ и приравнять к нулю. Запишем получившееся уравнение:

$$\frac{G^\prime\left(\beta^{-1}(b)\right)}{\beta^\prime\left(\beta^{-1}(b)\right)}(x-b)-G\left(\beta^{-1}(b)\right)=0.$$

Но мы же на самом деле ищем равновесную оптимальную стратегию. А в ней все агенты (так как они симметричны) будут делать ставки в соответствии с единой оптимальной стратегией: $$b=\beta(x)$$.

В итоге у нас получается дифференциальное уравнение:

$$G(x)\beta^\prime(x)+G^\prime(x)\beta(x)=xg(x).$$

Преобразуем его:

$$G(x)\beta^\prime(x)+G^\prime(x)\beta(x)=xG^\prime(x),$$

а затем решим относительно $$\beta$$ с учетом начального условия $$\beta(0)=0$$:

$$\beta(x)=\frac1{G(x)}\int_0^xyG^\prime(y)dy.$$

А теперь вспомним определение условного математического ожидания и получим итоговые формулы для стратегии игрока $$\beta$$ и его ожидаемой выплаты $$m$$:

$$\beta(x) =\mathbf E[Y_1|Y_1<x]; \\ m(x) =G(x)\mathbf E[Y_1|Y_1<x].$$

Пока что мы из некоего дифференциального уравнения нашли вид функции $$\beta$$. Но это пока только достаточное условие: мы знаем, что если оптимальная стратегия существует, то она имеет вид $$\beta$$. А чтобы доказать, что она вообще существует, мы возьмем уже полученную формулу для $$\beta$$ и покажем, что это действительно равновесная стратегия, то есть проверим и необходимое условие тоже.

Теорема 3.2. Стратегия

$$\beta(x)=\mathbf E[Y_1|Y_1<x]$$

является равновесной в аукционе первой цены.

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

Итак, пусть все участники, кроме первого агента, действуют по стратегии

$$\beta(x)=\frac1{G(x)}\int_0^xyG^\prime(y)dy=\mathbf E[Y_1|Y_1<x].$$

Обозначим ставку первого игрока через $$b$$. Тогда, если $$b>\beta(\omega)$$, первый агент получит отрицательную прибыль, какой бы ни была его внутренняя ценность. Следовательно, в любом случае $$b\le\beta(\omega)$$. Обозначим через $$z=\beta^{-1}(b)$$ значение, для которого $$b$$ — равновесная ставка. Используя формулу

$$\Pi(b,x)=G(\beta^{-1}(b))(x-b),$$

которую мы получили выше, найдем ожидаемый выигрыш первого игрока:

$$\Pi(b,x)=G(z)(x-\beta(z)) = \\ = G(z)x - G(z)\mathbf E[Y_1|Y_1<z] = G(z)x - \int_0^zyg(y)dy = \\ = G(z)x - G(z)z + \int_0^zG(y)dy = \\ = G(z)(x-z)+\int_0^zG(y)dy.$$

Итого получается:

$$\Pi(b,x) = G(z)(x-z)+\int_0^zG(y)dy.$$

Но это значит, что

$$\Pi(\beta(x),x)- \Pi(\beta(z),x) = G(x)(x-x)+\int_0^xG(y)dy - \\ G(z)(x-z)-\int_0^zG(y)dy = G(z)(z-x) - \int_x^zG(y)dy \ge 0.$$

Последнее неравенство выполнено, так как $$G$$ — неубывающая функция. В итоге мы получили, что в условиях нашего аукциона агенту, соперники которого действуют по стратегии $$\beta$$, всегда выгоднее ставить $$\beta(x)$$ ; а это и означает, что $$\beta$$ — оптимальная равновесная стратегия.

Можно переписать $$\beta$$ в виде, в котором будет очевидно, что участникам надо ставить меньше их внутренней ценности.

Следствие 3.2.1. В аукционе первой цены

$$\beta(x)=x-\int_0^x\frac{G(y)}{G(x)}dy.$$

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

$$\beta(x)=\frac1{G(x)}\int_0^xyG^\prime(y)dy = \\ =\frac1{G(x)}\left({xG(x) - \int_0^xG(y)dy}\right)=x-\int_0^x\frac{G(y)}{G(x)}dy $$

(одна часть — $$y$$, другая часть — $$G(y)$$ ).

Замечание. Кстати говоря, учитывая, что

$$\beta(x)=x-\int_0^x\frac{G(y)}{G(x)}dy \quad \text{и} \quad \frac{G(y)}{G(x)}=\left(\frac{F(y)}{F(x)}\right)^{N-1},$$

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

Пример 3.1. Предположим, что ценность каждого из агентов распределена равномерно на $$[0,1]$$, то есть

$$F(x)=x.$$

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

$$G(x)=x^{N-1}.$$

Как в этом случае будет выглядеть оптимальная стратегия?

Проинтегрируем выражение, полученное в предыдущем следствии:

$$\beta(x)=x-\int_0^x\frac{G(y)}{G(x)}dy=x-\int_0^x\frac{y^{N-1}}{x^{N-1}}= x-\frac{x^N}{Nx^{N-1}}=\frac{N-1}{N}x.$$

Из формулы $$\beta(x)=\frac{N-1}{N}x$$ видно, что, действительно, и в этом случае ставка строго меньше внутренней ценности, но с ростом количества участников к этой внутренней ценности стремится.

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

Рассмотрев выше ожидаемые выплаты игроков и их стратегии в обоих аукционах, обратимся теперь к доходу, который может от аукциона ожидать продавец (обозначим его $$\mathbf E[\mathrm{Revenue}]$$ ). В аукционе второй цены продавец получает ожидаемую стоимость второго участника:

$$\mathbf E[\mathrm{Revenue}] = \mathbf E[Y_2].$$

Лемма 3.1. Для $$\mathbf E[Y_2]$$ верна следующая формула:

$$\mathbf E[Y_2]=N\int_0^\omega y(1-F(y))g(y)dy.$$

Доказательство. В формуле просто записано, что вероятность $$y$$ быть второй сверху случайной величиной — это произведение вероятностей двух событий:

одно из $$N$$ чисел больше $$y$$ (вероятность $$1 - F(y)$$ );

$$y$$ является максимумом среди остальных $$N-1$$ чисел (вероятность $$g(y)$$ ).

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

$$\int_0^\omega y(1-F(y))g(y)dy$$

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

Итак, в случае аукциона второй цены

$$\mathbf E[\mathrm{Revenue}] = \mathbf E[Y_2] = N\int_0^\omega y(1-F(y))g(y)dy.$$

Теперь рассмотрим аукцион первой цены; там анализ будет чуть похитрее, но тоже ничего сверхъестественного. Учитывая, что $$m(x)$$ — ожидаемая выплата одного участника, перейдем к сумме "средних" выплат всех участников; напоминаем, что $$f(x)$$ — функция плотности распределения внутренних стоимостей агентов:

$$\mathbf E[\mathrm{Revenue}]=N\int_0^\omega m(x)f(x)dx=...$$

Подставим уже найденное нами в предыдущем пункте $$m(x)$$:

$$...=N\int_0^\omega\left(\int_0^xyG^\prime(y)dy\right)f(x)dx=...$$

Изменим порядок интегрирования на треугольной области интегрирования (в пространстве $$(x,y)$$, см. рис. 3.1) и перейдем от функции распределения $$G(y)$$ к ее плотности $$g(y)$$:

$$...=N\int_0^\omega\left(\int_y^\omega f(x)dx\right)yg(y)dy=...$$

И, наконец, по определению функции плотности вероятности случайной величины,

$$...=N\int_0^\omega y(1-F(y))g(y)dy$$(рис 3.1) Область интегрирования интеграла

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

Пример 3.2. Рассмотрим двух участников с равномерно распределенными ценностями на $$[0,1]$$. Тогда в аукционе первой цены агенты будут ставить $$b(x)=x/2$$ (как мы уже доказывали в примере 3.1), а в аукционе второй цены — $$b(x)=x$$ (как было показано в теореме 3.1). Приведем два варианта скрытых ценностей, когда с точки зрения продавца то один аукцион лучше, то другой.

Если ценность первого 0, а ценность второго 1, то аукцион первой цены даст доход 0,5, а второй цены даст нулевой доход; в этой ситуации для продавца первая цена лучше второй.

Если ценности первого и второго равны 1, то аукцион первой цены даст доход 0,5, а аукцион второй цены даст полную цену 1; в этой ситуации для продавца вторая цена лучше первой.

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

Напоследок еще раз повторим основные выводы из нашего анализа двух моделей аукционов:

в аукционе второй цены все говорят свои настоящие ценности — но получают вещь за меньшую цену — за цену второго сверху участника;

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

Свойства механизмов в контексте аукционов

Прежде всего напомним общее определение механизма.

Определение 3.2. Механизм

$$\mathcal{M}=(\Sigma_1,\ldots,\Sigma_N,g)$$

состоит из набора стратегий $$\Sigma_i$$ для каждого агента и функции исходов

$$g:\Sigma_1\times\ldots\times\Sigma_N\to\mathcal{O},$$

которая определяет исход, предусмотренный механизмом для полученного на вход профиля стратегий $$\mathbf s=(s_1,...,s_N)$$.

Теперь немного конкретизируем это определение, применив его к конкретной ситуации аукционов.

Во-первых, у агентов вместо множеств стратегий $$\Sigma_i$$ будут множества возможных ставок $$\mathcal{B}_i$$. Каждый агент должен сделать ставку $$b_i\in\mathcal{B}_i$$. Итого получится вектор ставок

$$\mathbf b=(b_1,\ldots,b_N)\in\mathcal{B}=\mathcal{B}_1\times\ldots\times\mathcal{B}_N.$$

Во-вторых, в контексте аукционов можно конкретизировать и понятие функции исходов. Она разделится на две функции: правило размещения ( $$\pi$$ ) и правило платежей ( $$\mu$$ ).

Правило размещения (allocation rule) $$\pi:\mathcal{B}\to\Delta$$ будет определять, кому достанется предмет; здесь $$\Delta$$ — множество распределений вероятностей над множеством агентов, потому что правило размещения, вообще говоря, не обязано ограничиваться строго детерминированным размещением.

А правило платежей (payment rule) $$\mu:\mathcal{B}\to\mathbb R^N$$ определяет, сколько каждый агент должен будет заплатить. $$\mu_i(\b)$$ — цена, которую должен заплатить $$i$$ -й агент по итогам аукциона. Как и размещение $$\pi_i(\b)$$, цена зависит исключительно от вектора ставок, поданного на вход механизма. Здесь важно отметить, что платить может оказаться нужно далеко не только победителю. Бывают аукционы, в которых все участники платят ту или иную сумму (либо за вход, либо сумму, связанную с их ставкой). Бывают аукционы, в которых некоторые участники платят, а другие перераспределяют между собой то, что первые заплатили (и для них $$\mu_i$$ будет принимать отрицательные значения); таковы, например, аукционы с условием баланса бюджета, которые мы рассмотрим в лекции 5.

Пример 3.3. Функции размещения и платежей в аукционе первой цены будут выглядеть так:

$$\pi_i(\mathbf b) = \begin{cases} 1, \text{если }b_i>\max_{j\neq i}b_j, \\ 0, \text{в противном случае}.\end{cases}\\ \mu_i(\mathbf b) = \begin{cases} b_i, \text{если }b_i>\max_{j\neq i}b_j, \\ 0, \text{в противном случае}.\end{cases}$$

То есть мы отдаем предмет агенту, который предложил больше всех, и ни с кого не берем денег, кроме этого агента; зато уж с победителя мы берем его ставку полностью. Каемся: в этих формулах мы допустили небольшую неточность. Может оказаться, что ни для какого $$i$$ не верно, что $$b_i>\max_{j\neq i}b_j$$. Это значит, что в аукционе равенство ставок между несколькими участниками; раньше мы упоминали, что будем в такой ситуации равновероятно отдавать вещь любому из победителей (и с него и брать деньги). Поэтому формулы для $$\pi_i$$ и $$\mu_i$$ не вполне точны. Но при равномерных функциях распределений внутренних ценностей и ставок вероятность совпадения равна нулю, поэтому мы ею будем в дальнейшем пренебрегать.

В аукционе второй цены функция размещения точно такая же, как и в аукционе первой цены. Зато функция выплат отличается:

$$\mu_i(\mathbf b) = \begin{cases} \max_{j\neq i}b_j, \text{если }b_i>\max_{j\neq i}b_j, \\ 0, \text{в противном случае}.\end{cases}$$

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

Стратегии в контексте аукционов тоже немного конкретизируются; теперь стратегии — это функции

$$\beta_i:[0,\omega_i]\to\mathcal{B}_i,$$

где $$\omega_i$$ — максимальная возможная для $$i$$ -го агента стоимость (возможно, $$\omega_i=\infty$$ ).

Равновесие вектора стратегий $$\mathbf\beta=(\beta_1,\ldots,\beta_N)$$ достигается, если для каждого $$i$$ и каждого $$x_i$$ отклонение от стратегии $$\beta_i$$ уменьшает ожидаемый выигрыш $$i$$ -го агента:

$$\mathbf E_{X_j,j\neq i}[m(\beta^\prime_i(x_i))]\le\mathbf E_{X_j,j\neq i}[m(\beta_i(x_i))],$$

где вероятность берется по распределениям $$X_j$$ других агентов, придерживающихся стратегии $$\beta_j$$.

Теперь снова обратимся к общему определению механизма и рассмотрим один из типов механизмов — прямые механизмы (direct mechanisms, direct revelation mechanisms). В этом случае у каждого агента просто спрашивают его тип, то есть $$\Sigma_i=\theta_i$$. В случае аукционов, соответственно, у агента спрашивают его истинную внутреннюю стоимость $$x_i$$. Но, как мы уже выясняли, агенты могут нам лгать, и поэтому мы хотим придумать такие механизмы, чтобы лгать было невыгодно.

Вспомним определение того, что механизм реализует социальную функцию.

Определение 3.3. Механизм $$\mathcal{M}=(\Sigma_1,\ldots,\Sigma_N,g)$$ реализует функцию социального выбора $$f:\Theta_1\times\ldots\times\Theta_N\to\mathcal O$$, если для всех $$\mathbf\theta=(\theta_1,\ldots,\theta_N)\in\Theta_1\times\ldots\times\Theta_N$$

$$g(s_1^*(\theta_1),\ldots,s_N^*(\theta_N))=f(\mathbf\theta),$$

где профиль стратегий $$(s^*_1,...,s^*_N)$$ находится в равновесии по отношению к игре, индуцированной $$\mathcal{M}$$.

А теперь добавим в это определение правдивость механизма.

Определение 3.4. Прямой механизм $$\mathcal{M}=(\Theta_1,\ldots,\Theta_N,g)$$ реализует функцию социального выбора $$f:\Theta_1\times\ldots\times\Theta_N\to\mathcal O$$, если для всех $$\mathbf\theta=(\theta_1,\ldots,\theta_N)\in\Theta_1\times\ldots\times\Theta_N$$

$$g(\theta_1,\ldots,\theta_N)=f(\mathbf\theta),$$

где профиль стратегий $$(\theta_1,...,\theta_N)$$ находится в равновесии по отношению к игре, индуцированной $$\mathcal M$$.

Учитывая, что в этом определении получилось, что $$g=f$$, можно определить правдиво реализуюмую функцию социального выбора.

Определение 3.5. Функция социального выбора $$f:\Theta_1\times\ldots\times\Theta_N\to\mathcal O$$ правдиво реализуема (truthfully implementable, incentive compatible), если профиль стратегий $$(s^*_1,\ldots,s^*_N)$$, где $$s^*_i(\theta_i)=\theta_i$$, находится в равновесии в игре, индуцированной прямым механизмом $$\mathcal M=(\theta_1,\ldots,\theta_N,f)$$ .

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

Теперь, введя определение, можно задаться вопросом — когда можно получить правдивый механизм для заданной функции социального выбора? Ответ на этот вопрос уже есть: Роджер Майерсон доказал принцип выявления доходности, который гарантирует, что если какую-то социальную функцию можно реализовать, ее можно и реализовать правдиво. Перед доказательством ослабленного варианта этого факта нам нужно будет вспомнить несколько определений.

Определение 3.6. Стратегия $$s_i$$ называется доминантной, если она (слабо) максимизирует ожидаемую прибыль агента для всех возможных стратегий других агентов:

$$\forall s^\prime_i\neq s_i, \mathbf s_{-i}\in \mathbf \Sigma_{-i}\quad u_i(s_i,\mathbf s_{-i},\theta_i)\ge u_i(s^\prime_i,\mathbf s_{-i}, \theta_i).$$

Мы уже говорили, что если стратегии у агентов доминантные, то можно быть абсолютно уверенным, что агент изберет доминантную стратегию, ведь она не зависит от его прогнозов на действия других агентов. По этой же причине можно отказаться от предположений на распределение типов у агентов $$F(\mathbf\theta)$$ ; да и вообще $$F(\mathbf\theta)$$ не рассматривать.

Определение 3.7. Механизм $$\mathcal M=(\Sigma_1,\ldots,\Sigma_N,g)$$ реализует функцию социального выбора $$f:\Theta_1\times\ldots\times\Theta_N\to\mathcal O$$ в доминантных стратегиях, если для всех векторов типов агентов $$\mathbf\theta=(\theta_1,\ldots,\theta_N)\in\Theta_1\times\ldots\times\Theta_N$$ выполнено равенство

$$g(s_1^*(\theta_1),\ldots,s_N^*(\theta_N))=f(\mathbf\theta),$$

и каждая из стратегий $$s^*_i$$ является доминантной для агента $$i$$.

Принцип выявления предпочтений

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

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

Исторически принцип выявления (по-английски звучит весьма пышно — revelation principle, но как "принцип откровения" мы решили все-таки не переводить) сначала появился в ограниченной постановке, для доминантных стратегий [22], но вскоре был обобщен на равновесия по Байесу-Нэшу [15,25,54]. Наиболее общая его формулировка, для байесовских игр, была доказана Майерсоном [56,57], и он же продолжил тему принципа выявления еще дальше, на игры, проходящие в несколько раундов (multistage games), когда действия агентов в следующем раунде могут зависеть от исхода предыдущих [58].

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

Определение 3.8. Функция социального выбора $$f:\Theta_1\times\ldots\times\Theta_N\to\mathcal O$$ правдиво реализуема в доминантных стратегияхТерминов для этого понятия много, в зависимости от контекста по-английски есть несколько разных обозначений: truthfully implementable in dominant strategies, dominant strategy incentive compatible, strategy-proof, straightforward., если профиль стратегий

$$(s^*_1,\ldots,s^*_N),$$

где $$s^*_i(\theta_i)=\theta_i$$, находится в равновесии доминантных стратегий в игре, индуцированной прямым механизмом $$\mathcal M=(\theta_1,\ldots,\theta_N,f)$$, то есть

$$\forall\theta_i,\theta^\prime_i\in\mathbf\theta_i,\ \mathbf\theta_{-i}\in\mathbf\Theta_{-i}\qquad u_i(f(\theta_i,\mathbf\theta_{-i}),\theta_i)\ge u_i(f(\theta^\prime_i,\mathbf\theta_{-i}),\theta_i).$$

Теперь можно и теорему сформулировать.

Теорема 3.3. (принцип выявления предпочтений в доминантных стратегиях). Пусть для данной социальной функции $$f$$ существует механизм $$\mathcal M=(\Sigma_1,\ldots,\Sigma_N,g)$$, который ее реализует в доминантных стратегиях. Тогда $$f$$ правдиво реализуема в доминантных стратегиях.

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

Предположим, что у нас есть неправдивый механизм $$\mathcal M_1$$, в котором агенты находятся в равновесии, но при этом лгут — показывают не свои типы, а другие $$s^*_i(\theta_i)$$. Рассмотрим тогда новый механизм $$\mathcal M_2$$ с немного измененным протоколом — после получения значений от агентов механизм будет их преобразовывать с помощью $$s^*_i(\theta_i)$$, а потом уже подставлять эти значения в функцию получения исхода. Иначе говоря, мы как бы говорим агенту: "Давай мы будем врать за тебя; ты говори правду, а мы уже подставим что надо". Мы это изобразили на рис. 3.2; слева изображена исходная схема, в которой агент пользуется стратегией $$s$$ и выдает аукционеру не свой тип $$\theta_i$$, а прошедший через стратегию $$s_i(\theta_i)$$. А справа на том же рисунке стратегию уже "вытащили" из агента и внесли в состав механизма (механизмом справа можно считать все, что внутри штриховой линии). Естественно, в результате агенту будет выгодно говорить такому механизму правду.

(рис 3.2) Принцип выявления предпочтений

Давайте теперь формально проведем доказательство по этой схеме. $$\mathcal M=(\Sigma_1,\ldots,\Sigma_N,g)$$ реализует $$f$$, значит, есть профиль стратегий

$$\mathbf s^*=(s^*_1,\ldots,s^*_n),$$

для которого

$$\begin{align*} \forall \theta g(s^*_i(\theta))=f(\theta)\text{ и } \\ \forall i,\theta_i,s^\prime_i,\mathbf s_{-i} u_i(g(s_i^*(\theta_i),\mathbf s_{-i}),\theta_i)\ge u_i(g(s^\prime_i,\mathbf s_{-i}),\theta_i). \end{align*}$$

В частности (подставим конкретное $$s^\prime$$ и $$\mathbf s_{-i}$$ ),

$$\forall i,\theta_i\quad u_i(g(s_i^*(\theta_i),\mathbf s_{-i}),\theta_i)\ge u_i(g(s^*_i(\theta_i),\mathbf s_{-i}^*(\mathbf\theta_{-i})),\theta_i).$$

Теперь, поскольку $$g(s^*_i(\theta))=f(\theta)$$, получим, что

$$\forall i,\theta_i\quad u_i(f(\theta_i,\mathbf\theta_{-i}),\theta_i)\ge u_i(f(\theta^\prime_i,\mathbf\theta_{-i}),\theta_i).$$

А это и есть в точности определение правдивой реализуемости.

Точно так же можно доказать эту теорему с неправдивыми механизмами, в которых реализуемая функция находится в равновесии по Нэшу или Байесу-Нэшу. Сформулируем общий факт.

Теорема 3.4. (принцип выявления предпочтений) Для любого механизма $$(\Sigma_1,\ldots,\Sigma_N,g)$$ и любого равновесия этого механизма $$\mathbf\beta$$ существует прямой механизм $$\mathcal M=(\mathbf Q,\mathbf M)$$, для которого:

стратегии говорить правду находятся в равновесии того же типа, что и $$\beta$$ ;

результаты работы этого механизма в этом равновесии в точности совпадают с результатами $$\mathcal M$$.

Доказательство. Как и в теореме 3.3, нужно просто лгать за агента. Определим компоненты требуемого механизма $$\mathcal M$$ как

$$\mathbf Q(\mathbf\theta) = \pi(\mathbf\beta(\mathbf x)),\quad \mathbf M(\mathbf x) = \mu(\mathbf\beta(\mathbf x)),$$

где $$\pi$$ — индуцированная $$g$$ функция распределения исходного механизма, а $$\mu$$ — функция выплат исходного механизма. Осталось только проверить, что у этого механизма действительно будет заявленное равновесие; это мы оставим читателю, потому что в теореме 3.3 уже всю структуру доказательства продемонстрировали.

Доказав важную и интересную теорему 3.4, займемся небольшой ее переформулировкой, которая пригодится нам позже. Вспомним, что правдивая реализуемость — это когда

$$\forall\theta_i,\theta^\prime_i\in\mathbf\theta_i,\ \mathbf\theta_{-i}\in\mathbf\Theta_{-i}\quad u_i(f(\theta_i,\mathbf\theta_{-i}),\theta_i)\ge u_i(f(\theta^\prime_i,\mathbf\theta_{-i}),\theta_i).$$

А теперь рассмотрим агента $$i$$ и любую пару возможных типов $$\theta_i^\prime$$ и $$\theta^{\prime\prime}_i$$. Если правдивость — доминантная стратегия, то $$\forall\mathbf\theta_{-i}\in\mathbf\Theta_{-i}$$ выполнено

$$u_i(f(\theta^\prime_i,\mathbf\theta_{-i}),\theta^\prime_i)\ge u_i(f(\theta^{\prime\prime}_i,\mathbf\theta_{-i}),\theta^\prime_i),$$

потому что при векторе типов $$(\theta^\prime,\mathbf\theta_{-i})$$ агенту $$i$$ должно быть выгодно сказать $$\theta^\prime$$, а не $$\theta^{\prime\prime}$$. С другой стороны, для всякого вектора $$\mathbf\theta_{-i}\in\mathbf\Theta_{-i}$$ выполнено

$$u_i(f(\theta^{\prime\prime}_i,\mathbf\theta_{-i}),\theta^{\prime\prime}_i)\ge u_i(f(\theta^\prime_i,\mathbf\theta_{-i}),\theta^{\prime\prime}_i),$$

потому что при векторе типов $$(\theta^{\prime\prime},\mathbf\theta_{-i})$$ агенту $$i$$ должно быть выгодно сказать $$\theta^{\prime\prime}$$, а не $$\theta^\prime$$.

Проще говоря, предпочтения агента $$i$$ в той их части, где сравниваются $$f(\theta^\prime_i,\mathbf\theta_{-i})$$ и $$f(\theta^{\prime\prime}_i,\mathbf\theta_{-i})$$, должны измениться, когда его тип меняется с $$\theta^\prime$$ на $$\theta^{\prime\prime}$$ или обратно. Это называется свойством слабого обращения преференций (weak preference reversal property).

Кстати, верно и обратное: если свойство слабого обращения преференций выполняется для всех $$\mathbf\theta_{-i}\in\mathbf\Theta_{-i}$$ и для всех пар $$\theta^\prime,\theta^{\prime\prime}\in\Theta_i$$, то говорить правду — доминантная стратегия для агента $$i$$. Это легко проверить, если зафиксировать $$\theta^\prime$$ в определении свойства слабого обращения преференций. А теперь введем новое определение и переформулируем теорему 3.3.

Определение 3.9. Множество нижнего контура (lower contour set) возможного исхода $$o$$ при агенте $$i$$ типа $$\theta_i$$ — это

$$L_i(o,\theta_i)=\{o^\prime\in\mathcal O:u_i(o,\theta_i)\ge u_i(o^\prime,\theta_i)\}.$$

Проще говоря, множество нижнего контура — это те исходы, которые для агента $$i$$ не лучше фиксированного исхода $$o$$.

Теорема 3.5. (переформулировка принципа выявления доходности) Социальная функция $$f$$ правдиво реализуема в доминантных стратегиях тогда и только тогда, когда для всех $$i$$, всех $$\mathbf\theta_{-i}\in\mathbf\Theta_{-i}$$ и всех пар типов $$\theta^\prime,\theta^{\prime\prime}\in\Theta_i$$ верно

$$f(\theta^{\prime\prime}_i, \mathbf\theta_{-i})\in L_i(f(\theta^\prime_i,\mathbf\theta_{-i}),\theta^\prime_i), \\ f(\theta^\prime_i, \mathbf\theta_{-i})\in L_i(f(\theta^{\prime\prime}_i,\mathbf\theta_{-i}),\theta^{\prime\prime}_i).$$

Доказательство. На самом деле мы просто переформулировали факт о том, что механизм реализуем в доминантных стратегиях. Оставляем доказательство этого читателю.

В заключение лекции скажем пару слов о том, что принцип выявления не обеспечивает. Главное упущение, которое может в некоторых случаях осложнять жизнь, заключается в том, что теорема 3.4 конструирует механизм, который имеет то же равновесие, что и исходный механизм, для правдивых стратегий. Но никто не гарантирует, что этот механизм не будет иметь других, неправдивых равновесий. Если они появляются, то вполне возможно, что агенты окажутся в этих неправдивых равновесиях, и анализ существенно осложнится. Но это все, конечно, относится только к равновесиям по Нэшу или Байесу-Нэшу, ведь равновесий в доминантных стратегиях много не бывает (точнее говоря, бывает, но все они эквивалентны).