Теория игр
Game Theory на собеседовании
Google, Amazon, Airbnb, Uber, Jane Street, Two Sigma - все они спрашивают о теории игр на собеседованиях. Не как математическую головоломку, а как способ мышления о стратегических системах. Nash Equilibrium в продукте - это вопрос «что стабильно для пользователей?». Mechanism design - «как создать стимулы, не требующие принуждения?». Auction design - «как Google зарабатывает $237 млрд?». Этот урок - практический перевод теории в язык интервью.
- **Google PM/SWE интервью:** «Объясните auction механизм Google Ads» - стандартный вопрос в рекламных командах. Знание GSP vs VCG, Quality Score как IC-инструмента - отличие кандидата уровня L5/L6
- **Quant finance:** Jane Street, Citadel, Two Sigma спрашивают Nash вопросы напрямую - matrix games, mixed strategies, minimax в trading contexts. Здесь нужны и формулы, и интуиция
- **Product strategy:** Matching markets, двусторонние платформы, chicken-and-egg проблема - вопросы для Director/VP уровня. Правильный ответ опирается на Gale-Shapley, network effects, mechanism design
Предварительные знания
Вопросы на Nash Equilibrium
На FAANG и quant-собеседованиях Nash Equilibrium появляется в двух формах: как прямой вопрос («найдите равновесие в этой матрице») и как скрытая структура в продуктовой или system design задаче («почему пользователи не переходят на наш лучший продукт?»). Ключевой навык: видеть игровую структуру там, где её явно не называют.
Прямые вопросы: • «Найдите Nash Equilibrium в матрице 2×2» • «Является ли это равновесием? Проверьте.» • «Есть ли здесь доминирующая стратегия?» Продуктовые вопросы: • «Два стриминга снижают цены - к чему это приведёт?» • «Почему разработчики пишут технический долг?» • «Почему компании гонятся за инженерами, даже переплачивая?» Архитектурные: • «Как спроектировать distributed system, где нет центрального арбитра?» • «Почему TCP congestion control работает без координатора?»
| Вопрос интервью | Структура игры | Правильный ответ |
|---|---|---|
| «Цена войны в такси-рынке» | Дилемма заключённого | Доминирующая стратегия - снижать цены; равновесие хуже Парето |
| «Почему инженеры переплачивают рынок?» | Matching market | Стабильное сопоставление - Гейл-Шепли; кандидаты предлагают → выгоднее работодателям |
| «Как Google заставляет рекламодателей говорить правду?» | Mechanism design, IC | Аукцион второй цены - честная заявка доминирует; VCG-механизм |
| «Почему стандарты принимаются медленно?» | Игра координации | Несколько NE; network effects создают lock-in; first-mover wins |
Формула успешного ответа на Nash вопрос: 1. Определить игроков и стратегии. 2. Записать матрицу выигрышей или описать структуру. 3. Найти лучший ответ каждого на каждую стратегию другого. 4. NE = пересечение лучших ответов. 5. Проверить на Парето-оптимальность - и объяснить расхождение.
На интервью Nash Equilibrium нужно только для матричных игр 2×2
NE-мышление применяется к любой стратегической ситуации: дизайн продуктов, архитектура систем, ценообразование, HR. Интервьюер часто проверяет именно способность видеть игровую структуру.
FAANG-интервьюеры в product/PM ролях спрашивают: «как изменится поведение пользователей?», «что сделают конкуренты?» - это Nash-мышление без явных матриц. Навык перевода реальной ситуации в игровую структуру ценнее знания формул.
Интервьюер спрашивает: «Два конкурента решают, сколько тратить на рекламу. Каждый может тратить много или мало. Если оба тратят много - прибыль падает; если оба мало - делят рынок мирно.» Какая структура у этой игры?
Mechanism Design и Auction вопросы
Вопросы о mechanism design на собеседованиях появляются в трёх контекстах: продуктовые («как сделать так, чтобы пользователи честно оценивали услуги?»), инженерные («как спроектировать API, при котором клиенты не будут злоупотреблять?»), аналитические («почему Uber использует surge pricing?»). Все они требуют одного ответа: incentive compatibility.
Incentive Compatibility (IC): «Честное поведение - лучшая стратегия для агента, независимо от действий других» Вопросы на IC: • Почему рейтинги на Airbnb ненадёжны? (нет IC - обе стороны боятся плохих отзывов) • Как сделать честный market place? (IC через escrow, репутацию, обязательные отзывы) • Почему Google использует Quality Score в аукционе? (IC - стимул к качеству) Revenue Maximization: • Зачем резервная цена на аукционе? (информационная рента) • Почему SaaS компании используют per-seat pricing? (ценовая дискриминация)
Формула ответа на mechanism design вопрос: 1. Определить агентов и их стимулы. 2. Указать текущую «игру» - почему агенты ведут себя нечестно. 3. Предложить изменение механизма - как сделать честность доминирующей стратегией. 4. Проверить на IC - нет ли стимула отклоняться. 5. Отметить trade-offs: сложность реализации, возможные обходы.
Mechanism design на интервью - только для продуктовых менеджеров
Инженеры, архитекторы, аналитики данных - все проектируют системы, где пользователи/клиенты стратегически адаптируются. Понимание IC критично для API design, rate limiting, кредитных скорингов, рекомендательных систем.
Любая система с несколькими агентами и стимулами - это механизм. Инженер, строящий rate limiter, должен предвидеть: как клиент будет обходить лимиты? Это mechanism design мышление.
Интервьюер спрашивает: «На маркетплейсе продавцы завышают цены, зная, что алгоритм рекомендаций их всё равно покажет. Как исправить это через incentive design?» Какой механизм правильный?
Аукционный дизайн на собеседовании
Вопросы об аукционах - классика FAANG интервью, особенно в командах рекламных продуктов (Google, Meta, Amazon) и маркетплейсов. Типичные вопросы: «Объясните, как работает аукцион Google Ads», «Почему использовать аукцион второй цены, а не первой?», «Как установить резервную цену?», «Что такое GSP и чем он отличается от VCG?»
Аукцион второй цены (Vickrey): • Победитель платит вторую по величине ставку • Честная заявка (bid = истинная ценность) - доминирующая стратегия • Почему: занижение рискует потерять победу, завышение - победить с убытком GSP (Google/Bing): • Несколько позиций с разными CTR • Ранжирование по bid × Quality Score • Платёж = (следующий bid_score) / свой Quality Score • Не строго IC, но «locally envy-free» равновесие Revenue Equivalence: • Первая и вторая цена дают ту же ожидаемую выручку • Нарушается при: аффилированных ценностях, асимметрии, риск-авёрсности Резервная цена: • Увеличивает ожидаемую выручку при единственном участнике • Оптимальная: r* = arg max r*(1-F(r*)) (Myerson)
| Вопрос | Ключевой ответ | Почему это важно |
|---|---|---|
| Зачем вторая цена? | Честная заявка доминирует - нет стратегического расчёта | Упрощает поведение участников, меньше манипуляций |
| Зачем Quality Score? | IC: стимулирует делать релевантные объявления | Google зарабатывает больше на кликах - выравнивание стимулов |
| Когда первая цена лучше? | При асимметричных участниках или риск-авёрсности | Revenue Equivalence не выполняется |
| Что такое reserve price? | Минимальная цена продажи - повышает выручку | Угроза «не продать» заставляет платить больше |
Google AdWords - это аукцион Викри (второй цены) для нескольких позиций
Google использует GSP (Generalized Second Price) - не чистый VCG. GSP не строго IC, но имеет практически работающее «locally envy-free» равновесие и проще в реализации.
Сказать «это аукцион Викри» на интервью в команду рекламы - типичная ошибка. Правильно: «это GSP - расширение идеи второй цены на несколько позиций с Quality Score, который создаёт дополнительный стимул к качеству». Это показывает глубину.
Интервьюер спрашивает: «Почему Google использует аукцион с Quality Score вместо чистого аукциона по ставке?» Какой ответ лучший?
Стратегические вопросы и продуктовое мышление
Самые интересные вопросы на собеседовании - не «найди NE в матрице», а «как выйти на двусторонний рынок?», «почему пользователи не переходят на нашу платформу?», «как спроектировать pricing?». Это стратегические игры, замаскированные под продуктовые задачи. Теория игр даёт framework для структурированного ответа.
Шаг 1: Определить игроков и стратегии → Кто принимает решения? Что они могут выбирать? Шаг 2: Описать выигрыши → Что каждый максимизирует? Где конфликт интересов? Шаг 3: Найти Nash Equilibrium → Что стабильно? Кто отклоняться не хочет? Шаг 4: Оценить эффективность → PoA: насколько хуже NE социального оптимума? Шаг 5: Предложить механизм → Как изменить правила, чтобы IC направил агентов к лучшему исходу?
Ещё один важный класс вопросов - **информационная асимметрия**. «Как покупатель может узнать реальное качество товара на маркетплейсе?» (сигнализация: продавцы высокого качества дают гарантию, потому что им это дёшево). «Почему страхование требует медосмотра?» (adverse selection: без скрининга только больные берут страховку). Эти вопросы проверяют понимание incomplete information games.
Для ответов на game theory вопросы нужно знать все формулы и теоремы
Интервьюеры проверяют структурированное мышление, а не знание формул. Умение переформулировать проблему как игру, найти NE и предложить mechanism - важнее вывода оптимальной резервной цены.
Даже без формулы Майерсона можно правильно объяснить: «резервная цена увеличивает выручку, потому что создаёт угрозу не продать - покупатели с высокими ценностями вынуждены ставить больше». Это глубже, чем просто r* = 0.5 для U[0,1].
Интервьюер спрашивает: «У нас новая платформа фриланса. Исполнители не хотят регистрироваться без заказов, заказчики - без исполнителей. Что делать?» Какой ответ наиболее правильный?
Ключевые идеи
- **Nash вопросы:** определи игроков → матрицу выигрышей → лучшие ответы → NE → Парето-сравнение
- **IC механизм:** честность как доминирующая стратегия - ответ на «как предотвратить злоупотребление?»
- **Аукционный дизайн:** вторая цена = IC, GSP = локально envy-free, резерв = выручка, Quality Score = стимул к качеству
- **Двусторонние платформы:** chicken-and-egg = две NE; субсидируй ценную сторону первой для преодоления (0,0)
Связанные темы
Интервью объединяет все ключевые концепции курса:
- Mechanism Design — IC, Revelation Principle, VCG - фундамент ответов на «как спроектировать честную систему»
- Теория аукционов — Первая/вторая цена, Revenue Equivalence, резерв Майерсона - стандарт рекламных продуктов
- Game Theory в Tech: pricing, markets — GSP, matching markets, двусторонние платформы - реальные примеры для интервью
Вопросы для размышления
- Возьмите любой продукт, которым вы пользуетесь каждый день (Telegram, GitHub, Notion). Попробуйте описать его как механизм: кто игроки, что стратегии, есть ли IC? Где рейтинги, где market design?
- «Почему разработчики создают технический долг, зная что он навредит команде?» - ответьте через теорию игр: структура дилеммы, Nash Equilibrium, как исправить mechanism?
- Если бы вы проектировали биддинговую систему для фриланс-платформы с нуля - какой тип аукциона выбрали бы и почему? Как бы учли Quality Score для исполнителей?