Безприорный механизм

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

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

ПФМ следует противопоставлять двум другим типам механизмов:

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

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

Что мы можем сделать без предварительного? Наивный подход – использовать статистику : спросить потенциальных покупателей, какова их оценка, и использовать их ответы для расчета эмпирической функции распределения . Затем примените методы проектирования байесовского оптимального механизма к эмпирической функции распределения.

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

Ниже описаны несколько подходов к разработке правдивых механизмов без априорной обработки.

Детерминированное эмпирическое распределение

Для каждого агента $i$ , позволять $F_{-i}$ — эмпирическая функция распределения, рассчитанная на основе оценок всех агентов, кроме $i$ . Используйте байесовский оптимальный механизм с $F_{-i}$ рассчитать цену и распределение для агента $i$ .

Очевидно, что ставка агента $i$ влияет только на цены, уплачиваемые другими агентами, а не на свою собственную цену; следовательно, механизм правдив. ^[1]^{: 339–341}

Этот «эмпирический механизм Майерсона » работает в некоторых случаях, но не работает в других.

Вот случай, в котором это работает довольно хорошо. Предположим, мы находимся на аукционе цифровых товаров . Мы запрашиваем у покупателей оценку товара и получаем следующие ответы:

51 покупатель сделал ставку «1 доллар»
50 покупателей сделали ставку «3 доллара».

Для каждого из покупателей в группе 1 эмпирическое распределение составляет 50 покупателей по 1 доллару и 50 покупателей по 3 доллара, поэтому эмпирическая функция распределения равна «0,5 шансов на 1 доллар и 0,5 шансов на 3 доллара». Для каждого покупателя в группе 2 эмпирическое распределение составляет 51 покупатель по 1 доллару и 49 покупателей по 3 доллара, поэтому эмпирическая функция распределения равна «0,51 шанса на 1 доллар и 0,49 шанса на 3 доллара». Байесовская оптимальная цена в обоих случаях составляет 3 доллара. Таким образом, в этом случае цена, данная всем покупателям, составит 3 доллара. Только 50 покупателей из группы 2 согласны с этой ценой, поэтому наша прибыль составляет 150 долларов. Это оптимальная прибыль (например, цена в 1 доллар даст нам прибыль всего в 101 доллар).

В общем, эмпирический механизм Майерсона работает, если выполняются следующие условия:

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

Тогда прибыль эмпирического механизма Майерсона приближается к оптимуму.

Если некоторые из этих условий неверны, то эмпирический механизм Майерсона может иметь низкую эффективность. Вот пример. Предположим, что: ^[1]^: 340

10 покупателей сделали ставку «10 долларов»;
91 покупатель сделал ставку «1 доллар».

Для каждого покупателя в группе 1 эмпирическая функция распределения равна «вероятность 0,09 получить 10 долларов и вероятность 0,91 получить 1 доллар», поэтому оптимальная по Байесу цена равна 1 доллару. Для каждого покупателя в группе 2 эмпирическая функция распределения равна «вероятность 0,1 получить 10 долларов и вероятность 0,9 получить 1 доллар», поэтому оптимальная по Байесу цена равна 10 долларам. Покупатели в группе 1 платят 1 доллар, а покупатели из группы 2 не хотят платить 10 долларов, поэтому мы получаем прибыль в размере 10 долларов. Напротив, цена в 1 доллар для каждого дала бы нам прибыль в 101 доллар. Наша прибыль составляет менее 10% от оптимума. Этот пример можно сделать сколь угодно плохим.

Более того, этот пример можно обобщить, чтобы доказать, что: ^[1]^: 341

Не существует констант

b,c

и симметричный детерминированный правдивый аукцион, который приносит прибыль не менее

OPT/b-h\cdot c

во всех случаях, когда оценки агентов находятся в пределах

[1,h]

.

Случайная выборка

В типичном механизме случайной выборки потенциальные покупатели случайным образом делятся на два субрынка. Каждый покупатель посещает каждый субрынок с вероятностью 1/2 независимо от остальных. На каждом субрынке мы вычисляем эмпирическую функцию распределения и используем ее для расчета цен на другом субрынке. Предложение агента влияет только на цены на другом рынке, а не на его собственном, поэтому механизм правдив. Во многих сценариях он обеспечивает хорошее приближение к оптимальной прибыли даже в худших сценариях; ссылки см . в разделе «Механизм случайной выборки» .

Оцените консенсус

Консенсус-оценка — это функция, на которую с высокой вероятностью не может повлиять один агент. Например, если мы рассчитаем максимальную прибыль, которую мы можем извлечь из заданной группы покупателей, то любой покупатель может повлиять на прибыль, сообщив неправдивую информацию. Но если мы округлим максимальную прибыль до ближайших 1000 долларов ниже нее, а ставки будут ограничены, например, 10 долларами, то с высокой вероятностью одна ставка вообще не повлияет на результат. Это гарантирует, что механизм правдив. Функцию консенсусной оценки следует выбирать тщательно, чтобы гарантировать хорошее приближение прибыли; см . в Консенсусной оценке ссылки .

Ссылки

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

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

[1]