Таким образом, исходя из (4), седловой элемент является минимальным в i0-й строке и максимальным в j0-м столбце в матрице А.
Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своем столбце. Если он является таковым, то он и есть седловой элемент, а пара стратегий, соответствующая ему, образует седловую точку.
Пара чистых стратегий (i0, j0) первого и второго игроков, образующая седловую точку и седловой элемент , называется решением игры.
Чистые стратегии i0 и j0, образующие седловую точку, называются оптимальными чистыми стратегиями соответственно первого и второго игроков.
Итак, если платежная матрица такова, что (3) имеет место, то поиск оптимального способа игры заканчивается. Но далеко не для всех матриц данное условие выполняется, т.е. не у всех матриц существует седловая точка.
Пример 1.
min | |||
А= | 1 | –1 | –1 |
–1 | 1 | –1 | |
max | 1 | 1 |
. Седловой точки нет.
Пример 2.
Найти решение игры
min | ||||
А= | 21 | 11 | 31 | 11 |
32 | 0 | 4 | 0 | |
max | 32 | 11 | 31 |
(1, 2) – седловая точка (значение 11).
Оптимальная чистая стратегия первого игрока – первая (i0 = 1), оптимальная чистая стратегия второго игрока – вторая (j0 = 2), цена игры равна 11 (v = 11).
Пример 3.
Найти решение игры
min | ||||
А= | 12 | 13 | 12 | 12 |
10 | 31 | 9 | 9 | |
max | 12 | 31 | 12 |
Две седловые точки (1, 1) и (1, 3) (значение 12).
В этой игре два оптимального решения: i0 = 1, j0 = 1, v = 12;
i0 = 1, j0 = 3, v = 12.
Пример 4
Найти решение игры
min | ||||
А= | 1 | –3 | –2 | –3 |
0 | 5 | 4 | 0 | |
2 | 3 | 2 | 2 | |
max | 2 | 5 | 4 |
Седловой точкой является пара (i0 = 3; j0 = 1), при которой v = a = b = 2.
Заметим, что хотя выигрыш в ситуации (3;3) также равен 2 = a = b, она не является седловой точкой, т.к. этот выигрыш не является максимальным среди выигрышей третьего столбца.
Пример 5
Найти решение игры
min | |||
А= | 10 | 30 | 10 |
40 | 20 | 20 | |
max | 40 | 30 |
Из анализа матрицы выигрышей видно, что a < b, т.е. данная матрица не имеет седловой точки.
Пример 6 . Сражение в море Бисмарка.
В 1943 году японский адмирал Кимура получил приказ переправить военный контингент через море Бисмарка к Новой Гвинее. Американский генерал Кинни получил приказ на перехват и бомбардировку японского флота. Кимура имел выбор между двухдневным маршрутом (северным) и трехдневным (южным). В свою очередь Кинни должен был решить, по какому маршруту послать самолеты в поисках японского транспорта: северному или южному. В случае ошибки самолеты возвращались в конце дня на свои базы и на следующий день могли быть посланы по другому маршруту.
Описанная ситуация может быть представлена следующей матрицей:
Кимура | |||
север | юг | ||
Кинни | север | 2, –2 | 2, –2 |
юг | 1, –1 | 3, –3 |
Выигрыши: (Кинни, Кимура).
Поскольку мы имеем игру с нулевой суммой, то ее можно свести к антагонистической игре с матрицей:
min | |||
А= | 2 | 2 | 2 |
1 | 3 | 1 | |
max | 2 | 3 |
Будем искать решение в чистых стратегиях:
игра имеет седловую точку: (Север, Север).
Пример 7
Найти решение игры
min | |||||
А= | 5 | 3 | 4 | 3 | 3 |
7 | 2 | 0 | –2 | –2 | |
10 | –1 | –4 | 2 | –4 | |
max | 10 | 3 | 4 | 3 |
Игра имеет два решения: i0 = 1, j0 = 2, v = 3
i0 = 1, j0 = 4, v = 3