Теория игр
Теория аукционов
В 1994 году FCC впервые использовала аукцион для продажи радиочастот. Результат: $617 миллионов вместо ожидаемых $100. В 2020 году Пол Милгром и Роберт Уилсон получили Нобель за дизайн этих аукционов. Каждый раз, когда показывается реклама в Google или Instagram - работает аукцион второй цены. Теория аукционов переросла из академической математики в инженерию, двигающую триллионы долларов.
- **Google Ads (GSP):** каждый клик по рекламе - результат молниеносного аукциона Викри для нескольких позиций. $237 млрд выручки Google в год держится на механизме из теории игр
- **FCC Spectrum Auctions:** продажа частот 4G/5G на $100+ млрд. Первый пакет выставлен в 1994 по дизайну Милгрома - часть того, за что ему дали Нобель 2020
- **NFT и криптовалютные аукционы:** Ethereum использует EIP-1559 - механизм fee auction, спроектированный с учётом IC, Revenue Equivalence и динамики базовой комиссии
Предварительные знания
Аукцион первой цены
На аукционе первой цены все участники делают запечатанные заявки. Кто поставил больше - получает лот и платит свою заявку. Казалось бы, просто: ставка равна его субъективной ценности. Но это неверно. Если игрок ставит свою истинную ценность v, его выигрыш = 0 (заплачено ровно столько, сколько получено). Рационально занижать заявку: ставка ниже v позволяет получать профит при победе.
При n симметричных участниках с ценностями v ~ U[0,1] независимо: Оптимальная стратегия: b*(v) = v · (n-1)/n Каждый занижает заявку на 1/n. Чем больше конкурентов - тем меньше занижение. При n → ∞: b* → v (честная заявка почти оптимальна).
Почему занижать заявку оптимально? Это trade-off: более низкая заявка уменьшает вероятность победы, но увеличивает выгоду при победе. В равновесии оба эффекта балансируются. Интуитивно: если бы все ставили честно, я мог бы поставить v - ε и всё равно побеждать при той же ценности соперников.
Аукционы в практике: от рыбного рынка до спектра частот
Первые документально подтверждённые аукционы - Древний Рим: продажа трофеев после войны. Аукцион первой цены (sealed-bid) используется при госзакупках (кто предложит контракт дешевле), продаже недвижимости при банкротстве, нефтяных концессиях. Теоретические основы заложили Вильям Викри (Нобель 1996) и Пол Милгром.
Честная заявка (bid = истинная ценность) - самая безопасная стратегия в любом аукционе
Честная заявка оптимальна только в аукционе ВТОРОЙ цены (Викри). В аукционе первой цены - строго субоптимальна: нужно занижать.
Тип аукциона принципиально меняет оптимальную стратегию. Именно поэтому теория аукционов важна - неправильная стратегия буквально стоит денег.
Почему в аукционе первой цены рациональный участник занижает заявку ниже своей истинной ценности?
Аукцион второй цены (Викри)
В 1961 году Уильям Викри предложил изящный вариант: победитель платит не свою заявку, а вторую по величине. Кажется странным - зачем продавцу это терять? Но магия: теперь честная заявка (bid = истинная ценность) является доминирующей стратегией. Никакого стратегического расчёта - просто ставится сумма, в которую игрок оценивает лот.
Пусть p = вторая заявка (не под контролем агента). Рассмотрим агента с ценностью v: • Если b > p: победа, выигрыш = v - p → Занижение до b' ∈ (p, b]: та же победа, тот же выигрыш → Занижение до b' < p: проигрыш, выигрыш = 0 < v-p (хуже если v > p) • Если b < p: проигрыш → Завышение до b' > p: победа, выигрыш = v - p < 0 (хуже если v < p) Итог: b = v слабо доминирует любую другую стратегию.
Аукцион Викри - прямое воплощение VCG для одного предмета. Трансфер агента = вторая заявка = Clarke tax: сколько «ущерба» победитель нанёс другому участнику, не получив предмет. Доминантная стратегия делает аукцион прост для понимания участниками и устойчив к сложным стратегическим расчётам.
Аукцион Викри всегда лучше аукциона первой цены для продавца
По теореме эквивалентности доходов, обе формы дают одинаковую ожидаемую выручку при симметричных независимых ценностях.
Хотя участники меньше платят в Викри (вторая цена < их заявки), они ставят честно - без занижения. В первой цене они занижают, но платят свою заявку. Математически выручка совпадает.
Почему в аукционе второй цены (Викри) честная заявка является доминирующей стратегией?
Теорема эквивалентности доходов
Вот парадокс: участник первой цены занижает заявку, участник второй цены - нет. Кажется, продавцу выгоднее первая цена. Но это не так. Теорема Викри-Майерсона (Revenue Equivalence Theorem) утверждает: при симметричных, независимых, приватных ценностях все «стандартные» аукционы дают одинаковую ожидаемую выручку.
При условиях: n симметричных участников, независимые приватные ценности v ~ F(v), любые два аукционных механизма, удовлетворяющих: 1. Тот же победитель (максимальная ценность) 2. Тот же ожидаемый выигрыш при минимальном типе ...дают одинаковую ожидаемую выручку продавцу. Следствие: 1-я цена, 2-я цена, аукцион с нарастанием (English), аукцион с падением (Dutch) - все эквивалентны!
| Условие | Revenue Equivalence | Пример |
|---|---|---|
| Симм. независимые типы | Выполняется | 4 компании на аукционе частот |
| Асимметричные типы | Нарушается | Сильный vs слабый участник |
| Affiliated values | Нарушается | Нефтяные права (общая стоимость) |
| Risk-averse участники | Нарушается | 1-я цена > 2-я цена по выручке |
Revenue Equivalence - мощный теоретический результат, но он разрушается в реальных условиях: при аффилированных ценностях (победа одного говорит что-то о ценностях других), при асимметрии участников, при риск-авёрсности. Именно поэтому дизайн реальных аукционов - не просто выбор «первая vs вторая цена», а сложная инженерная задача.
Аукцион второй цены всегда приносит меньше выручки продавцу, чем первой цены
По Revenue Equivalence при стандартных условиях обе формы дают одинаковую ожидаемую выручку. Участники компенсируют разницу через стратегию.
В 1-й цене участники занижают заявки ровно настолько, чтобы выручка совпала с 2-й ценой. Стратегическое поведение полностью уравновешивает разницу форматов - выручка одинакова.
Теорема Revenue Equivalence утверждает, что различные форматы аукционов дают одинаковую ожидаемую выручку при условии:
Оптимальные аукционы и реальные приложения
Revenue Equivalence говорит, что стандартные аукционы равны по выручке. Но ни один из них не максимизирует выручку продавца! Майерсон показал: оптимальный аукцион использует резервную цену r* и «виртуальные ценности» - и приносит строго больше, чем аукцион Викри без резерва. Продавец намеренно создаёт неэффективность, чтобы извлечь больше ренты.
Алгоритм: 1. Вычисли виртуальные ценности ψᵢ(vᵢ) = vᵢ - (1-Fᵢ(vᵢ))/fᵢ(vᵢ) 2. Продай тому, у кого max ψᵢ > 0 (если такой есть) 3. Установи платёж = минимальная заявка, при которой агент всё ещё побеждает Для U[0,1], n=1: r* = 0.5, ожидаемая выручка = 0.25 (vs 0 без резерва).
| Формат аукциона | Используется в | Ключевое свойство |
|---|---|---|
| Английский (открытый рост) | Sotheby's, eBay | Эффективный, много информации |
| Голландский (открытое падение) | Цветы, рыба | Быстрый, агрессивный |
| Первая цена (запечатанный) | Госзакупки, нефть | Стратегическое занижение |
| Вторая цена (Викри) | Google Ads (основа GSP) | IC, простота стратегии |
| Майерсона с резервом | Spectrum auctions | Максимальная выручка |
Google использует GSP (Generalized Second Price) для рекламы. Это расширение аукциона второй цены на несколько позиций (вверху страницы, внизу, и т.д.). Не является строго IC, но в равновесии даёт похожие выигрыши на VCG. Ключевое: рекламодатель платит минимальную заявку, позволяющую сохранить свою позицию - аналог второй цены.
Оптимальный аукцион всегда продаёт товар тому, кто ценит его больше всего
Оптимальный аукцион может намеренно НЕ продавать или продавать не тому, у кого максимальная ценность - если виртуальная ценность максимального участника отрицательна.
Максимальная выручка и максимальная эффективность - разные цели. Оптимальный аукцион жертвует эффективностью ради большей выручки через информационную ренту.
Зачем в оптимальном аукционе Майерсона устанавливается резервная цена?
Ключевые идеи
- **Аукцион 1-й цены:** стратегическое занижение b* = v·(n-1)/n в равновесии Байеса-Нэша
- **Аукцион Викри (2-я цена):** честная заявка - доминирующая стратегия; VCG для одного предмета
- **Revenue Equivalence:** при стандартных условиях все форматы дают одинаковую ожидаемую выручку
- **Оптимальный аукцион Майерсона:** резервная цена r* и виртуальные ценности - максимум выручки продавца
Связанные темы
Теория аукционов - прикладная вершина mechanism design:
- Mechanism Design — Аукцион - частный случай механизма; IC и Revelation Principle применяются напрямую
- Игры в развёрнутой форме — Английский аукцион - sequential game; анализируется через backward induction
- Game Theory в Tech: pricing, markets — GSP, surge pricing, marketplace auctions - аукционная теория в продуктах
Вопросы для размышления
- eBay использует английский аукцион с функцией автоставки. Как это взаимодействует с аукционом Викри? Является ли «поставить максимальную сумму» доминирующей стратегией на eBay?
- В рекламных аукционах Google качество объявления (Quality Score) влияет на позицию и цену. Как это меняет теоретические свойства аукциона - IC, Revenue Equivalence?
- NFT-аукционы часто используют формат «самый высокий предлагает». Какие проблемы с ценообразованием и sniping (ставка в последнюю секунду) это создаёт? Как улучшить дизайн?