Решение игры в смешанных стратегиях геометрическим методом

. По оси абсцисс отложим единичный отрезок А₁А₂, где точка А₁ (0, 0) изображает стратегию А₁, А₂ (1, 0) – стратегию А₂, а каждая промежуточная точка S_A этого отрезка изображает смешанную стратегию первого игрока P_A = (p₁, p₂), где p₁– расстояние от точки S_A до A₂, p₂–расстояние от точки S_A до A₁. Выигрыш игрока A будем откладывать на вертикальных отрезках.

$Графоаналитический способ решения матричных игр$

Случай 1. Если игрок B применит стратегию В₁, то выигрыш игрока A при стратегии А₁ равен а₁₁, поэтому на оси ординат отложим отрезок А₁В₁ = а₁₁. При применении игроком A стратегии А₂ выигрыш равен а₂₁, отложим этот отрезок на перпендикуляре из точки А₂, обозначим полученную точку В₁'. Ордината любой точки М₁ отрезка В₁В₁^′ равна среднему выигрышу игрока A при применении смешанной стратегии S_A (действительно, этот выигрыш равен математическому ожиданию случайной величины, т.е. a₁₁p₁ + a₂₁p₂). Запишем уравнение прямой В₁В₁^′:

, т.е. y=a₁₁+x(a₂₁-a₁₁),
тогда при x = p₂ получим
y = a₁₁ + p₂a₂₁ – p₂a₁₁ = a₁₁(1-p₂) + p₂a₂₁ = a₁₁p₁ + a₂₁p₂
Случай 2. Если игрок B применяет стратегию В₂, то аналогично откладываем отрезки а₁₂ и а₂₂ и получаем отрезок В₂В₂^′. Ордината любой точки М₂ отрезка В₂В₂^′ – выигрыш игрока A, если A применяет смешанную стратегию S_A, а B – стратегию В₂.
Построим нижнюю границу выигрыша игрока А – ломаную В₁ NВ₂^′. Ординаты точек этой ломаной показывают минимальные выигрыши игрока А при использовании им любой смешанной стратегии. Оптимальное решение игры определяет точка N, в которой выигрыш игрока А принимает наибольшее значение. Ордината точки N равна цене игры. Проекция этой точки на ось ОХ показывает оптимальную стратегию (р₁, р₂).
Аналогично находится оптимальная стратегия Q = (q₁ , q₂) игрока B, только в соответствии с принципом минимакса надо находить верхнюю границу выигрыша, т. е. строить ломаную А₂NА₁^′ и брать точку N с наименьшей ординатой.
Абсцисса точки N определяет оптимальную стратегию игрока B, т. е. Q = (q₁ , q₂).

Пример №1. Решить игру, заданную платежной матрицей , графоаналитическим способом.
Решение. Нижняя цена игры α = 1,5, верхняя цена игры β = 2. Так как α≠β, седловой точки нет. Так как a₁ = 1,5, a₂₁ = 2 строим точки B₁(0;1,5) и B₂(1;2), соединяем их отрезком. Так как a₂₁ = 3, a₂₂ = 1 строим точки B₂(0;3) и B₂’(1;1), соединяем их отрезком.

Уравнение прямой В₁В₁^′:

, т. е. y = 0,5x + 1,5;
уравнение В₂В₂^′:

, т. е. y = 3-2x.
Найдем точку N пересечения прямых В₁В₁^′ и В₂В₂^′, для чего решим систему уравнений:

т. е. N(0,6; 1,8), откуда p₂= 0,6; p₁= 0,4; γ = 1,8 – цена игры.
Аналогично строим точки А₁(0; 1,5) и А₁^′(1;3), А₂(0; 2) и А₂^′(1; 1) и находим точку M пересечения прямых А₁А₁^′ и А₂А₂^′.

$Решение игры в смешанных стратегиях геометрическим методом$

Ответ: смешанная стратегия игрока А: P_A= (0,4; 0,6), игрока В: Q_B = (0,8; 0,2); цена игры 1,8.

Пример №2. Решить матричную игру, в которой один из игроков имеет две чистые стратегии, или игру, которая сводится к таковой после отбрасывания доминируемых строк и столбцов. Для нахождения цены игры и оптимальной стратегии игрока, имеющего две чистые стратегии, применяется графический метод. Для другого игрока оптимальная стратегия ищется исходя из свойств оптимальных стратегий и цены игры. Список рекомендуемых для контрольной работы задач прилагается.

Перейти к онлайн решению своей задачи

Решение игры 2×2

Покажем на примере платёжной матрицы размерностью 2×2 реализацию алгоритма построения оптимального решения игровой задачи в смешанных стратегиях.

