§2.1.4. Смешанное расширение игры

Пусть матричная игра представлена платежной матрицей с элементами aij, где i=1,2,…,m – стратегии первого игрока, j=1,2,…,n – стратегии второго игрока. Данные стратегии игроков будем называть чистыми стратегиями.


В предыдущем параграфе мы доказали, что решение матричной игры в чистых стратегиях (т.е. при выборе каждым игроком одной и только одной стратегии из заданного множества его стратегий) существует тогда и только тогда, когда платежная матрица имеет седловую точку. Рассмотрим выбор стратегий в игре без седловой точки. Если игрок может предвидеть, какую из чистых стратегий изберёт противник, он может найти наилучший ответ на ход противника. Таким образом, каждый игрок заинтересован в том, чтобы его ходы были непредсказуемы. Для этого необходимо ввести в выбор стратегий элемент случайности. Однако отсутствие логики при выборе стратегий ухудшит положение каждого из игроков. Компромисс заключается в том, что игроки чередуют (смешивают) свои стратегии случайным образом, но по определённой разумной схеме. Этой схеме должна соответствовать комбинация чистых стратегий.
Введем следующие изменения правил игры: каждый игрок наряду с отдельными стратегиями из своего множества стратегий может применять их комбинации, в которых стратегии представлены в определенных пропорциях.
Рассмотрим матричную игру, представленную Таблицей 5.
Таблица 5

2-й игрок



1-й игрок

где – частота (вероятность) с которой первый игрок собирается использовать свою стратегию 1;
– частота (вероятность) с которой первый игрок собирается использовать свою стратегию 2;

– частота (вероятность) с которой первый игрок собирается использовать свою стратегию m.
Вектор называют смешанной стратегией первого игрока. Из определения вероятности:
.
Аналогично второй игрок чередует (смешивает) свои стратегии так, чтобы:
Стратегия 1 имела частоту (вероятность) ;
Стратегия 2 имела частоту (вероятность) ;

Стратегия n имела частоту (вероятность) .
Вектор называется смешанной стратегией второго игрока. Очевидно, что
.
Возможность применять наряду со стратегиями и , которые мы будем называть чистыми стратегиями 1-го и 2-го игроков соответственно, смешанных стратегий x и y, изменяет условия игры, расширяет их. Поэтому переход от чистых стратегий к смешанным стратегиям называют смешанным расширением игры.
Множества смешанных стратегий 1-го и 2-го игроков представляют собой соответственно:
– множество m-мерных векторов, координаты которых удовлетворяют условиям:
;
– множество n-мерных векторов, координаты которых удовлетворяют условиям:
.
Очевидно, что чистые стратегии игроков входят как элементы в множество их смешанных стратегий.
Пусть первый игрок выбрал некоторую смешанную стратегию x, а второй – y. Тогда каждый исход из платёжной матрицы становится случайным событием. Найдём вероятность этого события. Для того, чтобы осуществился исход , первый игрок выбирает стратегию i с вероятностью , а второй игрок выбирает стратегию j с вероятностью . В силу независимости выбора вероятность исхода равна вероятности совместных наступлений двух независимых событий, т.е. произведению их вероятностей .
Для каждой пары смешанных стратегий x€X и y€Y можно найти среднее значение выигрыша, которое мы обозначим . Это среднее значение будет равно математическому ожиданию платежа. Поскольку платёж осуществляется с вероятностью , то математическое ожидание определяется по формуле

Легко проверить, что функция H(x,y) двух векторных переменных x и y будет непрерывна на компактном множестве Sx х Sy.
Очевидно, что первый игрок заинтересован в том, чтобы платёж был как можно больше, а второй в том, чтобы платёж был как можно меньше. В соответствии с принципом гарантированного результата 1-й игрок для каждой смешанной стратегии x из множества Sx определяет наименьшее по y значение функции H(x,y) на множестве Sy. Наименьшее значение, которое мы обозначим H (x,y(x)) существует и достигается при y=y(x) в силу непрерывности функции H(x,y) на компактном ограниченном множестве Sy. Так же можно доказать, что функция y=y(x) является непрерывной по x на компактном множестве Sx. Затем 1-й игрок находит значение векторного аргумента x*, для которого функция H(x,y(x)) достигает максимума на множестве Sx. В силу непрерывности функции H(x,y(x)) на компактном ограниченном множестве Sx, она достигает там своего наибольшего значения
Число называется нижним значением игры в смешанных стратегиях. Число называется верхним значением игры в смешанных стратегиях.
Теорема 3. Нижнее значение игры в смешанных стратегиях меньше или равно верхнему значению игры в смешанных стратегиях, т.е. справедливо неравенство
.
Доказательство
Зафиксируем смешанную стратегию x из множества Sx и обозначим H(x,y(x)) наименьшее значение функции H(x,y) на компактном ограниченном множестве Sy. Тогда для всех x из Sx и y из Sy выполняется неравенство
H(x,y(x))≤ H(x,y) (1.11)
В соответствии с определением нижнее значение игры будет равно
=maxx H(x,y(x))= H(x*,y(x*)), (1.12)
где x* - максиминная стратегия 1-го игрока.
Подставляя в неравенство (1.11) x=x*, получим H(x*,y(x*))≤H(x*,y), и с учетом (1.12), получим неравенство
≤ H(x*,y) для всех y из Sy. (1.13)
Зафиксируем смешанную стратегию y из множества Sy и обозначим H(x(y),y) наибольшее значение функции H(x,y) на компактном ограниченном множестве Sx. Тогда для всех x из Sx и y из Sy выполняется неравенство
H(x(y),y)≥ H(x,y) (1.14)
В соответствии с определением нижнее значение игры будет равно
=miny H(x(y),y)= H(x(y*),y*) (1.15)
где y* - минимаксная стратегия 2-го игрока.
Подставляя в неравенство (1.14) y= y*, получим H(x(y*),y*)≥H(x,y*), с учетом (1.15), получим неравенство
≥ H(x,y*), (1.16)
верное для всех x из Sx.
Подставляя в неравенство (1.13) y= y*, и в неравенство (1.16) x=x*, получим неравенства
≤ H(x*,y*) и ≥ H(x*,y*),
откуда следует
≤ H(x*,y*)≤ (1.17)
Теорема доказана.

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

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

