Эквивалентность доходов

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

Обозначение

Существует ряд возможных результатов. ${\displaystyle X}$

Существуют агенты, которые имеют разные оценки для каждого результата. Оценка агента (также называемая его «типом») представлена ​​в виде функции: ${\displaystyle n}$ ${\displaystyle i}$

${\displaystyle v_{i}:X\longrightarrow R_{\geq 0}}$

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

Агенты имеют квазилинейные функции полезности; это означает, что если результат равен и, кроме того, агент получает платеж (положительный или отрицательный), то общая полезность агента равна: ${\displaystyle x}$ ${\displaystyle p_{i}}$ ${\displaystyle i}$

${\displaystyle u_{i}:=v_{i}(x)+p_{i}}$

Вектор всех функций-стоимостей обозначается как . ${\displaystyle v}$

Для каждого агента вектор всех функций стоимости других агентов обозначается как . Таким образом . ${\displaystyle i}$ ${\displaystyle v_{-i}}$ ${\displaystyle v\equiv (v_{i},v_{-i})}$

Механизм — это пара функций:

• Функция , которая принимает в качестве входных данных вектор значений и возвращает результат (ее также называют функцией социального выбора ); ${\displaystyle Outcome}$ ${\displaystyle v}$ ${\displaystyle x\in X}$
• Функция , которая принимает в качестве входных данных вектор-значение и возвращает вектор платежей, определяющий, сколько должен получить каждый игрок (отрицательный платеж означает, что игрок должен заплатить положительную сумму). ${\displaystyle Payment}$ ${\displaystyle v}$ ${\displaystyle (p_{1},\dots ,p_{n})}$

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

Заявление

При этих предположениях теорема об эквивалентности доходов гласит следующее. ^{[1] : 236–237}

Для любых двух совместимых механизмов стимулирования Байеса-Нэша, если:

• Функция в обоих механизмах одинакова: ${\displaystyle Outcome}$
• Для некоторого типа ожидаемая выплата игрока (усредненная по типам других игроков) одинакова в обоих механизмах; ${\displaystyle v_{i}^{0}}$ ${\displaystyle i}$
• Оценка каждого игрока берется из набора , связанного путями ,

затем:

• Ожидаемые выплаты всех типов одинаковы в обоих механизмах, и, следовательно:
• Ожидаемый доход (-сумма платежей) одинаков в обоих механизмах.

Пример

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

• Функция в обоих механизмах одинакова — покупатель, предложивший самую высокую цену, выигрывает лот; и: ${\displaystyle Outcome}$
• Игрок, оценивающий предмет как 0, всегда платит 0 в обоих механизмах.

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

Эквивалентность аукционных механизмов на аукционах отдельных предметов

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

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

Рассмотрим аукцион одной позиции второй цены , в котором игрок с самой высокой ставкой платит вторую по величине ставку. Оптимальным для каждого игрока будет сделать ставку на свою собственную стоимость . ${\displaystyle i}$ ${\displaystyle b_{i}=v_{i}}$

Предположим, выигрывает аукцион и платит вторую по величине ставку, или . Доход от этого аукциона составляет просто . ${\displaystyle i}$ ${\displaystyle \max _{j\neq i}b_{j}}$ ${\displaystyle \max _{j\neq i}b_{j}}$

Аукцион первой цены

На аукционе первой цены , где игрок с самой высокой ставкой просто платит свою ставку, если все игроки делают ставки, используя функцию ставок, это равновесие Нэша. ${\displaystyle b(v)=E(\max _{j\neq i}v_{j}~|~v_{j}\leq v~\forall ~j),}$

Другими словами, если каждый игрок делает ставку, которая равна ожидаемому значению второй по величине ставки, предполагая, что его ставка была самой высокой, то ни у одного игрока нет стимула отклоняться. Если бы это было правдой, то легко увидеть, что ожидаемый доход от этого аукциона также составляет , если выигрывает аукцион. ${\displaystyle \max _{j\neq i}b_{j}}$ ${\displaystyle i}$

Доказательство

Чтобы доказать это, предположим, что игрок 1 делает ставку , где , фактически блефуя, что ее значение равно , а не . Мы хотим найти значение , при котором ожидаемый выигрыш игрока будет максимальным. ${\displaystyle b(z)}$ ${\displaystyle z<v}$ ${\displaystyle z}$ ${\displaystyle v}$ ${\displaystyle z}$

