Байесовский оптимальный механизм (BOM) представляет собой механизм , в котором дизайнер не знает оценки агентов , для которых механизм предназначен, но он знает , что они являются случайными величинами , и он знает , что распределение вероятностей этих переменных.
Типичное приложение - это продавец, который хочет продать некоторые товары потенциальным покупателям. Продавец хочет установить цену на товары таким образом, чтобы получить максимальную прибыль. Оптимальные цены зависят от суммы, которую каждый покупатель готов платить за каждый товар. Продавец не знает этих сумм, но предполагает, что они взяты из определенного известного распределения вероятностей . Фраза «байесовская оптимальная конструкция механизма» имеет следующее значение: [1] : 335–338
- Байесовский означает, что мы знаем распределение вероятностей, из которого выводятся оценки агентов (в отличие от априорного дизайна механизма , который не предполагает никакого априорного распределения вероятностей).
- Оптимальный означает, что мы хотим максимизировать ожидаемый доход аукциониста, когда ожидание превышает случайность оценок агентов.
- Механизм означает, что мы хотим разработать правила, определяющие правдивый механизм , в котором каждый агент имеет стимул сообщать о своей истинной ценности.
Пример
В продаже есть один товар. Есть два потенциальных покупателя. Оценка каждого покупателя обращается IID от равномерного распределения на [0,1].
Vickrey аукцион правдивый механизм и его ожидаемая прибыль, в данном случае, является 1/3 [ править ] ( первую цена запечатанных ставок аукцион не является правдивым механизмом и его ожидаемая прибыль таким же ).
Этот аукцион не оптимален. Можно получить лучшую прибыль, установив резервную цену . Аукцион Викри с резервной ценой 1/2 приносит ожидаемую прибыль 5/12 [ необходима цитата ] , что в данном случае является оптимальным [ цитата ] .
Обозначение
Мы предполагаем, что у агентов есть однопараметрические функции полезности , такие как аукцион отдельных позиций. Каждый агент имеет ценность который представляет "выигрышную ценность" агента (например, оценку объекта агентом). Мы не знаем этих ценностей, но знаем, что каждыйiid извлекается из определенного распределения вероятностей. Обозначим черезИнтегральная функция распределения :
и по функция распределения вероятностей :
Распределение является вектором, так что для каждого , равно 1, если агент выигрывает и 0 в противном случае. Каждое распределение может иметь издержки для аукциониста,.
Избыток из распределения определяется как:
Это общая прибыль агентов за вычетом затрат на аукциониста.
Профицит - это максимально возможная прибыль. Если каждый выигравший агент платит точно свою стоимость , то прибыль аукциониста и есть излишек ; это означает, что аукционист забирает все излишки себе и оставляет агентам нулевую полезность.
Эта максимальная прибыль не может быть достигнута, потому что, если аукционист будет пытаться взимать с каждого выигравшего агента его стоимость , агенты будут лгать и сообщать о более низком значении, чтобы платить меньше. Механизм Майерсона решает эту проблему.
Механизм Майерсона
Роджер Майерсон разработал байесовский оптимальный механизм для однопараметрических служебных агентов. Ключевой уловкой в механизме Майерсона является использование виртуальных оценок . Для каждого агента, определите его виртуальную оценку как:
Обратите внимание, что виртуальная оценка обычно меньше фактической. Возможно даже, что виртуальная оценка будет отрицательной, а фактическая - положительной.
Определите виртуальный излишек распределения x как:
Обратите внимание, что виртуальный излишек обычно меньше фактического излишка.
Ключевая теорема Майерсона гласит: [1] : 336 [2]
- Ожидаемая прибыль любого правдивого механизма равна его ожидаемой виртуальной прибыли.
(ожидание берется из-за случайности оценок агентов).
Эта теорема предлагает следующий механизм:
- Спросите каждого агента сообщить его оценку
- На основании ответа и известных функций распределения , вычислить .
- Вычислить распределение x, которое максимизирует виртуальный излишек .
Чтобы завершить описание механизма, мы должны указать цену, которую должен заплатить каждый агент-победитель. Один из способов расчета цены - использовать механизм VCG для виртуальных оценок.. Механизм VCG возвращает как распределение, которое максимизирует виртуальный излишек, так и вектор цен. Поскольку вектор цен соответствует виртуальным оценкам, мы должны преобразовать его обратно в пространство реальных оценок. Итак, последний шаг механизма:
- Взять с каждого агента-победителя Цена , где цена, определяемая механизмом VCG.
Правдивость
Механизм Майерсона истинен, когда правило распределения удовлетворяет свойству слабой монотонности , т. Е. Функция распределения слабо возрастает в оценках агентов. Правило распределения VCG действительно слабо увеличивает оценки, но мы используем его с виртуальными оценками, а не с реальными оценками. Следовательно, механизм Майерсона истинен, если виртуальные оценки слабо растут в реальных оценках. Т.е. если для всех: является слабо возрастающей функцией .
Если не является слабо возрастающей функцией , то можно использовать глажку Майерсона .
Механизм Майерсона можно применять в различных условиях. Ниже представлены два примера.
Отдельный аукцион
Предположим, мы хотим продать один товар и знаем, что оценки всех агентов основаны на одном и том же распределении вероятностей с функциями . Тогда у всех участников аукциона будет одна и та же функция виртуальной оценки,. Предположим, что эта функция слабо возрастающая. В этом случае механизм VCG сводится к аукциону Викри : он передает предмет агенту с наибольшей оценкой (наивысшей ставкой). Но механизм Майерсона использует VCG с виртуальными оценками, которые могут быть отрицательными. Следовательно, механизм Майерсона в данном случае сводится к аукциону Викри с резервной ценой . Он присваивает предмет агенту с наибольшей оценкой, но только в том случае, если его виртуальная оценка составляет не менее 0 . Это означает, что резервная цена механизма Майерсона в точности равна:
Итак, если мы знаем функции распределения вероятностей , мы можем вычислить функцию , и по ней найти оптимальную цену бронирования.
Аукцион цифровых товаров
На аукционе цифровых товаров у нас есть неограниченное количество идентичных предметов. Каждому агенту нужно не более одного предмета. Оценки агентов по предмету исходят из того же распределения вероятностей с функциями и функция виртуальной оценки . Механизм VCG выделяет элемент каждому агенту с неотрицательной виртуальной оценкой и взимает минимальную выигрышную цену, которая составляет:
Это в точности равно оптимальной цене продажи - цене, которая максимизирует ожидаемое значение прибыли продавца с учетом распределения оценок:
Альтернативы
Разработка байесовского оптимального механизма требует знания распределений, из которых выводятся оценки агентов. Это требование не всегда выполняется. Есть и другие альтернативы:
- Когда распределение неизвестно, можно использовать априорный независимый механизм .
- Когда нельзя даже предположить, что агенты взяты из некоторого распределения вероятностей, следует использовать механизм без априорного распределения .
Рекомендации
- ^ a b Вазирани, Виджай В .; Нисан, Ноам ; Roughgarden, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.
- ^ Майерсон, Роджер Б. (1981). «Оптимальный дизайн аукциона». Математика исследования операций . 6 : 58. DOI : 10.1287 / moor.6.1.58 .