Теория игр

План лекции

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

2. Классификация игр

3. Антагонистические (биматричные) игры

4. Нижняя и верхняя цены игры. Седловая точка

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

6. Решение игр 2×2 в смешанных стратегиях

7. Связь теории игр с линейным программированием

8. Программная реализация

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

Теория игр — математическая теория принятия решений в условиях конфликта, когда результат зависит от действий нескольких сторон (игроков).

Основатель: Джон фон Нейман, Оскар Моргенштерн (1944)

Ключевая идея: каждый игрок выбирает стратегию, стремясь максимизировать свой выигрыш при учёте действий других игроков.

Примеры:

• Экономика: ценообразование, аукционы, олигополия
• Информатика: сетевые протоколы, распределение ресурсов
• Военное дело: стратегии, переговоры

Основные элементы игры

2. Классификация игр

Бескоалиционная игра — каждый игрок действует самостоятельно.

Антагонистическая игра (нулевая сумма) — выигрыш одного игрока равен проигрышу другого.

Антагонистические игры

Антагонистическая игра двух лиц — выигрыш первого игрока равен проигрышу второго.

Обозначим игроков: $A$ (первый, максимизирует) и $B$ (второй, минимизирует).

Матричная форма (платёжная матрица):

$a_{ij}$ — выигрыш игрока $A$, если он выбирает $A_i$, а игрок $B$ — $B_j$.

3. Нижняя и верхняя цена игры

Игрок $A$ (максимизирует): для каждой стратегии $A_i$ определяет гарантированный выигрыш — минимум по столбцам:

$$\alpha_i = \min_j a_{ij}$$

Затем выбирает стратегию с максимальным гарантированным выигрышем:

$$\alpha = \max_i \alpha_i = \max_i \min_j a_{ij}$$

Нижняя цена игры (максимин): $\alpha$ — гарантированный выигрыш игрока $A$.

Нижняя и верхняя цена игры (продолжение)

Игрок $B$ (минимизирует): для каждой стратегии $B_j$ определяет максимальный проигрыш по строкам:

$$\beta_j = \max_i a_{ij}$$

Затем выбирает стратегию с минимальным максимальным проигрышем:

$$\beta = \min_j \beta_j = \min_j \max_i a_{ij}$$

Верхняя цена игры (минимакс): $\beta$ — гарантированный проигрыш игрока $B$.

Всегда: $\alpha \leq \beta$

Седловая точка

Если $\alpha = \beta$, то игра имеет седловую точку в чистых стратегиях.

$$\max_i \min_j a_{ij} = \min_j \max_i a_{ij} = v$$

$v$ — цена игры — оптимальный гарантированный результат для обоих игроков.

Элемент $a_{i^*j^*}$ — седловой элемент матрицы, если:

• $a_{i^*j^*} = \max_i a_{ij^*}$ (максимум в столбце $j^*$)
• $a_{i^*j^*} = \min_j a_{ij^*}$ (минимум в строке $i^*$)

Пример: поиск седловой точки

$$A = \begin{pmatrix} 4 & 1 & 5 \\ 3 & 2 & 6 \\ 0 & 7 & 4 \end{pmatrix}$$

$$\alpha = \max(1, 2, 0) = 2, \quad \beta = \min(4, 7, 6) = 4$$

$\alpha \neq \beta$ — седловой точки в чистых стратегиях нет!

Пример: игра с седловой точкой

$$A = \begin{pmatrix} 3 & 5 & 2 \\ 6 & 1 & 4 \\ 2 & 3 & 6 \end{pmatrix}$$

$$\alpha = \max(2, 1, 2) = 2, \quad \beta = \min(6, 5, 6) = 5$$

$\alpha \neq \beta$ — седловой точки нет.

Проверим другой пример: $a_{22} = 1$ — нет. Попробуем матрицу, где седловая точка есть.

Пример: матрица с седловой точкой

$$A = \begin{pmatrix} 8 & 3 & 5 \\ 2 & 7 & 6 \\ 4 & 1 & 9 \end{pmatrix}$$

$\alpha = 3$, $\beta = 7$. Нет седловой точки.

Правило: седловая точка существует, если некоторый элемент является одновременно минимумом в строке и максимумом в столбце.

Пример: матрица с гарантированной седловой точкой

$$A = \begin{pmatrix} 3 & \mathbf{5} & 6 \\ 2 & 1 & 4 \\ 7 & 3 & \mathbf{5} \end{pmatrix}$$

$$\alpha = 3, \quad \beta = 5$$

Всё ещё нет. Седловая точка — редкое явление. Если её нет — используем смешанные стратегии.

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

Смешанная стратегия — вероятностное распределение на множестве чистых стратегий.

Игрок $A$ выбирает $A_i$ с вероятностью $p_i$:

$$\vec{p} = (p_1, p_2, \ldots, p_m), \quad p_i \geq 0, \quad \sum_{i=1}^{m} p_i = 1$$