Для того, чтобы применение стратегий , давало игрокам гарантированные результаты, необходимо, чтобы выполнялись неравенства
(1.20)
т.е., чтобы исход был равновесным. Как доказано в теореме 3, для этого необходимо и достаточно, чтобы выполнялись равенства
(1.21)
то есть необходимо и достаточно, чтобы нижнее значение игры было равно верхнему значению игры (1.22)

Примем без доказательства теорему 4.
Теорема 4.
В любой матричной игре нижнее значение игры в смешанных стратегиях равно верхнему значению игры в смешанных стратегиях, т.е. .
Теорема (4) доказывает существование решения матричной игры в смешанных стратегиях. Число v называется значением игры в смешанных стратегиях.
Равновесные стратегии и называют оптимальными стратегиями, имея в виду, что критерием оптимальности служит принцип гарантированного результата.
Совокупность v (значение игры) и (оптимальные стратегии) называют решением игры в смешанных стратегиях.
Решение игры обладает следующими свойствами:
Свойство 1. Пусть – нижнее значение игры в чистых стратегиях, а – нижнее значение игры в смешанных стратегиях. Тогда

Доказательство.
По определению . Пусть максимум по i достигается при i=i~, тогда для всех j=1.2…,n верно неравенство
α≤ai~j (1.23)
Возьмем произвольную смешанную стратегию y={ y1, y2,…, yn} из Sy. тогда справедливо . Умножим обе части неравенства (1.23) на yj≥0 и просуммируем по индексу j от 1 до n, получим неравенство
α≤∑ai~j yj (1.24)
Введем вектор x~={x~1, x~2,…, x~m}, где x~i=1, если i= i~ и x~i=0, если i ≠ i~. Вектор x~ удовлетворяет свойствам смешанной стратегии, поэтому положим, что x~ принадлежит множеству Sx. Преобразуем правую часть неравенства (1):
∑ai~j yj=∑∑ai~j x~i yj =Η(x~,y)
Тогда из неравенства (1.24) следует, что для любой смешанной стратегии y из Sy справедливо неравенство
α≤ Η(x~,y) (1.25)
По определению . Обозначим H(x,y(x)) наименьшее значение функции H(x,y) на множестве Sy, тогда для всех x из Sx будет верно неравенство
≥ H(x,y(x)), подставляя в последнее неравенство x=x~, получим
≥ H(x~,y(x~)) (1.26)
В неравенство (1.25) подставим y= y(x~), получим
α≤ Η(x~, y(x~) (1.27)
Из неравенств (1.26) и (1.27) следует ., что и требовалось доказать

Свойство 2. Пусть – верхнее значение игры в чистых стратегиях, а – верхнее значение игры в смешанных стратегиях. Тогда

Доказывается аналогично свойству 1.
Свойство 3. Нижняя чистая цена игры и верхняя чистая цена игры ограничивают значение сверху и снизу значение игры в смешанных стратегиях: .
Доказательство следует из теоремы (4) и свойств (1) и (2).
Свойство 4. Если матричная игра имеет равновесие в чистых стратегиях, то чистое значение игры равно значению игры в смешанных стратегиях, то есть при будет справедливо

Доказательство следует из свойства (3).
В случае, когда матричная игра имеет седловую точку, оптимальная смешанная стратегия первого игрока будет иметь вид
.
И оптимальная смешанная стратегия 2-го игрока будет иметь вид
.
Таким образом, равновесия в чистых стратегиях является частным случаем равновесия в смешанных стратегиях.
5. Теорема об активных стратегиях.
Стратегия i первого игрока называется его активной стратегией, если в оптимальной стратегии вероятность . Аналогично стратегия j игрока 2 называется его активной стратегией, если в оптимальной стратегии вероятность .
Теорема 5. Если один из участников игры применяет свою оптимальную стратегию, то ожидаемый выигрыш останется неизменным и равным v независимо от характера действий другого участника игры в пределах его активных стратегий.
Доказательство. Обозначим для каждых , где – множество оптимальных стратегий первого игрока; для каждых , где – множество оптимальных стратегий второго игрока. Пусть второй игрок выбрал чистую стратегию тогда величина среднего выигрыша будет равна . Данный средний выигрыш достигается в том случае, когда первый игрок выбирает свою оптимальную стратегию а второй игрок реализует чистую стратегию из числа активных. Очевидно, что
.
С другой стороны, по определению значение игры будет равно

Таким образом, получаем систему



Это условие может выполняться только в случае, когда


Теорема доказана.