Механизм, независимый от предшествующего периода

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

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

PIM обычно включает в себя случайный процесс выборки. Продавец делает выборки некоторых оценок из неизвестного распределения и на основе выборок строит аукцион, который приносит приблизительно оптимальную прибыль. Главный исследовательский вопрос в разработке PIM: какова сложность выборки механизма? То есть, сколько агентов нужно сделать выборку, чтобы достичь разумного приближения к оптимальному благосостоянию?

Результаты в ^[1] подразумевают несколько ограничений на сложность выборки максимизации дохода аукционов с одним лотом: ^[2]

• Для аппроксимации оптимального ожидаемого дохода сложность выборки равна - достаточно одной выборки. Это верно даже тогда, когда участники торгов не являются iid ^[3]${\displaystyle 1/4}$${\displaystyle 1}$
• Для аппроксимации оптимального ожидаемого дохода, когда участники торгов независимы ИЛИ когда имеется неограниченное количество товаров (цифровых товаров), сложность выборки определяется, когда распределения агентов имеют монотонную скорость риска , и когда распределения агентов являются регулярными , но не имеют монотонной скорости риска.${\displaystyle 1-\epsilon}$${\displaystyle O(1/\epsilon ^{2})}$${\displaystyle O(1/\epsilon ^{3})}$

Ситуация становится более сложной, когда агенты не являются iid (значение каждого агента берется из другого регулярного распределения) и товары имеют ограниченное предложение. Когда агенты приходят из разных распределений, сложность выборки -аппроксимации оптимального ожидаемого дохода на аукционах с одним предметом равна: ^[2]${\displaystyle к}$${\displaystyle 1-\epsilon}$

• максимум - с использованием варианта эмпирического аукциона Майерсона.${\displaystyle O({k^{10} \over \epsilon ^{7}}\ln ^{3}{k \over \epsilon })}$
• по крайней мере (для регулярных оценок с монотонной степенью риска) и по крайней мере (для произвольных регулярных оценок).${\displaystyle \Omega ({k \over {\sqrt {\epsilon \ln k}}})}$${\displaystyle \Омега ({k \над \эпсилон})}$

^[4] обсуждают произвольные аукционы с агентами полезности с одним параметром (не только аукционы с одним предметом) и произвольные аукционные механизмы (не только конкретные аукционы). Основываясь на известных результатах о сложности выборки , они показывают, что количество выборок, необходимых для аппроксимации аукциона с максимальным доходом из заданного класса аукционов, равно:

${\displaystyle O{\bigg (}({H \over \epsilon })^{2}(D\ln({H \over \epsilon })+\ln({1 \over \delta })){\bigg )}}$

где:

• оценки агентов ограничены в ,${\displaystyle [1,H]}$
• псевдо- VC размерность класса аукционов не превышает ,${\displaystyle D}$
• требуемый коэффициент аппроксимации равен ,${\displaystyle 1-\epsilon}$
• требуемая вероятность успеха равна .${\displaystyle 1-\дельта}$

В частности, они рассматривают класс простых аукционов, называемых аукционами -level : аукционы с резервными ценами (аукцион Викри с одной резервной ценой является аукционом 1-level). Они доказывают, что псевдо-VC-размерность этого класса равна , что немедленно переводится в границу их ошибки обобщения и сложности выборки. Они также доказывают границы ошибки представления этого класса аукционов.${\displaystyle т}$${\displaystyle т}$${\displaystyle O(nt\ln(nt))}$

Деванур и др. изучают рынок с различными типами товаров и агентами единичного спроса . ^[5]

Чавла и др. изучают PIM для задачи минимизации времени выполнения . ^[6]

Сю и др. изучают рынок с различными типами товаров. Поставки фиксированы. Покупатели могут покупать наборы товаров и иметь разные оценки наборов. Они доказывают, что если покупатели выбираются независимо из некоторого неизвестного распределения, вычисляется оптимальный вектор цен, и этот вектор цен затем применяется к новой выборке покупателей, то общественное благосостояние приблизительно оптимально. Конкурентное соотношение, подразумеваемое их теоремой 6.3, с вероятностью , по крайней мере${\displaystyle n}$${\displaystyle n}$${\displaystyle 1-\дельта}$

${\displaystyle 1-O{\bigg (}{\sqrt {h^{3}n^{0.5}m^{4}\ln ^{2}m\ln ^{2}{1 \over \delta } \over {\text{OptimalWelfare}}}}{\bigg )}}$. ^[7]

Предшествующие независимые механизмы (ПНМ) следует противопоставлять двум другим типам механизмов:

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

С точки зрения проектировщика, BOM является самым простым, затем PIM, затем PFM. Гарантии аппроксимации BOM и PIM находятся в ожидаемом, в то время как гарантии PFM находятся в наихудшем случае.

• Исследование рынка
• Алгоритмическое ценообразование