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

Теорема 3. Для того чтобы смешанные стратегии и были оптимальными в игре с матрицей (1) и ценой игры u, необходимо и достаточно, чтобы выполнялись следующие неравенства:

³ u; j = , причем = 1; (3)

£ u; i = , причем = 1. (4)

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

Пусть требуется найти оптимальные стратегии для игры с заданной платежной матрицей (1), для которой a_ij строго больше нуля (а_ij >0, i= ,j = ), тогда цена игры u > 0. Найдем оптимальную стратегию игрока А – ().

Разделим левую и правую части в выражении (3) на положительную величину u:

³ 1; = .

Введем обозначение = Х_i, тогда

Х_i ³ 1; j = ; = .

Поскольку игрок А стремится сделать свой гарантированный выигрыш (u) как можно большим (u ® max), то величина должна быть как можно меньше (u ® min), тогда имеем следующую задачу линейного программирования:

f(x) = ® min, (5)

Х_i ³ 1; j = , (6)

Х_i ³ 0; i = . (7)

Если Х* = (, ,… … ) – оптимальный план задачи (5) – (7), а минимум функции f(x) = f(x*) = f*, то цена игры u при этом составит u = , а т.к. = Х_i, тогда = (u × ,… u × ) = (,… ) – оптимальная смешанная стратегия игрока А.

Для игрока В используя выражение (4), получим

g(y) = ® max.

y_j £ 1, i = .

y_j ³ 0; j = .

Решение игры u = ; = (u × ,… u × ) = (,… ).

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

Сведем данную задачу к задаче линейного программирования.

Найдем оптимальную стратегию игрока А – ():

f(x) = X₁ + X₂ ® min.

X₁ + 8X₂ ³ 1,

10X₁ + 4X₂ ³ 1,

3X₁ + 5X₂ ³ 1,

X₁, X₂ ³ 0.

f(x) = 0,21; X₁ = 0,026; X₂ = 0,184,

отсюда

u = = 4,76; P₁ = 4,76 × 0,026 = 0,124; P₂ = 4,76 × 0,184 = 0,876.

Найдем оптимальную стратегию игрока В – ():

g(y) = y₁ + y₂ + y₃ ® max.

y₁ + 10y₂ + 3y₃ £ 1,

8y₁ + 4y₂ + 5y₃ £ 1,

y₁, y₂ , y₃ ³ 0.

g(y) = 0,21; y₁ = 0; y₂ = 0,0526; y₃ = 0,158,

отсюда

q₁ = 0; q₂ = 4,76 × 0,0526 = 0,25; q₃ = 4,76 × 0,158 = 0,75.

Таким образом, применяя свою первую чистую стратегию с вероятностью 0,124 и вторую – с вероятностью 0,876, игрок А выигрывает величину 4,76. Игрок В, применяя свою вторую чистую стратегию с вероятностью 0,25 и третью – с вероятностью 0,75, проигрывает величину 4,76, иначе он проигрывает больше.

Игра два на два (2 х 2)

Рассмотрим игру, в которой у игроков А и В по две стратегии. Платежная матрица имеет вид

Рассмотрим случай, когда игра не имеет седловой точки.

Теорема 4. Пусть и – оптимальные смешанные стратегии игры с платежной матрицей (1) и ценой игры u, тогда для любого i, при котором выполняется строгое неравенство

q_j < u,

имеет место равенство p_i = 0. А если p_i > 0, то

q_j = u.

Аналогично, если для некоторых j

× p_i > u,

то для этих j q_j = 0. А если q_j > 0, то

× p_i = u.

Определим оптимальную смешанную стратегию игрока А, а для этого решим систему трех уравнений с тремя неизвестными

а₁₁ × p₁ + а₂₁ × p₂ = u,

а₁₂ × p₁ + а₂₂ × p₂ = u,

p₁ + p₂ = 1.

Решив следующую систему, найдем оптимальную стратегию игрока В:

а₁₁ × q₁ + а₁₂ × q₂ = u,

а₂₁ × q₁ + а₂₂ × q₂ = u,

q₁ + q₂ = 1.

Рассмотрим первую систему. Вычитая из первого равенства второе, получая

(а₁₁ - а₁₂) × p₁ + (а₂₁ - а₂₂) × p₂ = 0.

Подставим P₂ = 1 - P₁, тогда

(а₁₁ - а₁₂) × p₁ + (а₂₁ - а₂₂) (1- p₁ ) = 0,

отсюда оптимальная смешанная стратегия для игрока А – А*(p₁, p₂)

P₁ = (а₂₂ - а₂₁)/(а₁₁ - а₁₂ + а₂₂ - а₂₁),

P₂ = 1- P₁ = (а₁₁ - а₁₂)/(а₁₁ - а₁₂ + а₂₂ - а₂₁).

цена игры

u = (а₁₁ × а₂₂ - а₂₁ × а₁₂)/ (а₁₁ - а₁₂ + а₂₂ - а₂₁).

Рассуждая аналогично, для определения оптимальной стратегии игрока В получая

q₁ = (а₂₂ - а₁₂)/(а₁₁ - а₁₂ + а₂₂ - а₂₁),

q₂ = (а₁₁ - а₂₁)/(а₁₁ - а₁₂ + а₂₂ - а₂₁).

Пример. Имеются две конкурирующие фирмы А и В, выпускающие изделия двух модификаций. Изучение спроса покупателей показало, что если выпускаются изделия первой модификации обеими фирмами, А₁ и В₁, то 40 % покупателей предпочитают изделия фирмы А и 60 % - фирмы В. Если выпускаются изделия А₁ и В₂, то 90 % покупателей приобретают изделия А. Если изготавливаются изделия А₂ и В₁, будет продано 70 % изделий фирмы А. Наконец, если выпускаются изделия второй модификации А₂ и В₂ обеими фирмами, то 20 % покупателей предпочитают изделия фирмы А.

Решение. Представим выигрыш фирмы А в табличной форме

а₁₁ = 40 % - 60 % = -20 %; а₁₂ = 90 % - 10 % = 80 %;

а₂₁ = 70 % - 30 % = 40 %; а₂₂ = 20 % - 80 % = -60 %.

	В1	В2	ai
А1	-20		-20
А2		-60	-60
bj

Нижняя цена игры составляет (-20), верхняя равна 40. Игра не имеет седловой точки. Найдем оптимальные смешанные стратегии

p₁ = (-60 - 40)/(-20 –80-60-40) = ; p₂ = ;

u = [-20 × (-60)- 40 × 80]/ (-20 –80-60-40) = 10;

q₁ = (-60 - 80)/(-20 –80-60-40) = ; q₂ = .

Выигрыш фирмы А в соответствии с ценой игры составит 10 %. Следовательно, А – В = 10 %, но А + В = 100 %, тогда А = 55 %; В = 45 %. Следовательно, при таких оптимальных стратегиях изделия фирмы А будут покупать 55 % потребителей, а фирма В – 45 % покупателей.