Mechanism Design

Как FCC продаёт радиочастоты на $45 миллиардов? Как Google решает, какую рекламу показать и по какой цене? Как распределить дефицитные вакцины между регионами? Всё это задачи mechanism design - «инженерной» стороны теории игр. Не анализ игр, а их проектирование. Нобель 2007 и 2020 годов - доказательство, что это одна из самых практически важных областей математики.

• **Google Ads (GSP):** каждый раз, когда пользователь ищет что-то в Google - механизм аукциона определяет, кто показывается и по какой цене. Это mechanism design в реальном времени, миллиарды раз в день
• **FCC spectrum auctions:** продажа частот телефонным компаниям - аукцион, спроектированный с нуля теоретиками игр. Милгром и Уилсон получили Нобель за этот дизайн в 2020
• **Matching markets:** алгоритм Гейл-Шепли распределяет ординаторов по больницам, детей по школам, органы донора по реципиентам - IC-механизм, изменивший медицину

Предварительные знания

• Cooperative Games

Incentive Compatibility

Налоговая служба хочет знать реальный доход граждан, чтобы справедливо собирать налоги. Больница хочет знать, насколько срочно пациенту нужна операция, чтобы правильно расставить приоритеты. Проблема: люди врут, если это выгодно. Mechanism design - это «игра наоборот»: вместо анализа данной игры, мы проектируем правила так, чтобы рациональным агентам было выгодно говорить правду и действовать нужным образом.

Механизм (d, t) - правило, отображающее заявки агентов в решение d и трансферы t. IC (доминантно): агенту выгодно сообщать истинный тип θᵢ независимо от действий других: uᵢ(d(θᵢ, θ₋ᵢ), tᵢ(θᵢ, θ₋ᵢ), θᵢ) ≥ uᵢ(d(θᵢ', θ₋ᵢ), tᵢ(θᵢ', θ₋ᵢ), θᵢ) для всех θᵢ', θ₋ᵢ IC (байесовский): выгодно в ожидании.

Incentive compatibility - центральный принцип mechanism design. Цель проектировщика: создать правила, при которых честное поведение - лучшее для каждого агента. Это устраняет нужду в мониторинге и принуждении: агенты сами заинтересованы говорить правду.

Revelation Principle

Допустим, проектируется механизм. Агенты могут делать сложные стратегические заявки, имитировать разные типы, блефовать. Задача кажется невозможной: нужно учесть все возможные стратегии. Принцип откровения (Revelation Principle) резко упрощает: достаточно рассматривать только прямые механизмы, где каждый агент сообщает свой тип напрямую.

Для любого механизма M с равновесием σ* существует прямой IC-механизм M', дающий тот же результат: • Агенты сообщают свои типы θᵢ напрямую • Механизм вычисляет то, что они получили бы в равновесии M Следствие: при поиске оптимальных механизмов достаточно рассматривать класс прямых IC-механизмов.

Revelation Principle - мощный аналитический инструмент. Он говорит: не нужно изучать все возможные сложные механизмы - достаточно найти оптимальный прямой IC-механизм. Это радикально сужает пространство поиска. На практике именно это позволило Майерсону вывести оптимальный аукционный дизайн.

VCG Механизм

Город хочет построить общественный парк. Разные жители ценят его по-разному. Как выяснить суммарную ценность и справедливо разделить расходы? VCG-механизм (Vickrey-Clarke-Groves) - элегантное решение: каждый агент платит ровно тот внешний ущерб, который он наносит другим своим участием. Это делает правдивость строго доминирующей стратегией.

Выбираем решение d*, максимизирующее суммарный заявленный выигрыш: d* = argmax_d Σᵢ vᵢ(d, θᵢ) Трансфер агента i: tᵢ = Σⱼ≠ᵢ vⱼ(d*, θⱼ) - max_d Σⱼ≠ᵢ vⱼ(d, θⱼ) = (выигрыш других при наличии i) - (их максимальный выигрыш без i) Агент i платит Clarke tax - внешний ущерб, который его присутствие наносит другим.

VCG - теоретически элегантен: IC + эффективность. Но на практике у него проблемы: бюджетный дефицит (суммарные платежи могут быть отрицательными), уязвимость к коллюзии между агентами, вычислительная сложность при большом числе альтернатив. Именно поэтому на практике чаще используют упрощённые варианты - аукционы Викри.

Auction Design как Mechanism Design

Аукционный дизайн - самое практичное приложение mechanism design. Продавец хочет максимизировать выручку. Покупатели знают свои ценности, продавец - нет. Как назначить правила торгов, чтобы агенты честно раскрывали информацию и продавец получал максимальный доход? Майерсон (1981) ответил полностью.

При независимых симметричных распределениях ценностей оптимальный аукцион: 1. Вычисляет «виртуальные ценности»: ψ(v) = v - (1-F(v))/f(v) 2. Присваивает товар тому, у кого max ψ(v) > 0 3. Устанавливает резервную цену r*: ψ(r*) = 0 Может быть реализован как аукцион второй цены с оптимальной резервной ценой.

Ключевые идеи

• **Mechanism Design - «игра наоборот»:** проектируем правила так, чтобы рациональным агентам было выгодно действовать нужным образом
• **Incentive Compatibility:** честность - доминирующая стратегия. Не нужен мониторинг - агентам самим выгодно раскрывать тип
• **Revelation Principle:** достаточно анализировать прямые IC-механизмы - упрощает проектирование
• **VCG:** единственный механизм, одновременно IC и эффективный. На практике GSP и аукцион Викри с резервом

Связанные темы

Mechanism design - прикладная ветвь теории игр, связанная с аукционами и платформами:

• Теория аукционов — Аукционы - главное приложение mechanism design; теорема Майерсона об оптимальных аукционах
• Игры в развёрнутой форме — Механизмы часто sequential - revelation принцип работает через backward induction
• Game Theory в Tech: pricing, markets — Google Ads, Uber surge pricing, marketplace design - mechanism design в продуктах

Вопросы для размышления

• Facebook и Google знают предпочтения пользователя лучше, чем он сам. Как это меняет incentive compatibility - можно ли проектировать механизмы, когда агент не знает свой собственный тип?
• Что произойдёт, если несколько агентов коллюдируют в VCG механизме - докладывают согласованно ложные типы? Как разработчики пытаются защититься от коллюзии?
• Uber использует surge pricing - повышение цен при высоком спросе. Это mechanism design? Каков стимул для водителей? Для пассажиров? Справедлив ли этот механизм?

Связанные уроки

• stat-14-pca