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

Если платежная матрица не имеет седловой точки, то если игрок будет пользоваться смешанными стратегиями, т.е. при каждом ходе менять стратегию случайным образом, то игрок А выигрывает больше, чем a, а игрок В проигрывает больше, чем b.

Рассмотрим платежную матрицу (7.1). Пусть игрок А использует чистые стратегии А₁, А₂, … А_i,…А_m с вероятностями p₁, p₂, … p_i,…p_m, причем =1, а игрок В использует свои чистые стратегии В₁, В₂, … В_j,…B_n с вероятностями q₁, q₂, … q_j,… q_n, причем = 1.

Тогда набор S_A = (p₁, p₂, … p_i,…p_m) называется смешанной стратегией игрока А, а набор S_B = (q₁, q₂, … q_j,… q_n) - смешанной стратегией игрока В.

Поскольку игроки выбирают свои стратегии случайным образом, то вероятность выбрать комбинацию А_iВ_j по теории вероятности равна (P_i × q_j). При использовании смешанных стратегий игра становится случайной, тогда говорят о среднем значении выигрыша, который определяется платежной функцией

f(S_A, S_B) = . (7.2)

Смешанные стратегии = (,,……) и = (,,……) называются оптимальными, т.е. дающими каждой стороне максимальный возможный для нее средний выигрыш (для А) или минимальный средний проигрыш (для В), если они образуют седловую точку для платежной функции (7.2), т.е. если выполняется следующее условие:

f(S_A, ) £ f(,) £ f(, S_B).

Величина u = f(, S_B) называется ценой игры.

Теорема 2. В смешанных стратегиях любая матричная игра имеет седловую точку, или каждая матричная игра с нулевой суммой имеет решение в смешанных стратегиях.

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

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

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

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

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

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

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

³ 1; = .

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

Х_i ³ 1; j = ; = .

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

f(x) = ® min, (7.5)

Х_i³ 1; j = , (7.6)

Х_i³ 0; i = . (7.7)

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

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

g(y) = ® max.

y_j £ 1, i = .

y_j³ 0; j = .

Решение игры u = ;

= (u × ,… u × ) = (,…).

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

	В₁	В₂	В₃	нижняя цена игры a = 4, верхняя цена игры b = 5, т.е. a ¹ b – седловой точки нет.
А₁
А₂

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

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

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)

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

	В₁	В₂	(7.8)
А₁	a₁₁	a₁₂
А₂	a₂₁	a₂₂

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

Теорема 4. Пусть и – оптимальные смешанные стратегии игры с платежной матрицей (7.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,

отсюда оптимальная смешанная стратегия для игрока А – S*( 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 %.

	В₁	В₂	a_i
А₁	-20		-20
А₂		-60	-60
b_j

Нижняя цена игры составляет (-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 % потребителей.

Геометрическое решение игры

Пусть игра 2 х 2 имеет платежную матрицу (7.8). Изобразим на оси абсцисс отрезок горизонтальной линии единичной длины и обозначим концы отрезка через нуль и единицу. Из точек 0 и 1 по осям ординат восстановим перпендикулярные линии и изобразим на них выигрыши игрока А при использовании им соответственно чистых стратегий А₁ и А₂. Все промежуточные точки отрезка () будут изображать смешанные стратегии:

При оптимальной смешанной стратегии выигрыш игрока А будет составлять величину u и отмечен точкой М.

Произведем аналогичные построения для игрока В:

При графическом решении игр возможны и другие ситуации:

Пример. Найдем графическое и аналитическое решение игры:

	В₁	В₂	a = 4, b = 5, a ¹ b - следовательно, седловой точки нет.
А₁
А₂

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

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

Игры 2 х n и m х 2

Допустим, платежная матрица задана и имеет вид 2 х n:

	В₁	В₂	…	В_n	Игрок А имеет две стратегии, а игрок В – неограниченное число стратегий.
А₁	a₁₁	a₁₂	…	a_1n
А₂	a₂₁	a₂₂	…	a_2n

Допустим, платежная матрица имеет вид m х 2:

Минимум М находится на пересечении стратегий А₁ и А_m, остальные отбрасываются, далее игра решается как задача 2 х 2.

Пример. Пусть игра задана в виде платежной матрицы

	В₁	В₂	В₃	Игра (2 х 3) не имеет седловой точки a = 4, b = 5, a ¹ b, имеем игру в смешанных стратегиях.
А₁
А₂

Решим задачу графически и аналитически. Для игрока А: получаем игру 2 х 2, используя стратегии В₂ и В₃ игрока В:

Для игрока В: