Исследование операций. Теория игр. Лекция 8

Исследование операций
Теорема 2. Для матричной игры с платёжной матрицей H имеют место соотношения
Доказательство. По теореме 1 .
Аналогично
Теорема 3. Если p и q стратегии игроков, а v некоторое число, причём
то p и q оптимальные стратегии игроков и I=v.
Доказательство. Из теоремы 1 имеем
Из неравенства в формулировке теоремы получим
19.09.2011
Исаченко А.Н. Лекция 5
Теория игр

Исследование операций
Следствие 1. Если p и q стратегии игроков, а v – число, причём
то p и q оптимальные стратегии и v=I.
Следствие 2. Если p и q стратегии игроков, то для их оптимальности достаточно выполнения
неравенства
Теорема 4. Каждая пара оптимальных смешанных стратегий игры с платёжной матрицей
является парой оптимальных смешанных стратегий игры с платёжной
матрицей , где k – произвольная константа.
Доказательство. Пусть p*,q* -пара оптимальных стратегий для игры с платёжной
матрицей H. Тогда по определению значения игры получим
Получим
что по следствию 1 доказывает теорему.
21.09.2011
Исаченко А.Н. Лекция 6
Теория игр

Исследование операций
Доминирование стратегий
Пусть конечная игра представлена платёжной матрицей H. Говорим, что для первого игрока
стратегия p’ доминирует стратегию p’’, если
Иными словами для любой чистой стратегии второго игрока выигрыш первого игрока при
применении им стратегии p’ не меньше выигрыша при применении им стратегии p’’. Если
все неравенства в системе строгие, то говорим о строгом доминировании, а при наличии
хотя бы одного равенства – о нестрогом доминировании.
Аналогично, для второго игрока стратегия q’ доминирует стратегию q’’, если
При этом говорят о строгом доминировании, если все неравенства строгие, и о нестрогом
доминировании в противном случае.
В частности, чистая стратегия первого игрока доминирует его чистую стратегию
если
Чистая стратегия второго игрока доминирует чистую стратегию , если
21.09.2011
Исаченко А.Н. Лекция 6
Теория игр

Исследование операций
Теорема 1. Если для первого игрока стратегия p’ доминирует стратегию p’’ и стратегия p’’
оптимальна, то стратегия p’ также оптимальна.
Доказательство. В силу доминирования выполняются неравенства
Откуда получим
В силу оптимальности получим Поэтому также оптимальна.
Аналогичное утверждение справедливо для стратегий второго игрока.
Лемма 1. Если чистая стратегия первого игрока строго (нестрого) доминируется его
стратегией p, отличной от стратегии , то для стратегии существует строго
(нестрого) доминирующая стратегия p’ с вероятностью .
Доказательство. Так как стратегия p отлична от чистой стратегии , то . По
вектору p составим вектор p’ с компонентами Очевидно p’ является
стратегией первого игрока с нулевой вероятностью применения чистой стратегии .
Из условия строгого доминирования получим Разделив обе части на
получим
Случай нестрогого доминирования доказывается аналогично.
21.09.2011
Исаченко А.Н. Лекция 6
Теория игр

Исследование операций
Теорема 2. Если чистая стратегия первого игрока строго доминируется его стратегией
p, то входит с нулевой вероятностью в любую оптимальную стратегию.
Если чистая стратегия нестрого доминируется его стратегией p, отличной от стратегии , то существует оптимальная стратегия первого игрока, в которую входит с
нулевой вероятностью.
Доказательство. Рассмотрим случай строгого доминирования. Пусть игра задаётся
платёжной матрицей H. Предположим, что существует оптимальная стратегия p* первого
игрока, причём . В соответствии с леммой 1 мы можем считать, что в стратегии p
Вероятность . В силу строгого доминирования
Получим
Так как при всех и , то положив , получим
что противоречит оптимальности p* . Следовательно, у любой оптимальной
стратегии первого игрока p* координата .
Заменой строгих неравенств на нестрогие доказывается вторая часть теоремы.
21.09.2011
Исаченко А.Н. Лекция 6
Теория игр

Исследование операций
Следствие 1. Пусть игра задана платёжной матрицей H и чистая стратегия первого
игрока доминируется некоторой его стратегией p, отличной от . Положим, что H’ –
матрица, полученная из H отбрасыванием её строки с номером i0 и p’ стратегия
оптимальная в игре с платёжной матрицей H’. Тогда стратегия p*, полученная из p’ вставкой
нуля на место i0-ой компоненты, является оптимальной для исходной игры. Причём
значения игр совпадают.
Доказательство. Пусть q* - оптимальная стратегия второго игрока в игре с платёжной
матрицей H’. Тогда
при всех i≠i0 и ∀ j. Здесь I’ – значение игры с платёжной матрицей H’. С другой стороны, так
как доминируется p, то
Далее
Cледовательно p*, q* является парой оптимальных стратегий в игре с платёжной матрицей
H, со значением игры I’.
21.09.2011
Исаченко А.Н. Лекция 6
Теория игр

Исследование операций
Связь матричных игр с линейным программированием.
Рассмотрим матричную игру с матрицей выигрышей . Не нарушая общности
будем считать, что Построим две двойственные задач ЛП:
(З1) (З2)
Все элементы матрицы H по предположению положительны, поэтому многогранные
множества задач (З1) и (З2) ограничены соответственно снизу и сверху. Многогранник
задачи (З2) не пуст, так как y = 0 является допустимым планом. Следовательно, задача (З2),
а с ней (по первой теореме двойственности) и задача (З1) разрешимы, и их функционалы в
оптимальных планах x* , y* совпадают (вторая теорема двойственности):
Из условий задачи 1 следует, что Обозначим
Получим т.е. являются смешанными
стратегиями игроков.
26.09.2011
Исаченко А.Н. Лекция 7
Теория игр

Исследование операций
Имеем,
Или
Умножим каждое из неравенств первой (второй) группы на компоненты произвольной
смешанной стратегии второго (первого) игрока и сложим результаты. Получим
Следовательно оптимальные стратегии игроков, а - значение игры.
Таким образом, чтобы найти решение матричной игры надо перейти к задаче с тем же
оптимальным решением, что и у исходной задачи, но с положительными элементами,
затем построить пару двойственных задач линейного программирования и найти их
решение (например симплекс-методом). По полученному решению вычислить значения
компонент оптимальных стратегий игроков и найти значение игры.
26.09.2011
Исаченко А.Н. Лекция 7
Теория игр