Комбинаторный аукцион

Комбинаторный аукцион является типом рынка смарта , в котором участники могут размещать ставки на комбинации дискретных разнородных элементов, или «пакетов», а не отдельных предметов или непрерывных величин. Эти пакеты также можно назвать лотами, а весь аукцион - многолотовым аукционом . ^[1] Комбинаторные аукционы применимы, когда участники торгов имеют неаддитивные оценки комплектов позиций, то есть они оценивают комбинации позиций больше или меньше суммы их оценок отдельных элементов комбинации.

Простые комбинаторные аукционы использовались в течение многих лет в аукционах по продаже недвижимости , где обычной процедурой является прием заявок на пакеты предметов. Недавно они использовались для грузовых перевозок, автобусных маршрутов, промышленных закупок и распределения радиочастотного спектра для беспроводной связи. В последние годы службы закупок применяли обратные комбинаторные аукционы при закупке товаров и услуг. Это приложение часто называют оптимизацией поиска.

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

Проблема определения победителя может быть сформулирована следующим образом: учитывая набор ставок на комбинаторном аукционе, найти распределение предметов среди участников торгов - включая вероятность того, что аукционист оставит некоторые предметы, - которое максимизирует доход аукциониста. Эта проблема сложна для больших экземпляров. В частности, он NP-сложен , что означает, что предполагается, что не существует алгоритма с полиномиальным временем , который находит оптимальное распределение. Комбинаторную задачу аукциона можно смоделировать как задачу упаковки множества . Поэтому было предложено множество алгоритмов для поиска приближенных решений комбинаторной задачи аукциона. Например, Hsieh (2010) предложил лагранжеву релаксацию подход к комбинаторным задачам обратного аукциона.

Многие из этих аспектов комбинаторных аукционов, включая некоторые примеры из реальной жизни, также обсуждаются в обширной книге под редакцией Крэмтона, Шохама и Стейнберга (2006).

История [ править ]

Комбинаторные аукционы были впервые предложены Rassenti, Smith и Bulfin (1982) для распределения посадочных мест в аэропортах . В их статье представлены многие ключевые идеи комбинаторных аукционов, в том числе математическая программная формулировка задачи аукциониста, связь между проблемой определения победителя и проблемой упаковки наборов , проблема вычислительной сложности, использование методов экспериментальной экономики для проверки комбинаторной аукционов, а также рассмотрение вопросов совместимости стимулов и выявления спроса на комбинаторных аукционах.

Аукцион комбинаторных часов [ править ]

Особым случаем комбинаторного аукциона является аукцион комбинаторных часов (CCA), который сочетает в себе аукцион часов, в ходе которого участники торгов могут предоставить свои подтверждения в ответ на рост цен, с аукционом последующих количественных предложений с запечатанными предложениями, на котором участники торгов подают запечатанные пакетные предложения. . Аукционист использует окончательные ставки для вычисления наилучшего распределения стоимости и выплат Викри . ^{[2] [3]}

См. Также [ править ]

• Оптимизация (математика)
• Комбинаторная теория игр
• Аукцион первой цены

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Питер Крэмтон, Йоав Шохам и Ричард Стейнберг (2006). Комбинаторные аукционы . MIT Press . ISBN 0-262-03342-9 . Предоставленная книга с широким освещением темы. 
• de Vries, S .; Вохра, Р. (2003). «Комбинаторные аукционы: обзор» (PDF) . ИНФОРМС Журнал по вычислительной технике . 15 (3): 284–309. CiteSeerX  10.1.1.23.8046 . DOI : 10.1287 / ijoc.15.3.284.16077 . ISSN  1526-5528 . Немного устаревший, но классический обзор.
• Вазирани, Виджай В .; Нисан, Ноам ; Roughgarden, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.. Предоставленная книга с хорошей вводной главой о комбинаторных аукционах с точки зрения теории информатики; см. главу 11 ^{.: 267–299}
• Рассенти, Стивен Дж .; Смит, Вернон Л .; Булфин, Роберт Л. (1982). «Комбинаторный механизм аукциона для распределения временных интервалов в аэропорту» (PDF) . Белл Журнал экономики . 13 (2): 402–417. DOI : 10.2307 / 3003463 . JSTOR  3003463 . Ранняя работа, популяризировавшая идею комбинаторного аукциона.
• Rothkopf, M .; Pekec, A .; Харстад, Р. (1998). «Комбинаторные аукционы, управляемые с помощью вычислений». Наука управления . 44 (8): 1131–1147. CiteSeerX  10.1.1.723.9753 . DOI : 10.1287 / mnsc.44.8.1131 . Влиятельная ранняя статья по вычислительным соображениям.
• Хаммами, Фарук; Рекик, Моня; Коэльо, Леандро К. (2019). «Точные и эвристические подходы к решению задачи построения заявок на транспортных аукционах с неоднородным флотом». Транспортные исследования Часть E: Обзор логистики и транспорта . 127 : 150–177. DOI : 10.1016 / j.tre.2019.05.009 . Приложение комбинаторных аукционов по закупке транспортных услуг.
• Се, Фу-Шиунг (2010). «Комбинаторный обратный аукцион, основанный на выявлении лагранжевых множителей» (PDF) . Системы поддержки принятия решений . 48 (2): 323–330. DOI : 10.1016 / j.dss.2009.08.009 .
• Шохам, Йоав; Лейтон-Браун, Кевин (2009). Мультиагентные системы: алгоритмические, теоретико-игровые и логические основы . Нью-Йорк: Издательство Кембриджского университета . ISBN 978-0-521-89943-7.Обзор в виде учебника; см. Раздел 11.3. Скачать бесплатно онлайн .