Смешанные стратегии матричных игр.

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

В табл. 4.4 приведен пример, когда нижняя цена игры не совпадает с верхней ценой игры .

Таблица 4.4.

				Минимальные выигрыши игрока А
	-2		-3 -3	-3 -2 -3
Максимальные выигрыши игрока В

 

Здесь , а . Таким образом, игрок А может выиграть не менее -2 (знак «-» перед цифрой означает проигрыш игроком А двух единиц), а игрок В может ограничить свой проигрыш (выигрыш игрока А) двумя единицами. Область между числами -2 и 2 остается нейтральной, и каждый игрок может попытаться улучшить свой результат за счет этой области. Для компромиссного распределения разности при многократном повторении игры игроками используется случайное применение своих чистых стратегий. Это обеспечивает наибольшую скрытность выбора стратегии, поскольку результат выбора не может быть известен противнику, так как он неизвестен самому игроку.

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

(4.7)

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

Аналогично, вектор , проекция которого удовлетворяет условиям (4.8),

(4.8)

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

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

. (4.9)

Функция (4.9) называется платежной функцией игры с матрицей, заданной в табл. 4.5.

Нижней ценой игры называется число , рассчитываемое по формуле:

. (4.10)

Верхней ценой игры называется число , рассчитываемое по формуле:

. (4.11)

Таблица 4.5.

			…		…		Вероятности использования чистых стратегий игроком А
… …
Вероятности использования чистых стратегий игроком В

 

Оптимальными смешанными стратегиями называются стратегии, удовлетворяющие соотношению (сравнить с формулой (4.6)).

. (4.12)

Величину

,

определенную соотношением (4.12), называют ценой игры.

Дадим другое определение оптимальных смешанных стратегий.

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

. (4.13)

Из соотношения (4.13) следует, что в седловой точке платежная функция достигает максимума по смешанным стратегиям игрока А и минимума по смешанным стратегиям игрока В. Возникает два вопроса:

1. Какие матричные игры имеют решение в смешанных стратегиях?

2. Как находить решение матричной игры, если оно существует?

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

Теорема 4.1. Основная теорема теории матричных игр. (Дж. фон Нейман). Для матричной игры с любой матрицей А величины и существуют и равны между собой:

.

Более того, существует хотя бы одна ситуация в смешанных стратегиях , для которой выполняется соотношение

.

Теорема 4.2. Основные свойства оптимальных смешанных стратегий. Пусть

, - оптимальные смешанные стратегии и - цена игры.

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

.

Аналогично, только те вероятности , могут отличаться от нуля, для которых

.

Имеют место соотношения

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

 

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

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

Рассмотрим игру 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.6.

Рис. 4.6

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

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

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

или .

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

.

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

.

 

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

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

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

Пусть статистик использует стратегии А₁, 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) табл. 5.10 можно записывать также в виде табл. 4.12.

Таблица 4.12

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

 

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

⇐ Предыдущая12345Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: