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

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

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

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

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

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

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

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

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

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

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

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

2. Консенсус-оценка:

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

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

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

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

Заказывайте покупателей по убыванию цены, а продавцов - по возрастающей.
Найдите самый большой ${ displaystyle k}$ такой, что ${ Displaystyle к cdot (b_ {k} -s_ {k}) geq R}$ .
В ${ displaystyle k-1}$ дорогие покупатели покупают товар по цене ${ displaystyle b_ {k}}$ . В ${ displaystyle k-1}$ дешевые продавцы продают товар по цене ${ displaystyle s_ {k}}$ .

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

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

История

Механизм извлечения прибыли - частный случай разделение затрат механизм.^[3] Он был адаптирован из литературы о разделении затрат для условий аукциона.^[4]^[5]

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

^ ^а ^б ^c Джейсон Д. Хартлайн и Анна Р. Карлин, «Максимизация прибыли при проектировании механизмов». Глава 13 в Вазирани, Виджай В.; Нисан, Ноам; Roughgarden, Тим; Тардос, Ива (2007). Алгоритмическая теория игр (PDF). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.
^ Дешмук, Каустубх; Гольдберг, Эндрю В .; Хартлайн, Джейсон Д .; Карлин, Анна Р. (2002). «Правдивые и конкурентоспособные двойные аукционы». Алгоритмы - ESA 2002. Конспект лекций по информатике. 2461. п. 361. Дои:10.1007/3-540-45749-6_34. ISBN 978-3-540-44180-9.
^ Мулен, Эрве; Шенкер, Скотт (2001). «Стратегически устойчивое разделение субмодульных затрат: баланс бюджета против эффективности». Экономическая теория. 18 (3): 511. CiteSeerX 10.1.1.25.4285. Дои:10.1007 / pl00004200.
^ Эндрю В. Голдберг, Джейсон Д. Хартлайн (2003). «Конкурентоспособность через консенсус». Материалы четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. СОДА 03. Получено 14 марта 2016.
^ Фиат, Амос; Гольдберг, Эндрю В .; Хартлайн, Джейсон Д .; Карлин, Анна Р. (2002). «Конкурсные обобщенные аукционы». Материалы тридцать четвертого ежегодного симпозиума ACM по теории вычислений - STOC '02. п. 72. Дои:10.1145/509907.509921. ISBN 1581134959.

[agt-1] а ^б ^c Джейсон Д. Хартлайн и Анна Р. Карлин, «Максимизация прибыли при проектировании механизмов». Глава 13 в Вазирани, Виджай В.; Нисан, Ноам; Roughgarden, Тим; Тардос, Ива (2007). Алгоритмическая теория игр (PDF). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.

[dghk-2] Дешмук, Каустубх; Гольдберг, Эндрю В .; Хартлайн, Джейсон Д .; Карлин, Анна Р. (2002). «Правдивые и конкурентоспособные двойные аукционы». Алгоритмы - ESA 2002. Конспект лекций по информатике. 2461. п. 361. Дои:10.1007/3-540-45749-6_34. ISBN 978-3-540-44180-9.

[ms01-3] Мулен, Эрве; Шенкер, Скотт (2001). «Стратегически устойчивое разделение субмодульных затрат: баланс бюджета против эффективности». Экономическая теория. 18 (3): 511. CiteSeerX 10.1.1.25.4285. Дои:10.1007 / pl00004200.

[gh03-4] Эндрю В. Голдберг, Джейсон Д. Хартлайн (2003). «Конкурентоспособность через консенсус». Материалы четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. СОДА 03. Получено 14 марта 2016.

[fghk02-5] Фиат, Амос; Гольдберг, Эндрю В .; Хартлайн, Джейсон Д .; Карлин, Анна Р. (2002). «Конкурсные обобщенные аукционы». Материалы тридцать четвертого ежегодного симпозиума ACM по теории вычислений - STOC '02. п. 72. Дои:10.1145/509907.509921. ISBN 1581134959.

[1]

[2]

[3]

[4]

[5]