Шпаргалки / Математика / Школа / Дискретная математика

Теория игр

История термина

  • Термин “теория игр” впервые появился в 1944 году, когда Джон фон Нейман и Оскар Моргенштерн опубликовали книгу “Theory of Games and Economic Behavior”.
  • Фон Нейман заложил математическую основу стратегического анализа — как предсказывать оптимальные решения игроков в различных ситуациях.
  • В 1950–60-х Эйнольд и Нэш расширили теорию: придумали равновесие Нэша, смешанные стратегии и изучение некооперативных игр.

Суть теории игр

  • Теория игр — раздел математики, изучающий стратегическое взаимодействие рациональных игроков.
  • Игроки могут быть: люди, фирмы, государства, животные, алгоритмы.
  • Основная цель — найти оптимальные стратегии, которые максимизируют выигрыш или минимизируют проигрыш с учётом действий других игроков.

Сферы применения

  1. Экономика — анализ конкуренции, аукционы, ценообразование, торговые стратегии.
  2. Политология — стратегические решения государств, выбор союзов, распределение ресурсов.
  3. Биология — эволюционная стабильность, конкуренция видов.
  4. Компьютерные науки — алгоритмы, искусственный интеллект, планирование и принятие решений.
  5. Социология и психология — поведение людей в группах, дилемма заключённого.

Ключевая идея

  • Любая ситуация, где результат зависит от действий нескольких участников, может быть формализована как игра:
    • Игроки → участники
    • Стратегии → возможные действия
    • Выигрыши → количественная оценка результата
  • Основная цель теории игр — понять, какие стратегии рациональны и предсказать исход.

    Основные типы игр

Тип игры Суть Пример
Детерминированная Всё зависит от ходов, нет случайности Шахматы, шашки
Стохастическая Есть элемент случайности Монополия, покер с картами
С нулевой суммой Выигрыш одного = проигрыш другого Шахматы, камень-ножницы-бумага
С ненулевой суммой Выигрыш одного ≠ проигрыш другого Торг, распределение ресурсов
Кооперативная Игроки могут договариваться Договоры, альянсы
Некооперативная Игроки действуют самостоятельно Классические шахматы, бизнес-конкуренция

Ключевые понятия

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

Игры с нулевой суммой (математика)

  • Для двух игроков A и B: сумма выигрышей = 0
  • Матрица выигрышей игрока A: \(H = [h_{ij}]\), где \(i\) — ход A, \(j\) — ход B

Минимакс (оптимальная стратегия):

\[ v = \max_{i} \min_{j} h_{ij} = \min_{j} \max_{i} h_{ij} \]
  • \(v\) — цена игры (выигрыш при оптимальных стратегиях)

Равновесие Нэша

Для \(n\) игроков с стратегиями \(s_1, \dots, s_n\) и выигрышами \(u_1, \dots, u_n\):

\[ u_i(s_1^*, \dots, s_i^*, \dots, s_n^*) \ge u_i(s_1^*, \dots, s_i, \dots, s_n^*) \quad \forall i \]
  • \(s_i^*\) — оптимальная стратегия игрока \(i\)
  • Никто не может улучшить свой результат, меняя стратегию в одиночку

Смешанные стратегии

  • Игрок выбирает стратегию случайно с вероятностями \(p_1, \dots, p_m\)
  • Условия: \(p_i \ge 0, \sum_i p_i = 1\)

Ожидаемый выигрыш:

\[ E[H] = \sum_{i,j} p_i q_j h_{ij} \]
  • \(p_i\) — вероятности ходов игрока A
  • \(q_j\) — вероятности ходов игрока B

Пример матрицы выигрышей (таблица всех исходов)

“Камень-ножницы-бумага” (A выигрывает = 1, проигрывает = -1, ничья = 0):

\[ H = \begin{bmatrix} 0 & -1 & 1 \\ 1 & 0 & -1 \\ -1 & 1 & 0 \end{bmatrix} \]
  • Строки = ходы игрока A: Камень, Ножницы, Бумага
  • Столбцы = ходы игрока B: Камень, Ножницы, Бумага
  • Значения = выигрыши игрока A

Оптимальная стратегия (смешанная):

  • Оптимальная смешанная стратегия: \(p = (1/3, 1/3, 1/3)\) для обоих игроков
  • Игроки выбирают каждый ход случайно с равной вероятностью → никто не может улучшить результат, меняя стратегию в одиночку

    Кооперативная игра (ядро)

  • Игроки: \(N = \{1,2,\dots,n\}\)
  • Коалиции \(S \subseteq N\), стоимость коалиции \(v(S)\)

Ядро (Core) — выплаты \((x_1, \dots, x_n)\):

\[ \sum_{i \in N} x_i = v(N), \quad \sum_{i \in S} x_i \ge v(S) \quad \forall S \subseteq N \]
  • Никто не захочет уйти из коалиции

Ключевые идеи

  1. Игры с нулевой суммой → оптимальная стратегия = минимакс
  2. Кооперативные игры → ищем Pareto-оптимальные исходы
  3. Стохастические игры → смешанные стратегии
  4. Равновесие Нэша = базовая концепция стратегического анализа
  5. Любая игра с конечными стратегиями = матрица + стратегия + оптимизация