13.2 Игры без седловых точек. Использование линейной оптимизации

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

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

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

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

Средний выигрыш первого игрока равен математическому ожиданию

и называется функцией выигрыша первого игрока в смешанных стратегиях. Данную формулу можно записать в матричном виде

где вектор-строка задает вероятности применения различных чистых стратегий первым игроком, - платежная матрица и задает вероятности применения чистых стратегий вторым игроком:

По формуле (13.6) легко найти выигрыши игроков в случае, когда один из них применяет чистую стратегию, а второй – смешанную.

Так, средний выигрыш первого игрока при условии, что он применяет чистую стратегию , а игрок B – смешанную стратегию, получается заменой в формулах (13.6) или (13.7) вектор- строки на :

Аналогично, средний выигрыш первого игрока при условии, что он применяет смешанную стратегию, а игрок В – некоторую чистую стратегию равен:

Приведем алгоритм нахождения оптимальных смешанных стратегий.

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

Стратегии, входящие в оптимальные смешанные стратегии, называются активными.

Смешанная стратегия, которая гарантирует игроку наибольший возможный средний выигрыш (или наименьший возможный средний проигрыш), называется его оптимальной смешенной стратегией.

Определение смешанных стратегий с помощью линейной оптимизации

Пусть игра не имеет оптимального решения в чистых стратегиях, т.е. седловая точка отсутствует .

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

Будем искать решение игры в смешанных стратегиях:

; .

Применение игроком I оптимальной смешанной стратегии гарантирует ему, независимо от поведения игрока II, выигрыш, не меньший цены игры  .

Пусть игрок II применяет свою активную чистую j-ю стратегию, а игрок I - свою оптимальную стратегию . Тогда средний выигрыш игрока I будет равен

Учитывая, что не может быть меньше , запишем условия:

Разделив левую и правую части каждого из неравенств (10.3) на цену игры , получим:

При использовании обозначений

неравенства (10.5) примут вид:

где, очевидно, все , так как .

Условие нормировки с учетом определения (13.13) дает следующее соотношение

Учитывая, что игрок I стремится максимизировать , получаем линейную функцию

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

Решение задачи линейной оптимизации позволяет найти цену игры и оптимальную стратегию первого игрока:

Аналогично можно показать, что оптимальная стратегия второго игрока определяется по формулам

где - неотрицательные решения задачи линейной оптимизации, двойственной по отношению к исходной задаче:

,

а переменные

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

Исходная задача	Двойственная задача

Цена игры и вероятности применения стратегий игроками I и II равны:

Проиллюстрируем вышесказанное на двух простых примерах.

Пример 1. Определение оптимальных смешанных стратегий

Найдем решение парной игры с платежной матрицей ( )

II I	1	2	3	4
1	24	20	18	21
2	19	22	24	20
3	14	16	20	25

Вероятности применения стратегий могут быть получены решением систем

Решение этих задач ЛП дает оптимальные смешанные стратегии первого

и второго игроков

а также цену игры

Пример 2. Определение выигрышей в игре без седловых точек

Пусть задана платежная матрица игры

	0	1/2	5/6
	1	3/4	1/2

и смешанные стратегии игроков А и В уже определены:

Требуется определить выигрыши игрока А в ситуациях, когда

1. игрок В применяет смешанную стратегию;

2. игрок В применяет чистую стратегию ;

3. игрок В применяет чистую стратегию ;

4. игрок В применяет чистую стратегию .

Решение.

По формуле (**) определяем средний выигрыш игрока A в случае, когда оба игрока применяют смешанные стратегии

По формуле (****) определяем выигрыши игрока А для случаев, когда игрок B применяет свои 1-ю, 2-ю и 3-ю стратегии соответственно

Таким образом, в данном случае игроку А выгодно, чтобы игрок В применил свою стратегию , так как это приведет к увеличению выигрыша игрока А.