1.3.2. Решение матричных игр в смешанных стратегиях

1.3.2. Решение матричных игр в смешанных стратегиях

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

2 9

6 3

В данном случае =3, а =6. Таким образом, игрок А может выиграть не менее 3, а игрок В может ограничить свой проигрыш (выигрыш игрока А) шесть единицами. Область между 3 и 6 остается как бы нейтральной, и каждый игрок может попытаться улучшить свой результат за счет этой области. Но как это сделать? Если игроки применяют свои наиболее предпочтительные стратегии А2 и В1, то игрок А выигрывает, а игрок В проигрывает 6 единиц. Это, конечно, устраивает игрока А, но невыгодно игроку В. Поэтому, если игрок В заметит, что игрок А предпочтительно использует свою стратегию А2, то он может перейти на свою стратегию В2 и понизить выигрыш игрока А до 2 единиц. В свою очередь игрок А может в ответ перейти на свою первую стратегию и выиграть уже 9 единиц. В свою очередь, узнав об этом, игрок В может снова сменить стратегию и понизить выигрыш игрока А до 2 единиц.

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

Обозначим через p1, …, pm вероятности, с которыми игрок А использует в ходе игры свои чистые стратегии А1, ….Am, а через q1, …, qn аналогичные величины для игрока В. Очевидно, должны выполняться условия неотрицательности:

И условия нормировки:

Упорядоченные множества P1, …, pm и Q1, …, qn полностью определяют характер действий игроков и называются смешанными стратегиями игроков А и В соответственно. Очевидно, игроки располагают бесконечным множеством смешанных стратегий.

Так как каждый раз применение игроком одной чистой стратегии исключает применение другой, то чистые стратегии являются Несовместными событиями. Кроме того, они являются единственными возможными событиями.

Чистая стратегия есть частный случай смешанной стратегии. Действительно, если в смешанной стратегии какая-либо I-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта I-Я чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока.

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

Эта функция называется платежной функцией игры с платежной матрицей aij.

По аналогии с введенными ранее понятиями нижней чистой и верхней чистой цены игры вводятся понятия нижней и верхней цены (без слова «чистая») применительно к смешанным стратегиям, сохраняя для них те же обозначения и . Понятно, что вместо выигрыша aij теперь надо иметь ввиду средний выигрыш , а вместо чистых стратегий с номерами i и j, следует подразумевать смешанные стратегии и (в дальнейшем черточки будем опускать, если это не вызывает недоразумений).

Нижней ценой игры будем называть число

А верхней ценой игры число

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

Величину в этой формуле называют ценой игры и обозначают .

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

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

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

Теорема В смешанных стратегиях любая конечная матричная игра имеет седловую точку.

© 2011-2024 Контрольные работы по математике и другим предметам!