Вероятность выигрыша тогда . Ожидаемая стоимость этой ставки . Тогда ожидаемый выигрыш игрока равен ${\displaystyle Pr(\max _{i>1}v_{i}<z)}$ ${\displaystyle E(\max _{i>1}v_{i}~|~v_{i}<z~\forall ~i)}$

${\displaystyle Pr(\max _{i>1}v_{i}<z)(v-E(\max _{i>1}v_{i}~|~v_{i}<z~\forall ~i))}$

Пусть , случайная величина. Тогда мы можем переписать вышесказанное как ${\displaystyle X=\max _{i>1}v_{i}}$

${\displaystyle Pr(X<z)(v-E(X~|X\leq z))}$.

Используя общий факт, что , мы можем переписать вышесказанное как ${\displaystyle E(X~|~X\leq z)\cdot Pr(X<z)=\int _{0}^{z}Pr(X<z)-Pr(X<y)dy}$

${\displaystyle Pr(X<z)\cdot v-Pr(X<z)\cdot z+\int _{0}^{z}Pr(X<y)dy}$.

Взяв производные по , получаем ${\displaystyle z}$

${\displaystyle Pr(X<z)'(v-z)=0\Rightarrow v=z}$.

Таким образом, ставка с вашим значением максимизирует ожидаемый выигрыш игрока. Поскольку монотонно увеличивается, мы проверяем, что это действительно максимальная точка. ${\displaystyle v}$ ${\displaystyle Pr(X<z)}$

английский аукцион

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

Рассмотрим случай двух покупателей, каждый из которых имеет значение, которое является независимым от распределения с поддержкой [0,1], кумулятивной функцией распределения F(v) и функцией плотности вероятности f(v). Если покупатели ведут себя в соответствии со своими доминирующими стратегиями, то покупатель со значением v выигрывает, если значение x его оппонента ниже. Таким образом, вероятность его выигрыша равна

${\displaystyle w=\Pr\{x<v\}\equiv F(v)}$

и его ожидаемая оплата составляет

${\displaystyle C(v)=\int \limits _{0}^{v}{}xf(x)dx}$

Ожидаемая выплата, обусловленная выигрышем, таким образом, составляет

${\displaystyle e(v)={\frac {C(v)}{F(v)}}={\frac {\int \limits _{0}^{v}{}xf(x)dx}{F(v)}}}$

Умножая обе части на F(v) и дифференцируя по v, получаем следующее дифференциальное уравнение для e(v).

${\displaystyle {e}'(v)F(v)+e(v)f(v)=vf(v)}$.

Перестроим это уравнение,

${\displaystyle {e}'(v)={\frac {f(v)}{F(v)}}(v-e(v))}$

Пусть B(v) будет функцией равновесной ставки в закрытом аукционе первой цены. Мы устанавливаем эквивалентность доходов, показывая, что B(v)=e(v), то есть равновесный платеж победителя на одном аукционе равен равновесному ожидаемому платежу победителя на другом.

Предположим, что покупатель имеет значение v и делает ставку b. Его оппонент делает ставку в соответствии со стратегией равновесных ставок. Поддержка распределения ставок оппонента равна [0,B(1)]. Таким образом, любая ставка не менее B(1) выигрывает с вероятностью 1. Следовательно, лучшая ставка b лежит в интервале [0,B(1)], и поэтому мы можем записать эту ставку как b = B(x), где x лежит в [0,1]. Если у оппонента есть значение y, он делает ставку B(y). Следовательно, вероятность выигрыша равна

${\displaystyle w=\Pr\{b<B(y)\}=\Pr\{B(x)<B(y)\}=\Pr\{x<y\}=F(v)}$.

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

${\displaystyle U=w(v-B(x))=F(x)(v-B(x))}$.

Дифференцируя, необходимое условие максимума равно

${\displaystyle {U}'(x)=f(x)(v-B(x))-F(x){B}'(x)=F(x)\left({\frac {f(x)}{F(x)}}(v-B(x))-{B}'(x)\right)=0}$.

То есть, если B(x) является наилучшим ответом покупателя, он должен удовлетворять этому условию первого порядка. Наконец, отметим, что для того, чтобы B(v) была функцией равновесной ставки, наилучшим ответом покупателя должен быть B(v). Таким образом, x=v. Подставляя x в необходимое условие,

${\displaystyle {\frac {f(v)}{F(v)}}(v-B(v))-{B}'(v)=0}$.

Обратите внимание, что это дифференциальное уравнение идентично уравнению для e(v). Поскольку e(0)=B(0)=0, то следует, что . ${\displaystyle B(v)=e(v)}$

Использование эквивалентности доходов для прогнозирования функций торгов

Мы можем использовать эквивалентность доходов для прогнозирования функции ставок игрока в игре. Рассмотрим версию аукциона второй цены для двух игроков и аукциона первой цены, где стоимость каждого игрока равномерно вытягивается из . ${\displaystyle [0,1]}$

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

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

${\displaystyle E({\text{Payment}}~|~{\text{Player 1 wins}})P({\text{Player 1 wins}})+E({\text{Payment}}~|~{\text{Player 1 loses}})P({\text{Player 1 loses}})}$

Поскольку игроки честно делают ставки на аукционе второй цены, мы можем заменить все цены на значения игроков. Если игрок 1 выигрывает, он платит то, что игрок 2 делает ставки, или . Сам игрок 1 делает ставки . Поскольку оплата равна нулю, когда игрок 1 проигрывает, вышесказанное ${\displaystyle p_{2}=v_{2}}$ ${\displaystyle p_{1}=v_{1}}$

${\displaystyle E(v_{2}~|~v_{2}<v_{1})P(v_{2}<v_{1})+0}$

Так как мы пришли из равномерного распределения, мы можем упростить это до ${\displaystyle v_{1},v_{2}}$

${\displaystyle {\frac {v_{1}}{2}}\cdot v_{1}={\frac {v_{1}^{2}}{2}}}$

Аукцион первой цены

Мы можем использовать эквивалентность доходов для генерации правильной симметричной функции торгов на аукционе первой цены. Предположим, что на аукционе первой цены каждый игрок имеет функцию торгов , где эта функция неизвестна на данный момент. ${\displaystyle b(v)}$

Ожидаемая выплата игрока 1 в этой игре составит

${\displaystyle E({\text{Payment}}~|~{\text{Player 1 wins}})P({\text{Player 1 wins}})+E({\text{Payment}}~|~{\text{Player 1 loses}})P({\text{Player 1 loses}})}$(как указано выше)

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

${\displaystyle b(v_{1})\cdot v_{1}+0}$

По принципу эквивалентности доходов мы можем приравнять это выражение к доходу аукциона второй цены, который мы рассчитали выше:

${\displaystyle b(v_{1})\cdot v_{1}={\frac {v_{1}^{2}}{2}}}$

Из этого можно вывести функцию торгов:

${\displaystyle b(v_{1})={\frac {v_{1}}{2}}}$

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

Аукционы с полной оплатой

Аналогично, мы знаем, что ожидаемая выплата игрока 1 на аукционе второй цены составляет , и она должна быть равна ожидаемой выплате на аукционе со всеми выплатами , т.е. ${\displaystyle {\frac {v_{1}^{2}}{2}}}$

${\displaystyle {\frac {v_{1}^{2}}{2}}=b(v_{1})}$

Таким образом, функция ставок для каждого игрока в аукционе с полной оплатой равна ${\displaystyle {\frac {v^{2}}{2}}}$

Подразумеваемое

Важным следствием теоремы является то, что любой аукцион с одним предметом, который безоговорочно отдает предмет тому, кто сделал самую высокую ставку, будет иметь тот же ожидаемый доход. Это означает, что если мы хотим увеличить доход аукциониста, функция результата должна быть изменена. Один из способов сделать это — установить цену резервирования для предмета. Это изменяет функцию результата, поскольку теперь предмет не всегда отдается тому, кто сделал самую высокую ставку. Тщательно выбирая цену резервирования, аукционист может получить существенно более высокий ожидаемый доход. ^{[1] : 237}

Ограничения

Теорема эквивалентности доходов нарушается в некоторых важных случаях: ^{[1] : 238–239}

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

Ссылки

1. Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.

• Хартлайн, Джейсон, Аппроксимация в экономическом проектировании (PDF).