56. Смешанные стратегии. Основная теорема теории игр. (ходы→∞).

Если игра не имеет седловой точки, то применение чистых стратегий не дает оптимального решения игры.

Смешанной стратегией S_A игрока А называется применение чистых стратегий A₁, A₂, ..., A_m с вероятностями p₁, p₂, ..., p_i, ..., p_m причем сумма вероятностей равна 1:   Смешанные стратегии игрока Азаписываются в виде матрицы

или в виде строки S_A = (p₁, p₂, ..., p_i, ..., p_m) Аналогично смешанные стратегии игрока В обозначаются:

, или,

SB = (q1, q2, ..., qi, ..., qn),

где сумма вероятностей появления стратегий равна 1: 

Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой 1 соответствует чистой стратегии. На основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий S*_A , S*_B в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры v. Цена игры удовлетворяет неравенству:

α ≤ v ≤ β

(3.5)

где α и β — нижняя и верхняя цены игры. Справедлива следующая основная теорема теории игр — теорема Неймана. Каждая конечная игра имеет по крайней мере одно оптимальное решение, возможно, среди смешанных стратегий. Пусть S*_A = (p*₁, p*₂, ..., p*_i, ..., p*_m) и S*_B = (q*₁, q*₂, ..., q*_i, ..., q*_n) — пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной.

Справедлива основная теорема об активных стратегиях: если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий.

Эта теорема имеет большое практическое значение — она дает конкретные модели нахождения оптимальных стратегий при отсутствии седловой точки.

Рассмотрим игру размера 2×2, которая является простейшим случаем конечной игры. Если такая игра имеет седловую точку, то оптимальное решение — это пара чистых стратегий, соответствующих этой точке.  Игра, в которой отсутствует седловая точка, в соответствии с основной теоремой теории игр оптимальное решение существует и определяется парой смешанных стратегий S*_A = (p*₁, p*₂) и S*_B = (q*₁, q*₂).

Для того чтобы их найти, воспользуемся теоремой об активных стратегиях. Если игрок А придерживается своей оптимальной стратегии S'_A, то его средний выигрыш будет равен цене игры v, какой бы активной стратегией ни пользовался игрок В. Для игры 2×2 любая чистая стратегия противника является активной, если отсутствует седловая точка. Выигрыш игрока А (проигрыш игрока В) — случайная величина, математическое ожидание (среднее значение) которой является ценой игры. Поэтому средний выигрыш игрока А (оптимальная стратегия) будет равен v и для 1-й, и для 2-й стратегии противника.

Пусть игра задана платежной матрицей

Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию  , а игрок В — чистую стратегию B₁ (это соответствует 1-му столбцу платежной матрицы Р), равен цене игры v: a₁₁ p*₁+ a₂₁ p*₂= v. Тот же средний выигрыш получает игрок А, если 2-й игрок применяет стратегию B₂, т.е. a₁₂ p*₁+ a₂₂ p*₂= v. Учитывая, что p*₁+ p*₂= 1, получаем систему уравнений для определения оптимальной стратегии S'_A и цены игры v:

(3.6)

Решая эту систему, получим оптимальную стратегию

(3.7)

и цену игры

(3.8)

Применяя теорему об активных стратегиях при отыскании SВ*- оптимальной стратегии игрока В, получаем, что при любой чистой стратегии игрока А (А1 или А2) средний проигрыш игрока В равен цене игры v, т.е.

(3.9)

Тогда оптимальная стратегия определяется формулами:

(3.10)