Механизм случайной выборки

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

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

РСМ на крупных рынках

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

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

1. Покупателей просят раскрыть свои оценки.
2. Покупатели разделены на два субрынка: $M_{L}$ («левый») и $M_{R}$ («справа»), используя простую случайную выборку : каждый покупатель переходит в одну из сторон, подбрасывая честную монету .
3. В каждом субрынке $M_{s}$, эмпирическая функция распределения $F_{s}$ рассчитывается.
4. Байесовский оптимальный механизм (механизм Майерсона) применяется на субрынке. $M_{R}$ с раздачей $F_{L}$и в $M_{L}$ с $F_{R}$.

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

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

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

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

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

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

В общем, проблема оптимизации может включать в себя гораздо больше, чем просто одну цену. Например, мы можем захотеть продать несколько разных цифровых товаров, каждый из которых может иметь разную цену. Поэтому вместо «цены» мы говорим о «предложении». Мы предполагаем, что существует глобальное множество $G$ возможных предложений. За каждое предложение $g\in G$ и агент $i$, $g(i)$ это сумма, которую агент $i$ платит при получении предложения $g$. В примере с цифровыми товарами $G$ множество возможных цен. За любую возможную цену $p$, есть функция $g_{p}$ такой, что $g_{p}(i)$ либо 0 (если $v_{i}<p$) или $p$ (если $v_{i}\geq p$).

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

$g(S):=\sum _{i\in S}g(i)$

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

$OPT_{G}(S):=\max _{g\in G}g(S)$

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

$g_{s}:=\arg \max _{g\in G}g(M_{s})$

Предложение $g_{L}$ применяется к покупателям в $M_{R}$, то есть: каждый покупатель $i\in M_{R}$ кто это сказал $g_{L}(i)>0$ получает предложенное распределение и платит $g_{L}(i)$; каждый покупатель в $M_{R}$ кто это сказал $g_{L}(i)=0$ ничего не получайте и не платите. Предложение $g_{R}$ применяется к покупателям в $M_{L}$ аналогичным образом.

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

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

$O(n^{2}K^{2})$

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

RSM на небольших рынках

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

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

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

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

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

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

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

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

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

Сложность примера

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

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

• Для $1/4$-аппроксимация оптимального ожидаемого дохода, сложность выборки равна $1$ - достаточно одного образца. Это верно, даже если участники торгов не являются iid.
• Для $1-\epsilon$-аппроксимация оптимального ожидаемого дохода, когда участниками торгов являются iid ИЛИ когда существует неограниченное предложение товаров (цифровых товаров), сложность выборки равна $O(1/\epsilon ^{2})$ когда распределения агентов имеют монотонную степень опасности и $O(1/\epsilon ^{3})$ когда распределения агентов регулярны, но не имеют монотонной степени риска.

Ситуация усложняется, когда агенты не являются одинаковыми (ценность каждого агента извлекается из различного регулярного распределения) и предложение товаров ограничено. Когда агенты приходят из $k$ различные распределения, выборочная сложность $1-\epsilon$-аппроксимация оптимального ожидаемого дохода на аукционах по единичным товарам равна:

• максимум $O({k^{10} \over \epsilon ^{7}}\ln ^{3}{k \over \epsilon })$ - с использованием варианта эмпирического аукциона Майерсона.
• по меньшей мере $\Omega ({k \over {\sqrt {\epsilon \ln k}}})$ (для регулярных оценок монотонного уровня риска) и по крайней мере $\Omega ({k \over \epsilon })$ (для произвольных регулярных оценок).

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

$O{\bigg (}({H \over \epsilon })^{2}(D\ln({H \over \epsilon })+\ln({1 \over \delta })){\bigg )}$

где:

• оценки агентов ограничены $[1,H]$,
• псевдо- венчурный размер класса аукционов не превышает $D$,
• требуемый коэффициент аппроксимации равен $1-\epsilon$,
• требуемая вероятность успеха равна $1-\delta$.

В частности, они рассматривают класс простых аукционов, называемый $t$ уровня : аукционы с Аукционы $t$ резервные цены (аукцион Викри с единственной резервной ценой — это аукцион 1 уровня). Они доказывают, что псевдо-VC-размерность этого класса равна $O(nt\ln(nt))$, что немедленно приводит к ограничению их ошибки обобщения и сложности выборки. Они также доказывают пределы ошибки представления этого класса аукционов.

Завидовать

Недостатком механизма случайной выборки является то, что он не свободен от зависти . Например, если оптимальные цены на двух субрынках $M_{L}$ и $M_{R}$ различны, то покупателям на каждом субрынке предлагается разная цена. Другими словами, существует ценовая дискриминация . Это неизбежно в следующем смысле: не существует защищенного от стратегии аукциона с единой ценой, который бы приближался к оптимальной прибыли.

См. также

• Исследование рынка
• Цены
• Консенсусная оценка — альтернативный подход к проектированию механизма без предварительной оценки .