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

Рассмотрим игру G=(X, Y, L) с матрицей т´п. Будем считать, что в игре G отсутствует седловая точка.

Обозначим через распределение вероятностей применение оптимальной сме­шанной стратегии первым игроком. Некоторые могут быть равны нулю. Это означает, что соответствующая стратегия не является полезной. Перед нами стоит задача найти значения для i=1, ...,т.

Предположим, что второй игрок использует стратегию у_k . Если это полезная стратегия, то выигрыш первого игрока будет равен v, если же эта стратегия не являет­ся полезной, то выигрыш первого игрока может быть и больше v. Следовательно, в общем случае имеет место:

(1)

Такие выражения могут быть составлены для каждой чистой стратегии второго игрока, т. е. для i=1, ..., п. Кроме того, известно, что

(2)

Будем считать v>0. Это будет выполняться всегда, если все элементы матрицы игры q_ik положительны. Если же среди элементов q_ik имеются отрицательные, то их можно сделать положительными, прибавив ко всем элементам матрицы игры некоторое число 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 уравнений, решая которые легко найти величины ,определяющие опти­мальную смешанную стратегию второго игрока.