Приоритетный механизм - Prior-free mechanism

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

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

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

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

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

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

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

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

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

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

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

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

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

1. 51 покупатель сделал ставку "1 доллар"
2. 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

1. 10 покупателей сделали ставку «10 долларов»;
2. 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/b-h\cdot c}$ во всех случаях, когда оценки агентов находятся в ${\displaystyle [1,h]}$.

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

Основная статья: Механизм случайной выборки

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

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

Основная статья: Консенсус-оценка

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

Рекомендации

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