3. Решение игры в смешанных стратегиях.

Смешанная стратегия стороны А обозначается:

,

где р_i , - частоты , с которыми применяются стратегии , причем . Аналогично, для стороны В ее оптимальная стратегия обозначается:

,

где ,

q_j , - частоты применения стратегий В_j стороной В.

Имеет место следующая фундаментальная теорема теории игр.

Теорема. Любая парная игра с нулевой суммой имеет оптимальное решение в чистых или смешенных стратегиях.

Если платёжная матрица не имеет седловую точку, то решение имеется в смешенных стратегиях .

Пусть платежная матрица имеет вид:

Таблица 2.

Ai	Bj
	B1	B2	...	Bn
A1 A2 ... Am	r11 r21 ... rm1	r12 r22 ... rm2	... ... ... ...	r1n r2n ... rmn

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

Если сторона А применяет оптимальную стратегию то её выигрыш будет не меньше, чем n. Тогда для любой стратегии B_j стороны B будут иметь место соотношения:

причём .

Разделим систему неравенств на n > 0 и обозначим .

Тогда:

x_i ³ 0

При этом .

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

Таким образом , пришли к следующей задаче линейного программирования (ЗЛП):

min L_A = x₁ + x₂ + ... + x_m

x_i ³ 0

Решая задачу, находят оптимальные значения и min L_А .

Ожидаемый выигрыш определяется по формуле: , а вероятности чистых стратегий А_i по формулам: . Таким образом оптимальная стратегия - определенна.

Аналогично, для нахождения оптимальной стратегии стороны В решается следующая ЗЛП:

Решая ЗЛП, находят y_i и max L.

Тогда и .

Оптимальная стратегия .

Очевидно, что (на основании теоремы).

Можно показать, что задачи минимизации L_A и максимизации L_B являются парой двойственных задач. Поэтому можно решать одну из них, а потом по соотношениям двойственности находить решение другой.

Пример. Решить парную игру с нулевой суммой, заданную платежной матрицей:

В

А

Здесь . Так как , значит что игра решается в смешенных стратегиях.

Составим ЗЛП для оптимальной стратегии стороны В (так как не надо будет вводить искусственные переменные для приведения задачи к стандартной форме):

y_{j ³} 0, S_i ³ 0

Решим задачу симплекс-методом /2/. Исходная таблица имеет вид:

Таблица 3.

БП	y1	y2	y3	S1	S2	S3	Pешение
L	-1	-1	-1	0	0	0	0
S1	1	2	3	1	0	0	1
S2	4	0	1	0	1	0	1
S3	2	3	0	0	0	1	1

Оптимальная симплекс таблица имеет следующий вид:

Таблица 4.

БП	y1	y2	y3	S1	S2	S3	Pешение
L	0	0	0	11/37	4/37	5/37	20/37
y3	0	0	1	12/37	1/37	-8/37	5/37
y1	1	0	0	-3/37	9/37	2/37	8/37
y2	0	1	0	2/37	-6/37	11/37	7/37

Таким образом, решение задачи имеет вид:

y₁ = 8/37, y₂ = 7/37, y₃ = 5/37, L_B = 20/37.

Тогда средний выигрыш игры равен .

Частоты чистых стратегий B_j равны:

Таким образом, оптимальная смешанная стратегия стороны B имеет следующий вид:

Оптимальную смешанную стратегию стороны А найдем из соотношений двойственности /3/. Решение двойственной задачи линейного программирования определим из соотношения:

Вектор коэффициентов при оптимальных базисных переменных решенной задачи : . Обратная матрица базиса:

Тогда вектор переменных двойственной задачи имеет вид:

, то есть .

Значения целевых функций прямой и двойственной задач линейного программирования совпадают. Таким образом:

и n = 1.85.

Тогда вероятности чистых стратегий A_i равны:

Оптимальная смешанная стратегия стороны А:

.

Таким образом решение игры в смешенных стратегиях имеет вид:

и цена игры .