Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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




Пусть матричная игра представлена платежной матрицей с элементами 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 можно найти среднее значение выигрыша, которое мы обозначим . Это среднее значение будет равно математическому ожиданию платежа. Поскольку платёж осуществляется с вероятностью , то математическое ожидание определяется по формуле

(1.10)

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

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

.

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

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

 

 

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

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


mylektsii.ru - Мои Лекции - 2015-2019 год. (0.032 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал