Методы решения матричных игр

Начнём с матричных игр, число стратегий хотя бы одного из игроков в которых равно двум.

Для построения решений 2 x n- и m x 2- игр существует эффективный метод, основанный на простых геометрических соображениях и, конечно на доказанных выше утверждениях. Этот метод называют наглядно-графическим.

2 х n – игры

Пусть

a₁₁ a₁₂ … a_1n

a₂₁ a₂₂ … a_2n

-матрица 2 х n- игры.

Согласно следствию из теоремы 2

V= (a_1kp+a_2k(1-p))

Поэтому отыскание значения игры и оптимального значения p^* для игрока A равносильно определению значения p, при котором функция

(a_1kp+a_2k(1-p)), (*)

достигает своего максимального значения, которое равно v.

Опишем общую схему решения этой задачи, приводящую к искомому результату.

Максимум функции (*) проще всего найти, построив её график.

Для этого поступим следующим образом.

Предположим, что игрок A выбрал смешанную стратегию P={p, 1-p}, а игрок B – k-ю чистую стратегию 1_k, k=1,2,…., n. Тогда средний выигрыш игрока A в ситуации {P, 1_k} оказывается равным

(k) :w=a_1kp+a_2k(1-p).

На плоскости (p, w) это уравнение описывает прямую. Тем самым, каждой чистой стратегии игрока B будет соответствовать своя прямая.

Поэтому для построения графика функции (*) сначала на плоскости (p, w) последовательно и аккуратно рисуются все прямые

(k):w=a_1kp+a_2k(1-p), k=1,2,…,n

(Рис 1). Затем для каждого значения p в полосе 0≤p≤1 путём визуального сравнения соответствующих ему значений w на каждом из построенных прямых определяется и отмечается наименьшее(рис 2)

w w

1 0 1 P

0 P

рис. 1 Рис. 2

В результате описанной процедуры получается ломаная, которая и является графиком функции (*) (выделена жирным на рис 3). В рассматриваемой полосе эта ломаная как бы огибает снизу все семейство построенных прямых, и по этой причине её принято называть нижней огибающей.

Верхняя точка построенной нижней огибающей определяет и значение игры- v и оптимальную стратегию игрока А - P^*={p^*,1-p^*} рис.

w w

0 1 P 0 P^* 1 P

Рис. 3 Рис. 4

Опробуем описанную схему решения 2 x n-игры на конкретном примере.

Пример 4. Рассмотрим игру, заданную 2 x 6- матрицей

6 4 3 1 -1 0

-2 -1 1 0 5 4

Решение.

1-й шаг. Анализ игры на наличие Седловой точки. Нижнее значение игры равно -1, верхнее значение игры равно 1. Седловой точки нет. Решение игры нужно искать в смешанных стратегиях.

2-й шаг. Вычисление средних выигрышей игрока А (проводится при условии, что игрок В выбирает только чистые стратегии).

Из таблицы

P 6 4 3 1 -1 0

1-p -2 -1 1 0 5 4

легко получаем

(1): w=6p-2(1-p),

(2): w=4p - (1-p),

(3): w=3p +(1-p),

(4): w=p,

(5): w=-p+5(1-p),

(6): w=-p+4(1-p).

3-й шаг. Построение нижней огибающей.

Аккуратно строим на координатной плоскости (p,w) все шесть прямых, уравнения которых получены на 2-м шаге рис.5, и находим нижнюю огибающую.

W (1)

4 (2)

3 (3)

1 (4)

-1

-2 (6)

(5)

Рис. 5

Обращаем внимание читателя на то, что масштабы по осям p и w различны: в любой матричной игре ширина вертикальной полосы одна и та же (равна 1), в то время как w может принимать очень разные значения.

4-й шаг. Отыскание значения игры и оптимальной смешанной стратегии игрока А.

При аккуратном построении нижней огибающей нетрудно определить, точкой пересечения каких двух из посторонних шести прямых является её наивысшая точка. В данном случае это прямые (4) и (5), заданные уравнениями w=p и w=-p+5(1-p) соответственно. Решая систему уравнений

w=p,

w=-p+5(1-p),

получаем

p^*=5/7, w^*=5/7

w

1

0 P

Рис. 6

Тем самым, значение игры v и оптимальная стратегия P^* игрока A найдены:

V= , P^*= ,

Собственно, этим и заканчивается решение игры для игрока А , поскольку его в первую очередь интересует отыскание собственной оптимальной стратегии и ожидаемого наилучшего гарантированного среднего результата.

Замечание. Решающий матричную игру обычно отождествляет себя с одним из игроков ( как правило, это игрок А) , считая другого своим противником. Это связано ещё и с тем, что в некоторых случаях основное внимание уделяется поиску оптимальных стратегий только игрока А, а стратегии противника могут вообще не интересовать исследователя.

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

Покажем теперь, как зная оптимальную смешанную стратегию игрока А из примера 4, отыскать оптимальную смешанную стратегию игрока В и тем самым найти полное решение игры.

Прежде всего заметим, что для 1-й, 2-й, 3-й, и 6-й чистых стратегий игрока В выполняются неравенства

H(P^*,1_k)>v k=1, 2, 3, 6

(см. рис. 6).

Согласно следствию из теоремы 3, завершающему серию утверждений предыдущего раздела, соответствующие значения q^*_k в искомой оптимальной смешанной стратегии

