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

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

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

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

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

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

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

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

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

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

${\displaystyle f_{i}(z)=F_{i}'(z)}$

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

Излишек распределения определяется как:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle w^{-1}(0)}$

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

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

${\displaystyle w^{-1}(0)}$

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

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

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

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