10.4. Игра m´n с Седловыми
точками
Рассмотрим общий случай игры с
платёжной матрицей порядка m´n.
.
В данном случае
первый игрок имеет m чистых стратегий. Количество чистых
стратегий второго игрока – n.
Найдём
оптимальные стратегии каждого из игроков, т.е. такие стратегии, применение
которых обеспечивает игроку наибольший гарантированный выигрыш при всевозможных
действиях противника.
Если первый
игрок выбирает первую стратегию, которая описывается первой строкой, то ему
гарантированно будет уплачен выигрыш, равный либо больший минимального элемента
первой строки 
. Индексом j мы
будем обозначать столбцы матрицы.
При выборе i-той строки (строки будем обозначать индексом
i) выигрыш первого игрока 
.
Естественно,
что первый игрок стремится получить как можно больший гарантированный выигрыш.
Для этого он должен выбрать стратегию i такой,
чтобы 
был как можно больше,
т.е. найти максимальный элемент для всех i=1…m. Итак, для первого игрока существует
выбор 
, который
гарантирует ему выигрыш не меньший
при всевозможных стратегиях второго игрока.
Обозначим
найденный элемент матрицы через a, а строку и столбец, на пересечении
которых он находится, через 
и 
:
. (10.1)
Минимальный
выигрыш, который может гарантировать себе первый игрок, применяя свои чистые
стратегии, при всевозможных действиях второго игрока называется нижней чистой ценой игры. Мы обозначили
ее через a, которую вычисляли по формуле (10.1).
Второй
игрок стремится проиграть как можно меньше. Его стратегии описываются столбцами
в платежной матрице. При выборе 1-й стратегии максимум, что он может проиграть:
.
Если он сделает j-й ход, то его проигрыш будет меньше либо равен:
(10.2)
в зависимости от выбора стратегии
первым игроком. Для того чтобы уменьшить выигрыш первого игрока при всех его
возможных действиях, второй должен отыскать такую свою стратегию 
, при которой платеж из множества вышерассмотренных элементов
(10.2) будет минимален. Т.е. второй игрок должен найти
Обозначим этот платеж через b
(10.3)
Минимальный проигрыш,
который может гарантировать себе второй игрок, за счет применения своих чистых
стратегий, при всевозможных действиях первого, называется верхней чистой ценой игры. Верхняя чистая цена игры находится по
формуле (10.3).
Если
в игре нижняя и верхняя цены совпадают, т.е. a=b, то говорят, что эта игра имеет седловую точку в чистых стратегиях и a и b
называют просто ценой игры:
v=a=b,
. (10.4)
Образующие
седловую точку стратегии и являются оптимальными
стратегиями, которые должны применять соответственно первый и второй игрок при
отсутствии информации о предполагаемом ходе противника. Если первый игрок
придерживается своей чистой стратегии , а второй игрок – нет, то выигрыш первого может быть и
больше, чем 
. Таким образом, для каждой стратегии j будет справедливо неравенство:
(т.е. 
). (10.5)
Если же произойдет
обратная ситуация: первый игрок не будет следовать стратегии , а второй воспользуется своей чистой стратегией , то выигрыш первого будет меньше, чем мог бы. И для любого i верно:
.
(10.6)
Объединяя неравенства (10.5) и (10.6),
можно записать:
. (10.7)
Исходя из неравенства (10.7),
можно сказать, что седловой элемент платежной матрицы А 
является минимальным в
-й строке и максимальным в -том столбце.
Седловая точка матрицы А – это пара целых чисел (,), для которых является одновременно
минимумом -й строки матрицы и максимумом -того столбца.
Понятие
седловой точки можно ввести и для функции двух переменных. Определение седловой точки для двумерной функции
будет таким.
Пусть f(x,y) – действительная функция,
определенная для всех xÎА и yÎB. Тогда точка (x0,y0) из области
определения называется седловой точкой
функции f(x,y), если
выполняются условия:
1) f(x,
)£ f(
)
для всех xÎA;
2) f(,)£ f(,
)
для всех yÎВ.
Из определения седловой точки матрицы
А вытекает алгоритм ее нахождения:
1. Для каждой строки матрицы А найти минимальный элемент.
2. Проверить, является ли этот элемент
максимальным в своем столбце. Если он таковым является, то это и есть седловой
элемент, а пара соответствующих ему чистых стратегий (,) (найденные строка и столбец) образуют седловую точку. Если
элемент не является максимальным в столбце, то необходимо продолжить поиск.
Пара чистых стратегий (,) игроков, образующая седловую точку, и седловой элемент называется решением игры.
Пример 10.3.
Игра задана следующей платежной матрицей
.
Найти решение данной игры.
Решение.
Рассмотрим первую строку и найдем в ней минимальный элемент. Это элемент -4
третьего столбца. Он не является максимальным в своем столбце. Значит это не
седловой элемент.
Минимальный элемент 2-ой строки – -2 также не является седловым, т.к. -2
не максимальный элемент 4-го столбца.
Найдем минимальный элемент 3-ей строки. Это 3. Этот элемент является
максимумом своего (второго) столбца. Значит седловой элемент – 3, седловая
точка – пересечение 3-й и 2-й оптимальных чистых стратегий игроков (рис 10.2).
Рис.10.2
Покажем,
действительно ли это седловая точка. Минимальные элементы строк: -4; -2; 3.
Максимальный из них 3. Это и есть по определению нижняя чистая цена игры.
Максимальные
элементы столбцов: 10; 3; 4; 5. Минимальный из них - верхняя чистая цена игры –
3. Таким образом, верхняя и нижняя цены совпадают и 3, по определению, седловая
элемент.
Итак, мы нашли
решение игры. Цена игры – 3. Оптимальная чистая стратегия первого игрока -
третья, оптимальная чистая стратегия второго игрока - вторая.
Рассмотрим
теорему об эквивалентности определения седловой точки и соотношения (10.4).
Теорема 1. Пусть для вещественной функции 
при xÎA и yÎВ существует
и 
.
Тогда необходимым и достаточным
условием того, что
является
существование седловой точки функции . Кроме того, если 
- седловая точка функции , то
.
Следствие 1. Пусть задана матрица А
.
Необходимым и
достаточным условием того, что 
является существование
седловой точки матрицы А. Кроме того,
если (,) - седловая точка матрицы А, то 
.
Предыдущая | Главная | Глава 10 | Следующая