Q^*={q₁^*,q₂^*,q₃^*,q₄^*,q₅^*,q₆^*}

Игрока В должны быть равными нулю. Сказанное можно представить так:

q₁^*=0, q₂^*=0, q₃^*=0, q₄^*=q, q₅^*=1-q, q₆^*=0

из шести чистых стратегий игрока В выделены стратегии В₄ и В₅, соответствующие прямым (4) и (5), пересечение которых определяет наивысшую точку нижней огибающей).

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

0 0 0 q 1-q 0

6 4 3 1 -1 0

-2 -1 1 0 5 4

К значению игры

q-1(1-q)= , 5(1-q)= ,

(В обоих случаях) получаем, что

q^*=

Полное решение игры имеет следующий вид:

P^*= , , Q^*= 0,0,0, , ,0 , v= .

В зависимости от формы нижней огибающей, может представиться несколько возможностей.

A. Нижняя огибающая имеет ровно одну наивысшую точку (p^*,w^*).

1) 0<p^*<1 и в наивысшей точке нижней огибающей пересекаются ровно две прямые. Тогда одна из этих прямых (к-я) имеет положительный наклон, а другая (l-я) – отрицательный (рис. 7), и оптимальная смешанная стратегия игрока В получается, если положить

q_k^*=q, q₁^*=1-q, q_j^*=0, j≠k, j≠l,

где q- решение уравнения

a_1kq+a_1l(1-q)=a_2kq+a₂₁(1-q)

2) 0<p^*<1 и в наивысшей точке нижней огибающей пересекаются по меньшей мере три прямые. Выберем прямую с наибольшим положительным наклоном (к-ю) и прямую с наибольшим оптимальным наклоном (l-я). Каждая из этих прямых содержит звено нижней огибающей (рис. 7).

w w

(k) 1 0 1

P P

(l) (k) (l)

Рис. 7 Рис. 8

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

q_k^*=q, q₁^*=1-q, q_j^*=0, j≠k, j≠l,

где q – решение уравнения

a_1kq+a_1l(1-q)=a_2kq+a_2l(1-q)

3) p^*=0(оптимальная стратегия игрока А –это его чистая стратегия А₂). Тогда игроку B выгодно применять чистую стратегию 1_k , соответствующему номеру k^* прямой, проходящей через точку (0, v) и имеющей наибольший отрицательный наклон (Рис. 9).

4) P^*=1 (оптимальная стратегия игрока А – это его чистая стратегия A_i). Тогда оптимальная для игрока В является чистая стратегия 1_k , соответствующая номеру k^* прямой, проходящей через точку (1,v) и имеющей наибольший положительный наклон (Рис. 10).

w w

(k^*) (k^*)

0 1 1

P 0 P

Рис. 9 Рис. 10

w

(k^*)

0 1

P

Рис. 11

B. Нижняя огибающая содержит горизонтальный участок, соответствующий чистой стратегии 1_k. Игрока В, которая и является оптимальной для него (Рис. 11)

Замечание. Ситуацию с наличием лишь двух конкурирующих стратегий игрока А нельзя считать надуманной. Она возникает сравнительно часто. Например, в случае, если нужно сравнить два образца некоторого изделия (скажем, старого и модернизированного) с целью выяснения возможности замены, это весьма удобно сделать при помощи матрицы 2 х n- игры.

m x 2- игры

Пусть теперь в матричной игре две чистые стратегии имеет игрок В, а число чистых стратегий у игрока А произвольно (равно m).

Это означает, что матрицы игры имеет вид

a₁₁ a₁₂

a₂₁ a₂₂

. .

. .

. .

a_m1 a_m2

Есть два способа решения этой игры:

1) Путем применения рассуждений, во многом напоминающих те, что описаны для 2 х n- игры,

2) Путем непосредственного сведения к 2 х n – игре.

Способ 1-й. Пусть Q ={q, 1-q} – произвольная смешанная стратегия игрока B. Если игрок А выбирает i-ю чистую стратегию, i=1,2…,m, то средний выигрыш игрока В в ситуации {1_i ,Q} будет равен

(i):w= a_1iq+a_i2(1-q), i=1,2,….,m.(*)

Зависимость этого выигрыша от переменной q описывается прямой.

График функции

(a_i1q+a_i2 (1-q))

Является верхняя огибающая семейства прямых (*) в полосе 0≤q≤1, соответствующих чистым стратегиями игрока А (Рис. 12)

Абсциссой нижней точки полученной ломаной будет значение q^*, определяющее оптимальную смешанную стратегию игрока B, а ординатой v –значение игры.

Замечание. Отыскание оптимальной смешанной w

стратегии игрока А проводится по той же схеме,

которая позволяет находить оптимальную

смешанную стратегию игрока B в 2 х n – игре.

v

q^* 1 q

Рис. 12

Способ 2-й. Рассмотрим 2 х m – игру с матрицей Ầ, которая получается из матрицы A m x 2 - игры

путём транспонирования и замены всех элементов на противоположные:

ᾶ_ik=-a_ik , i=1,…,m; k=1,…,n.

Игрока Ầ в этой новой игре имеет все те же интересы, что и игрок B в исходной игре, а интересы игрока B полностью совпадают с интересами игрока А исходной игры. Найденные стратегии игроков Ầ и B᷉ суть

Стратегий игроков B и А соответственно. Что касается значения ṽ новой игры, то оно противоположно значению v исходной игры,

ṽ=-v

m x n –игры

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