Комбинаторный аукцион — это тип интеллектуального рынка , на котором участники могут делать ставки на комбинации дискретных разнородных предметов или «пакеты», а не на отдельные предметы или непрерывные количества. Эти пакеты также можно называть лотами, а весь аукцион — многолотовым аукционом . [1] Комбинаторные аукционы применяются, когда участники торгов имеют неаддитивные оценки на наборы предметов, то есть они оценивают комбинации предметов больше или меньше суммы оценок отдельных элементов комбинации.
Простые комбинаторные аукционы использовались в течение многих лет на аукционах недвижимости , где обычной процедурой является принятие заявок на пакеты товаров. Недавно они использовались для транспортировки грузовых автомобилей, автобусных маршрутов, промышленных закупок и при распределении радиочастотного спектра для беспроводной связи. В последние годы группы по закупкам применяли обратные комбинаторные аукционы при закупке товаров и услуг. Это применение часто называют оптимизацией снабжения. Поскольку закупки в строительстве часто включают переговоры по нескольким компонентам, комбинаторные обратные аукционы предлагаются для снижения затрат в этой отрасли. [2]
Хотя они позволяют участникам торгов быть более выразительными, комбинаторные аукционы представляют как вычислительные, так и игровые теоретические проблемы по сравнению с традиционными аукционами. Примером вычислительной проблемы является то, как эффективно определить распределение после того, как заявки были представлены аукционисту. Это называется проблемой определения победителя .
Задача определения победителя может быть сформулирована следующим образом: учитывая набор ставок на комбинаторном аукционе, найти распределение предметов среди участников торгов, включая возможность того, что аукционист оставит себе некоторые предметы, которое максимизирует доход аукциониста. Эта задача сложна для больших экземпляров. В частности, она является NP-трудной , что означает, что предполагается, что не существует алгоритма с полиномиальным временем , который находит оптимальное распределение. Задача комбинаторного аукциона может быть смоделирована как задача упаковки множеств . Поэтому было предложено много алгоритмов для поиска приближенных решений для задачи комбинаторного аукциона. Например, Hsieh (2010) предложил подход релаксации Лагранжа для задач комбинаторного обратного аукциона.
Многие из этих аспектов комбинаторных аукционов, включая некоторые примеры из реальной жизни, также обсуждаются в обширной книге под редакцией Крэмтона, Шохама и Стейнберга (2006).
Комбинаторные аукционы были впервые предложены Рассенти, Смитом и Булфином (1982) для распределения посадочных слотов в аэропортах . В их статье было представлено много ключевых идей о комбинаторных аукционах, включая формулировку математического программирования задачи аукциониста, связь между задачей определения победителя и задачей упаковки наборов , проблему вычислительной сложности, использование методов экспериментальной экономики для тестирования комбинаторных аукционов и рассмотрение вопросов совместимости стимулов и выявления спроса в комбинаторных аукционах.
Частным случаем комбинаторного аукциона является комбинаторный аукцион часов (CCA), который объединяет аукцион часов, в ходе которого участники торгов могут предоставить свои подтверждения в ответ на рост цен, с последующим аукционом запечатанных заявок, в котором участники торгов представляют запечатанные пакетные заявки. Аукционист использует окончательные заявки для вычисления наилучшего распределения стоимости и выплат Викри . [3] [4] Было показано, что CCA склонны к возможности повышения стоимости конкурентов. [5] [6]
{{cite journal}}: Цитировать журнал требует |journal=( помощь ){{cite journal}}: CS1 maint: bot: original URL status unknown (link)Ранняя работа, популяризировавшая идею комбинаторного аукциона.