j i
Определение. Число
, определяемое по формуле (2), называется чистой верхней ценой игры и показывает, какой максимальный выигрыш за счет своих стратегий может себе гарантировать игрок 1.Другими словами, применяя свои чистые стратегии, игрок 1 может обеспечить себе выигрыш не меньше
, а игрок 2 за счет применения своих чистых стратегий может не допустить выигрыш игрока 1 больше, чем .Переходя к рациональному представлению матрицы игры, отметим, что стратегии двух игроков сводятся в таблицу, а непосредственно само представление упрощает поиск решения матричных игр.
ПРИМЕР 3: Провести SP-разбиение матрицы игры (Н)
X1 | 2 | 3 | 4 | 5 |
X2 | 1 | 4 | 0 | 5 |
X3 | 1 | 0 | 6 | 7 |
X4 | 1 | 2 | 3 | 4 |
Y1 | Y2 | Y3 | Y4 |
2 | 3 | 4 | 5 | 2 | |
1 | 4 | 0 | 5 | 0 | |
1 | 0 | 6 | 7 | 0 | |
1 | 2 | 3 | 4 | 1 | |
2 | 4 | 6 | 7 |
Решение: вычисляем верхнюю и нижнюю цену игры
Исходная игра имеет SP
(x1,y1) в чистых стратегиях. Существование SPв чистых стратегиях матричной игры с полной информацией позволяет провести SP-разбиение (Н) исходной игры: .Формирование SP- разбиения матричной игры с SPпо существу и является рациональным представлением исходной матрицы (Н) игры. Значит, понятие рациональности представления матрицы игры преследует цель сформулировать методы рационального преобразования платёжной матрицы с целью вычисления цены игры vили упрощения построения подыгры-решения.
Далее рассмотрим такое понятие, как решение, при помощи фиктивного разыгрывания. Есть 2 игрока, которые без теории игр, хотят сделать игру несколько раз, причём каждый из них склонен к статистике и оценивает стратегию своего противника. При каждом разыгрывании противоборствующие стороны стремятся максимизировать свой ожидаемый выигрыш против наблюдаемого вероятностного распределения противника: если игрок 2 использует j-ю стратегию
раз, то игрок 1 выберет i-ю стратегию, чтобы максимизировать . Аналогично, если игрок 1 использует i-ю стратегию раз, то игрок 2 выберет j-ю стратегию, чтобы минимизировать . Условно эмпирические распределения сходятся к оптимальным стратегиям. Точнее, пусть - число использований первым игроком i-ой стратегии в течение первых Nрозыгрышей. Пусть , то тогда является смешанной стратегией. Здесь справедливо утверждение о том, что предел любой сходящейся подпоследовательности является оптимальной стратегией, т.е. если и полученные стратегии игроков 1 и 2, то выполняется равенство . Такой метод полезен в случае игры с большим числом стратегий.Опишем некоторые свойства решений матричных игр. Пусть G(X,Y,A) – игра двух лиц с нулевой суммой, в которой игрок 1 выбирает стратегию
, а игрок 2 - , после чего игрок 1 получает выигрыш A=A(x,y) за счёт игрока 2.Свойство 1: Если чистая стратегия одного из игроков содержится в спектре (спектр – множество чистых стратегий, вероятность которых положительна) некоторой его оптимальной стратегии, то выигрыш этого игрока в ситуации, образованной данной стратегией и любой оптимальной стратегией другого игрока, равен значению конечной антагонистической игры.
Свойство 2: Ни одна доминируемая чистая стратегия игрока не содержится в спектре его оптимальной стратегии.
Свойство 3: Если
– конечная антагонистическая игра, а , подыгра игры Gпричём - чистая стратегия игрока 1 в игре G, доминируемая над некоторой стратегией , спектр которой не содержит . Тогда всякое решение игры является решением игры G.Свойство 4: Тройка
является решением игры <=>, когда является решением игры , где а – любое вещественное число, к>0ГЛАВА 2. Игры с нулевой суммой в чистых стратегиях
2.1 Вычисление оптимальных стратегий на примере решения задач
Используя теорему о минимаксе, можно утверждать, что каждая антагонистическая игра имеет оптимальные стратегии.
Теорема: пусть А – матричная игра и строки
данной матрицы являются доминирующими. Тогда игрок 1 имеет такую оптимальную стратегию х, что ; кроме того, любая оптимальная стратегия для игры, получающаяся в результате удаления доминирующих строк, будет также оптимальной для первоначальной игры.Пример 1. Игра доминирования
Рассмотрим игру с матрицей
. Здесь второй столбец доминирует 4 и игрок 2 соответственно не будет использовать 4 стратегию. Поэтому можно рассмотреть матрицу следующего вида . В этой матрице третья строка доминирует первую. При удалении получается матрица . А в этой матрице третий столбец доминируется вторым. Следовательно, исходная матрица сводится к следующей матрице .Пример 2. Игра на уклонение.
Предполагается, что игроки выбирают целые числа iи jмежду 1 и n, а игрок 1 выигрывает величину
, т.е. расстояние между iиj. Пусть первый игрок придерживается стратегии , тогда для всех (( - значение игры).· Пусть
нечётно, тогда игрок 2 имеет чистую стратегию для всех