Теория игр
Теория аукционов: эквивалентность выручки и аукционы с многими лотами
Почему eBay и закрытый аукцион Christie's дают продавцу одинаковую среднюю выручку? И как устроить аукцион так, чтобы выручить максимум - даже иногда намеренно не продавая товар?
- **eBay vs Sotheby's:** аукционы первой и второй цены дают одинаковую ожидаемую выручку при i.i.d. оценках - теорема эквивалентности выручки Викри
- **FCC Spectrum Auction 2017:** комбинаторный аукцион на 84,7 млрд долларов - крупнейший в истории, покупатели ставили на пакеты частот
- **Google AdWords:** резервная цена в аукционе за рекламные места реализует механизм Майерсона для максимизации выручки
- **Приватизация 90-х:** неправильно спроектированные аукционы без резервных цен привели к продаже активов на порядок ниже рыночной стоимости
Предварительные знания
- Равновесие Байеса-Нэша: стратегии при неполной информации
- Порядковые статистики: E[θ_(n-1)] для оценки выручки
- Базовые понятия теории механизмов: IC и IR ограничения
Теорема эквивалентности выручки
eBay и Sotheby's используют принципиально разные форматы аукционов, но теорема эквивалентности выручки 1961 года (Уильям Викри) доказывает: при симметричных оценках из одного распределения аукционы первой и второй цены дают одинаковую ожидаемую выручку продавцу. eBay обработал 1,7 млрд транзакций в 2023 году, опираясь именно на этот результат.
Теорема эквивалентности выручки применима при условии:
Ключевые условия: независимые одинаково распределённые оценки, один и тот же победитель, нулевая утилита для наихудшего типа.
Комбинаторные аукционы
В 2017 году FCC (Федеральная комиссия США по связи) провела аукцион радиочастотного спектра с обратной покупкой: 84,7 млрд долларов транзакций, 70 МГц спектра перераспределено. Это крупнейший в истории комбинаторный аукцион - покупатели ставили на комбинации лотов, а не на каждый по отдельности.
Почему задача определения победителей в комбинаторном аукционе NP-трудна?
Задача определения победителей - NP-трудное обобщение задачи о взвешенном паковании множеств. На практике используют ILP-солверы (CPLEX, Gurobi) или эвристики.
Оптимальный аукцион: теория Майерсона
Майерсон (1981, Нобелевская премия 2007) решил задачу: как спроектировать аукцион, максимизирующий выручку продавца? Ответ: аукцион с резервной ценой, где продавец устанавливает минимальную цену продажи. Резервная цена отсекает покупателей с низкими оценками, увеличивая средний платёж.
Парадокс оптимального аукциона: продавец намеренно не продаёт товар иногда (когда все оценки ниже r*), чтобы извлечь больше выручки в среднем. Это неэффективно с точки зрения общественного благосостояния, но оптимально для продавца.
Для чего в теории Майерсона вводится концепция виртуальной ценности ψ(θ)?
Виртуальная ценность ψ(θ) = θ - (1-F(θ))/f(θ) отражает, что продавец вынужден платить информационную ренту (1-F)/f покупателям с высокими оценками, чтобы они не мимикрировали под менее ценных участников.
Аукционы в экономике и computer science
Теория аукционов объединяет микроэкономику, теорию вычислительной сложности и алгоритмическое проектирование механизмов.
- Алгоритмическая теория игр — Задача определения победителей в комбинаторном аукционе - NP-трудная оптимизационная задача
- Теория механизмов — Аукционы - частный случай механизмов: VCG обобщает Викри на многообъектные ситуации
- Машинное обучение — Auto-bidding в рекламных системах использует RL для стратегического участия в аукционах Майерсона
Итоги
- Теорема эквивалентности выручки: все симметричные IC-аукционы с i.i.d. оценками дают одинаковую E[R]
- Аукцион первой цены: стратегия β(θ) < θ; аукцион второй цены (Викри): доминанта β(θ) = θ
- Комбинаторные аукционы: winner determination - NP-трудная задача, решается ILP-солверами
- Оптимальный аукцион Майерсона: продавать тому, у кого ψ(θ) = θ - (1-F)/f максимальна и ≥ 0
- Резервная цена r*: ψ(r*) = 0; для U[0,1] это r* = 1/2