Графические решения матричных игр

Графический метод применим к тем играм, в которых хотя бы один игрок имеет две стратегий..

Рассмотрим игру 2×п, представленную в табл. 4.6. Эта игра не имеет седловой точки. Согласно теореме 4.2 имеем

 

(4.14)

Таблица 4.6

	В1	В2	...	Вk	…	Вn	Вероятности использования чистых стратегий игрок.А
A1			…		…		p
A2
		…		…		1-p
Вероятности использования чистых страте­гий игроком В	q1	q2	…	qk	…	qn

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

(4.15)

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

w_k=а_1k p + a_2k(1-p)=(a_1k-a_2k)p + a_2k (4.16)

для каждого к = 1, 2,..., п в системе координат pOw (рис.4.1). В соответствии с требованием (4.16) на каждой из построенных прямых определяются и отмечаются наименьшие значения. На рис. 4.2 эти значения выделены полужирной ломаной линией. Эта ломаная огибает снизу все семейство построенных прямых и называется нижней огибающей семейства.

В соответствии с (4.14) цену игры υ определяет верхняя точка построенной нижней огибающей. Координаты этой точки являются оптимальной стратегией игрока А:

.

Рис. 4.1 Рис. 4.2

Пример 4.3. Найти решение игры вида 2×п, приведенной в табл. 4.7.

Таблица 4.7

	В1	В2	B3	В4	B5	В6	Вероятности использования чистых стратегий игроком А
A1					-1		p
A2	-2	-1					1-p
Вероятности использования чистых страте­гий игроком В	q1	q2	q3	q4	q5	q6

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

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

Графики данных прямых, построенных в системе координат pOw, представлены на рис.4.3.

Рис. 4.3

Нижняя огибающая выделена на рис. 4.3 полужирной ломаной линией. Точка максимума нижней огибающей лежит на пересечении прямых w₄ и w₅. Решая уравнение p -6р + 5, получим p_opt = . Цена игры, являющаяся математическим ожиданием выигрыша игрока А, равна

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

Иногда решение матричной игры сводится только к поиску оп­тимальных смешанных стратегий игрока А. При этом стратегии противника могут не интересовать исследователя. Однако в целом ряде случаев необходимо знать оптимальные смешанные стратегии обоих игроков.

Пусть в наивысшей точке нижней огибающей пересекаются прямые w_k и w (рис. 4.4), при этом прямая w_k имеет положительный наклон, а прямая w_i− отрицательный. Оптимальная смешанная стратегия игрока В получается, если положить

= q; = 1-q; =0 при j k, l,

где q находят из уравнения

.

Таким образом, игрок В применяет стратегию В_к с вероятно стью q_k = q, а стратегию B_t — с вероятностью q_l = 1 - q.

Рис. 4.4

Пример 4.4. Для условий примера 4.3 определить смешанные стратегии игрока В.

Решение. В наивысшей точке нижней огибающей пересекаются прямые w₄ и w₅ (рис.4.3), при этом прямая w₄ имеет положительный наклон, а прямая w₅ — отрицательный. Составим уравнение:

q-(1-q)=0 × q+5(1-q) или 7q=6.

Отсюда находим

.

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

Примет 4.5. Найти решение игры вида , приведенной в табл. 4.9.

Таблица 4.9

	В1	В2	Вероятности использования чистых стратегий игроком А
A1		-1
A2	-1
A3
Вероятности использования чистых стратегий игроком В	q	1-q

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

Построим график верхней огибающей. Предварительно запишем уравнения прямых:

Графики этих прямых, построенных в системе координат , представлены на рис. 4.5.

Рис. 4.5

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

Решая уравнение , получим . Цена игры, являющаяся математическим ожиданием выигрыша игрока В, равна .

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

или

.

Отсюда находим

.

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

.

 

Игры с природой.

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

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

Пусть статистик использует стратегии А₁, A₂,..., А_m, а природа обладает стратегиями П₁, П₂,..., П_n. Если статистик имеет возможность оценить последствия применения каждой своей чистой стратегии А_i в зависимости от любой стратегии природы П_k, т.е. если ему известен численный результат a_ikдля каждой допустимой комбинации (A_iП_k),то игру можно задать платежной матрицей (табл. 4.10).

В последнем столбце табл. 4.10 приведены минимально возможные выигрыши статистика α_i при стратегии A_i, а в последней строке - максимально возможный выигрыш статистика β_k при состоянии П_к.

Таблица 4.10

	П1	П2	...	Пn	αi
A1	a11	a12	...	a1n	α1
A2	a21	a22	...	a2n	α2
...	...	...	...	...	...
Am	am1	am2	...	amn	αm
βk	β1	β2	...	βn

 

Помимо матрицы платежей (a_ik), приведённой в табл.4.10, для анализа игры с природой используется также матрица рисков статистика.

Риском статистика r_ik называют разность между максимальным выигрышем , который он мог бы получить, достоверно зная, что природа реализует состояние П_к, и тем выигрышем a_ik, который он получит, используя стратегию A_i, не зная, какое состояние П_к природа реализует:

(4.21)

Для анализа игры с природой часто используются средние значения рисков и средние значения выигрыша , которые вычисляются по формулам:

, где i=1,2,..., m (4.22)

, где i=1,2,..., m (4.23)

В этих формулах введена вероятность q_k наступления события П_к. Таким образом, матрица рисков статистика имеет вид табл. 4.11.

Таблица 4.11

	П1	П2	...	Пn
A1	r11	r12	...	r1n
A2	r21	r22	...	r2n
...	...	...	...	...	...
Am	rm1	rm2	...	rmn
qk	q1	q2	...	qn

С учетом (4.23) табл. 4.10 можно записывать также в виде табл. 4.12.

Таблица 4.12

	П1	П2	...	Пn
A1	a11	a12	...	a1n
A2	a21	a22	...	a2n
...	...	...	...	...	...
Am	am1	am2	...	amn
qk	q1	q2	...	qn

 

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