Комбинаторный аукцион
Комбинаторный аукцион — это тип умного рынка , на котором участники могут делать ставки на комбинации дискретных разнородных предметов или «пакетов», а не на отдельные предметы или непрерывные количества. Эти пакеты можно также назвать лотами, а весь аукцион — аукционом с несколькими лотами . [1] Комбинаторные аукционы применимы, когда участники торгов имеют неаддитивные оценки пакетов товаров, то есть они оценивают комбинации предметов больше или меньше, чем сумма оценок отдельных элементов комбинации.
Простые комбинаторные аукционы уже много лет используются на аукционах по недвижимости , где обычной процедурой является прием заявок на пакеты предметов. В последнее время они используются для перевозки грузовых автомобилей, автобусных маршрутов, промышленных закупок и для распределения радиоспектра для беспроводной связи. В последние годы группы закупок применили обратные комбинаторные аукционы при закупках товаров и услуг. Это приложение часто называют оптимизацией источников. Поскольку закупки в строительстве часто включают переговоры по нескольким компонентам, комбинаторные обратные аукционы . для снижения затрат в этой отрасли предлагаются [2]
Хотя комбинаторные аукционы позволяют участникам торгов быть более выразительными, они представляют собой как вычислительные, так и теоретико-игровые проблемы по сравнению с традиционными аукционами. Примером вычислительной проблемы является то, как эффективно определить распределение после того, как ставки были отправлены аукционисту. Это называется проблемой определения победителя .
Задачу определения победителя можно сформулировать следующим образом: учитывая набор ставок на комбинаторном аукционе, найти распределение предметов среди участников торгов, включая возможность того, что аукционист сохранит некоторые предметы, что максимизирует доход аукциониста. Эта проблема сложна для больших экземпляров. В частности, это NP-трудно , что означает, что предполагается, что не существует алгоритма с полиномиальным временем , который находит оптимальное распределение. Задачу комбинаторного аукциона можно смоделировать как задачу упаковки множеств . Поэтому было предложено множество алгоритмов для поиска приближенных решений комбинаторной задачи аукциона. Например, Се (2010) предложил подход лагранжевой релаксации для комбинаторных задач обратного аукциона.
Многие из этих аспектов комбинаторных аукционов, включая некоторые примеры из реальной жизни, также обсуждаются в обширной книге под редакцией Крэмтона, Шохама и Стейнберга (2006).
История
[ редактировать ]Комбинаторные аукционы были впервые предложены Рассенти, Смитом и Булфином (1982) для распределения мест для посадки в аэропортах . В их статье представлены многие ключевые идеи о комбинаторных аукционах, включая формулировку математического программирования проблемы аукциониста, связь между проблемой определения победителя и проблемой упаковки множеств , проблему вычислительной сложности, использование методов экспериментальной экономики для проверки комбинаторных аукционов. аукционов, а также рассмотрение вопросов совместимости стимулов и выявления спроса на комбинаторных аукционах.
Комбинаторный аукцион часов
[ редактировать ]Особым случаем комбинаторного аукциона является комбинаторный часовой аукцион (CCA), который сочетает в себе часовой аукцион, в ходе которого участники торгов могут предоставлять свои подтверждения в ответ на рост цен, с последующим аукционом закрытых заявок, на котором участники торгов подают запечатанные пакетные заявки. . Аукционист использует окончательные ставки для расчета наилучшего распределения стоимости и выплат Викри . [3] [4] Было показано, что CCA склонны к повышению затрат конкурентов. [5] [6]
См. также
[ редактировать ]- Оптимизация (математика) — изучение математических алгоритмов решения задач оптимизации.
- Комбинаторная теория игр - раздел теории игр о последовательных играх для двух игроков с совершенной информацией.
- Аукцион первой цены – аукцион, на котором все участники одновременно подают нераскрытые ставки.
Ссылки
[ редактировать ]- ^ Маллен, Трейси; Веллман, Майкл П. (1998). «Менеджер аукциона: рыночное промежуточное программное обеспечение для крупномасштабной электронной коммерции» (PDF) . Семинар USENIX по электронной коммерции .
- ^ Аль-Шакси, Салим (2018). «Комбинаторные обратные аукционы в строительных закупках» . hdl : 1721.1/117609 . Проверено 22 мая 2021 г.
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Бихлер, Мартин; Гури, Джейкоб К. (26 октября 2017 г.). Справочник по проектированию аукционов Spectrum . Издательство Кембриджского университета. ISBN 978-1-107-13534-5 . Проверено 22 октября 2020 г.
- ^ Осубель, Лоуренс М.; Баранов Олег (1 октября 2017 г.). «Практическое руководство по комбинаторному часовому аукциону» . Экономический журнал . 127 (605): Ф334–Ф350. дои : 10.1111/ecoj.12404 . ISSN 0013-0133 . S2CID 26571660 .
- ^ Левин, Дж. и А. Скшипач. 2016. Свойства комбинаторного часового аукциона». American Economic Review 106(9), стр. 2528-255. http://dx.doi.org/10.1257/aer.20141212
- ^ Янссен, М. и Б. Касбергер. 2019. На часах комбинаторного часового аукциона. Теоретическая экономика 14, стр. 1271-1307. https://doi.org/10.3982/TE3203
Дальнейшее чтение
[ редактировать ]- Питер Крэмтон, Йоав Шохам и Ричард Стейнберг (2006). Комбинаторные аукционы . МТИ Пресс . ISBN 0-262-03342-9 . Книга, широко освещающая данную тему.
- де Врис, С.; Вохра, Р. (2003). «Комбинаторные аукционы: обзор» (PDF) . ИНФОРМС Журнал по вычислительной технике . 15 (3): 284–309. CiteSeerX 10.1.1.23.8046 . дои : 10.1287/ijoc.15.3.284.16077 . ISSN 1526-5528 . Немного устаревший, но классический опрос.
- Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0 . . Книга с хорошей вводной главой о комбинаторных аукционах с точки зрения теории информатики; см. главу 11. : 267–299
- Рассенти, Стивен Дж .; Смит, Вернон Л.; Булфин, Роберт Л. (1982). «Механизм комбинаторного аукциона для распределения временных интервалов в аэропорту» (PDF) . Bell Journal of Economics . 13 (2): 402–417. дои : 10.2307/3003463 . JSTOR 3003463 . Архивировано из оригинала 15 января 2009 г. Проверено 22 июня 2023 г.
{{cite journal}}: CS1 maint: bot: статус исходного URL неизвестен ( ссылка ) Ранняя работа, популяризировавшая идею комбинаторного аукциона. - Роткопф, М.; Пекеч, А.; Харстад, Р. (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 . S2CID 182223089 . Применение комбинаторных аукционов при закупке транспортных услуг.
- Се, Фу-Шюн (2010). «Комбинаторный обратный аукцион, основанный на выявлении множителей Лагранжа» (PDF) . Системы поддержки принятия решений . 48 (2): 323–330. дои : 10.1016/j.dss.2009.08.009 .
- Паласиос-Уэрта, Игнасио, Дэвид К. Паркс и Ричард Стейнберг. 2024. « Комбинаторные аукционы на практике ». Журнал экономической литературы , 62 (2): 517–53.
- Шохам, Йоав; Лейтон-Браун, Кевин (2009). Мультиагентные системы: алгоритмические, теоретико-игровые и логические основы . Нью-Йорк: Издательство Кембриджского университета . ISBN 978-0-521-89943-7 . Обзор в форме учебника; см. раздел 11.3. Можно скачать бесплатно в Интернете .