Игрок $B$ выбирает $B_j$ с вероятностью $q_j$:

$$\vec{q} = (q_1, q_2, \ldots, q_n), \quad q_j \geq 0, \quad \sum_{j=1}^{n} q_j = 1$$

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

При смешанных стратегиях $\vec{p}$ и $\vec{q}$ математическое ожидание выигрыша:

$$E(\vec{p}, \vec{q}) = \sum_{i=1}^{m} \sum_{j=1}^{n} a_{ij} p_i q_j = \vec{p}^T A \vec{q}$$

Теорема фон Неймана (1928):

Всякая конечная антагонистическая игра имеет решение в смешанных стратегиях:

$$\max_{\vec{p}} \min_{\vec{q}} E(\vec{p}, \vec{q}) = \min_{\vec{q}} \max_{\vec{p}} E(\vec{p}, \vec{q}) = v$$

Нижняя и верхняя цены в смешанных стратегиях

$$v_A = \max_{\vec{p}} \min_{j} \sum_{i=1}^{m} a_{ij} p_i \quad \text{— нижняя цена в смешанных стратегиях}$$

$$v_B = \min_{\vec{q}} \max_{i} \sum_{j=1}^{n} a_{ij} q_j \quad \text{— верхняя цена в смешанных стратегиях}$$

Теорема: $v_A = v_B = v$ — цена игры в смешанных стратегиях.

Оптимальные смешанные стратегии $\vec{p}^*$, $\vec{q}^*$ и цена $v$ — решение игры.

5. Решение игры 2×2 в смешанных стратегиях

Платёжная матрица:

$$A = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}$$

Игрок $A$ выбирает $A_1$ с вероятностью $p$, $A_2$ — с вероятностью $1 - p$.

Ожидаемый выигрыш при ответе $B$:

• Если $B$ выбирает $B_1$: $E_1 = p \cdot a_{11} + (1-p) \cdot a_{21}$
• Если $B$ выбирает $B_2$: $E_2 = p \cdot a_{12} + (1-p) \cdot a_{22}$

Принцип: игрок $A$ выбирает $p$ так, чтобы $E_1 = E_2$ (уравнивание выигрышей):

$$p \cdot a_{11} + (1-p) \cdot a_{21} = p \cdot a_{12} + (1-p) \cdot a_{22}$$

Решение игры 2×2: формулы

Из уравнения $E_1 = E_2$:

$$p = \frac{a_{22} - a_{21}}{(a_{11} - a_{12}) + (a_{22} - a_{21})}$$

$$q = \frac{a_{22} - a_{12}}{(a_{11} - a_{21}) + (a_{22} - a_{12})}$$

Цена игры:

$$v = p \cdot a_{11} + (1-p) \cdot a_{21} = q \cdot a_{11} + (1-q) \cdot a_{12}$$

Пример: решение игры 2×2

$$A = \begin{pmatrix} 3 & 1 \\ 2 & 4 \end{pmatrix}$$

Проверим чистые стратегии: $\alpha = \max(\min(3,1),\, \min(2,4)) = \max(1, 2) = 2$

$\beta = \min(\max(3,2),\, \max(1,4)) = \min(3, 4) = 3$

$\alpha \neq \beta$ — седловой точки нет. Решаем в смешанных стратегиях.

$$p = \frac{4 - 2}{(3 - 1) + (4 - 2)} = \frac{2}{2 + 2} = \frac{1}{2}$$

$$q = \frac{4 - 1}{(3 - 2) + (4 - 1)} = \frac{3}{1 + 3} = \frac{3}{4}$$

$$v = 0.5 \cdot 3 + 0.5 \cdot 2 = 2.5$$

Ответ: $p^* = (0.5,\, 0.5)$, $q^* = (0.75,\, 0.25)$, $v = 2.5$

Пример: проверка решения

$$\vec{p}^* = (0.5,\, 0.5), \quad \vec{q}^* = (0.75,\, 0.25), \quad v = 2.5$$

Если $B$ играет $B_1$: $E = 0.5 \cdot 3 + 0.5 \cdot 2 = 2.5 = v$ ✓

Если $B$ играет $B_2$: $E = 0.5 \cdot 1 + 0.5 \cdot 4 = 2.5 = v$ ✓

Если $A$ играет $A_1$: $E = 0.75 \cdot 3 + 0.25 \cdot 1 = 2.5 = v$ ✓

Если $A$ играет $A_2$: $E = 0.75 \cdot 2 + 0.25 \cdot 4 = 2.5 = v$ ✓

Независимо от стратегии противника — выигрыш равен цене игры $v = 2.5$.

6. Связь теории игр с линейным программированием

Для игры $m \times n$ задача поиска оптимальной смешанной стратегии сводится к паре двойственных задач ЛП.

Задача игрока $A$ (максимизация):

$$v_A = \max x_0$$

