WikiDer > Механизм случайной выборки - Википедия

Random-sampling mechanism - Wikipedia

А механизм случайной выборки (RSM) это правдивый механизм который использует отбор проб для достижения примерно оптимального прироста бесприоритетные механизмы и предшествующие независимые механизмы.

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

RSM на крупных рынках

Схема деления рынка вдвое

Когда рынок большой, можно использовать следующую общую схему:[1]:341–344

  1. Покупателей просят раскрыть свои оценки.
  2. Покупатели разделены на два субрынка: ("слева") и ("право"), используя простая случайная выборка: каждый покупатель переходит в одну из сторон, бросая честная монета.
  3. На каждом субрынке , эмпирическая функция распределения рассчитывается.
  4. В Байесовский оптимальный механизм (Механизм Майерсона) применяется на субрынке с распределением , И в с .

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

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

Интуитивно по закон больших чисел, если рынок достаточно велик, то эмпирические распределения достаточно похожи на реальные распределения, поэтому мы ожидаем, что RSEM достигнет почти оптимальной прибыли. Однако это не обязательно верно во всех случаях. Это было доказано в некоторых частных случаях.

Самый простой случай аукцион цифровых товаров. Здесь шаг 4 прост и состоит только из расчета оптимальной цены на каждом субрынке. Оптимальная цена в применяется к наоборот. Следовательно, этот механизм называется «Оптимальная цена со случайной выборкой» (RSOP). Этот случай прост, потому что он всегда рассчитывает возможные распределения. То есть всегда можно применить цену, рассчитанную с одной стороны, к другой стороне. Это не обязательно относится к физическим товарам.

Даже на аукционе цифровых товаров RSOP не обязательно приводит к оптимальной прибыли. Он сходится только под ограниченные оценки предположение: для каждого покупателя оценка товара составляет от 1 до , куда некоторая константа. Скорость сходимости RSOP к оптимальности зависит от . Скорость сходимости также зависит от количества возможных «предложений», рассматриваемых механизмом.[2]

Чтобы понять, что такое «предложение», рассмотрим аукцион цифровых товаров, на котором оценки покупателей в долларах, как известно, ограничены . Если в механизме используются только цены в долларах, то есть только возможные предложения.

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

Для каждого набора агентов, прибыль механизма от подачи оферты агентам в является:

а оптимальная прибыль механизма составляет:

RSM рассчитывает для каждого субрынка , оптимальное предложение , рассчитывается следующим образом:

Предложение применяется к покупателям в , то есть: каждый покупатель кто это сказал получает предложенное размещение и платит ; каждый покупатель в кто это сказал ничего не получают и не платят. Предложение применяется к покупателям в Аналогичным образом.

Схема прибыли-оракула

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

звонки в оракул-прибыль.

RSM на малых рынках

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

Сокращение рынка вдвое, цифровые товары

Первое исследование в этой обстановке было для аукцион цифровых товаров с Однопараметрическая утилита.[4]

Для механизма оптимальной цены с произвольной выборкой были рассчитаны несколько более точных приближений:

  • К,[5] прибыль механизма составляет не менее 1/7600 от оптимальной.
  • К,[6] прибыль механизма составляет не менее 1/15 оптимальной.
  • К,[7] прибыль механизма составляет не менее 1 / 4,68 от оптимального, а в большинстве случаев - 1/4 от оптимального, что мало.

Единичные физические товары

Когда оценки агентов удовлетворяют некоторому техническому условию регулярности (называемому монотонная степень опасности), можно достичь приближения постоянного коэффициента к аукциону с максимальной прибылью, используя следующий механизм:[8]

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

Прибыль от этого механизма не менее , куда количество агентов. Это 1/8 при наличии двух агентов и увеличивается до 1/4 по мере роста числа агентов. Эта схема может быть обобщена для обработки ограничений на подмножества агентов, которые могут выигрывать одновременно (например, существует только конечное число элементов). Он также может обрабатывать агентов с разными атрибутами (например, молодые и старые участники торгов).

Сложность образца

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

Результаты в [8] подразумевают несколько ограничений на выборочную сложность максимизации дохода от аукционов по отдельным позициям:[9]

  • Для -аппроксимация оптимального ожидаемого дохода, сложность выборки равна - Достаточно одного образца. Это верно даже тогда, когда участники торгов не являются i.i.d.[10]
  • Для - аппроксимация оптимального ожидаемого дохода, когда участники торгов являются i.i.d ИЛИ при неограниченном количестве предметов (цифровых товаров) сложность выборки равна когда в распределениях агентов монотонная степень опасности, и когда распределения агентов регулярны, но не имеют монотонной степени опасности.

