Теория игр
Game Theory в Tech: pricing, markets
$237 млрд в год Google Ads, $100+ млрд рынок Uber, миллионы жизней через matching в медицине - всё это mechanism design в действии. Лучшие product decisions в Tech - это правильный ответ на вопрос: «Какую игру создают наши правила для пользователей?» Понимание теории игр отличает инженера, который реализует алгоритм, от продуктового лидера, который проектирует систему.
- **Google AdWords:** $237 млрд/год на механизме GSP. Quality Score как IC-инструмент выравнивания стимулов. История создания - одно из важнейших бизнес-решений XXI века
- **Matching markets:** алгоритм Гейла-Шепли в NRMP (ординатуры), NYC Schools, Kidney Exchange (Рот, Нобель 2012). Буквально спасает жизни через theory of matching
- **Uber/Lyft:** surge pricing - dynamic mechanism design. Chicken-and-egg bootstrap через driver-side subsidies. Двустороннее равновесие как стратегия выхода на рынок
Предварительные знания
Аукционный дизайн в Tech платформах
Каждый раз, когда пользователь вводит поисковый запрос в Google, запускается аукцион, который длится ~100 миллисекунд. Тысячи рекламодателей соревнуются за показ своего объявления. Результат определяется не просто по ставке, а по комбинации ставки и качества объявления. Этот механизм - GSP (Generalized Second Price) - один из самых прибыльных mechanism design продуктов в истории.
n позиций с CTR (click-through rates) α₁ > α₂ > ... > αₙ n+1 рекламодателей с ценностью за клик vᵢ и Quality Score qᵢ Ранжирование по bid_score = bᵢ · qᵢ Платёж i-го позиционера: pᵢ = b_{i+1} · q_{i+1} / qᵢ (аналог второй цены с поправкой на качество) GSP не является строго IC (в отличие от чистого VCG), но имеет «locally envy-free» равновесие.
Quality Score в GSP - ключевое отличие от простого аукциона по ставке. Это стимулирует рекламодателей делать релевантные объявления: высокое качество снижает платёж за ту же позицию. Google зарабатывает больше с качественными объявлениями (они кликаются чаще) - выравнивание стимулов через mechanism design.
История: Overture и Google AdWords
Overture (GoTo.com) в 1998 году первой запустила аукцион для рекламы - но аукцион первой цены без Quality Score. Рекламодатели занижали ставки стратегически. Google в 2002 году создала AdWords с Quality Score и аналогом второй цены - выручка выросла, а качество рекламы улучшилось. Это billion-dollar mechanism design decision. Сейчас Google Ads - $237 млрд/год.
Google AdWords - это просто аукцион второй цены (Викри) в больших масштабах
GSP отличается от Викри: несколько позиций с разными CTR, Quality Score в ранжировании. GSP не является строго IC, в отличие от VCG для нескольких позиций.
Для нескольких позиций VCG-совместимый механизм сложен в реализации и имеет проблему бюджетного дефицита. GSP - практичный компромисс, работающий в «locally envy-free» Nash Equilibrium.
Почему Google включает Quality Score в формулу GSP аукциона, а не просто ранжирует по ставке?
Matching Markets и алгоритм Гейла-Шепли
В обычном рынке цена уравновешивает спрос и предложение. Но некоторые рынки принципиально отличаются: вас не устраивает любая больница, а только хорошая. Работодатель не хочет любого кандидата, а подходящего. Здесь важно не просто «договориться», а найти стабильное сопоставление - такое, что никакая пара не захочет «переметнуться» друг к другу.
Сопоставление нестабильно, если есть пара (m, w), которые предпочитают друг друга своим текущим партнёрам. Алгоритм Гейла-Шепли (Deferred Acceptance): 1. Каждый мужчина предлагает первой в своём списке 2. Каждая женщина «держит» лучшее предложение, отвергает остальных 3. Отвергнутые предлагают следующим в своём списке 4. Повтор до стабильного состояния Результат: всегда стабильное сопоставление, оптимальное для предлагающей стороны.
Алгоритм Гейла-Шепли лежит в основе: NRMP (распределение ординаторов по больницам в США), NYC и Boston школьных зачислений, Google Summer of Code matching, матчмейкинг в онлайн-играх. Элвин Рот (Нобель 2012) применил matching theory для дизайна рынка почечных трансплантаций - буквально спасая жизни.
Matching markets работают так же, как обычные ценовые рынки - просто с другими товарами
Matching markets принципиально отличаются: в них нет цены-координатора, стабильность важнее оптимальности, и стороны имеют предпочтения друг к другу (не только к «товару»).
На обычном рынке яблок вам всё равно, кто продавец. На рынке труда или образования - важно, кто именно партнёр. Это меняет всю механику: нужна стабильность, а не только market-clearing price.
Алгоритм Гейла-Шепли (Deferred Acceptance) гарантирует:
Платформенная экономика и сетевые эффекты
Uber ценнее при большем числе водителей и пассажиров. Apple App Store ценнее при большем числе разработчиков и пользователей. Это двусторонние платформы (two-sided markets): ценность для одной стороны растёт с размером другой. Теория игр объясняет, почему такие рынки тяготеют к монополии и как дизайнить механизмы субсидирования сторон.
Платформа соединяет сторону A (n_A пользователей) и сторону B (n_B пользователей). Ценность для A: v_A(n_B), для B: v_B(n_A) - взаимные сетевые эффекты. Оптимальные цены (Rochet-Tirole): p_A + p_B = MC + (1/ε_A + 1/ε_B)⁻¹ Одна сторона субсидируется за счёт другой. Пример: кредитные карты бесплатны для потребителей, дорогие для магазинов.
Сетевые эффекты создают **chicken-and-egg** проблему и **tipping point**: платформа либо растёт (переходит из (0,0) к (maxD, maxP)) либо умирает. Стратегия запуска двусторонних платформ - теория игр: кого субсидировать первым (ту сторону, без которой ценность = 0), как устанавливать цены, чтобы перейти tipping point.
Монополия двусторонней платформы - всегда плохо для пользователей
Монополия платформы (Uber, Google) может давать максимальные сетевые эффекты - при достаточном числе участников с обеих сторон. Проблема в том, что монополист злоупотребляет позицией после достижения dominance.
Сетевые эффекты создают winner-take-all динамику: одна платформа на рынке = максимум ценности для всех. Но после захвата рынка монополист поднимает цены и снижает качество - anti-trust проблема.
Почему на двусторонних платформах (кредитные карты, рекламные сети) одна сторона часто субсидируется за счёт другой?
Рекомендательные системы и стратегические пользователи
YouTube рекомендует видео, чтобы максимизировать engagement. Спикеры стратегически оптимизируют заголовки и превью под алгоритм. Стримеры искусственно создают cliff-hangers. Это игра между платформой (механизм) и контент-создателями (агенты). Если создатели знают алгоритм - они адаптируются, алгоритм теряет информационную ценность.
Модель: классификатор f(x) предсказывает y. Агенты стратегически изменяют x для получения лучшей классификации. Это игра: классификатор минимизирует ошибку, агенты максимизируют свой utility. If agents can costlessly imitate: любой классификатор разрушается. При стоимости манипуляции: равновесие зависит от cost structure.
| Система | Стратегическое поведение агентов | Следствие для платформы |
|---|---|---|
| YouTube recommendations | Кликбейт заголовки, cliff-hangers | Контент деградирует к low-quality |
| Google Search SEO | Link farming, keyword stuffing | Алгоритм постоянно обновляется |
| Кредитный скоринг | Стратегическое закрытие/открытие карт | Модель теряет предиктивность |
| Рейтинги на Airbnb | Взаимная накрутка отзывов | Инфляция рейтингов |
Решение проблемы стратегических пользователей - Stackelberg-aware design: проектировать механизм, зная что агенты оптимизируются под него. Это приводит к Stackelberg equilibrium (лидер-последователь): платформа объявляет механизм первой (commits), агенты оптимизируются, платформа знает это при проектировании. Это отдельная от NE концепция равновесия.
Рекомендательные алгоритмы объективны - они показывают то, что пользователям нравится
Алгоритмы создают стратегические стимулы для создателей контента. Контент адаптируется под алгоритм, создавая новый стимул для алгоритма адаптироваться. Это игра, а не объективное отражение предпочтений.
YouTube алгоритм оптимизирован под watch time → создатели делают длинные видео с кликбейтом → watch time растёт, но satisfaction падает. Платформа меняет алгоритм → новый цикл игры.
«Strategic classification» - ситуация, когда:
Ключевые идеи
- **GSP аукцион:** ранжирование по bid × quality создаёт стимулы к качеству - IC через mechanism design
- **Matching markets:** стабильность важнее оптимальности; Гейл-Шепли даёт мужчин-оптимальное стабильное сопоставление
- **Двусторонние платформы:** сетевые эффекты → tipping point → winner-take-all; субсидировать более ценную сторону
- **Strategic classification:** агенты адаптируются под алгоритм → Stackelberg-aware mechanism design
Связанные темы
Tech применения соединяют все предыдущие концепции:
- Mechanism Design — GSP, Uber surge - прикладные механизмы с IC и revenue optimization
- Теория аукционов — GSP - расширение аукциона Викри на несколько позиций; Revenue Equivalence в рекламных аукционах
- Game Theory на собеседовании — Вопросы про design рекламных аукционов, matching, pricing - часть FAANG-интервью
Вопросы для размышления
- TikTok показывает контент без подписок - алгоритм определяет всё. Какую игру создаёт этот дизайн для создателей? Какое равновесие он поддерживает по сравнению с YouTube?
- В matching markets алгоритм Гейла-Шепли оптимален для предлагающей стороны. В NRMP предлагают больницы - значит, они получают лучшее сопоставление, а ординаторы - худшее. Как это исправляет D-A algorithm when residents propose?
- Surge pricing Uber - mechanism design или ценовая дискриминация? Кому это выгодно? Кому вредит? Какое равновесие оно создаёт для водителей и пассажиров?