Если в игре с матрицей А нижнее и верхнее, чистые цены игры совпадают т.е. , то говорят, что эта игра имеет седловую точку, в чистых выражениях и чистую цену игры:
Седловая точка — это пара чистых стратегий (i0, j0) первого и второго игрока, при котором достигается равенство .
В понятии седловой точки вложен следующий смысл:
если один из игроков придерживается стратегии, соответствующей седловой точки, то другой игрок не может поступить лучше, чем придерживаться стратегии, соответствующей седловой точки.
— отклонение первого игрока от седловой точки может приводить только к уменьшению его выигрыша.
— отклонение второго игрока от седловой точки может приводить к увеличению его проигрыша .
Седловой элемент — является минимальным элементом строки и максимальным элементом в столбце.
Для определения седлового элемента необходимо последовательно в каждой точке определить минимальный элемент, а затем проверять является ли он максимальным элементом столбца и если является, тогда таким образом найдена седловая точка — цена игры, оптимальные стратегии первого и второго игрока:
Если .
y1
yl
…
yj
…
ym
x1
…
xi
ail
aij
…
xk
akl
akj
…
xn
— если все элементы матрицы одинаковы, то каждая из них будет седловым.
Пример:
10 3 6 6
Найти минимальный элемент в строке, который равен максимальному в столбце .
Поменяем знак: —3
β=2; α=-2 ⇒
Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий.
— для первого игрока
— для второго игрока
Чистая стратегия — это чистый случай смешанной стратегии. Чистые стратегии являются несовместимыми стратегиями, т.е. применение одной чистой стратегии исключает применение любой другой стратегии.
— средний выигрыш одного игрока
Теорема Фон–Неймана:
Для матричной игры с любой матрицей А величины α и β существуют и равны между собой :
Следствия из теоремы Фон–Неймана:
Для того, чтобы смешанная стратегия , первого игрока была оптимальной смешанной стратегией матрицы игр с матрицей А и ценой игры необходимо и достаточно выполнение следующих неравенств.
(1)
т.е. математическое ожидание любого столбца должна быть больше цены игры.
Аналогично для второго игрока: смешанная стратегия является оптимальной смешанной стратегией, если выполняется следующие n-неравенств:
(2)
т.е. математическое ожидание каждой строки матрицы должна быть меньше цены игры.
Таким образом, из следствия теоремы Фон–Неймана вытекает:
— чтобы установить , является ли предлагаемая смешанная стратегия решением матричной игры достаточно проверить, удовлетворяют ли они соотношениям (1), (2).
(3)
Решение матричной игры
Для матричной игры неравенство (1) и (2) можно превратить в строгие равенства, тогда из (I) части можно получить:
Пример: Две фирмы выпускают периодически издания.
Заменить вторую стратегию на третью:
т.е. когда смешанные стратегии приводят к неудобству производства, они могут быть заменены на чистые стратегии, которые получились в результате расчетов средних значений по каждому виду продукции.
Должны выполняться два условия:
1. расходы не превышают 40000
2. ν = 4820 и не меньше:
I стратегия рынка:
II стратегий рынка:
Методы поиска оптимальных смешанных стратегий для матричных игр, размерами больше, чем
Рассмотрим случай матричной игры :
Используя другие подходы:
1. возможное преимущество одной стратегии над другой стратегией.
Рассмотрим I и к-ю стратегию
Если для і, к-й стратегий першого игрока выполняется соотношение:
причем, хотя бы одна из неравенств является строгим, то говорят, что стратегия і превосходит (доминирует) стратегию к и в этом случае стратегию к первому игроку применять невыгодно и она входит в смешанную стратегию этого игрока с нулевой вероятностью.
Лекция № 9
II-й игрок (матрица проигрышей, чем меньше элемент, тем лучше)
y1 … yj … ym
I-й игрок (матрица выигрышей), чем больше элемент, тем лучше.
Вторая стратегия r второго игрока доминирует j, если выполняется неравенство:
При этом хотя бы одно из неравенств является строгим.
Следовательно II игр нет смысла применять j-ю стратегию, т.к. для него это матрица проигрышей (из неравенства).
Если имеется доминирование стратегий в некоторой матричной игре А, то доминируемые стратегии могут быть вычеркнуты из матрицы А и получена новая матричная игра А1, имеющая меньшие размеры матрицы.
Если в этой матричной игре А1 обнаруживается доминирование стратегий, то эта матрица снова может быть преобразована путем вычеркивания доминирующих стратегий, следовательно, матрица .
Процесс может продолжаться до тех пор пока позволяют условия, либо пока матрица не станет .
Пример: Пусть имеется матричная игра .
2 6
(для первого игрока);
(для второго игрока).
Признаки нулевых вероятностей применения чистых стратегий в смешанных стратегиях
1. Если некоторая стратегия подчинена выпуклой линейной комбинации двух других стратегий, то подчиненная чистая стратегия входит с нулевой вероятностью в смешанную стратегию.
Допустим, что существуют чистые стратегии k, l, r и число такие, что выполняются условия:
,
для первого игрока: ; ;
т.е. стратегия к подчинена выпуклой линейной комбинации стратегий l и r.
Если в неравенстве стоит n элементов, тогда:
и
В этом случае можно говорить о линейной выпуклой комбинации элементов при коэффициентах .
Рассмотрим обобщенную стратегию второго игрока: и умножим неравенство на соответствующее:
и сложим эти неравенства (их m штук):
(1)
Теперь можем воспользоваться следствием из теоремы Фон-Неймана:
— математическое ожидание в столбце меньше или равно цены игры.
,
т.е. первому игроку нет смысла применять подчиненную j-ю стратегию, т.к. он получит выигрыш меньше цены.
Обобщение первого признака
Если некоторая чистая стратегия подчинена выпуклой линейной комбинации n других стратегий, то подчиненная чистая стратегия входит с нулевой вероятностью в смешанную стратегию:
то тогда к-я стратегия не должна применяться первым игроком.
Для второго игрока знак меньше меняется на больше.
Пример: Пусть имеется матричная игра
2. Второй признак нулевой вероятности применения чистых стратегий в смешанных.
Если выполняется линейная комбинация стратегий, подчинена выпуклой линейной комбинации других стратегий, то в подчиненной выполняются комбинации стратегий, существует по меньшей мере одна чистая, входящая в смешанную с нулевой вероятностью.
k, l, r, s подчинена выпуклой линейной комбинации стратегий r, s, т.е. выполняется неравенство:
(для первого игрока)
Умножаем эти m неравенств на компоненты смешанной стратегии второго игрока: и суммируем полученное неравенство по j:
(2)
Воспользуемся соотношением из теоремы Фон-Неймана:
Математическое ожидание по строкам меньше или равно цены игры.
т.е. противоречие с нашим допущением, что первая сумма и вторая сумма равна в выражении (2). Следовательно, одна из этих сумм меньше и, следовательно, одна из стратегий: к или l должны входить с нулевой вероятностью в смешанную стратегию первого игрока.
Численные методы решения матричных игр
1. Метод последовательного приближения цены игры.
Применяется, когда седловая точка не обнаружена или исходную матрицу нельзя привести к размерности .
Сущность метода последовательного приближения цены игры состоят в следующем: мысленно игра проводится много раз, т.е. последний проигрывается много партий. В каждой партии игры каждый игрок выбирает ту стратегию, которая дает ему наибольший общий выигрыш во всех партиях, включая текущую. После каждой партии вычисляется: среднее значение выигрыша первого игрока, проигрыша второго игрока, а их среднее арифметическое применяется за приближенные значения цены игры.
Для определения оптимальных смешанных стратегий обоих игроков подсчитывается частота применения каждой чистой стратегии, которая применяется каждой чистой стратегии, которая принимается за приближенное значение вероятности использования этой чистой стратегии в оптимальной смешанной стратегии соответствующего игрока.
Доказано, что при неограниченном увеличении числа партий, средний выигрыш первого игрока и средний проигрыш второго игрока будут неограниченно стремиться к цене игры (), а приближенное значение смешанных стратегий будут стремиться к оптимальным смешанным стратегиям каждого игрока.
Объем вычислений в методе пропорционален сумме числа строки столбцов матричных игр. Сходимость метода достаточно медленная, но компетентная реализация позволит им пользоваться.
Пример: Существует матричная игра :
3 4 6
нет седловой точки
№
пар-тии
Страте-гия
II-го игрока
Суммарный выигрыш I-го игрока
Страте-гия
I-го игрока
Суммарный проигрыш II -го игрока
Средний выигрыш
I-го игрока
Сред-ний выи-грыш
II-го игрока
Цена
игры,
n
-1
-2
-2
0.5
(3-2)=1
(-1+4)=3
(2+2)=4
(3+2)=5
(-2+2)=0
(4+6)=10
4/2=2
0/2=0
Среднее арифметическое:
Лекция № 10