Предварительно независимый механизм

Приор-независимый механизм (ПИМ) является механизмом , в котором дизайнер знает , что оценки агентов взяты из некоторого распределения вероятностей , но не знает , распределения.

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

PIM обычно включает процесс случайной выборки . Продавец выбирает некоторые оценки из неизвестного распределения и на основе этих выборок строит аукцион, который приносит приблизительно оптимальную прибыль. Главный вопрос исследования при разработке PIM: какова типовая сложность механизма? То есть, сколько агентов необходимо отобрать, чтобы достичь разумного приближения к оптимальному благосостоянию?

Индивидуальные аукционы

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

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

Ситуация усложняется, когда агенты не являются активными (стоимость каждого агента определяется различным регулярным распределением), а количество товаров ограничено. Когда агенты происходят из разных распределений, примерная сложность аппроксимации оптимального ожидаемого дохода на аукционах по отдельным позициям составляет: ^[2] $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 })$

Однопараметрические агенты

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

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

куда:

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

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

Многопараметрические агенты

Деванур и др. Изучают рынок с различными типами товаров и агентами единичного спроса . ^[5]

Чавла и др. Изучают PIM для решения проблемы минимизации срока изготовления . ^[6]

Хсу и др. Изучают рынок с различными типами товаров. Поставки фиксированы. Покупатели могут покупать наборы предметов и иметь разные оценки наборов. Они доказывают, что если покупатели отбираются независимо от некоторого неизвестного распределения, вычисляется оптимальный вектор цен, а затем этот вектор цен применяется к новой выборке покупателей, то социальное благосостояние приблизительно оптимально. Коэффициент конкуренции, вытекающий из их теоремы 6.3, с вероятностью не менее $n$ $n$ $1-\delta$

1-O{\bigg (}{\sqrt {h^{3}n^{0.5}m^{4}\ln ^{2}m\ln ^{2}{1 \over \delta } \over {\text{OptimalWelfare}}}}{\bigg )}

. ^[7]

Альтернативы

Предварительно независимые механизмы (PIM) следует противопоставить двум другим типам механизмов:

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

С точки зрения разработчика, проще всего будет BOM, затем PIM, затем PFM. Гарантии приближения BOM и PIM ожидаются, а гарантии PFM - в худшем случае.

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

использованная литература

^ Дангватнотай, Пирапонг; Roughgarden, Тим; Ян, Цици (2015). «Максимизация доходов с одного образца» . Игры и экономическое поведение . 91 : 318–333. DOI : 10.1016 / j.geb.2014.03.011 .
^ ^a ^b Коул, Ричард; Roughgarden, Тим (2014). «Примерная сложность максимизации дохода». Материалы 46-го ежегодного симпозиума ACM по теории вычислений - STOC '14 . п. 243. arXiv : 1502.00963 . DOI : 10.1145 / 2591796.2591867 . ISBN 9781450327107.
^ Хартлайн, Джейсон Д .; Roughgarden, Тим (2009). «Простые механизмы против оптимальных». Материалы десятой конференции ACM по электронной коммерции - EC '09 . п. 225. DOI : 10,1145 / 1566374,1566407 . ISBN 9781605584584.
^ О псевдоразмерности почти оптимальных аукционов . НИПС. 2015. arXiv : 1506.03684 . Bibcode : 2015arXiv150603684M .
^ Деванур, Нихил; Хартлайн, Джейсон; Карлин, Анна; Нгуен, Тач (2011). «Дизайн априорно-независимого многопараметрического механизма». Интернет и сетевая экономика . Конспект лекций по информатике. 7090 . п. 122. DOI : 10.1007 / 978-3-642-25510-6_11 . ISBN 978-3-642-25509-0.
^ Чавла, Шучи ; Хартлайн, Джейсон Д .; Малек, Дэвид; Сиван, Баласубраманян (2013). «Предварительно независимые механизмы планирования». Материалы 45-го ежегодного симпозиума ACM по теории вычислений - STOC '13 . п. 51. arXiv : 1305.0597 . DOI : 10.1145 / 2488608.2488616 . ISBN 9781450320290.
^ Сюй, Джастин; Моргенштерн, Джейми; Роджерс, Райан; Рот, Аарон; Вохра, Ракеш (2016). «Цены координируют рынки?». Материалы 48-го ежегодного симпозиума ACM SIGACT по теории вычислений - STOC 2016 . п. 440. arXiv : 1511.00925 . DOI : 10.1145 / 2897518.2897559 . ISBN 9781450341325.

[dhang15-1] Дангватнотай, Пирапонг; Roughgarden, Тим; Ян, Цици (2015). «Максимизация доходов с одного образца» . Игры и экономическое поведение . 91 : 318–333. DOI : 10.1016 / j.geb.2014.03.011 .

[cr15-2] Коул, Ричард; Roughgarden, Тим (2014). «Примерная сложность максимизации дохода». Материалы 46-го ежегодного симпозиума ACM по теории вычислений - STOC '14 . п. 243. arXiv : 1502.00963 . DOI : 10.1145 / 2591796.2591867 . ISBN 9781450327107.

[hr09-3] Хартлайн, Джейсон Д .; Roughgarden, Тим (2009). «Простые механизмы против оптимальных». Материалы десятой конференции ACM по электронной коммерции - EC '09 . п. 225. DOI : 10,1145 / 1566374,1566407 . ISBN 9781605584584.

[4] О псевдоразмерности почти оптимальных аукционов . НИПС. 2015. arXiv : 1506.03684 . Bibcode : 2015arXiv150603684M .

[dhkn11-5] Деванур, Нихил; Хартлайн, Джейсон; Карлин, Анна; Нгуен, Тач (2011). «Дизайн априорно-независимого многопараметрического механизма». Интернет и сетевая экономика . Конспект лекций по информатике. 7090 . п. 122. DOI : 10.1007 / 978-3-642-25510-6_11 . ISBN 978-3-642-25509-0.

[6] Чавла, Шучи ; Хартлайн, Джейсон Д .; Малек, Дэвид; Сиван, Баласубраманян (2013). «Предварительно независимые механизмы планирования». Материалы 45-го ежегодного симпозиума ACM по теории вычислений - STOC '13 . п. 51. arXiv : 1305.0597 . DOI : 10.1145 / 2488608.2488616 . ISBN 9781450320290.

[hmrrv16-7] Сюй, Джастин; Моргенштерн, Джейми; Роджерс, Райан; Рот, Аарон; Вохра, Ракеш (2016). «Цены координируют рынки?». Материалы 48-го ежегодного симпозиума ACM SIGACT по теории вычислений - STOC 2016 . п. 440. arXiv : 1511.00925 . DOI : 10.1145 / 2897518.2897559 . ISBN 9781450341325.

[1]