Механизм-дизайн: проектирование правил игры

«Инженерная» ветвь теории игр

Классическая теория игр анализирует существующие правила: каков равновесный исход? Механизм-дизайн решает обратную задачу: какие правила ввести, чтобы рациональное поведение игроков привело к желаемому социальному результату?

Аналогия: классическая теория игр — физика (описывает мир), механизм-дизайн — инженерия (проектирует мир). Леонид Гурвич, Эрик Маскин и Роджер Майерсон получили Нобелевскую премию 2007 года за основополагающие вклады.

Примеры задач механизм-дизайна: как продать государственные частоты телевидения с максимальной выручкой? Как организовать торги на электрическом рынке для минимизации затрат? Как распределить ресурсы здравоохранения «справедливо» при частной информации пациентов?

Проблема: частная информация

Ключевой барьер — агенты имеют частную информацию (тип θᵢ), которую планировщик не наблюдает: готовность платить, производственная функция, склонность к риску. Агенты могут лгать о своём типе ради выгоды.

Механизм M = (S, g): пространство сообщений S = S₁ × ... × Sₙ и функция исхода g: S → X × ℝⁿ (решение + платежи). Агент стратегически выбирает сообщение sᵢ, необязательно правдивое.

Принцип откровения

Прямой механизм: Каждый агент сообщает свой тип θ̂ᵢ (возможно, ложный). Функция исхода g(θ̂) = (x(θ̂), t(θ̂)).

Инцентивная совместимость (DSIC): Правдивость θ̂ᵢ = θᵢ — доминантная стратегия каждого агента при любых типах соперников. Формально: uᵢ(θᵢ, g(θᵢ, θ₋ᵢ)) ≥ uᵢ(θᵢ, g(θ̂ᵢ, θ₋ᵢ)) для всех θᵢ, θ̂ᵢ ≠ θᵢ, θ₋ᵢ.

Теорема откровения: Для любого механизма M, реализующего исход f в (байесовском или доминантном) равновесии, существует эквивалентный прямой механизм, реализующий тот же исход при правдивых стратегиях.

Следствие: без ограничения общности можно рассматривать только прямые DSIC-механизмы. Это колоссальное упрощение: вместо всех возможных правил достаточно анализировать правдивые прямые механизмы.

VCG-механизм

VCG (Vickrey–Clarke–Groves) — канонический пример DSIC-механизма для задачи эффективного распределения.

Правило выбора: x*(θ) = argmax_x Σᵢ vᵢ(x, θᵢ) — выбор, максимизирующий суммарную ценность.

Платёж Кларка: tᵢ(θ) = Σⱼ≠ᵢ vⱼ(x*(θ), θⱼ) − Σⱼ≠ᵢ vⱼ(x*₋ᵢ(θ₋ᵢ), θⱼ)

Где x*₋ᵢ — оптимальный исход без агента i. Платёж = «сколько остальные выиграли от присутствия i».

Числовой пример — аукцион двух слотов: Слоты с кликабельностью α₁ = 1.0 и α₂ = 0.5. Три рекламодателя с оценками θ₁ = 10, θ₂ = 7, θ₃ = 4.

VCG-распределение: слот 1 → агент 1 (оценка 10), слот 2 → агент 2 (оценка 7).

Платёж агента 1: Σⱼ≠₁ vⱼ при x* = 7×0.5+4×0 = 3.5. Без агента 1 оптимально: слот 1 → 2 (7), слот 2 → 3 (4×0.5=2) → Σⱼ≠₁ = 9. t₁ = 3.5 − 9 = −5.5 (агент 1 платит 5.5).

Платёж агента 2: vⱼ≠₂ при x* = 10×1 = 10. Без агента 2: слот 1 → 1, слот 2 → 3 → vⱼ≠₂ = 10+4×0.5=12. t₂ = 10 − 12 = −2 (платит 2).

Свойства VCG: DSIC (правдивость оптимальна), эффективность. Недостаток: не всегда бюджетно-сбалансирован (сумма платежей может быть отрицательной — планировщику нужны дополнительные средства).

Теорема Майерсона–Сэттертвейта

Теорема (1983): При двустороннем рынке с частными оценками продавца (s) и покупателя (b), s ~ Fₛ, b ~ F_b, не существует механизма, одновременно являющегося IC, IR (индивидуально рациональным), EF (эффективным) и BB (бюджетно-сбалансированным).

Смысл: фундаментальная неизбежность потерь — часть взаимовыгодных сделок не реализуется при частной информации. Это нормативный «закон» асимметрии информации.

Приложение: переговоры о слиянии компаний, продажа земли, контракты в здравоохранении — везде часть «размытой» ценности теряется из-за асимметрии информации.

Аукционы спектра — теория в действии

В 1994 году FCC (США) впервые провела аукционы частот спектра вместо их административного распределения. Милгром, Уилсон и Мак-Афи разработали одновременный восходящий аукцион (SAA): все лоты торгуются параллельно, раунд за раундом. Это позволяет участникам приобретать взаимодополняющие лоты и избегать «проблемы экспозиции» (когда ценность пакета выше суммы отдельных лотов). Правительство США выручило более $100 млрд на аукционах спектра — прямой результат применения теории механизм-дизайна.

Механизм VCG в интернет-рекламе и аукционах спектра

VCG-механизм лежит в основе крупнейших аукционных рынков мира. Аукционы частотного спектра, проводимые Федеральной комиссией США по связи (FCC) с 1994 года, распределяют права на использование радиочастот среди телекоммуникационных компаний через комбинаторные аукционы, теоретически обоснованные VCG. С 1994 по 2015 год США выручили более 100 миллиардов долларов в таких аукционах. Google AdWords использует вариант VCG — обобщённый аукцион второй цены (GSP) — для назначения позиций рекламы: рекламодатели торгуются за позиции и платят цену следующего игрока, а не собственную ставку. Несмотря на то что GSP не является VCG строго, его устойчивые равновесия совпадают с VCG-исходами при определённых условиях. Facebook Ads аналогично использует аукционный механизм с второй ценой. Комбинаторные аукционы для продажи пакетов авиарейсов, прав добычи газа и контрактов на поставку электроэнергии требуют VCG-механизма для достижения эффективного размещения при дополнительности или заменимости лотов. Репликатор на миллиард долларов: правильный дизайн аукционного механизма приносит государству и обществу существенно больший доход и эффективность, чем неоптимальные альтернативы.

Задание: (а) Спроектируйте VCG-механизм для аукциона одного объекта (агенты с оценками θᵢ ~ U[0,1]). Покажите эквивалентность аукциону второй цены. (б) Почему в VCG-механизме правдивость — доминантная стратегия (формально, через IC-условие)? (в) Назовите реальный пример, где VCG применяется на практике.