Теория игр
Равновесие Нэша, доминирующие стратегии, дилемма заключённого
🎯 Через 4 минуты вы сможете находить доминирующие стратегии и равновесие Нэша в нормальных и последовательных играх.
Теория игр
Введение
Теория игр — продвинутая тема, которая всё чаще появляется на олимпиаде РАНХиГС. Нужно уверенно работать с матрицами выигрышей, находить доминирующие стратегии и равновесие Нэша.
Теория
Основные понятия
Игра — стратегическое взаимодействие, где выигрыш каждого зависит от действий всех.
Нормальная форма (матрица):
| B: Лево | B: Право | |
|---|---|---|
| A: Верх | (3,2) | (1,4) |
| A: Низ | (2,1) | (4,3) |
Первое число — выигрыш A, второе — B.
Доминирующие стратегии
Стратегия строго доминирует, если она лучше любой другой при любых действиях соперника.
Равновесие в доминирующих стратегиях — каждый играет свою доминирующую стратегию.
Равновесие Нэша
Пара стратегий (s_A, s_B) — равновесие Нэша, если ни один игрок не хочет отклоняться в одностороннем порядке.
Как найти: для каждой стратегии B найти лучший ответ A (подчеркнуть). Для каждой стратегии A найти лучший ответ B. Клетка, где оба числа подчёркнуты — равновесие Нэша.
Дилемма заключённого
| B: Молчать | B: Сдать | |
|---|---|---|
| A: Молчать | (-1,-1) | (-10,0) |
| A: Сдать | (0,-10) | (-5,-5) |
Доминирующая стратегия: Сдать. Равновесие: (Сдать, Сдать) = (-5,-5). Но (Молчать, Молчать) = (-1,-1) лучше для обоих! Проблема кооперации.
Последовательные игры
Дерево игры — игроки ходят по очереди. Решается обратной индукцией (backward induction): начинаем с конца дерева.
Смешанные стратегии
Если нет равновесия в чистых стратегиях — ищем в смешанных (вероятностное распределение). Условие: соперник должен быть безразличен между своими стратегиями.
Типовые задачи
Задача 1. Найти равновесие Нэша
| B: L | B: R | |
|---|---|---|
| A: U | (3,1) | (0,2) |
| A: D | (1,0) | (2,3) |
A: если B играет L: U(3)>D(1)→U. Если B играет R: D(2)>U(0)→D. B: если A играет U: R(2)>L(1)→R. Если A играет D: R(3)>D(0)→R.
B имеет доминирующую стратегию R. A при R играет D. Равновесие: (D, R) = (2,3).
Задача 2. Дилемма олигополистов
Две фирмы: высокая или низкая цена.
| B: Высокая | B: Низкая | |
|---|---|---|
| A: Высокая | (10,10) | (2,12) |
| A: Низкая | (12,2) | (5,5) |
Доминирующая для обоих: Низкая. NE: (Низкая, Низкая) = (5,5). Это дилемма заключённого — кооперация (Высокая, Высокая) лучше.
Частые ошибки
- Путают строки (игрок A) и столбцы (игрок B).
- Забывают проверить оба числа в клетке для NE.
- Считают, что NE = лучший исход. NE может быть Парето-неэффективным.
Как искать равновесие в матрице
Приём, который экономит время: подчёркивайте лучшие ответы. Для каждого столбца подчеркните лучший выигрыш первого игрока, для каждой строки — лучший выигрыш второго. Клетка, где подчёркнуты оба числа, и есть равновесие Нэша. Если такой клетки нет, равновесие существует только в смешанных стратегиях.
Смешанное равновесие ищут из условия безразличия: соперник выбирает вероятности так, чтобы вам было всё равно, какую чистую стратегию играть. Приравниваете два ожидаемых выигрыша и решаете уравнение относительно вероятности.
Последовательные игры решают обратной индукцией: начинают с последнего хода, отбрасывают заведомо худшие ветки и поднимаются к началу дерева. Именно так получается преимущество первого хода в модели Штакельберга.
Чек-лист
- [ ] Умею читать матрицу выигрышей
- [ ] Нахожу доминирующие стратегии
- [ ] Нахожу равновесие Нэша методом подчёркивания
- [ ] Понимаю дилемму заключённого
- [ ] Решаю последовательные игры обратной индукцией
✅ Теперь вы умеете
- Определять доминирующую стратегию по матрице выигрышей
- Находить равновесие Нэша через лучшие ответы
- Решать последовательную игру обратной индукцией
- Распознавать Парето-неэффективное равновесие в дилемме заключённого