Матричные игры. Чистые и смешанные стратегии.
Простейшим вариантом игры является антагонистическая игра, в которой противодействуют две оперирующих стороны (2 игрока), при этом множества различных альтернатив из которых они выбирают решения конечны. Такая игра называется матричной.
М а т р и ч н о й и г р о й называется конечная игра двух лиц с нулевой суммой.
Тогда такая игра характеризуется конструкцией
(D1 ´ D2, { f1, f2 }). (5.7)
Участники игры могут выбирать свои решения из конечного множества альтернатив
D1 = X = { xi, i = 1,..., m },
D2 = Y = { yj, j = 1,..., n }.
Т.к. игра антагонистическая, то f1+f2=0. Откуда f1= f; f2= -f. В такой игре может быть m´n различных исходов, которые характеризуются различными значениями выигрыша первого игрока fij = f(xi,yj). Все эти исходы можно характеризовать прямоугольной матрицей выигрышей F (платежная матрица), элементы fij которой характеризуют выигрыш первого игрока и, соответственно, проигрыш второго при выборе игроками альтернатив, номера которых соответствуют номеру строки i и столбца j этой матрицы.
Итак, совокупность пар (xi,yj) характеризует множество исходов игры, а матрица, содержащая элементы соответствующие значениям выигрыша, называется п л а т е ж н о й м а т р и ц е й и имеет следующий вид
| y1 | y2 | . . . . . . . . . | yn | |
| x1 | f11 | f12 | . . . . . . . . . | f1n |
| x2 | f21 | f22 | . . . . . . . . . | f2n |
| F = | . . . | . . . | . . . . . . . . . | . . . |
| . . . | . . . | . . . . . . . . . | . . . | |
| xm | fm1 | fm2 | . . . . . . . . . | fmn |
В матричных играх, под стратегией понимается ход, приводящий к наибольшему выигрышу. Множество таких ходов у первого игрока равно X и его часто называют множеством ч и с т ы х с т р а т е г и й первого игрока.
Проанализируем рациональное поведение одного из игроков, например, первого. На каждую i-ю стратегию (ход, максимизирующий выигрыш) первого игрока, второй игрок ответит j-ой стратегией, которая минимизирует выигрыш первого игрока от применения его стратегии. Тогда гарантированный выигрыш первого игрока от применения i-ой чистой стратегии при использовании всех возможных стратегий второго игрока будет равен
Fi(-)= min fij, j=1,…,n
В этих условиях для первого игрока наилучшим (оптимальным) поведением представляется выбор стратегии, максимизирующей значение гарантированного выигрыша Fi(-), соответственно оптимальной стратегией является стратегия, на которой достигается
F(-) = max Fi(-) = max min fij. (5.8)
i i j
Это для первого игрока гарантированный выигрыш (при рациональном его поведении меньше этого значения он выиграть не может), который называется н и ж н е й ц е н о й и г р ы.
Стратегии, доставляющие первому игроку выигрыш, равный нижней цене игры называются г а р а н т и р у ю щ и м и.
Второй игрок, поступая аналогично, путем выбора своих гарантирующих стратегий может свести свой проигрыш к гарантированному минимуму
F(+) = min max fij , (5.9)
j i
который называется в е р х н е й ц е н о й и г р ы. Для первого игрока F(+) представляет собой максимально возможный выигрыш при рациональном поведении второго игрока. Обычно принято оба вида гарантирующих стратегий для краткости называть минимаксными.
Итак, первый игрок имеет m чистых стратегий, а второй игрок имеет n чистых стратегий. В каждой строке платежной матрицы F, характеризующей возможные исходы игры, первый игрок выбирает элемент матрицы, имеющий наименьшее значение, далее среди этих значений ищется наибольшее, которое и соответствует нижней цене игры. В каждом столбце матрицы второй игрок выбирает наибольшее значение, а затем среди этих значений находится наименьшее значение (наименьший проигрыш), что соответствует верхней цене игры.
Рациональным поведением игрока в такой ситуации является, очевидно, выбор гарантирующей стратегии, тогда его выигрыш будет находиться в диапазоне от F(-) до F(+).
Пример.
 6
