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

Пусть матричная игра представлена платежной матрицей с элементами a_ij, где 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 будет непрерывна на компактном множестве S_x х S_y.

Очевидно, что первый игрок заинтересован в том, чтобы платёж был как можно больше, а второй в том, чтобы платёж был как можно меньше. В соответствии с принципом гарантированного результата 1-й игрок для каждой смешанной стратегии x из множества S_x определяет наименьшее по y значение функции H(x, y) на множестве S_y. Наименьшее значение, которое мы обозначим H (x, y(x)) существует и достигается при y=y(x) в силу непрерывности функции H(x, y) на компактном ограниченном множестве S_y. Так же можно доказать, что функция y=y(x) является непрерывной по x на компактном множестве S_x. Затем 1-й игрок находит значение векторного аргумента x^*, для которого функция H(x, y(x)) достигает максимума на множестве S_x. В силу непрерывности функции H(x, y(x)) на компактном ограниченном множестве S_x, она достигает там своего наибольшего значения

Число называется нижним значением игры в смешанных стратегиях. Число называется верхним значением игры в смешанных стратегиях.

Теорема 3. Нижнее значение игры в смешанных стратегиях меньше или равно верхнему значению игры в смешанных стратегиях, т.е. справедливо неравенство

.

Доказательство

Зафиксируем смешанную стратегию x из множества S_x и обозначим H(x, y(x)) наименьшее значение функции H(x, y) на компактном ограниченном множестве S_y. Тогда для всех x из S_x и y из S_y выполняется неравенство

H(x, y(x))≤ H(x, y) (1.11)

В соответствии с определением нижнее значение игры будет равно

=max_x 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 из S_y. (1.13)

Зафиксируем смешанную стратегию y из множества S_y и обозначим H(x(y), y) наибольшее значение функции H(x, y) на компактном ограниченном множестве S_x. Тогда для всех x из S_x и y из S_y выполняется неравенство

H(x(y), y)≥ H(x, y) (1.14)

В соответствии с определением нижнее значение игры будет равно

=min_y 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 из S_x.

Подставляя в неравенство (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 верно неравенство

α ≤ a_i~j (1.23)

Возьмем произвольную смешанную стратегию y={ y₁, y₂, …, y_n} из S_y. тогда справедливо . Умножим обе части неравенства (1.23) на y_j≥ 0 и просуммируем по индексу j от 1 до n, получим неравенство

α ≤ ∑ a_i~j y_j (1.24)

Введем вектор x^~={x^~₁, x^~₂, …, x^~_m}, где x^~_i=1, если i= i^~ и x^~_i=0, если i ≠ i^~. Вектор x^~ удовлетворяет свойствам смешанной стратегии, поэтому положим, что x^~ принадлежит множеству S_x. Преобразуем правую часть неравенства (1):

∑ a_i~j y_j=∑ ∑ a_i~j x^~_i y_j =Η (x^~, y)

Тогда из неравенства (1.24) следует, что для любой смешанной стратегии y из S_y справедливо неравенство

α ≤ Η (x^~, y) (1.25)

По определению . Обозначим H(x, y(x)) наименьшее значение функции H(x, y) на множестве S_y, тогда для всех x из S_x будет верно неравенство

≥ 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 независимо от характера действий другого участника игры в пределах его активных стратегий.

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

.

С другой стороны, по определению значение игры будет равно

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

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

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