Ситуация усложняется, когда агенты не являются i.i.d (стоимость каждого агента берется из разного регулярного распределения), а количество товаров ограничено. Когда агенты приходят из различных распределений, сложность выборки -приближение оптимальной ожидаемой выручки на аукционах по отдельным позициям составляет:[9]

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

[11] обсуждать произвольные аукционы с однопараметрическая утилита агенты (не только отдельные аукционы) и произвольные механизмы аукционов (не только отдельные аукционы). На основании известных результатов о сложность образца, они показывают, что количество образцов, необходимых для приблизительного определения аукциона с максимальным доходом от данного класса аукционов, составляет:

куда:

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

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

Завидовать

Недостатком механизма случайной выборки является то, что он не без зависти. Например, если оптимальные цены на двух субрынках и различны, то покупателям на каждом субрынке предлагается разная цена. Другими словами, есть ценовая дискриминация. Это неизбежно в том смысле, что единой цены не существует. стратегически устойчивый аукцион, который приближает оптимальную прибыль.[12]

Смотрите также

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

  1. ^ Вазирани, Виджай В.; Нисан, Ноам; Roughgarden, Тим; Тардос, Ива (2007). Алгоритмическая теория игр (PDF). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.
  2. ^ Балкан, Мария-Флорина; Блюм, Аврим; Хартлайн, Джейсон Д .; Мансур, Ишай (2008). «Сведение дизайна механизма к разработке алгоритма с помощью машинного обучения». Журнал компьютерных и системных наук. 74 (8): 1245. Дои:10.1016 / j.jcss.2007.08.002.
  3. ^ Эдит Элкинд (2007). Разработка и изучение оптимальных аукционов конечной поддержки. СОДА.
  4. ^ Гольдберг, Эндрю В .; Хартлайн, Джейсон Д. (2001). «Конкурсные аукционы по продаже множества цифровых товаров». Алгоритмы - ESA 2001. Конспект лекций по информатике. 2161. п. 416. CiteSeerX 10.1.1.8.5115. Дои:10.1007/3-540-44676-1_35. ISBN 978-3-540-42493-2.
  5. ^ Гольдберг, Эндрю В .; Хартлайн, Джейсон Д .; Карлин, Анна Р .; Сакс, Майкл; Райт, Эндрю (2006). «Конкурсные аукционы». Игры и экономическое поведение. 55 (2): 242. Дои:10.1016 / j.geb.2006.02.003.
  6. ^ Файги, Уриэль; Флаксман, Авраам; Хартлайн, Джейсон Д .; Клейнберг, Роберт (2005). «О коэффициенте конкуренции аукционов случайной выборки». Интернет и сетевая экономика. Конспект лекций по информатике. 3828. п. 878. CiteSeerX 10.1.1.136.2094. Дои:10.1007/11600930_89. ISBN 978-3-540-30900-0.
  7. ^ Алаеи, Саид; Малекян, Азарахш; Шринивасан, Аравинд (2009). «Об аукционах случайной выборки цифровых товаров». Материалы десятой конференции ACM по электронной коммерции - EC '09. п. 187. CiteSeerX 10.1.1.758.3195. Дои:10.1145/1566374.1566402. ISBN 9781605584584.
  8. ^ а б Дхангватнотай, Пирапонг; Roughgarden, Тим; Ян, Цици (2015). «Максимизация дохода с помощью одного образца». Игры и экономическое поведение. 91: 318–333. Дои:10.1016 / j.geb.2014.03.011.
  9. ^ а б Коул, Ричард; Roughgarden, Тим (2014). «Примерная сложность максимизации дохода». Материалы 46-го ежегодного симпозиума ACM по теории вычислений - STOC '14. п. 243. arXiv:1502.00963. Дои:10.1145/2591796.2591867. ISBN 9781450327107.
  10. ^ Хартлайн, Джейсон Д .; Roughgarden, Тим (2009). «Простые механизмы против оптимальных». Материалы десятой конференции ACM по электронной коммерции - EC '09. п. 225. Дои:10.1145/1566374.1566407. ISBN 9781605584584.
  11. ^ О псевдоразмерности почти оптимальных аукционов. НИПС. 2015 г. arXiv:1506.03684. Bibcode:2015arXiv150603684M.
  12. ^ Эндрю В. Голдберг и Джейсон Д. Хартлайн (2003). «Конкурентоспособность через консенсус». Материалы четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. SODA '03. Получено 7 января 2016.