Войти
A комбинаторный аукцион - это тип интеллектуального рынка, на котором участники могут делать ставки на комбинации дискретных разнородных предметов, или «упаковки», а не отдельные предметы или непрерывные количества. Эти пакеты можно также называть лотами, а весь аукцион аукционом с несколькими лотами . Комбинаторные аукционы применимы, когда участники торгов имеют супераддитивные оценки наборов предметов, то есть они оценивают комбинации предметов больше, чем сумму их оценок отдельных элементов комбинации.
Простые комбинаторные аукционы уже много лет используются в аукционах недвижимости, где обычной процедурой является прием заявок на пакеты предметов. Недавно они использовались для грузовых перевозок, автобусных маршрутов, промышленных закупок и распределения радиочастот для беспроводной связи. В последние годы команды по закупкам применяли обратные комбинаторные аукционы при закупке товаров и услуг. Это приложение часто называют оптимизацией поиска.
Хотя комбинаторные аукционы позволяют участникам торгов быть более выразительными, они представляют собой как вычислительные, так и теоретико-игровые проблемы по сравнению с традиционными аукционами. Пример вычислительной проблемы - как эффективно определить распределение после того, как ставки были поданы аукционисту. Это называется проблемой определения победителя.
Проблема определения победителя может быть сформулирована следующим образом: учитывая набор ставок на комбинаторном аукционе, найти распределение предметов среди участников торгов, включая вероятность того, что аукционист оставит некоторые предметы, что максимизирует доход аукциониста. Эта проблема сложна для больших экземпляров. В частности, это NP-жесткий, что означает, что предполагается, что не существует алгоритма с полиномиальным временем, который находит оптимальное распределение. Комбинаторную задачу аукциона можно смоделировать как задачу упаковки множества. Поэтому было предложено множество алгоритмов для поиска приближенных решений комбинаторной задачи аукциона. Например, Hsieh (2010) предложил подход лагранжевой релаксации для комбинаторных задач обратного аукциона.
Многие из этих аспектов комбинаторных аукционов, включая некоторые примеры из реальной жизни, также обсуждаются в обширной книге под редакцией Крамтона, Шохама и Стейнберга (2006).
Комбинаторные аукционы были впервые предложены Rassenti, Smith, and Bulfin (1982) для выделения посадочных мест в аэропорту . В их статье представлены многие ключевые идеи комбинаторных аукционов, в том числе математическая программная формулировка задачи аукциониста, связь между проблемой определения победителя и проблемой упаковки наборов, проблема вычислительной сложности, использование методов из экспериментальной экономики для тестирования комбинаторных аукционов, и рассмотрение вопросов совместимости стимулов и выявления спроса на комбинаторных аукционах.
Особым случаем комбинаторного аукциона является аукцион комбинаторных часов (CCA), который объединяет аукцион часов, во время которого участники торгов могут предоставить свои подтверждения в ответ на рост цен, с последующим аукционом запечатанных предложений, на котором участники торгов подают запечатанные пакетные предложения. Аукционист использует окончательные ставки для расчета наилучшего распределения стоимости и выплат Викри.
| 1 =() Приложение комбинаторных аукционов по закупке транспортных услуг.