Механизм извлечения прибыли

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

Извлечение прибыли на аукционе цифровых товаров

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

• Спросите каждого агента, сколько он готов заплатить за фильм.
• Для каждого целого числа $k=1,2,...$, позволять $N_{k}$ быть числом агентов, готовых платить по крайней мере $R/k$. Обратите внимание, что $N_{k}$ слабо возрастает с $k$.
• Если существует $k$ такой, что $N_{k}\geq k$, затем найдите самый большой такой $k$ (которое должно быть равно $N_{k}$), продать фильм этим $k$ агентов и взимать с каждого такого агента цену в размере $R/k$.
• Если нет такого $k$ существует, то аукцион отменяется и победителей нет.

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

• Если выигравший агент увеличит свою ставку, то $k$ слабо возрастает и агент по-прежнему остается одним из $k$ предложивший самую высокую цену, поэтому он все равно выигрывает.
• Выигравший агент платит $R/k$, что и есть пороговая цена – цена, ниже которой ставка перестает быть выигрышной.

Оценка максимального дохода

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

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

Случайным образом разделите участников торгов на две группы так, чтобы каждый участник торгов имел шанс 1/2 попасть в каждую группу. Пусть R1 — максимальный доход в группе 1, а R2 — максимальный доход в группе 2. Запустите R1-извлекатель прибыли в группе 2 и R2-извлекатель прибыли в группе 1.

Этот механизм гарантирует прибыль в размере не менее 1/4 максимальной прибыли. Вариант этого механизма делит агентов на три группы вместо двух и позволяет получить не менее 1/3,25 максимальной прибыли.

2. Оцените консенсус :

Рассчитайте максимальный доход во всей популяции; применить определенный процесс случайного округления, который гарантирует, что расчет верен с высокой вероятностью. Пусть R — предполагаемый доход; запустить R-экстрактор прибыли во всей популяции.

Этот механизм гарантирует прибыль в размере не менее 1/3,39 максимальной прибыли на аукционе цифровых товаров.

Извлечение прибыли на двойном аукционе

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

• Расположите покупателей по убыванию цены, а продавцов – по возрастанию.
• Найдите самый большой $k$ такой, что $k\cdot (b_{k}-s_{k})\geq R$.
• The $k-1$ дорогие покупатели покупают товар по цене $b_{k}$. $k-1$ продавцы с низкой стоимостью продают товар по цене $s_{k}$.

Механизм правдив – это можно доказать, используя аргумент монотонности, аналогичный аукциону цифровых товаров. Доход аукциониста составляет $(k-1)\cdot (b_{k}-s_{k})\geq {k-1 \over k}R$, который приближается к требуемому доходу, когда он достаточно велик.

Сочетание этого экстрактора прибыли с оценщиком консенсуса дает правдивый механизм двойного аукциона, который гарантирует прибыль не менее 1/3,75 от максимальной прибыли.

История

Механизм извлечения прибыли является частным случаем механизма разделения затрат . Он был адаптирован на основе литературы по разделению затрат для условий аукциона.