$$\begin{cases} \sum\limits_{i=1}^{m} a_{ij} x_i \geq x_0, \quad j = 1, \ldots, n \\ \sum\limits_{i=1}^{m} x_i = 1 \\ x_i \geq 0, \quad i = 1, \ldots, m \end{cases}$$

где $x_i = p_i / v$.

Связь с ЛП (продолжение)

Задача игрока $B$ (минимизация):

$$v_B = \min y_0$$

$$\begin{cases} \sum\limits_{j=1}^{n} a_{ij} y_j \leq y_0, \quad i = 1, \ldots, m \\ \sum\limits_{j=1}^{n} y_j = 1 \\ y_j \geq 0, \quad j = 1, \ldots, n \end{cases}$$

где $y_j = q_j / v$.

По теореме двойственности: $v_A = v_B = v$.

Приведение к стандартной форме ЛП

Пусть $x_i = p_i / v$, тогда $x_0 = 1/v$ и задача игрока $A$:

$$\max \left\{ \sum_{i=1}^{m} x_i \;\Big|\; \sum_{i=1}^{m} a_{ij} x_i \geq 1, \; x_i \geq 0 \right\}$$

Алгоритм:

1. Если все $a_{ij} > 0$ — решаем задачу ЛП симплекс-методом
2. Если есть $a_{ij} \leq 0$ — прибавляем к всем элементам константу $k$ (цена игры изменится на $k$)
3. Находим $x_i^*$, вычисляем $v = 1 / \sum x_i^*$, $p_i = v \cdot x_i^*$

Пример: игра 2×2 через ЛП

$$A = \begin{pmatrix} 3 & 1 \\ 2 & 4 \end{pmatrix}$$

Все $a_{ij} > 0$. Задача игрока $A$:

$$\max \; (x_1 + x_2)$$

$$\begin{cases} 3x_1 + 2x_2 \geq 1 \\ x_1 + 4x_2 \geq 1 \\ x_1, x_2 \geq 0 \end{cases}$$

Решение: $x_1^* = 1/5$, $x_2^* = 1/5$.

$$v = \frac{1}{x_1^* + x_2^*} = \frac{1}{2/5} = 2.5$$

$$p_1 = 2.5 \cdot 0.2 = 0.5, \quad p_2 = 0.5$$

Доминирование стратегий

Стратегия $A_i$ доминирует $A_k$, если $a_{ij} \geq a_{kj}$ для всех $j$ (и хотя бы для одного строго).

Доминируемую стратегию можно исключить — она никогда не войдёт в оптимальную смешанную стратегию.

Пример:

$$A = \begin{pmatrix} 4 & 3 & 6 \\ 2 & 5 & 1 \\ 4 & 3 & 5 \end{pmatrix}$$

$A_1$ доминирует $A_3$ (строго по $B_3$). Исключаем $A_3$:

$$A' = \begin{pmatrix} 4 & 3 & 6 \\ 2 & 5 & 1 \end{pmatrix}$$

7. Программная реализация

import numpy as np
from scipy.optimize import linprog

def solve_game_2x2(matrix):
    a = np.array(matrix)
    p = (a[1,1] - a[1,0]) / ((a[0,0] - a[0,1]) + (a[1,1] - a[1,0]))
    q = (a[1,1] - a[0,1]) / ((a[0,0] - a[1,0]) + (a[1,1] - a[0,1]))
    v = p * a[0,0] + (1 - p) * a[1,0]
    return {'p': [p, 1-p], 'q': [q, 1-q], 'v': v}

r = solve_game_2x2([[3, 1], [2, 4]])
print(f"p={r['p']}, q={r['q']}, v={r['v']}")
# p=[0.5, 0.5], q=[0.75, 0.25], v=2.5

Программная реализация: произвольная игра через ЛП

def solve_game_lp(payoff):
    m, n = np.array(payoff).shape
    A = np.array(payoff)
    if A.min() <= 0:
        A = A - A.min() + 1
    c = -np.ones(m)
    Aub = -A.T
    bub = -np.ones(n)
    res = linprog(c, A_ub=Aub, b_ub=bub, bounds=(0, None))
    v = 1 / res.fun
    p = v * res.x
    return {'p': p, 'v': v}

r = solve_game_lp([[3, 1, 5], [2, 4, 3], [1, 6, 2]])
print(f"p={r['p']}, v={r['v']}")

Заключение

Ключевые выводы лекции

Вопросы для самоконтроля

1. Что такое теория игр? Какие элементы описывают игру?
2. Что такое платёжная матрица?
3. Чему равны нижняя и верхняя цена игры?
4. В каком случае существует седловая точка в чистых стратегиях?
5. Что такое смешанная стратегия?
6. Сформулируйте теорему фон Неймана о минимаксе.
7. Как решается игра $2 \times 2$ в смешанных стратегиях?
8. Как антагонистическая игра сводится к задаче ЛП?

Рекомендуемые ресурсы