Эквивалент выручки - Revenue equivalence

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

Обозначение

Есть набор ${ 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 эквив (v_ {я}, v _ {- я})}$.

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

• An ${ 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 г$, эффективно блефуя, что его ценность ${ displaystyle z}$ скорее, чем ${ displaystyle v}$. Мы хотим найти значение ${ displaystyle z}$ таким образом, чтобы ожидаемый выигрыш игрока был максимальным.

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

${ Displaystyle Pr ( max _ {я> 1} v_ {i} 1} v_ {i} ~ | ~ v_ {i}$

Позволять ${ Displaystyle Х = макс _ {я> 1} v_ {я}}$, случайная величина. Затем мы можем переписать приведенное выше как

${ Displaystyle Pr (Икс$.

Используя тот общий факт, что ${ Displaystyle Е (Икс ~ | ~ Икс leq z) cdot Pr (X$, мы можем переписать приведенное выше как

${ Displaystyle Pr (Икс$.

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

${ Displaystyle Pr (X$.

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

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

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

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

${ Displaystyle ш = Pr {х$

и его ожидаемый платеж

${ 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 {е} '(v) F (v) + е (v) f (v) = vf (v)}$.

Преобразуя это уравнение,

${ Displaystyle {е} '(v) = { гидроразрыва {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$.

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

${ Displaystyle U = вес (v-B (x)) = F (x) (v-B (x))}$.

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

${ Displaystyle {U} '(x) = f (x) (vB (x)) - F (x) {B}' (x) = F (x) left ({ frac {f (x)} {F (x)}} (vB (x)) - {B} '(x) right) = 0}$.

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

${ Displaystyle { гидроразрыва {f (v)} {F (v)}} (v-B (v)) - {B} '(v) = 0}$.

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

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

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

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

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

${ displaystyle E ({ text {Payment}} ~ | ~ { text {Игрок 1 выигрывает}}) P ({ text {Игрок 1 выигрывает}}) + E ({ text {Payment}} ~ | ~ { text {Игрок 1 проигрывает}}) P ({ text {Игрок 1 проигрывает}})}$

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

${ Displaystyle E (v_ {2} ~ | ~ v_ {2}$

С ${ 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 {Игрок 1 выигрывает}}) P ({ text {Игрок 1 выигрывает}}) + E ({ text {Payment}} ~ | ~ { text {Игрок 1 проигрывает}}) P ({ text {Игрок 1 проигрывает}})}$ (как указано выше)

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

${ 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}}}$

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

All-pay аукционы

Точно так же мы знаем, что ожидаемый платеж игрока 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. ^ ^{а б c} Вазирани, Виджай В.; Нисан, Ноам; Roughgarden, Тим; Тардос, Ива (2007). Алгоритмическая теория игр (PDF). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN  0-521-87282-0.

• Хартлайн, Джейсон, Приближение в экономическом дизайне (PDF).