Пример №3. Найдем решение матричной игры

V_* = -1, V* = 1, V_* ≠V* - решения в чистых стратегиях не существует.
Припишем строкам платёжной матрицы неизвестные вероятности p₁ и p₂ (вероятности выбора стратегий A₁ и A₂) соответственно:
.
Поскольку p₁ + p₂ =1 → p₂ = 1 - p₁. Обозначим p₁ = p, тогда p₂ =1 - p. В результате получим:

Умножим столбец поэлементно на 1-й столбец и, сложив произведения, получим - математическое ожидание (среднее значение) выигрыша первого игрока A, при условии, что второй игрок B следует первой стратегии.
M₁(p) = 1∙p + (-1)(1-p) = 2p-1
Умножим столбец поэлементно на 2-й столбец и, сложив произведения, получим линейную зависимость - математическое ожидание (средний выигрыш) игрока A при применении игроком B второй стратегии
M₂(p) = (-1)∙p + 1(1-p) = -2p+1
Поскольку мы разыскиваем оптимальное решение первого игрока A, которое не должно зависеть от выбора стратегий вторым игроком B, приравняем полученные зависимости средних выигрышей:
2p-1 = -2p+1
Отсюда, p= ½, 1-p = ½, то есть оптимальная смешанная стратегия игрока A - это P = (½, ½ ) (каждую из стратегий надо применять с относительной частотой ½). Подставив p=½ в любую из зависимостей M_i(p), i=1,2 найдем цену игры:
V=M_i(½) = 0.
Теперь припишем столбцам вероятности q₁ и q₂ соответственно, а поскольку:
q₁ + q₂ =1 →q₂ = 1 - q₁. Обозначим q₁ = q, тогда q₂ =1 - q. В результате получим:
.
Умножив строку (q, 1-q) на 1-ю строку и сложив произведения, получим линейную зависимость - математическое ожидание:
W₁(q) = 1· q + (-1) ·(1-q) = 2q - 1
Это средний выигрыш игрока A (равный проигрышу игрока B) при применении игроком A 1-й стратегии.
Умножив строку (q, 1-q) на 2-ю строку и сложив произведения, получим линейную зависимость - математическое ожидание:
W₂ = (-1) · q + 1· (1-q) = -2q + 1
Это средний выигрыш игрока A (равный проигрышу игрока B) при применении игроком A 2-й стратегии.
Приравняем полученные зависимости:
2q -1 = -2q + 1
Отсюда, q = ½, 1 - q = ½, то есть оптимальная смешанная стратегия игрока B - это Q = (½, ½) (каждую из стратегий надо применять с относительной частотой ½).
Решение о конкретном выборе одной из своих стратегий каждый из игроков может принимать с помощью подбрасывания монеты или бинарного датчика случайных чисел.
Как показывает приведённый пример, оптимальные смешанные стратегии сравнительно легко находятся для игр, имеющих небольшую размерность платёжной матрицы (небольшие m и n), т.е. для игр, в которых каждый из игроков имеет небольшое число стратегий. В то же время для игр, имеющих большую размерность, поиск решения становится достаточно сложным. Поэтому до построения оптимального решения в смешанных стратегиях проводят предварительный анализ платёжной матрицы на предмет её упрощения, исключения из неё дублирующих и доминируемых стратегий, что позволяет существенно упростить поиск решения игровой задачи в смешанных стратегиях.

Решение игр вида 2хn и mх2

Графо-аналитический метод.

У таких игр всегда имеется решение, содержащее не более двух активных стратегий для каждого из игроков. Если найти эти активные стратегии, то игра 2 х n или m х 2 сводится к игре 2 х 2, которую мы уже умеем решать. Поэтому игры 2 х n и m х 2 решают обычно графоаналитическим методом.
Рассмотрим решение матричной игры на примере.

Пример №4. $Решение игр вида 2хn и mх2$
Решение.

				α_i
	1	4	7	1
	6	3	2	2
β_j	6	4	7	2 4

α=2, β=4, α≠β, поэтому игра не имеет седловой точки, и решение должно быть в смешанных стратегиях.
1. Строим графическое изображение игры.

Если игрок B применяет стратегию В₁, то выигрыш игрока A при применении стратегии А₁ равен а₁₁ = 1, а при использовании А₂ выигрыш равен а₂₁ = 6, поэтому откладываем отрезки А₁В₁ = 1, А₂В₁^′ = 6 на перпендикулярах в А₁ и А₂ и соединяем их отрезком. Аналогично для стратегий В₂ и В₃ строим отрезки В₂ В₂^′ и В₃ В₃^′.
2. Выделяем нижнюю границу выигрыша В₁М N В₃^′ и находим наибольшую ординату этой нижней границы, ординату точки М, которая равна цене игры γ.
3. Определяем пару стратегий, пересекающихся в точке оптимума М.
В этой точке пересекаются отрезки В₂В₂^′ и В₁В₁^′, соответствующие стратегиям В₁ и В₂ игрока B. Следовательно, стратегию В₃ ему применять невыгодно. Исключаем из матрицы третий столбец и решаем игру 2 x 2 аналитически:

