Аукцион с отложенным принятием ( DAA ) — это аукцион , в котором распределение выбирается путем многократного отклонения наименее привлекательных заявок. Это честный механизм со стратегическими свойствами, которые делают его особенно подходящим для сложных аукционов, таких как аукцион по перераспределению радиочастотного спектра . [1] Важное преимущество DAA перед более известным аукционом VCG заключается в том, что DAA невосприимчив к манипуляциям со стороны коалиций участников торгов, в то время как VCG невосприимчив к манипуляциям только со стороны отдельных участников торгов.
Аукцион с отложенным принятием торга связан с часовыми аукционами, такими как японский аукцион , поскольку оба они работают по принципу отклонения ставок, которые не могут выиграть, до тех пор, пока не останутся только ставки, которые должны выиграть.
Предположим, что правительство хочет продать права на вещание в двух регионах: Север и Юг. За эти права конкурируют три агента:
Правительство хочет максимизировать общественное благосостояние. В этом случае есть два возможных распределения: либо отдать все права Алисе (благосостояние = 3), либо отдать Север Бобу, а Юг Карлу (благосостояние = 2). Поскольку оценки являются частной информацией агентов, правительству необходимо использовать правдивый механизм , чтобы побудить агентов раскрыть свои истинные оценки. Мы сравниваем два типа правдивых механизмов.
Алгоритм Викри-Кларка-Гроувса (VCG) находит социально-оптимальное распределение, которое заключается в том, чтобы отдать обе области Алисе. Алисе следует заплатить цену, определяемую внешними эффектами, которые она налагает на других агентов. В этом случае Алиса платит 2 млн долларов, поскольку без нее благосостояние Боба и Карла составило бы 2 млн долларов. Боб и Карл ничего не получают и ничего не платят.
Аукцион с отложенным принятием итеративно отклоняет самого низкооцененного агента, которого можно отклонить, сохраняя при этом оптимальный набор активных агентов. Итак, Карл отклоняется первым, затем Боб. Алиса остается, и ее принимают. Затем она платит пороговую цену, которая является значением самой низкой ставки, которую она могла бы сделать и все равно выиграть. В этом случае пороговая цена Алисы составляет 1 млн долларов, которую она платит.
Оба типа аукционов являются правдивыми — ни один агент не может выиграть, сообщая другую стоимость. Однако они отличаются, когда агенты могут формировать коалиции . Предположим, что Боб и Карл вместе увеличивают свою ставку до 4 млн долларов. Теперь ни Боб, ни Карл по отдельности не оказывают никакого влияния на Алису. Поэтому аукцион VCG примет Боба и Карла, взимая с каждого из них цену 0! Напротив, DAA отклонит Алису, затем примет Боба и Карла и взимает с каждого из них его пороговую цену, которая составляет 3 млн долларов. Каждый из них теряет 2 млн долларов, поэтому предпринятая стратегия не окупается.
Эффективность аукционов с отложенным принятием была проанализирована Дюттингом и соавторами в 2014 году. Они сосредоточились на аукционах с рюкзаками и на аукционах для однонаправленных участников торгов. [2] Применение этой идеи в условиях двойного аукциона было изложено тогдашними исследователями в области компьютерных наук из Стэнфорда, включая Тима Рафгардена, в 2014 году в том же году. [3]