Игры с решением в чистых стратегиях

Определение 16. Парную игру, в которой сумма выигрышей игроков равна нулю (выигрыш первого игрока равен проигрышу второго игрока), называют парной игрой с нулевой суммой или антагонистической игрой.

Замечание. Всякую парную игру с нулевой суммой всегда можно полностью задать платежной матрицей одного из игроков. Как правило, задают платежную матрицу первого игрока. Предполагается, что все игроки одинаково разумны. Задача каждого игрокасостоит в том, что каждый игрок стремится обеспечить себе максимально возможный выигрыш при любых действиях другого игрока.

Пусть – платежная матрица первого игрока в антагонистической игре двух игроков, имеющих соответственно и стратегий. Построим оптимальные стратегии игроков.

Оптимальная стратегия первого игрока. Первый игрок желает получить максимальный собственный выигрыш. При этом он предполагает, что в любом случае второй игрок выберет стратегию, минимизирующую выигрыш первого игрока. Задача первого игрока – получить некоторый гарантированный выигрыш. Обозначим минимальное значение выигрыша первого игрока при каждой его стратегии (в каждой строке матрицы ) , . Зная минимальные выигрыши при различных стратегиях второго игрока, первый игрок выберет ту стратегию, при которой максимально. Обозначим это значение . Тогда .

Определение 17. Величину – гарантированный максимальный выигрыш, который может обеспечить себе первый игрок, – называют нижней ценой игры или максимином.

Замечание. Формально оптимальная стратегия первого игрока состоит в выборе строки и в ней элемента матрицы : . Эту стратегию называют максиминной со стороны первого игрока. Если первый игрок будет придерживаться максиминной стратегии, то его выигрыш в любом случае будет не меньше максиминного значения.

Оптимальная стратегия второго игрока. Второй игрок желает минимизировать собственный проигрыш. При этом он предполагает, что в любом случае первый игрок выберет стратегию, максимизирующую собственный выигрыш. Задача второго игрока – проиграть не более некоторой гарантированной суммы. Обозначим максимальное значение выигрыша первого игрока при каждой стратегии второго игрока (в каждом столбце матрицы ) , . Зная максимальные выигрыши первого игрока при различных стратегиях второго игрока , второй игрок выберет ту стратегию, при которой минимально. Обозначим это значение . Тогда .

Определение 18. Величину – минимальный проигрыш, который может обеспечить себе второй игрок, – называют верхней ценой игры или минимаксом.

Замечание. Формально оптимальная стратегия второго игрока состоит в выборе столбца и в ней элемента матрицы : . Эту стратегию называют минимаксной со стороны второго игрока. Если второй игрок будет придерживаться минимаксной стратегии, то он в любом случае проиграет не больше минимаксного значения.

Теорема 1. Для произвольной прямоугольной матрицы всегда выполняется неравенство или .

Определение 19. Если верхняя цена игры равна нижней, то есть , то такую игру называют игрой с решением (седловой точкой) в чистых стратегиях.

Определение 20. Значение называют ценой игры (чистой ценой игры).

Определение 21. Элемент называют седловым элементом матрицы .

Замечание. Седловой элемент матрицы одновременно является минимальным в своей строке и максимальным в своем столбце, то есть

Определение 22. Пару чистых стратегий и , соответствующих элементу , называют седловой точкой игры.

Замечание. Стратегии и , образующие седловую точку платежной матрицы, являются оптимальными. Существование решения матричной игры в чистых стратегиях соответствует наличию состояния равновесия в данной матричной игре. Отклонение первого игрока от оптимальной стратегии уменьшает его выигрыш. Отклонение второго игрока от оптимальной стратегии увеличивает его проигрыш.

Определение 23. Тройку называют решением игры.

Пример 40.4. В игре участвуют два игрока. Каждый из них может записать независимо от другого цифры 1, 2 и 3. Если разность между цифрами, записанными игроками, положительна, то первый игрок выигрывает количество очков, равное разности между цифрами. Если разность отрицательна, то выигрывает второй игрок. Если разность нулевая, то игра заканчивается вничью. Составить платежную матрицу и найти цену игры.

Решение. Обозначим игроков А и В. У игрока А есть три стратегии: записать , , . У игрока В также есть три стратегии: , , . Данная игра является парной антагонистической игрой, следовательно, для ее формального описания достаточно задать платежную матрицу первого игрока. Вычислим возможные выигрыши первого игрока:

; ; ;

; ; ;

; ; .

Тогда платежная матрица первого игрока примет вид .

Найдем оптимальную стратегию первого игрока. Для этого найдем минимальный выигрыш при каждой его стратегии (минимальный элемент в каждой строке ):

, , .

Найдем нижнюю цену игры (выберем из выписанных минимальных элементов наибольший): . Таким образом, оптимальная стратегия первого игрока: – выписывать число 3.

Найдем оптимальную стратегию второго игрока. Для этого найдем максимальный выигрыш первого игрока при каждой стратегии второго игрока (максимальный элемент в каждом столбце ):

, , .

Найдем верхнюю цену игры (выберем из выписанных максимальных элементов наименьший): . Таким образом, оптимальная стратегия второго игрока: – выписывать число 3.

Ответ. Цена игры , решение игры .