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

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

  • Термин “теория игр” впервые появился в 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. Любая игра с конечными стратегиями = матрица + стратегия + оптимизация