;

.
Ответ: γ = 7/2; P_A = (1/2; 1/2); Q_B = (1/6; 5/6; 0).

Перейти к онлайн решению своей задачи

Правила решения игры mx2

строится графическое изображение игры;
выделяется нижняя граница выигрыша и находится наибольшая ордината нижней границы, которая равна цене игры γ;
определяется пара стратегий, пересекающихся в точке оптимума M. Эти стратегии являются активными стратегиями игрока B. Если в точке оптимума пересекаются более двух стратегий, то в качестве активных стратегий может быть выбрана любая пара из них;
решается полученная игра 2x2.

Решение игры mx2 осуществляется аналогично. Вместо пункта 2 применяется;
♦ выделяется верхняя граница выигрыша, и на ней находится точка оптимума с наибольшей ординатой.

Пример №5

Решение.

			α_i
	0,4	1,0	0,4
	0,5	0,5	0,5
	1,0	0,3	0,3
	0,8	0,3	0,3
β_j	1,0	1,0	0,5 / 1,0

a= 0,5, b= 1,0. Седловой точки нет.
1. строим графическое изображение игры относительно игрока В.
Если А применяет А₁, то при использовании игроком В стратегии В₁ выигрыш игрока А равен 0,4, а выигрыш А при стратегии В₂ равен 1,0, поэтому на перпендикулярах строим такие отрезки. Видно, что стратегия А₄ заведомо невыгодная по сравнению со стратегией А₃ (выигрыш меньше).
2. Выделяем верхнюю границу выигрыша А₃NА₁^′; точка с наименьшей ординатой – N.
3. В этой точке пересекаются отрезки А₁А₁^′ и А₃А₃^′, соответствующие активным стратегиям А₁ и А₃. Стратегия А₂ не является активной, поэтому из матрицы исключаем вторую и четвертую строки:

4. решаем игру:

13p₃ = 6; p₃ =6/13; p₁ = 7/13 $Правила решения игры 2xn$

q₂ = 6/13.
Ответ: γ = 44/65; P_A = (7/13; 0; 6/13; 0); Q_B = (7/13; 6/13).

Примечание: Игроку А не выгодно отклоняться от спектра своих активных стратегий.

Перейти к онлайн решению своей задачи

Модель сотрудничества и конкуренции

Рассмотреть матричную игру как модель сотрудничества и конкуренции. Найти графически решение игры. Указать, как проявляется конкуренция между игроками и сотрудничество между ними.

Решение: Седловой точки нет. Обозначим искомую оптимальную стратегию первого игрока (х, 1-х). Это вектор-столбец, который мы записываем для удобства в виде строки.

Обозначим nj(x) - средний выигрыш первого в расчете на партию, когда он использует стратегию (х, 1-х), а второй - j-ю стратегию.

Имеем

n1(x)=х - 2(1-х);

n2(x)=2х +(1-х);

n3(x)=-4х + 2(1-х);

n4(x)=3х - 3(1-х).

Возьмем на плоскости систему координат, по горизонтальной оси вправо отложим х, по вертикальной оси - значения функции nj(x). Функции n1(x), n2(x), n3(x), n4(x) - линейные, значит их графики - прямые линии 1, 2, 3, 4 соответственно.

Находим нижнюю огибающую огибающую семейства четырех прямых.

Находим ее высшую точку - М. Она и дает решение игры. Ее координаты определяются решением уравнения n2(x)=n4(x), откуда х*=4/5, n=n2(x)=n4(x)=9/5.

Таким образом, оптимальная стратегия первого есть Р*=(4/5, 1/5), а цена игры n=9/5.

Заметим, что при этой стратегии первого второй игрок не выбирает первый и третий столбцы. Обозначим вероятность выбора вторым игроком второго столбца через y, а четвертого столбца - через (1 - y). Учтем, например, что р₁*=х*>0 и воспользуемся утверждением о том, что если р_к*>0, то М(1; y*)=n, т.е.

2y* +(1-y*)=9/5, откуда y*=4/5.

Окончательный ответ таков: оптимальная стратегия первого Р*=(4/5, 1/5), оптимальная стратегия второго - Q=(0;4/5;0;1/5), цена игры n=15/11.