Комбинаторный аукцион - Combinatorial auction
А комбинаторный аукцион это тип умный рынок в котором участники могут делать ставки на комбинации дискретных разнородных товаров или «пакетов», а не на отдельные товары или непрерывные количества. Эти пакеты также можно назвать лотами, а весь аукцион - многолотовый аукцион.[1] Комбинаторные аукционы применимы, когда участники торгов супераддитив оценки наборов предметов, то есть они оценивают комбинации предметов больше, чем сумму их оценок отдельных элементов комбинации.
Простой комбинаторный аукционы долгие годы использовались в аукционы недвижимости, где обычной процедурой является прием заявок на пакеты товаров. Недавно они использовались для грузовых перевозок, автобусных маршрутов, промышленных закупок и распределение радиоспектра для беспроводной связи. В последние годы команды по закупкам применяли обратные комбинаторные аукционы при закупке товаров и услуг. Это приложение часто называют оптимизацией поиска.
Хотя они позволяют участникам торгов быть более выразительными, комбинаторные аукционы представляют собой как вычислительные, так и теоретико-игровые проблемы по сравнению с традиционными аукционами. Пример вычислительной проблемы - как эффективно определить распределение после того, как ставки были поданы аукционисту. Это называется проблемой определения победителя.
Проблема определения победителя может быть сформулирована следующим образом: учитывая набор ставок на комбинаторном аукционе, найти распределение предметов среди участников торгов - включая вероятность того, что аукционист оставит некоторые предметы, - которое максимизирует доход аукциониста. Эта проблема сложна для больших экземпляров. В частности, это NP-жесткий, что означает, что предполагается, что не существует полиномиальное время алгоритм, который находит оптимальное распределение. Комбинаторную задачу аукциона можно смоделировать как набор упаковки проблема. Поэтому было предложено множество алгоритмов для поиска приближенных решений комбинаторной задачи аукциона. Например, Hsieh (2010) предложил Лагранжева релаксация подход к комбинаторным задачам обратного аукциона.
Многие из этих аспектов комбинаторных аукционов, включая некоторые примеры из реальной жизни, также обсуждаются в обширной книге под редакцией Крэмтона, Шохама и Стейнберга (2006).
История
Комбинаторные аукционы впервые были предложены Рассенти, Смит и Булфин (1982) для размещения аэропорта посадочные места. В их статье были представлены многие ключевые идеи комбинаторных аукционов, в том числе математическая программная формулировка задачи аукциониста, связь между проблемой определения победителя и набор-упаковка проблема, проблема вычислительной сложности, использование методов экспериментальной экономики для тестирования комбинаторных аукционов, и рассмотрение вопросов совместимость стимулов и выявление спроса на комбинаторных аукционах.
Комбинаторные часы Аукцион
Частным случаем комбинаторного аукциона является комбинаторные часы аукцион (CCA), который объединяет тактовый аукцион, во время которого участники торгов могут предоставить свои подтверждения в ответ на рост цен, с последующим аукционом закрытых заявок, на котором участники торгов подают запечатанные пакетные заявки. Аукционист использует окончательные ставки для вычисления наилучшего распределения стоимости и Платежи по Викри.[2][3]
Смотрите также
использованная литература
- ^ Маллен, Трейси; Веллман, Майкл П. (1998). "Менеджер аукциона: рыночное промежуточное ПО для крупномасштабной электронной торговли" (PDF). Семинар USENIX по электронной коммерции.
- ^ Бихлер, Мартин; Гори, Джейкоб К. (26 октября 2017 г.). Справочник по дизайну аукционов Spectrum. Издательство Кембриджского университета. ISBN 978-1-107-13534-5. Получено 22 октября 2020.
- ^ Ausubel, Lawrence M .; Баранов, Олег (1 октября 2017 г.). «Практическое руководство по аукциону комбинаторных часов». Экономический журнал. 127 (605): F334 – F350. Дои:10.1111 / ecoj.12404. ISSN 0013-0133. S2CID 26571660.
дальнейшее чтение
- Питер Крэмтон, Йоав Шохам и Ричард Стейнберг (2006). Комбинаторные аукционы. MIT Press. ISBN 0-262-03342-9. Предоставленная книга с широким освещением темы.
- de Vries, S .; Вохра, Р. (2003). «Комбинаторные аукционы: обзор» (PDF). ИНФОРМС Журнал по вычислительной технике. 15 (3): 284–309. CiteSeerX 10.1.1.23.8046. Дои: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. Дои:10.2307/3003463. JSTOR 3003463. Ранняя работа, популяризировавшая идею комбинаторного аукциона.
- Rothkopf, M .; Pekec, A .; Харстад, Р. (1998). «Комбинаторные аукционы, управляемые с помощью вычислений». Наука управления. 44 (8): 1131–1147. CiteSeerX 10.1.1.723.9753. Дои:10.1287 / mnsc.44.8.1131. Влиятельная ранняя статья по вычислительным соображениям.
- Хаммами, Фарук; Рекик, Моня; Коэльо, Леандро К. (2019). «Точные и эвристические подходы к решению задачи построения заявок на транспортных аукционах с неоднородным флотом». Транспортные исследования, часть e: Обзор логистики и перевозок. 127: 150–177. Дои:10.1016 / j.tre.2019.05.009. Приложение комбинаторных аукционов по закупке транспортных услуг.
- Се, Фу-Шиунг (2010). «Комбинаторный обратный аукцион, основанный на выявлении лагранжевых множителей» (PDF). Системы поддержки принятия решений. 48 (2): 323–330. Дои:10.1016 / j.dss.2009.08.009.
- Шохам, Йоав; Лейтон-Браун, Кевин (2009). Мультиагентные системы: алгоритмические, теоретико-игровые и логические основы. Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-89943-7. Обзор в виде учебника; см. Раздел 11.3. Скачать бесплатно онлайн.