Нахождение оптимальных стратегий

Рассмотрим игру 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 уравнений, решая которые легко найти величины ,определяющие опти­мальную смешанную стратегию второго игрока.