Приоритетный механизм

Эта статья в значительной степени или полностью основана на одном источнике . Пожалуйста, помогите улучшить эту статью , добавив ссылки на дополнительные источники .
Найти источники: «Механизм безприоритета» - новости · газеты · книги · ученый · JSTOR ( май 2021 г. )

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

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

PFM следует противопоставить двум другим типам механизмов:

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

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

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

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

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

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

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

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

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

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

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}

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

{\ displaystyle b, c}

{\ displaystyle OPT / bh \ cdot c}

{\ displaystyle [1, h]}

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

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

Консенсус-оценки

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

использованная литература

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

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

[1]