Аукцион отложенного приема
Аукцион с отложенным приемом ( DAA ) — это аукцион , на котором распределение выбирается путем многократного отклонения наименее привлекательных предложений. Это надежный механизм со стратегическими свойствами, которые делают его особенно подходящим для сложных аукционов, таких как аукцион по перераспределению радиочастот . [1] Важным преимуществом DAA перед более известным аукционом VCG является то, что DAA невосприимчив к манипуляциям со стороны коалиций участников торгов, тогда как VCG невосприимчив к манипуляциям только со стороны отдельных участников торгов.
Аукцион с отложенным принятием связан с часовыми аукционами, такими как японский аукцион , поскольку оба они работают путем отклонения ставок, которые не могут выиграть, пока не останутся только те ставки, которые должны выиграть.
Пример
[ редактировать ]Предположим, правительство хочет продать права на вещание в двух регионах: Севере и Юге. За эти права конкурируют три агента:
- Алисе нужны обе области, и она оценивает их (вместе) в 3 миллиона долларов.
- Бобу нужен только Север, и он оценивает его в 1 миллион долларов.
- Карлу нужен только Юг, и он оценивает его в 1 миллион долларов.
Правительство хочет максимизировать социальное благосостояние. В этом случае есть два возможных распределения: либо передать все права Алисе (благосостояние=3), либо передать север Бобу, а юг Карлу (благосостояние=2). Поскольку оценки являются частной информацией агентов, правительству необходимо использовать правдивый механизм , чтобы побудить агентов раскрыть свои истинные оценки. Мы сравниваем два типа правдивых механизмов.
Решение Викри – Кларка – Гроувса
[ редактировать ]Алгоритм Викри-Кларка-Гроувса (VCG) находит социально оптимальное распределение, которое должно передать обе области Алисе. Алисе придется заплатить цену, определяемую внешними эффектами, которые она налагает на других агентов. В данном случае Алиса платит 2 миллиона долларов, так как без нее благосостояние Боба и Карла составило бы 2 миллиона долларов. Боб и Карл ничего не получают и ничего не платят.
Решение для аукциона с отложенным приемом
[ редактировать ]Аукцион с отложенным принятием итеративно отклоняет агент с наименьшей стоимостью, который может быть отклонен, сохраняя при этом оптимальный набор активных агентов. Итак, сначала отвергается Карл, затем Боб. Алиса остается, и ее принимают. Затем она платит пороговую цену, которая представляет собой самую низкую ставку, которую она могла предложить и все равно выиграть. В данном случае пороговая цена Алисы составляет 1 миллион долларов, который она платит.
Оба типа аукционов правдивы: ни один агент не сможет получить выгоду, сообщив другую стоимость. Однако они различаются, когда агенты могут образовывать коалиции . Предположим, что Боб и Карл вместе увеличивают свою ставку до 4 миллионов долларов. Теперь ни Боб, ни Карл по отдельности не имеют никакого влияния на Алису. Таким образом, аукцион VCG примет Боба и Карла, назначив каждому из них цену 0! Напротив, DAA отклонит Алису, затем примет Боба и Карла и назначит каждому из них свою пороговую цену, которая составляет 3 миллиона долларов. Каждый из них теряет по 2 миллиона долларов, следовательно, предложенная стратегия не окупается.
См. также
[ редактировать ]Эффективность аукционов с отсрочкой акцепта была проанализирована Дюттингом и др. в 2014 году. Они сосредоточились на ранцевых аукционах и аукционах для целеустремленных участников. [2] Применение этой идеи в условиях двойного аукциона было описано тогдашними исследователями в области компьютерных наук из Стэнфорда, включая Тима Рафгардена, в том же 2014 году. [3]
Похожие статьи
[ редактировать ]Ссылки
[ редактировать ]- ^ Пол Милгром и Илья Сигал (2014). «Аукционы с отложенным приемом и перераспределение радиоспектра» (PDF) . Проверено 8 августа 2016 г.
- ^ Дюттинг, Пол; Гкацелис, Василис; Рафгарден, Тим (2014). «Проведение аукционов отложенного приема». Материалы пятнадцатой конференции ACM по экономике и вычислениям - EC '14 . п. 187. дои : 10.1145/2600057.2602861 . ISBN 9781450325653 .
- ^ Дюттинг, Пол; Рафгарден, Тим; Талгам-Коэн, Инбал (2014). Модульность и жадность на двойных аукционах . Материалы 15-й конференции по экономике и вычислениям (EC'14). стр. 241–258. дои : 10.1145/2600057.2602854 . ISBN 9781450325653 .