Чистые и смешанные стратегии

Чистые  и смешанные стратегии

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

Первый игрок имеет m стратегий i = 1,2,...,m, второй имеет nстратегий j = 1,2,...,n. Каждой паре стратегий (i,j) поставлено в соответствие число а_ij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 – свою j-ю стратегию.

Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i= ), 2 – свою j-ю стратегию (j= ), после чего игрок 1 получает выигрыш а_ij за счёт игрока 2 (если а_ij< 0, то это значит, что игрок 1 платит второму сумму | а_ij | ). На этом игра заканчивается.

Каждая стратегия игрока i= ; j =   часто называется чистой стратегией.

Если рассмотреть матрицу

А = 

то проведение каждой партии матричной игры с матрицей А сводится к выбору игроком 1 i-й строки, а игроком 2 j-го столбца и получения игроком 1 (за счёт игрока 2) выигрыша а_ij.

Главным в исследовании игр  является понятие оптимальных стратегий  игроков. В это понятие интуитивно вкладывается такой смысл: стратегия  игрока является оптимальной, если применение этой стратегии обеспечивает ему наибольший гарантированный выигрыш при всевозможных стратегиях другого игрока. Исходя из этих позиций, игрок 1 исследует матрицу выигрышей А следующим образом: для каждого значения i (i = ) определяется минимальное значение выигрыша в зависимости от применяемых стратегий игрока 2

а_ij     (i =  )

т.е. определяется минимальный  выигрыш для игрока 1 при условии, что он примет свою i-ю чистую стратегию, затем из этих минимальных выигрышей отыскивается такая стратегия i = i_о, при которой этот минимальный выигрыш будет максимальным, т.е. находится

а_ij =  =                      (1).

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

Игрок 2 при оптимальном  своём поведении должен стремится по возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается

а_ij

т.е. определяется max выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию, затем игрок 2 отыскивает такую свою j = j₁ стратегию, при которой игрок 1 получит min выигрыш, т.е. находит

a_ij =  =                        (2).

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

Другими словами, применяя свои чистые стратегии игрок 1 может обеспечить себе выигрыш не меньше  , а игрок 2 за счёт применения своих чистых стратегий может не допустить выигрыш игрока 1 больше, чем  .

Определение. Если в игре с матрицей А  = , то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры

u =  = .

Седловая  точка – это пара чистых стратегий (i_о,j_о) соответственно игроков 1 и 2, при которых достигается равенство   =  . В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе:

                   

где i, j – любые чистые стратегии соответственно игроков 1 и 2;(i_о,j_о) – стратегии, образующие седловую точку.

Таким образом, исходя из (3), седловой элемент   является минимальным в i_о-й строке и максимальным в j_о-м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своёмстолбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий(i_о,j_о) игроков 1 и 2, образующая седловую точку и седловой элемент  , называется решением игры. При этом i_о и j_о называютсяоптимальными чистыми стратегиями соответственно игроков 1 и 2.

 

 

 

 

 

Пример 1

Седловой точкой является пара (i_о = 3; j_о = 1), при которой u = = = 2.

Заметим, что  хотя выигрыш в ситуации (3;3) также  равен 2 = = , она не является седловой точкой, т.к. этот выигрыш не является максимальным среди выигрышей третьего столбца.

Пример 2

Из анализа  матрицы выигрышей видно, что  , т.е. данная матрица не имеет седловой точки. Если игрок 1 выбирает свою чистую максиминную стратегию i = 2, то игрок 2, выбрав свою минимаксную j = 2, проиграет только 20. В этом случае игроку 1 выгодно выбрать стратегию i = 1, т.е. отклониться от своей чистой максиминной стратегии и выиграть 30. Тогда игроку 2 будет выгодно выбрать стратегию j = 1, т.е. отклониться от своей чистой минимаксной стратегии и проиграть 10. В свою очередь игрок 1 должен выбрать свою 2-ю стратегию, чтобы выиграть 40, а игрок 2 ответит выбором 2-й стратегии и т.д. 

Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий.

Таким образом, если игрок 1 имеет m чистых стратегий 1,2,...,m, то его  смешанная стратегия x - это набор  чисел x = (x1, ..., xm) удовлетворяющих соотношениям

xi >= 0 (i = 1,m), = 1.

Аналогично для игрока 2, который имеет n чистых стратегий, смешанная стратегия y - это набор чисел

y = (y1, ..., yn), yj >= 0, (j = 1,n), = 1.

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

Средний выигрыш игрока 1 в матричной игре с матрицей А выражается в виде математического ожидания его выигрышей

E (A, x, y) == x A yT

Первый игрок имеет  целью за счёт изменения своих  смешанных стратегий х максимально  увеличить свой средний выигрыш  Е (А, х, y), а второй - за счёт своих  смешанных стратегий стремится сделать Е (А, х, y) минимальным, т.е. для решения игры необходимо найти такие х и y, при которых достигается верхняя цена игры

Е (А, х, y).

Аналогичной должна быть ситуация и  для игрока 2, т.е. нижняя цена игры должна быть

Е (А, х, y).

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

Е (А, х, y) = Е (А, х, y) = Е (А, хо, уо).

Величина Е (А, хо ,уо) называется при  этом ценой игры и обозначается через u.

Имеется и другое определение оптимальных  смешанных стратегий: хо, уо называются оптимальными смешанными стратегиями  соответственно игроков 1 и 2, если они  образуют седловую точку:

Е (А, х, уо)<= Е (А, хо, уо)<= Е (А, хо, у)

Оптимальные смешанные стратегии  и цена игры называются решением матричной  игры.