Методы и модели игры

 

 2 x n игры

Пусть

- платежная матрица 2 х n игры.

Согласно теореме о двойном  описании игры (теорема 2) нахождение цены игры и оптимального значения р⁰ для игрока А равносильно разрешению уравнения

.

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

Максимум функции

 (*)

проще всего найти, построив ее график. Для этого поступают следующим  образом.

Предположим, что игрок А выбрал смешанную стратегию Р = {р, 1 - р}, а игрок В - k-ю чистую стратегию, k = 1, 2, ... , n. Тогда средний выигрыш игрока А в ситуации {Р, k} оказывается равным

(k):   

.

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

Поэтому сначала на плоскости (ω, р) последовательно и аккуратно рисуются все 
прямые

(k):   

,  k = 1, 2, ... , n

(рис.2). Затем для каждого значения р, 0 £ р £ 1, путем визуального сравнения соответствующих ему значений ω на каждой из построенных прямых определяется и отмечается минимальное из них (рис. 3).  В результате описанной процедуры получается ломаная, которая и является графиком функции (*) (выделена жирным на рис. 4). Эта ломаная как бы огибает снизу все семейство построенных прямых,

Рис.2 Рис.3 Рис.4

 

и по этой причине ее принято называть нижней огибающей этого семейства. Верхняя точка построенной нижней огибающей определяет и цену игры – v  и оптимальную стратегию игрока А – Р⁰ = {р⁰, 1 - р⁰} (рис. 5).

 

Замечание. Описанная процедура  может рассматриваться как некоторый  аналог максиминного подхода при  отсутствии седловой точки.

 

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

 

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

Решение.

1-й шаг. Анализ игры на наличие седловой точки.

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

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

Из таблицы

p	6	4	3	1	-1	0
1 - p	-2	-1	1	0	5	4

 

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

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

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

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

(4): ω =   p ,

(5): ω = 6p - 2(1 - p),

(6): ω =         4(1 - p),

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

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

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

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

ω =  р,

ω = -p + 5(l - p), ,

получаем

,

(рис.7).

Рис.5 Рис.6 Рис.7

 

Тем самым, цена игры ν и оптимальная стратегия Р⁰ игрока A соответственно равны

, .

 

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

 

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

 

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

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

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

А. Нижняя огибающая имеет ровно одну наивысшую точку (р⁰, ω⁰):

1) Если р⁰ = 0 (оптимальная стратегия игрока А – чистая стратегия А₂), то игроку В выгодно применять чистую стратегию, соответствующую номеру прямой, проходящей через точку (0, ω⁰) и имеющей наибольший отрицательный наклон (рис. 8).

Рис.8 Рис.9 Рис.10

 

2) Если p⁰ == 1 (оптимальная стратегия игрока А — чистая стратегия А₁), то оптимальной для игрока В является чистая стратегия, соответствующая номеру прямой, проходящей через точку (1, ω⁰) и имеющей наименьший положительный наклон (рис. 9).

3) Если 0 < p⁰ < 1, то в наивысшей точке нижней огибающей пересекаются, по меньшей мере, две прямые, одна из которых (k-я) имеет положительный наклон, а другая (l-я) — отрицательный (рис. 10), и оптимальная смешанная стратегия игрока В получается, если положить

q_k = q, q_l = 1 - q, q_j = 0, j ≠ k, l.

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

.

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

Рис. 11

 

Пример 5 (продолжение). Покажем теперь, как найти полное решение игры, то есть еще и оптимальную смешанную стратегию

игрока В.

Для этого поступают так:

1) полагают

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

 

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

0	0	0	q	1 - q	0
6	4	3	1	-1	0
-2	-1	1	0	5	4

к цене игры

,

 

3) получают (в обоих случаях), что

.

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

, , .

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

 

m х 2 игры

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

.

Анализ такой игры во многом напоминает рассуждения, описанные для игры 2 х n.

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

 

 (i): i = 1, 2,..., m.  (*)

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

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

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

Рис.12

 

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

Замечание. Отыскание оптимальной смешанной стратегии игрока А проводится по той же схеме, которая позволяет находить оптимальную смешанную стратегию игрока В в игре 2 х n.

Рассмотрим конкретный пример.

 

Пример 6.  3 х 2 игра задана матрицей

.

 

Решение.

1 шаг. Анализ игры на наличие седловой точки.

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

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

Из таблицы

q	1 - q
3	-1
-1	3
1	0

 

получаем:

(1): ω = 3q –   (1 - q)

(2): ω = -q + 3(1 - q)

(3): ω =  q

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

Построим на координатной плоскости (q, ω) все три прямых, а затем и их верхнюю огибающую (рис. 13).

Рис. 13

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

Нижняя точка верхней огибающей  является точкой пересечения прямых (1) и (2). Решая систему уравнений

ω = 3q –   (1 - q),

ω = -q + 3(1 - q),

получаем

, .

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

Полагая

приравниваем средние выигрыши игрока А, соответствующие чистым выигрышам игрока В,

и находим р⁰ = 1/2. 

Таким образом, цена игры и оптимальные  смешанные стратегии игроков А и В соответственно

.

 

m х n игры

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

 

Правило доминирования

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

Опишем одну из таких  возможностей более подробно.

— произвольная m х n-матрица. Будем говорить, что i-я строка матрицы А

a_i1  a_i2   …   a_in

не больше j -и строки этой матрицы

a_j1  a_j2   …   a_jn ,

если одновременно выполнены следующие n неравенств

При этом говорят также, что j -я строка доминирует i-ю строку, или что стратегия A_j игрока А доминирует стратегию А_i.

Замечание. Игрок А поступит разумно, если будет избегать стратегий, которым в матрице игры отвечают доминируемые строки.

Если в матрице А одна из строк (j -я) доминирует другую строку (i-ю), то число строк в матрице А можно уменьшить путем отбрасывания доминируемой строки (i-й). Далее, будем говорить, что k-й столбец матрицы А

не меньше l-го столбца этой матрицы

если одновременно выполнены следующие m неравенств

При этом говорят также, что 2-й столбец доминирует k-й столбец, или что стратегия В_l игрока В доминирует стратегию В_k.

Замечание. Игрок В поступит разумно, если будет избегать стратегий, которым в матрице игры отвечают доминируемые столбцы.

Если в матрице А один из столбцов (l-й) доминирует другой столбец (k-й), то число столбцов в матрице А можно уменьшить путем отбрасывания доминируемого столбца (k-го).

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