Теория игр

Введение

Теория игр — продвинутая тема, которая всё чаще появляется на олимпиаде РАНХиГС. Нужно уверенно работать с матрицами выигрышей, находить доминирующие стратегии и равновесие Нэша.

---

Теория

Основные понятия

Игра — стратегическое взаимодействие, где выигрыш каждого зависит от действий всех.

Нормальная форма (матрица):

| | 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). Это дилемма заключённого — кооперация (Высокая, Высокая) лучше.

---

Частые ошибки

---

Чек-лист

• [ ] Умею читать матрицу выигрышей
• [ ] Нахожу доминирующие стратегии
• [ ] Нахожу равновесие Нэша методом подчёркивания
• [ ] Понимаю дилемму заключённого
• [ ] Решаю последовательные игры обратной индукцией