Байесовский оптимальный механизм

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

Типичное приложение — это продавец, который хочет продать некоторые товары потенциальным покупателям. Продавец хочет установить цену на товары таким образом, чтобы максимизировать свою прибыль. Оптимальные цены зависят от суммы, которую каждый покупатель готов заплатить за каждый товар. Продавец не знает этих сумм, но предполагает, что они взяты из некоторого известного распределения вероятностей . Фраза «байесовский оптимальный дизайн механизма» имеет следующий смысл: ^[1]^{: 335–338}

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

Пример

Продается один товар. Есть два потенциальных покупателя. Оценка каждого покупателя рассчитывается iid из равномерного распределения на [0,1].

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

Этот аукцион не является оптимальным. Можно получить большую прибыль, установив резервную цену . Аукцион Викри с резервной ценой 1/2 достигает ожидаемой прибыли 5/12, что в данном случае является оптимальным. ^[2]

Обозначения

Мы предполагаем, что агенты имеют функции полезности с одним параметром , такие как аукцион одного предмета. Каждый агент $i$ имеет ценность $v_{i}$ которая представляет собой «выигрышную стоимость» агента (например, оценку агентом предмета). Мы не знаем этих значений, но знаем, что каждое $v_{i}$ извлекается iid из определенного распределения вероятностей. Обозначим через $F_{i}$ кумулятивная функция распределения :

F_{i}(z)=\Pr[v_{i}<z]

и по $f_{i}$ функция распределения вероятностей :

f_{i}(z)=F_{i}'(z)

Распределение — это вектор $x$ , такой, что для каждого $i$ , $x_{i}$ равно 1, если агент $i$ выигрывает и 0 в противном случае. Каждое распределение может иметь издержки для аукциониста, $c(x)$ .

Профицит : ассигнований определяется как

S(x)=\sum _{i}x_{i}\cdot v_{i}-c(x)

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

Излишек – это максимально возможная прибыль. Если каждый выигравший агент $i$ платит ровно свою стоимость $v_{i}$ , то прибыль аукциониста равна именно излишку $S(x)$ ; это означает, что аукционист забирает все излишки себе и оставляет агентам нулевую полезность.

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

Механизм Майерсона

Роджер Майерсон разработал байесовский оптимальный механизм для однопараметрических служебных агентов. Ключевой трюк в механизме Майерсона — использование виртуальных оценок . Для каждого агента $i$ , определим его виртуальную оценку как:

w_{i}(v_{i})=v_{i}-{\frac {1-F_{i}(v_{i})}{f_{i}(v_{i})}}

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

Определите виртуальный излишек распределения $x$ как:

S^{*}(x)=\sum _{i}x_{i}\cdot w_{i}(v_{i})-c(x)

Обратите внимание, что виртуальный профицит обычно меньше фактического профицита.

Ключевая теорема Майерсона гласит: ^[1]^: 336^[3]

Ожидаемая прибыль любого правдивого механизма равна его ожидаемому виртуальному излишку.

(ожидание берется за случайность оценок агентов).

Эта теорема предполагает следующий механизм:

Спросите каждого агента $i$ сообщить об их оценке $v_{i}$
На основании ответа и известных функций распределения $F_{i},f_{i}$ , вычислить $w_{i}$ .
Вычислите распределение x, которое максимизирует виртуальный излишек. $S^{*}(x)$ .

Для завершения описания механизма следует указать цену, которую должен заплатить каждый выигравший агент. Одним из способов расчета цены является использование механизма VCG для виртуальных оценок. $w_{i}$ . Механизм VCG возвращает как распределение, максимизирующее виртуальный излишек, так и вектор цен. Поскольку вектор цен соответствует виртуальным оценкам, мы должны преобразовать его обратно в пространство реальных оценок. Итак, последний шаг механизма:

Возьмите с каждого победившего агента $i$ цена $p_{i}=w_{i}^{-1}(p'_{i})$ , где $p'_{i}$ — цена, определяемая механизмом VCG.

Правдивость

Механизм Майерсона истинен, когда правило распределения удовлетворяет свойству слабой монотонности , т. е. функция распределения слабо возрастает в оценках агентов. Правило распределения VCG действительно слабо возрастает в оценках, но мы используем его с виртуальными оценками, а не с реальными оценками. Следовательно, механизм Майерсона верен, если виртуальные оценки слабо возрастают по сравнению с реальными оценками. Т.е. если для всех $i$ : $w_{i}$ является слабовозрастающей функцией $v_{i}$ .

Если $w_{i}$ не является слабовозрастающей функцией $v_{i}$ , то утюжок Myerson можно использовать .

Механизм Майерсона можно применять в различных условиях. Два примера представлены ниже.

Единичный аукцион

Предположим, мы хотим продать один товар и знаем, что оценки всех агентов исходят из одного и того же распределения вероятностей с функциями $F,f$ . Тогда все участники торгов имеют одну и ту же функцию виртуальной оценки: $w$ . Предположим, что эта функция слабовозрастающая. В этом случае механизм VCG сводится к аукциону Викри : он передает лот агенту с наибольшей оценкой (самой высокой ставкой). Но механизм Майерсона использует VCG с виртуальными оценками, которые могут быть отрицательными. Следовательно, механизм Майерсона в данном случае сводится к аукциону Викри с резервированной ценой . Он назначает предмет агенту с наибольшей оценкой, но только если его виртуальная оценка равна как минимум 0 . Это означает, что резервационная цена механизма Майерсона равна ровно:

w^{-1}(0)

Итак, если мы знаем функции распределения вероятностей $F,f$ , мы можем вычислить функцию $w$ , и исходя из нее найдите оптимальную цену резервирования.

Аукцион цифровых товаров

На аукционе цифровых товаров у нас есть неограниченное количество идентичных товаров. Каждому агенту нужен не более одного предмета. Оценки агентов на предмет происходят из одного и того же распределения вероятностей с функциями $F,f$ и функция виртуальной оценки $w$ . Механизм VCG распределяет предмет каждому агенту с неотрицательной виртуальной оценкой и взимает минимальную выигрышную цену, которая составляет:

w^{-1}(0)

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

\arg \max _{z}{z\cdot (1-F(z))}

Альтернативы

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

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

Ссылки

^ Jump up to: ^а ^б Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0 .
^ Серхио Паррейрас. «Ожидаемый доход, полученный на аукционе Викери с резервной ценой 1/2» . стекобмен .
^ Майерсон, Роджер Б. (1981). «Оптимальный аукционный дизайн». Математика исследования операций . 6 (1): 58–73. дои : 10.1287/moor.6.1.58 .

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

[2] Серхио Паррейрас. «Ожидаемый доход, полученный на аукционе Викери с резервной ценой 1/2» . стекобмен .

[myerson81-3] Майерсон, Роджер Б. (1981). «Оптимальный аукционный дизайн». Математика исследования операций . 6 (1): 58–73. дои : 10.1287/moor.6.1.58 .

[1]

[2]

[3]