Решение матричных игр в смешанных стратегиях
Однако не все матрицы имеют седловую точку. Тогда решение находят, применяя смешанные стратегии, то есть, чередуя случайным образом несколько чистых стратегий (гибкая тактика). Согласно основному неравенству теории игр нижняя цена игры никогда не может быть больше верхней цены игры, т.е. 
. Следовательно, если нижняя цена игры – это то, что игрок А согласен получить в результате игры, а верхняя цена игры – это то, что игрок В согласен отдать игроку А в процессе игры, тогда в случае отсутствия седловой точки 
возникает желание у обоих игроков рискнуть, чтобы получить больший выигрыш в игре.
То есть, игрокам надо так выбирать свои чистые стратегии в очередной партии, чтобы партнер не догадался о них. Этого можно добиться только тогда, когда сам не знаешь, какую стратегию будешь использовать при очередном ходе. Анализ игры без седловой точки показывает, что игрок А выигрывает больше максимина α, получаемого им при максиминной стратегии, если в ходе игры будет пользоваться не одной, а несколькими чистыми стратегиями, т.е. будет смешивать чистые стратегии. Аналогично – игрок В проигрывает меньше минимакса β, выплачиваемого им игроку А, при минимаксной стратегии, если он будет использовать свою смешанную стратегию.
Вектор, каждая из компонент которого показывает вероятность использования игроком соответствующей чистой стратегии, называют смешанной стратегией данного игрока. Из этого определения следует, что сумма компонент этого вектора равна единице, а сами компоненты не отрицательны.
Обычно смешанную стратегию первого игрока обозначают как вектор
U = 
,
где рi – вероятность выбора игроком А i-ой стратегии.
а второго игрока – как вектор
Z = 
,
где qj, ≥ 0 – вероятность выбора игроком B j-ой стратегии
.
Если рo – оптимальная стратегия первого игрока, q° - оптимальная стратегия второго игрока, то число
- называют ценой игры.
Для того чтобы число υ – было ценой игры, а po и q° – оптимальными стратегиями, необходимо и достаточно выполнение неравенств:
, где (j = 1,...,n),
, где (i = 1,...,m).
Если один из игроков применяет оптимальную смешанную стратегию, то его выигрыш равен цене игры и не зависит от того, с какими частотами будет применять второй игрок стратегии, вошедшие в оптимальную, в том числе и чистые стратегии.
Пример. Найти решение игры, заданной матрицей 
.
Решение
Сначала, проверяется наличие седловой точки.
Таблица 3.
| В1 | В2 |  | |
| А1 А2 | 2(Т1) 4(Т2) | ||
 |
Для этого определяются минимальные элементы в каждой из строк (2 и 4) и максимальные элементы в каждом из столбцов (6 и 5) (Табл. 3).
Значит, нижняя цена игры
,
верхняя цена игры
.
Так как α = 4 ≠ β = 5, то игра седловой точки не имеет и ее решение – смешанные оптимальные стратегии, а цена игры 
лежит в пределах 4≤ ≤5.
Пусть для игрока А стратегия задается вектором U = (p1, p2). Тогда при применении игроком В чистой стратегии В1 или В2 игрок А получит средний выигрыш, равный цене игры, то есть
Из решения трех уравнений с тремя неизвестными оптимальная стратегия игрока А1: 
; 
; v = 
.
Пусть для игрока В стратегия задается вектором Z = (q1, q2). Тогда:
Отсюда оптимальная стратегия игрока В: 
Следовательно, решением игры будут смешанные стратегии 
, 
с оценкой игры v = . Таким образом, если, например, имеется многоходовая игра, то из пяти партий игрок А два раза выбирает первую стратегию и три раза выбирает вторую стратегию, а игрок В один раз использует первую стратегию, и четыре раза – вторую стратегию. В этом случае выигрыш является оптимальным для двух сторон.
Сведение задач теории игр к задачам линейного программирования
Пусть задана платежная матрица игры:
.
Для оптимальной стратегии первого игрока 
и цены игры выполняется неравенство:
, где (j = 1,...,n),
Разделив обе его части на получим:
1.
Обозначив, 
получим:
Так как первый игрок стремится получить максимальный выигрыш, то он должен обеспечить минимум величине 1/ . С учетом этого определение оптимальной стратегии первого игрока сводится к нахождению минимума функции:
при условиях:
.
Аналогично определение оптимальной стратегии второго игрока сводится к нахождению максимума функции:
при условиях:
,
где 
.
Таким образом, чтобы найти решение данной игры по матрице А, нужно составить следующую пару двойственных задач и найти их решение.
| Прямая задача (задача второго игрока) | Двойственная задача (задача первого игрока) |
| Целевая функция | |
| Z(x) = x1 + x2 + … + xn → max | U(y) = y1 + y2 + … + ym → min |
| Функциональные ограничения | |
| а11х1 + а12х2 + … + а1nхn ≤ 1 a21х1 + а22х2 + … + а2nхn ≤ 1 … … … am1х1 + аm2х2 + … + аmnхn ≤ 1 | а11у1 + а21у2 + … + аm1уm ≥ 1 а12у1 + а221у2 + … + аm2уm ≥ 1 … … … а1nу1 + а2nу2 + … + аmnуm ≥ 1 |
| Прямые ограничения | |
| x1 ≥0, x2 ≥0, … , xn≥0 | y1 ≥0, y2 ≥0, … , ym≥0 |
Используя решения пары задач, можно выявить оптимальные стратегии и цену игры:
; 
; 
.
Итак, для того чтобы решить игру с использованием методов линейного программирования выполняют следующее:
1) составляют пару двойственных задач, эквивалентных данной игре;
2) определяют оптимальные планы двойственных задач;
3) находят решение игры по соотношениям между планами задач, оптимальными стратегиями и ценой игры.
Замечание: Т.к. в задачах линейного программирования существует требование неотрицательности переменных, то для приведения матричной игры к задаче линейного программирования необходимо, чтобы элементы платежной матрицы были бы положительными 
. Если 
, то ко всем элементам платежной матрицы необходимо добавить некоторое число 
так, чтобы новые элементы платежной матрицы были бы положительны 
. Тогда после нахождения оптимального решения 
; 
необходимо исправить цену игры: 
.