Теория игр
Введение в теорию игр
Почему страны вооружаются, хотя мир был бы лучше для всех? Почему фирмы снижают цены до нуля? Почему вратарь прыгает случайно? За этими разными вопросами стоит одна математика - теория игр: наука о том, как рациональные агенты принимают решения, когда результат зависит от действий других.
- **Аукционы:** Google продаёт рекламу через аукцион Викри второй цены - дизайн, основанный на теории игр (Нобель 2020, Милгром и Уилсон)
- **Биология:** Стратегии выживания животных (ястреб vs голубь) моделируются эволюционной теорией игр - ESS (эволюционно стабильные стратегии)
- **AI:** Алгоритмы для покера (Libratus, Pluribus) и Go (AlphaGo) основаны на поиске равновесия Нэша и минимаксе
Игроки и рациональность
Две компании решают, снижать ли цены. Два государства выбирают: вооружаться или разоружаться. Два водителя едут навстречу друг другу и решают, свернуть или нет. Все эти ситуации - **игры** в математическом смысле: участники принимают решения, которые влияют на исход для всех.
Формальная модель стратегического взаимодействия. Определяется тремя элементами: 1. множество игроков N = {1, 2, ..., n} 2. множество стратегий Sᵢ для каждого игрока 3. функция выигрыша uᵢ: S₁ × S₂ × ... × Sₙ → R для каждого игрока.
**Игрок** - участник, принимающий решения. Это может быть человек, фирма, государство, биологический вид или алгоритм. Ключевое предположение классической теории игр: игроки **рациональны** - каждый максимизирует свой выигрыш, зная, что остальные делают то же самое.
Рациональность - сильное допущение. Поведенческая экономика (Канеман, Тверски) показала, что люди систематически отклоняются от рациональности. Но рациональность - полезная отправная точка: сначала поймём, как «должны» вести себя идеальные агенты, затем изучим отклонения.
Игры бывают с **полной информацией** (все знают правила и выигрыши всех) и **неполной** (кто-то не знает чужие выигрыши). Шахматы - полная информация (все фигуры видны), покер - неполная (карты соперника скрыты). Мы начнём с полной информации.
Что означает «рациональность» игрока в теории игр?
Чистые и смешанные стратегии
**Стратегия** - полный план действий игрока на все возможные ситуации. В простых играх стратегия - одно действие (Cooperate или Defect). В сложных - дерево решений: «если соперник сделал X, я делаю Y; если Z - делаю W».
Определённый выбор действия. Игрок точно знает, что он будет делать. Множество чистых стратегий Sᵢ - конечный (или бесконечный) набор вариантов.
Вероятностное распределение над чистыми стратегиями. Игрок рандомизирует выбор: играет стратегию A с вероятностью p и стратегию B с вероятностью (1-p).
Зачем рандомизировать? Рассмотрим вратаря на пенальти. Если он всегда прыгает влево - бьющий это выучит и будет бить вправо. Оптимальная стратегия - прыгать случайно с определёнными вероятностями, чтобы быть непредсказуемым.
Камень-Ножницы-Бумага - игра, где нет «лучшей» чистой стратегии (любая проигрывает одной из двух других). Единственная оптимальная стратегия - смешанная: играть каждый вариант с вероятностью 1/3. Любое отклонение от равномерности можно эксплуатировать.
Профиль стратегий - комбинация стратегий всех игроков: s = (s₁, s₂, ..., sₙ). Запись s₋ᵢ означает «стратегии всех игроков, кроме i-го». Это обозначение ключевое для определения равновесия Нэша.
Когда рациональный игрок выбирает смешанную стратегию?
Функция выигрыша
**Функция выигрыша** (payoff function) uᵢ(s₁, s₂, ..., sₙ) - число, отражающее «счастье» игрока i при данном профиле стратегий. Чем выше - тем лучше для игрока. Это может быть прибыль, удовольствие, число лет свободы или любая другая мера «полезности».
Важно: выигрыши - это **ordinal utility** (порядок важнее абсолютных значений). Если u(A) = 10 и u(B) = 5, это значит только «A лучше B для игрока», но не «A ровно вдвое лучше». Для смешанных стратегий нужна **cardinal utility** - ожидаемый выигрыш: E[u] = Σ p(s) · u(s).
Игры классифицируются по типу выигрышей: **антагонистические** (zero-sum) - выигрыш одного = проигрыш другого (шахматы, покер), **кооперативные** - сумма может расти (торговля), **смешанные** - и конфликт, и кооперация (дилемма заключённого).
| Тип игры | u₁ + u₂ | Пример |
|---|---|---|
| Zero-sum | = 0 всегда | Шахматы, покер, пенальти |
| Positive-sum | > 0 возможно | Торговля, альянсы |
| Negative-sum | < 0 возможно | Война, гонка вооружений |
| Переменная сумма | Зависит от исхода | Дилемма заключённого |
Что означает zero-sum (антагонистическая) игра?
Нормальная форма и дилемма заключённого
**Нормальная форма** (стратегическая форма) - самый простой способ записать игру: матрица, где строки - стратегии игрока 1, столбцы - стратегии игрока 2, а в ячейках - пары выигрышей (u₁, u₂).
**Дилемма заключённого** - самая знаменитая игра в теории игр. Два подозреваемых арестованы. Каждый может молчать (Cooperate) или предать сообщника (Defect). Парадокс: рациональный выбор каждого (предать) приводит к худшему для обоих исходу (-2, -2), хотя взаимное молчание (-1, -1) было бы лучше.
Логика каждого заключённого: «Если другой молчит, мне выгоднее предать (0 > -1). Если другой предаёт, мне тоже выгоднее предать (-2 > -3). При ЛЮБЫХ действиях другого мне выгоднее предать.» Оба приходят к такому выводу - и оба предают.
Происхождение дилеммы заключённого
Игру формализовали Мерилл Флуд и Мелвин Дрешер в 1950 году в RAND Corporation. Альберт Такер придумал историю про заключённых и дал игре название. С тех пор дилемма заключённого стала каноническим примером конфликта между индивидуальной рациональностью и коллективным благом.
Дилемма заключённого встречается повсюду: гонка вооружений (каждая страна вооружается, хотя обоюдное разоружение лучше), загрязнение (каждая фирма загрязняет, хотя чистая среда лучше для всех), допинг в спорте (каждый принимает, хотя чистый спорт лучше).
Нормальная форма - удобная запись, но она не показывает порядок ходов. Для последовательных игр (шахматы, переговоры) используют **экстенсивную форму** - дерево решений. Мы изучим её позже, а пока сосредоточимся на одновременных играх в нормальной форме.
Теория игр - это про настольные игры и видеоигры
Теория игр - раздел математики о стратегическом взаимодействии рациональных агентов. Она применяется в экономике, политологии, биологии, computer science, военном деле и дизайне аукционов.
Слово «игра» здесь - формальный термин для любой ситуации, где результат зависит от решений нескольких участников. Нобелевские премии за теорию игр получали экономисты (Нэш, Шеллинг, Ауманн), а не разработчики настолок.
Почему в дилемме заключённого оба рациональных игрока предают, хотя взаимное сотрудничество лучше?
Ключевые идеи
- **Игра** = (игроки, стратегии, выигрыши) - формальная модель стратегического взаимодействия
- **Чистая стратегия** - определённый выбор; **смешанная** - рандомизация для непредсказуемости
- **Нормальная форма** - матрица выигрышей для одновременных игр
- **Дилемма заключённого** показывает: индивидуальная рациональность может вести к коллективно худшему исходу
Связанные темы
Введение в теорию игр открывает путь к фундаментальным результатам:
- Равновесие Нэша — Центральная концепция - профиль стратегий, от которого никому не выгодно отклоняться
- Доминирование и итеративное удаление — Систематический метод упрощения игр через удаление «глупых» стратегий
Вопросы для размышления
- Дилемма заключённого показывает конфликт индивидуальной и коллективной рациональности. Известны ли реальные ситуации с такой структурой в повседневной жизни?
- Если предположить, что игроки НЕ рациональны (ошибаются, руководствуются эмоциями) - как это меняет анализ игры?
- Почему вратарь на пенальти не всегда прыгает в одну сторону, даже если статистика показывает, что бьющий чаще бьёт влево?