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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\ Displaystyle г (S): = \ сумма _ {я \ in S} г (я)}$

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

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

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

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

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

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

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

${\ Displaystyle О (п ^ {2} К ^ {2})}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где:

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

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

Завидовать

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

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

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

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