Нахождение оптимальных стратегий
Рассмотрим игру G=(X, Y, L) с матрицей т´п. Будем считать, что в игре G отсутствует седловая точка.
Обозначим через распределение вероятностей применение оптимальной смешанной стратегии первым игроком. Некоторые
могут быть равны нулю. Это означает, что соответствующая стратегия
не является полезной. Перед нами стоит задача найти значения
для i=1, ...,т.
Предположим, что второй игрок использует стратегию уk . Если это полезная стратегия, то выигрыш первого игрока будет равен v, если же эта стратегия не является полезной, то выигрыш первого игрока может быть и больше v. Следовательно, в общем случае имеет место:
(1)
Такие выражения могут быть составлены для каждой чистой стратегии второго игрока, т. е. для i=1, ..., п. Кроме того, известно, что
(2)
Будем считать v>0. Это будет выполняться всегда, если все элементы матрицы игры qik положительны. Если же среди элементов qik имеются отрицательные, то их можно сделать положительными, прибавив ко всем элементам матрицы игры некоторое число v'>0. При этом цена игры увеличится также на величину v'.
Поделим уравнения (1) и (2) на v, обозначив
Очевидно, что рi>0. Неравенства (1) при k = 1, ..., п запишутся при этом в виде
(3)
а соотношение (2) примет вид:
(4)
В линейные неравенства входят неизвестные величины р1,..., рт, определяющие смешанную стратегию первого игрока. Определение оптимальной смешанной стратегии требует нахождения такого решения системы (3), при котором величина v становится максимальной, а следовательно, линейная форма (4) принимает минимальное значение. Но это есть обычная задача линейного программирования.
Для удобства в выражениях (3) следует перейти от неравенств к равенствам, вычтя из правых частей положительные добавочные неизвестные , что дает систему уравнений
Решая систему при условии минимизации линейной формы (4), мы находим смешанную стратегию первого игрока, цену игры v и полезные стратегии второго игрока .
Для нахождения распределения вероятностей применение оптимальной смешанной стратегии вторым игроком , содержащей k неизвестных, необходимо составить k уравнений. Одно из них
Остальные k—1 уравнений получим, составив выражения для средних потерь при оптимальной смешанной стратегии второго игрока и при любых k—1 полезных стратегиях первого игрока. Так, для полезной стратегии будем иметь уравнение
Составив k — 1 уравнений и добавив к ним предыдущее уравнение, получим k уравнений, решая которые легко найти величины ,определяющие оптимальную смешанную стратегию
второго игрока.