Ранее независимый механизм - Prior-independent mechanism

А Предварительно независимый механизм (PIM) это механизм в котором дизайнер знает, что оценки агентов основаны на некоторых распределение вероятностей, но не знает распределения.

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

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

Разовые аукционы

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

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

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

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

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

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

{ 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}$ .

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

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

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

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

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

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

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

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

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

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]