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

http://math.semestr.ru/games/smgame.php

В общем случае V* ≠ V* - седловой точки не существует. Оптимальное решение в чистых стратегиях также не существует. Однако, если расширить понятие чистой стратегии введением понятия смешанной стратегии, то удаётся реализовать алгоритм нахождения оптимального решения не вполне определённой игровой задачи. В такой ситуации предлагается использование статистического (вероятностного) подхода к нахождению оптимального решения антагонистической игры. Для каждого игрока, наряду с данным набором возможных для него стратегий, вводится неизвестный вектор вероятностей (относительных частот), с которыми следует применять ту или иную стратегию.

Обозначим вектор вероятностей (относительных частот) выбора заданных стратегий игрока A следующим образом: 
P = (p1, p2,…, pm), 
где pi≥ 0, p1 + p2 +…+ pm= 1. Величина pi называется вероятностью (относительной частотой) применения стратегии Ai.

Аналогично для игрока B вводится неизвестный вектор вероятностей (относительных частот) имеет вид: 
Q = (q1, q2,…, qn), 
где qj≥ 0, q1 + q2 +…+ qn = 1. Величина qj называется вероятностью (относительной частотой) применения стратегии Bj. Совокупность (комбинация) чистых стратегий A1, A2, …Am и B1, B2, …Bn в сочетании с векторами вероятностей выбора каждой из них называются смешанными стратегиями.

Основной теоремой в теории конечных антагонистических игр является Теорема фон Неймана: каждая конечная матричная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий. 
Из этой теоремы следует, что не вполне определённая игра имеет хотя бы одно оптимальное решение в смешанных стратегиях. В таких играх решением будет пара оптимальных смешанных стратегий P* и Q*, таких, что если один из игроков придерживается своей оптимальной стратегии, то и другому игроку не выгодно отклоняться от своей оптимальной стратегии. 
Средний выигрыш игрока A определяется математическим ожиданием: 
 
Если вероятность (относительная частота) применения стратегии отлична от нуля, то такая стратегия называется активной.

Стратегии P*, Q* называются оптимальными смешанными стратегиями, если MA(P, Q*) ≤ MA(P*, Q*) ≤ MA(P*, Q) (1) 
В этом случае MA(P*, Q*) называется ценой игры и обозначается через V (V* ≤ V ≤ V*). Первое из неравенств (1)означает, что отклонение игрока A от своей оптимальной смешанной стратегии при условии, что игрок B придерживается своей оптимальной смешанной стратегии, приводит к уменьшению среднего выигрыша игрока A. Второе из неравенств означает, что отклонение игрока B от своей оптимальной смешанной стратегии при условии, что игрок A придерживается своей оптимальной смешанной стратегии, приводит к увеличению среднего проигрыша игрока B.

Методы решения матричной игры в смешанных стратегиях

Итак, если седловая точка отсутствует, решение игры проводят в смешанных стратегиях и решают следующими методами:

1. Решение игры через систему уравнений. 
   Если задана квадратная матрица nxn (n=m), то вектор вероятностей можно найти, решив систему уравнений. Этот метод используется не всегда и применим только в отдельных случаях (если матрица 2x2, то решение игры получается практически всегда). Если в решении получаются отрицательные вероятности, то данную систему решают симплекс-методом.
2. Решение игры графическим методом. 
   В случаях, когда n=2 или m=2, матричную игру можно решить графически.
3. Решение матричной игры симплекс-методом. 
   В этом случае матричная игра сводится к задаче линейного программирования.