Итак, в аукционе участвуют $$N$$ покупателей (агентов). У каждого из них есть своя внутренняя ценность $$x_i$$, которая определяется случайной величиной $$X_i$$, распределенной по одному и тому же распределению $$F(x)$$ (в этой лекции мы будем находиться в симметричном случае). Первый момент множества из $$N-1$$ агентов, то есть случайную величину, характеризующую максимальную цену из них, обозначим через $$G(x) = F(x)^{N-1}$$. Мы ограничимся стандартными аукционами, в которых вещь достается тому, кто больше всех предложил. При этом, конечно, то, сколько он в действительности заплатит, зависит от формы аукциона.
Для аукциона $$A$$ и агента $$i$$ введем обозначение $$m_i^{\mathcal A}(x_i)$$ — сколько участник $$i$$ ожидает заплатить, участвуя в $$A$$ и используя равновесную стратегию (предполагается, что равновесие в $$A$$ существует). Агенты в симметричном случае одинаковые, поэтому $$m^{\mathcal A}$$ не зависит от $$i$$. Введем вдобавок начальное условие: участник со ставкой $$0$$ платит $$0$$.
Кроме того, мы будем предполагать, что агенты нейтральны к риску (
Теорема будет достаточно удивительной: окажется, что в любом равновесии ожидаемые выплаты агентов (а значит, и доход продавца) одинаковы! То есть можно не ожидать, что при помощи какой-нибудь хитрой схемы аукционер сможет максимизировать свой доход, — при эгоистичных агентах, которые могут успешно рассчитать
Начнем с формулировки теоремы эквивалентности
А ожидание дохода продавца получается как сумма всех ожидаемых выплат покупателей:
$$\mathbf E[\mathrm{Revenue}] = \mathbf E\left[\sum\limits_{i=1}^N m^{\mathcal A}_i(x)\right] = N\mathbf E\left[m^{\mathcal A}(x)\right],$$если мы находимся в симметричном случае, где все агенты равноправны.
Теорема 4.1. Пусть скрытые значения агентов $$x_i$$ распределены независимо и одинаково, и все агенты нейтральны к риску. Тогда любое симметричное равновесие любого стандартного аукциона, такое, что ожидаемая выплата агента со ставкой 0 равна нулю, дает один и тот же ожидаемый доход продавцу.
Доказательство. Будем следовать схеме, которую мы уже излагали в доказательстве теоремы 3.2. Рассмотрим первого агента: остальные следуют равновесной стратегии $$\beta$$, а он ставит некоторое значение $$b$$. Поскольку $$b$$ — тоже возможная ставка, существует некоторое $$z$$, для которого $$b=\beta(z)$$. Здесь $$z$$ можно рассматривать как "ложную"
Агент выигрывает, когда его ставка $$\beta(z)$$ превышает самую большую из других ставок $$\beta(Y_1)$$, то есть (так как $$\beta$$ возрастает) когда $$z>Y_1$$. Тогда игрок ожидает получить следующую прибыль:
$$\Pi^{\mathcal A}(z,x) = G(z)x - m^{\mathcal A}(z),$$где $$G(z)=F(z)^{N-1}$$ (распределение $$Y_1$$ ). Заметим, что $$m^{\mathcal A}(z)$$ зависит от $$\beta$$ и от $$z$$, но не зависит от внутренней ценности $$x$$.
Нам нужно максимизировать прибыль, которую агент ожидает получить. Метод максимизации будет самый что ни на есть классический: взять производную и приравнять ее нулю. Дифференцируя выражение для ожидаемой прибыли по $$z$$, получим следующее равенство:
$$\frac{\partial}{\partial z}\Pi^{\mathcal A}(z,x) = g(z)x - \frac{d}{dz}m^{\mathcal A}(z)=0.$$Но мы находимся в равновесии, а это значит, что агенту нужно поступать в соответствии со стратегией $$\beta$$, применяя ее к своей истинной скрытой ценности. Иначе говоря, максимум достигается, если агент берет $$z=x$$ и сообщает $$\beta(x)$$. Приравняв в предыдущем уравнении $$z$$ и $$x$$, получим следующее:
$$\frac{d}{dy}m^{\mathcal A}(y) = g(y)y.$$Когда мы найдем решение этого
В итоге у нас получилось, что ожидаемая выплата агента не зависит от $${\mathcal A}$$, а только от распределения на $$x$$. Поскольку ожидаемый доход продавца складывается из ожидаемых выплат агентов, получается, что этот доход тоже не зависит от $${\mathcal A}$$.
Давайте рассмотрим на простом примере, как можно подсчитать ожидаемые выплаты агентов и ожидаемую прибыль продавца.
Пример 4.1. Пусть скрытые значения агентов $$x_i$$ распределены равномерно на $$[0,1]$$. Тогда $$F(x)=x$$, $$G(x)=x^{N-1}$$, и из теоремы получается, что
$$m^{\mathcal A}(x) = \frac{N-1}Nx^{N}, \\ \mathbf E[m^{\mathcal A}(x)] = \frac{N-1}{N(N+1)}.$$А ожидаемый доход продавца — это $$N\cdot\mathbf E[m^{\mathcal A}(x)]$$:
$$\mathbf E[R^{\mathcal A}] = \frac{N-1}{N+1}.$$Конец примера 4.1.
Математики говорят: "Theorems come and go, a good
в будущем пригодится нам, разумеется, гораздо чаще, чем сама формулировка теоремы. Заметим, что формула действует только если равновесие в аукционе есть — это нужно проверять отдельно, а уже потом, если получилось, что равновесие есть, использовать эту формулу.
В качестве примеров применения теоремы эквивалентности
Пример 4.2. Рассмотрим аукцион, в котором платят все (по-английски такая ситуация называется all-pay
Проверим, что это действительно равновесие (хотя бы по Нэшу). Пусть все играют по $$\beta^{\mathrm{allpay}}$$, а один агент ставит $$z$$. Тогда он получит
$$G(z)x-\beta(z) = G(z)x - \int_0^zg(y)dy = G(z)(x-z) + \int_0^zG(y)dy.$$Это мы уже видели в лекции 3, когда рассматривали аукцион первой цены. Здесь тоже применим совершенно тот же вывод, и, следовательно, здесь тоже будет достигнуто равновесие.
Конец примера 4.2.
Наверное, читатели удивляются: кто ж согласится участвовать в таком невыгодном аукционе? Однако пример есть, и недалеко от поверхности. Этот аукцион представляет собой модель лоббирования: каждая из группировок, которые хотят добиться нужного результата в парламенте, платят за лоббирование, но результат-то один! Чуть менее чистый пример — рекламные кампании: все тратят деньги, а лидирующее положение на рынке занимает одна компания (это, правда, не всегда так).
Второй пример — аукцион, при анализе которого нам потребуется немного вспомнить математическую статистику.
Пример 4.3. В аукционе третьей цены все похоже на аукционы первой и второй цены — агенты делают ставки, побеждает тот, кто поставил больше всех, но победитель платит только третью сверху ставку, а не вторую и не первую. Здесь будет много интересного из статистики, а в конце получится довольно забавный результат.
Итак, наша магическая формула подсказывает:
$$m^{\mathrm{III}}(x) = \int_0^xyg(y)dy.$$Игрок выигрывает, когда $$Y_1<x$$, и платит третью сверху цену. С учетом того, что равновесная стратегия $$\beta^{\mathrm{III}}$$ является неубывающей функцией, выплата выигравшего игрока будет равна $$\beta^{\mathrm{III}}(Y_2)$$, где $$Y_2$$ — вторая сверху внутренняя ценность из оставшегося $$N-1$$ игрока.
Теперь на время забудем об аукционах и займемся статистикой. Найдем плотность второй порядковой статистики в выборке из $$n$$ элементов.
Событие $$Y_2<y$$ — это объединение двух непересекающихся событий:
Следовательно, для функции распределения этой
и, продифференцировав, получим плотность
$$f^{(n)}_2(y) = F^{(n)^\prime}_2(y)= n(n-1)(1-F(y))F(y)^{n-2}f(y).$$Нас еще интересуют условные вероятности. Сначала — совместная вероятность; поскольку мы предполагаем, что все $$y_k$$ независимы, ее плотность просто равна произведению плотностей:
$$f^{(n)}_Y(y_1,y_2,...,y_n) = n!f(y_1)f(y_2)... f(y_n).$$Теперь построим формулу для $$f^{(n)}_Y(y_1,y_2,\ldots,y_k)$$:
$$f^{(n)}_Y(y_1,y_2,\ldots,y_k) = \frac{\int^{y_k}_{-\infty}\ldots\int^{y_k}_{-\infty} f^{(n)}_Y(y_1,y_2,\ldots,y_n)dy_{k+1}\ldots dy_n} {(n-k)!}.$$Пределы интегрирования в этом выражении описывают тот факт, что переменные с $$y_{k+1}$$ до $$y_n$$ должны оказаться меньше $$y_k$$. А в знаменателе стоит $$(n-k)$$!, потому что при подсчете интегралов мы посчитаем одни и те же события $$(n-k)$$! раз (это получается из-за того, что формула совместной вероятности не различает значения переменных $$y_i$$, по которым идет интегрирование, друг относительно друга).
Теперь подставим формулу для совместной вероятности (с $$n$$ переменными) и проинтегрируем получившееся выражение. Интегрировать в данном случае — дело совсем нехитрое:
$$\frac{\int^{y_k}_{-\infty}\ldots\int^{y_k}_{-\infty} f^{(n)}_Y(y_1,y_2,\ldots,y_n)dy_{k+1}\ldots dy_n} {(n-k)!} \\= \frac{\int^{y_k}_{-\infty}\ldots\int^{y_k}_{-\infty} n!f(y_1)f(y_2)\ldots f(y_n) dy_{k+1}\ldots dy_n} {(n-k)!} \\= \frac{n!F(y_k)^{n-k}f(y_1)f(y_2)\ldots f(y_k)}{(n-k)!}.$$Например, при $$k=2$$ мы получим следующее выражение:
$$f_{1,2}^{(n)}(y_1,y_2) = n(n-1)f(y_1)f(y_2)F(y_2)^{n-2}.$$Теперь можно вывести формулу и для
Найдем
Получив таким образом
Приравняем это выражение к тому, что дает нам полученная при доказательстве теоремы 4.1 формула:
$$\int_0^x\beta^{\mathrm{III}}(y)(N-1)(F(x)-F(y))f_1^{(N-2)}(y)dy = \int_0^xyg(y)dy.$$Продифференцировав по $$x$$, получим:
$$(N-1)f(x)\int_0^x\beta^{\mathrm{III}}(y)f_1^{(N-2)}(y)dy = xg(x),$$то есть
$$(N-1)f(x)\int_0^x\beta^{\mathrm{III}}(y)f_1^{(N-2)}(y)dy = (N-1)xf(x)F(x)^{N-2}.$$Так как $$F^{N-2}_1(x) = F(x)^{N-2}$$, получается, что
$$\int_0^x\beta^{\mathrm{III}}(y)f_1^{(N-2)}(y)dy = xF^{(N-2)}_1(x).$$Теперь продифференцируем это равенство по $$x$$:
$$\beta^{\mathrm{III}}(x)f_1^{(N-2)}(x) = xf^{(N-2)}_1(x) + F^{(N-2)}_1(x),$$а затем выразим отсюда $$\beta^{\mathrm{III}}$$:
$$\beta^{\mathrm{III}}(x) = x + \frac{F^{(N-2)}_1(x)}{f^{(N-2)}_1(x)} = x + \frac{F(x)}{(N-2)f(x)}.$$Итак, мы получили итоговую формулу
К сожалению, это все верно, только когда $$\beta$$ возрастает; а для этого, как видно из этой же формулы, надо, чтобы $$F/f$$ возрастало. Иначе говоря (вспомним, что $$f$$ — это производная $$F$$, то есть $$f/F$$ — это производная $$\ln F$$ ), $$\ln F$$ должен быть вогнутой функцией (в такой ситуации говорят, что $$F$$ log-вогнута, log-concave).
А обещанный интересный эффект вот в чем. У нас получилось, что $$\beta^{\mathrm{III}}(x)$$ всегда строго больше $$x$$, а это значит, что агенту всегда оптимально ставить строго больше, чем свое истинное значение скрытой ценности. Несколько неожиданно, но в общем вполне логично: можно ожидать, что уж третий-то сверху окажется ниже истинной стоимости.
Конец примера 4.3.
Рассмотрим прямой механизм $$\mathcal M = (\mathbf Q,\mathbf M)$$. Напомним, что в нем у участников просто спрашивают их скрытую стоимость: $$\mathbf\Theta = \mathcal X$$, и механизм можно рассматривать как два правила:
Тогда исходы механизма определяются как множество пар значений этих функций для всевозможных векторов ставок:
$$\mathcal O =\{\vphantom{1^2_3}(\mathbf Q(\mathbf x),\mathbf M(\mathbf x))\mid \mathbf x\}.$$Введем два важных обозначения. Обозначим через $$q_i(z_i)$$ ожидаемую доходность агента $$i$$, когда он говорит $$z_i$$, а остальные говорят правду:
$$q_i(z_i) = \int_{\mathbf X_{-i}}Q_i(z_i,\mathbf x_{-i})f_{-i}(\mathbf x_{-i}){\mathbf d}\mathbf x_{-i}.$$А через $$m_i(z_i)$$ — его ожидаемую выплату в этой ситуации:
$$m_i(z_i) = \int_{\mathbf X_{-i}}M_i(z_i,\mathbf x_{-i})f_{-i}(\mathbf x_{-i}){\mathbf d}\mathbf x_{-i}$$(в этих формулах, а также в дальнейшем, $$\bf d$$ означает многомерный
Теперь можно определить правдивость механизма в этих обозначениях.
Лемма 4.1. Прямой механизм $$(\mathbf Q,\mathbf M)$$ является правдивым тогда и только тогда, когда
$$\forall i\ \forall x_i,z_i\quad U_i(x_i) = q_i(x_i)x_i - m_i(x_i) \ge q_i(z_i)x_i - m_i(z_i).$$$$U_i(x_i)$$ называется равновесной функцией дохода.
Доказательство. Собственно, неравенство, которое приведено в формулировке леммы, и исчерпывает доказательство: для правдивости относительно агента $$i$$ нужно, чтобы его ожидаемый доход при правдивой ставке был не ниже, чем при любой другой ставке; это должно происходить в ожидании по типам всех остальных агентов.
Ничего содержательно нового в этой вариации определения нет: по-прежнему механизм правдив, если выгодно говорить правду. Новизна — в удачно подобранных определениях, которые нам позволят доказать несколько важных свойств.
Теорема 4.2. (свойства правдивых механизмов). Каждый правдивый механизм $$\mathcal M = (\mathbf Q,\mathbf M)$$ с равновесными функциями дохода $$U_i$$ обладает следующими свойствами:
Более того, второе из этих свойств на самом деле равносильно правдивости.
Доказательство.
$$U_i(x_i) = \max_{z_i}\{ q_i(z_i)x_i - m_i(z_i)\}$$.
$$q_i(x_i)z_i - m_i(x_i) = U_i(x_i) + q_i(x_i)(z_i-x_i)$$.
Значит,
$$U_i(z_i)\ge U_i(x_i) + q_i(x_i)(z_i-x_i)$$.
Всякая выпуклая функция абсолютно непрерывна и, следовательно, дифференцируема почти всюду в своей области определения. Значит, $$U^\prime_i(x_i) = q_i(x_i)$$ почти всюду. И опять же, раз $$U_i$$ выпуклая, то, значит, ее
$$U_i(x_i) = U_i(0) + \int_0^{x_i}q_i(t_i)dt_i$$.
Вот мы и получили, что форма ожидаемого дохода агента зависит только от правила распределения, но не от правила выплаты. Правило же выплаты определяет только $$U_i(0)$$ (это называется эквивалентностью наград, payoff
$$U_i(z_i)\ge U_i(x_i) + q_i(x_i)(z_i-x_i)$$.
Но мы знаем, что
$$U_i(x_i) = U_i(0) + \int_0^{x_i}q_i(t_i)dt_i$$.
Значит,
$$\int_{x_i}^{z_i}q_i(t_i)dt_i \ge q_i(x_i)(z_i-x_i)$$.
Но если $$q_i$$ не убывает, это неравенство верно. Получилось, что из неубывания $$q_i$$ следует правдивость механизма.
Обобщив все вышесказанное и вспомнив, что
$$U_i(x)=q_i(x_i)x_i-m_i(x_i),\text{ причем }U_i(0)=-m_i(0),$$можно сформулировать еще одну, более общую формулировку теоремы эквивалентности
Теорема 4.3. (теорема эквивалентности
и это означает, что ожидаемая выплата агента с точностью до константы зависит только от правила распределения.
Это обобщает наш предыдущий результат (теорема 4.1) — теперь агенты могут быть несимметричными, и правила распределения тоже могут различаться. Предыдущая теорема получается как частный случай: если агенты симметричны, есть неубывающая равновесная стратегия и объект распределяется покупателю с наивысшей ставкой, то правила распределения у всех таких аукционов совпадают и зависят только от распределения $$F$$.
Теорема об эквивалентности
Однако практика не всегда подтверждает теорию; на практике есть некоторые вещи, в основном психологические, которые иногда приводят к тому, что агенты действуют не оптимально (точнее, не так, как планировалось, что для них будет оптимально).
В 2004 году компания Google решила весьма оригинально выйти на рынок. Их IPO прошло в виде большого голландского аукциона: потенциальные инвесторы выставляли заявки на цены, по которым они готовы купить акции Google, а конечная цена устанавливалась как наивысшая из всех, по которым на все акции еще нашелся бы покупатель. Google таким образом надеялся максимизировать доход от IPO.
Все прошло очень хорошо, но все же не настолько хорошо, насколько ожидалось изначально. Экономисты предполагали, что акции Google будут проданы по ценам между $108 и $135. Однако на самом деле по итогам аукциона они колебались между $85 и $95. Как можно объяснить эту "неудачу" (в кавычках, потому что на самом деле Google и так вышел на рынок очень уверенно, и его акции долгое время были одним из лучших вложений на рынке ценных бумаг)? Мог ли Google, выбрав другую модель IPO (другую модель аукциона или продажу по фиксированной цене), увеличить свои доходы от первого дня торгов?
Во-первых, могли сыграть роль психологические факторы. Специалисты отмечают, что голландский аукцион не понравился многим потенциальным инвесторам, в том числе по сугубо психологическим причинам: старый, редко ныне используемый формат, вряд ли что-то хорошее из него выйдет...
А во-вторых, и в-главных, теорема об эквивалентности
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.