Решение матричных игр

Аналогично игрок 2 при оптимальном своём поведении должен стремится по возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается , то есть определяется наибольший выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию. Затем отыскивается такая стратегия игрока 2 j = j0, при которой игрок 1 получит минимальный выигрыш, то есть находится значение
,(3)
которое называют верхней ценой игры или минимаксом. Стратегия j0 называется минимаксной стратегией игрока 2.
Справедливо следующее соотношение между нижней и верхней ценами игры.
Лемма. Для любой матричной игры имеет место неравенство .
Оптимальной в игре естественно считать ситуацию (i0, j0), отклоняться от которой не выгодно никому из игроков. Такую ситуацию называют равновесной.
Определение. Говорят, что матричная игра имеет седловую точку в чистых стратегиях, если выполнено условие . При этом число называют чистой ценой игры.
Седловая точка это пара чистых стратегий (i0, j0) соответственно игроков 1 и 2, при которых достигается равенство . Это такая точка, для которой выполнены неравенства
(4)
Из неравенств (4) следует, что седловой элемент является минимальным в i0-й строке и максимальным в j0-м столбце матрицы А. Следовательно, отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если это так, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку.
Если игра имеет седловую точку, то она называется вполне определенной. Пара чистых стратегий (i0, j0) игроков 1 и 2, образующая седловую точку, и чистая цена игры называется решением игры. При этом i0 и j0 называют оптимальными чистыми стратегиями соответственно игроков 1 и 2.
Пример 1.
Седловая точка (3,1), цена игры , так как элемент а31 минимальный в третьей строке и при этом максимальный в первом столбце.
Пример 2.
Найдем нижнюю цену игры: , , .
Найдем верхнюю цену игры: , , .
Нижняя и верхняя цены игры различны, значит, игра не имеет седловой точки.