Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

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




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

В табл. 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)

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

wk1k p + a2k(1-p)=(a1k-a2k)p + a2k (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 полужирной ломаной линией. Точка максимума нижней огибающей лежит на пересечении прямых w4 и w5. Решая уравнение p -6р + 5, получим popt = . Цена игры, являющаяся математическим ожиданием выигрыша игрока А, равна

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

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

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

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

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

.

Таким образом, игрок В применяет стратегию Вк с вероятно стью qk = q, а стратегию Bt — с вероятностью ql = 1 - q.

Рис. 4.4

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

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

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), при этом прямая имеет положительный наклон, а прямая - отрицательный. Составим уравнение:

или .

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

.

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

.

 

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

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

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

Пусть статистик использует стратегии А1, A2,..., Аm, а природа обладает стратегиями П1, П2,..., Пn. Если статистик имеет возможность оценить последствия применения каждой своей чистой стратегии Аi в зависимости от любой стратегии природы Пk, т.е. если ему известен численный результат aikдля каждой допустимой комбинации (AiПk),то игру можно задать платежной матрицей (табл. 4.10)

В последнем столбце табл. 4.10 приведены минимально возможные выигрыши статистика αi при стратегии Ai, а в последней строке - максимально возможный выигрыш статистика β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  

 

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

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

(4.21)

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

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

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

В этих формулах введена вероятность qk наступления события Пк. Таким образом, матрица рисков статистика имеет вид табл. 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  

 

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

Поделиться:





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



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...