| 3* | |||||||||
| F= | гарантирующие | |||||||||
| 3* | стратегии 1-го игрока | |||||||||
| 6* | 6* | |||||||||
гарантирующие стратегии
2-го игрока
F(-) = 3; F(+) = 6.
Если верхняя цена игры равна нижней F(-) = F(+) = С, то то игру называют игрой, р а з р е ш и м о й в ч и с т ы х с т р а т е г и я х, а значения верхней и нижней цены игры называют просто ц е н о й игры
max min fij = min max fij = С. (5.10)
i j j i
Соответствующие гарантирующие стратегии в этой ситуации являются о п т и м а л ь н ы м и и целесообразно выбирать именно такие стратегии.
Так как данная ситуация соответствует наличию седловой точки у платежной функции f(x,y) (функции двух векторных аргументов), то и игру называют и г р о й с с е д л о в о й т о ч к о й. Причем седловая точка определяется парой оптимальных чистых стратегий. Характерной особенностью такой игры является устойчивость поведения игроков, которая заключается в том, что любое отклонение одного из участников игры от своей оптимальной стратегии может привести только к большому проигрышу (в лучшем случае выигрыш останется без изменений). Так, например, в игре с платежной матрицей
| F = | ||||
имеется седловая точка (x3,y2). Совокупность соответствующих стратегий является решением игры, при этом цена игры равна 2.
Соответствующие чистые стратегии являются устойчивыми, так как отклонение каждого из игроков от оптимального решения приводит к худшим для этого игрока результатам.
Следует отметить, что имеется большое число ситуаций, когда матричная игра не разрешима в чистых стратегиях. Так в рассмотренном ранее примере верхняя цена игры равна 6, а нижняя цена игры равна 3. Таким образом седловая точка отсутствует. Тогда чистые стратегии становятся неустойчивыми, и выбор оптимальной чистой стратегии становится неопределенным.
Итак, в ситуациях, когда игра не разрешима в чистых стратегиях, выбор оптимальной стратегии становится неопределенным. Очевидно, что в одношаговой игре целесообразно выбирать гарантирующую стратегию. В то же время в многошаговых играх создается возможность повысить выигрыш за счет рациональной комбинации чистых стратегий, в том смысле, что бы выбирать их на каждом шаге с определенной вероятностью или частотой.
С м е ш а н н о й с т р а т е г и е й первого игрока называется упорядоченная последовательность m чисел p = (p1,p2,.. .,pm )т, удовлетворяющих условиям
m
pi ³ 0, i=1,...,m; S pi = 1. (5.11)
i=1
При этом числа pi, i=1,...,m интерпретируются как вероятности выбора i-ой чистой стратегии на каждом шаге игры, или как относительная частота выбора этой стратегии на нескольких шагах.
Аналогично смешанной стратегии первого игрока вводится смешанная стратегия второго игрока q = ( q1,q2,...,qn )т.
Следует отметить, что смешанная стратегия позволяет описывать и чистые стратегии. Действительно, в случае, когда pi=0, i = 1,...,m, i¹j, а pj = 1, смешанная стратегия соответствует чистой стратегии с номером j.
Смешанных стратегий у каждого игрока может быть достаточно много (бесконечно много), в этой связи целесообразно ставить вопрос о поиске оптимальной смешанной стратегии. Однако для того, чтобы производить поиск такой стратегии следует убедиться, существует ли она - оптимальная смешанная стратегия. Ответ на этот вопрос дает основная теорема теории игр.
О с н о в н а я т е о р е м а т е о р и и и г р (теорема о минимаксе). Любая матричная игра разрешима в смешанных стратегиях.
Таким образом у первого игрока (соответственно и у второго игрока) с у щ е с т в у е т оптимальная смешанная стратегия, применение которой позволяет максимизировать средний выигрыш в многошаговой матричной игре.
max min pтF q = min max pтF q = C . (5.12)
p q q p
Поясним приведенную основную теорему теории игр. Запишем матрицу игры в виде F = { fij }, где i = 1,...,m, j = 1,...,n. Смешанные стратегии первого игрока обозначим через p, смешанные стратегии второго игрока - через q. Тогда на каждом шаге 1-ый игрок выбирает свою i-ю чистую стратегию с вероятностью pi, а 2-ой игрок выбирает свою j-ю чистую стратегию с вероятностью qj.
В этом случае среднее значение величины выигрыша (математическое ожидание) определяется как
m n
С = S S pifijqj = pтF q. (5.13)
i=1 j=1
Средний выигрыш является скалярной функцией двух векторных аргументов p и q. Тогда существует седловая точка функции среднего выигрыша.
Итак, оптимальная смешанная стратегия существует. Необходимо решить вопрос о том как ее найти.
Пусть оптимальная смешанная стратегия p известна. Анализ оптимальной смешанной стратегии, показывает, что все ее компоненты можно разделить на две группы: равные нулю и большие нуля. Чистые стратегии, которым в оптимальной смешанной стратегии соответствуют нулевые компоненты называются п а с с и в н ы м и (неактивными) чистыми стратегиями. Действительно, если оптимальный стиль поведения в многошаговой игре, который описывается оптимальной смешанной стратегией, предписывает на каждом шаге выбирать некоторые стратегии с вероятностью 0, то такие стратегии естественно назвать пассивными.
Чистые стратегии, которым в оптимальной смешанной стратегии соответствуют компоненты большие нуля называются а к т и в н ы м и стратегиями.
Компоненты смешанной стратегии ассоциируются с вероятностями применения соответствующих чистых стратегий, тогда активность стратегии соответствует целесообразности ее применения в многошаговой игре. Соответственно пассивные чистые стратегии можно не рассматривать вообще, что создает основу для упрощения игры. Для выделения пассивных стратегий вводится понятие доминирующих (доминируемых) стратегий.
Чистая стратегия первого игрока с номером i д о м и н и р у е т чистую стратегию с номером k, если для элементов платежной матрицы выполняется условие fij ³ fkj, j = 1,...,n, и хотя бы одно неравенство строгое. Тогда говорят, что i-ая стратегия, доминирует стратегию k-ую, или k-ая стратегия, доминируется стратегией i-ой. Аналогично для второго игрока чистая стратегия с номером j доминирует чистую стратегию с номером k, если выполняется условие fij £ fik, i = 1,...,m.
Говорят, что i-я чистая стратегия первого игрока доминируется л и н е й н о й к о м б и н а ц и е й некоторого подмножества L других его чистых стратегий, если выполняется условие
fij £ S lk fkj , j = 1,...,n, L Í {1,..., m}
kÎL
и хотя бы одно неравенство строгое. Здесь lk - коэффициенты, удовлетворяющие условиям
lk³0, kÎL; Slk = 1.
kÎL
Доминируемые стратегии всегда пассивны, и наоборот, если стратегия пассивна, то она доминируется какой-либо чистой стратегией, или линейной комбинацией стратегий.
Например, пусть задана платежная матрица в виде
| F = | ||||
Анализ матрицы F показывает, что 3-я стратегия первого игрока доминируется линейной комбинацией 1-ой и 2-ой стратегий с коэффициентами 2/3 и 1/3; 1-я стратегия второго игрока доминируется его 4-ой стратегией, а 2-я стратегия доминируется линейной комбинацией 3-ей и 4-ой стратегий с коэффициентами 0.75 и 0.25. Тогда игровая модель с платежной матрицей F эквивалентна модели с матрицей
П р и м е ч а н и е. Сравнивая выражение, записанное при определении смешанной стратегии, и выражение для линейной комбинации стратегий, заметим, что элементы смешанной стратегии, по существу, представляют собой коэффициенты линейной комбинации всех чистых стратегий соответствующего игрока.
Существует следующее утверждение, имеющее важное прикладное значение.
Утверждение (об активных стратегиях). Выигрыш от использования оптимальной смешанной стратегии, примененной против любой активной стратегии или линейной комбинации активных стратегий, равен цене игры .
Следовательно, если игрок в процессе игры не выходит из класса своих активных стратегий, то при любом поведении противника (даже, если тот применяет оптимальную смешанную стратегию) он не проиграет больше цены игры (может проиграть меньше). В том случае, если он использует пассивные стратегии, то проигрыш может быть больше цены игры.
Тогда, если p* - оптимальная смешанная стратегия первого игрока, то выигрыш первого игрока при использовании p* против некоторой j-ой чистой стратегии второго игрока вычисляется как
p*тF ej ³ C , (5.14)
где ej - вектор, такой что его компоненты eji=0, i=1,...,n, i¹j, а ejj=1.
Утверждение (о числе активных стратегий). В любой матричной игре с платежной матрицей F размерности (m´n) количество активных стратегий каждого игрока не превосходит min {m, n} (наименьшего из чисел m и n).