18. Аналитическое решение игры 2´2. Геометрическое решение игры 2´2.

Рассмотрим матричную игру, в которой каждый из игроков имеет по две чистые стратегии. В общем виде -игра определяется матрицей

.

Пусть X — произвольная смешанная стратегия игрока I. Если х — вероятность выбора игроком I своей первой чистой стратегии в условиях X, то вероятность выбора им второй чистой стратегии есть 1-х. Поэтому стратегию X можно представить в виде (х, 1-х). Аналогично если Y — произвольная смешанная стратегия игрока II, то она имеет вид (у, 1 -у). Таким образом, стратегия X однозначно определяется числом х, а стратегия Y — числом у. В соответствии с этим мы будем обозначать ситуацию (X, Y) как пару чисел (х, у). В силу предположения, что чистых оптимальных стратегий нет, х* > 0 и у* > 0.

Введем следующие обозначения:

. — i-я строка матрицы Н;

— j-й столбец матрицы Н.

На основании теоремы 17.7

и

или

(17.20)

и

(17.21)

Из систем (17.20) и (17.21) следует, что при столбцы (строки) матрицы Н не могут быть пропорциональны с коэффициентом пропорциональности, отличным от единицы. Если же коэффициент пропорциональности равен единице, то матрица принимает следующий вид:

и игрок I (II) имеет чистую оптимальную стратегию, что противоречит предположению.

Следовательно, если и игроки имеют только смешанные оптимальные стратегии, определитель матрицы Н отличен от нуля. Из этого следует, что системы уравнений (17.20) и (17.21) имеют единственное решение. Решая их, находим

(17.22)

Таким образом, для решения матричной - игры необходимо сначала проверить равенство (17.8). Если оно выполняется, то игроки имеют чистые оптимальные стратегии (игрок I — чистую максиминную, а игрок II — чистую минимаксную). В противном случае по формулам (17.22) следует найти оптимальные стратегии игроков и значение игры.

Пример. Решить игру

.

Прежде всего проверим наличие седловой точки (в чистых стратегиях). Имеем

и, следовательно, седловых точек нет. Перейдем к нахождению оптимальных смешанных стратегий и значения игры. Используя формулы (17.22), получим:

Таким образом, .

Пример. Используя доминирование, мы свели игру к эквивалентной игре (см. 17.5.1)с матрицей выигрышей

.

Так как, , седловых точек в чистых стратегиях нет.

Перейдем к нахождению решения в смешанных стратегиях. По формулам (17.22) имеем:

и, следовательно, .

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

Пусть игра задана платежной матрицей . По оси абсцисс отложим единичный отрезок А₁А₂, где точка А₁ (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 Случай 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. Решить матричную игру, в которой один из игроков имеет две чистые стратегии, или игру, которая сводится к таковой после отбрасывания доминируемых строк и столбцов. Для нахождения цены игры и оптимальной стратегии игрока, имеющего две чистые стратегии, применяется графический метод. Для другого игрока оптимальная стратегия ищется исходя из свойств оптимальных стратегий и цены игры. Список рекомендуемых для контрольной работы задач прилагается.