♟️ Теория игр

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

Q: Чем смешанная стратегия лучше чистой?

Когда седла нет, чистая стратегия даёт только нижнюю цену $\alpha$: противник, угадав выбор, не даст больше. Смешанная стратегия гарантирует цену игры $v > \alpha$ при любом поведении соперника, потому что все его ответы приводят к одному и тому же среднему. Платой за надёжность служит нестабильность отдельной партии: конкретный розыгрыш может принести и проигрыш.

Q: Как найти вероятности оптимальной смеси для матрицы 2×2?

Уравнять средние выигрыши соперника по его столбцам: $p\,a_{11} + (1-p)\,a_{21} = p\,a_{12} + (1-p)\,a_{22}$. Из уравнения выходит $p = (a_{22} - a_{21}) / (a_{11} + a_{22} - a_{12} - a_{21})$. Для матрицы $\begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix}$ получаем $p = (3 - 2)/(4 + 3 - 1 - 2) = 1/4$ и цену $v = 2{,}5$. Вероятности второго игрока ищут зеркально — по строкам. Для матриц большего размера оптимальные смеси находят симплекс-методом, сведя игру к задаче линейного программирования.

англ. Mixed strategy

Вероятностный вектор $X = (p_1, \ldots, p_m)$ над чистыми стратегиями: игрок бросает жребий, и средний выигрыш становится гарантированным.

Смешанная стратегия — случайный выбор чистой стратегии: вектор вероятностей $X = (p_{1}, \dots, p_{m})$ , где $p_{i} \geq 0$ и $\sum_{i} p_{i} = 1$ . Чистая стратегия — вырожденный случай $p_{k} = 1$ . Против смеси соперника $Y = (q_{1}, \dots, q_{n})$ средний выигрыш — математическое ожидание: $M (X, Y) = \sum_{i} \sum_{j} p_{i} a_{ij} q_{j}$ . Смешивать выгодно там, где чистая стратегия разгадывается: жребий скрывает замысел.

Главный приём: оптимальная смесь уравнивает ожидания соперника по всем его столбцам, лишая его шансов улучшить положение. Для $A = (4213)$ решаем $4 p + 2 (1 - p) = 1 p + 3 (1 - p)$ , откуда $2 + 2 p = 3 - 2 p$ и $p = 1/4$ . Оба ожидания равны $2, 5$ — это и есть цена игры. Подробная техника на 2×2 и больше — в уроке смешанные стратегии, понятие среднего — в статье математическое ожидание.

\overset{a}{ˉ}_{j} = i = 1 \sum m p_{i} a_{ij}, j = 1, \dots, n

средние выигрыши A против чистых столбцов B; оптимальная смесь уравнивает все

\overset{a}{ˉ}_{j}

на уровне цены игры

v

, поэтому сопернику всё равно, какой столбец играть

Частые вопросы

Чем смешанная стратегия лучше чистой?

Когда седла нет, чистая стратегия даёт только нижнюю цену $α$ : противник, угадав выбор, не даст больше. Смешанная стратегия гарантирует цену игры $v > α$ при любом поведении соперника, потому что все его ответы приводят к одному и тому же среднему. Платой за надёжность служит нестабильность отдельной партии: конкретный розыгрыш может принести и проигрыш.

Как найти вероятности оптимальной смеси для матрицы 2×2?

Уравнять средние выигрыши соперника по его столбцам: $p a_{11} + (1 - p) a_{21} = p a_{12} + (1 - p) a_{22}$ . Из уравнения выходит $p = (a_{22} - a_{21}) / (a_{11} + a_{22} - a_{12} - a_{21})$ . Для матрицы $(4213)$ получаем $p = (3 - 2) / (4 + 3 - 1 - 2) = 1/4$ и цену $v = 2, 5$ . Вероятности второго игрока ищут зеркально — по строкам. Для матриц большего размера оптимальные смеси находят симплекс-методом, сведя игру к задаче линейного программирования.