Активные стратегии игрока теорема об активных стратегиях

Решение матричной игры () среди смешанных стратегий. Теорема об активных стратегиях.

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

Анализируя
платежные матрицы игр (),
мы показали, что если каждому игроку
предоставить выбор только одной
стратегии, то в расчете на разумного
противника этот выбор должен определяться
принципом минимакса. При этом игрок

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

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

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

Пусть имеется игра
()
без седловой точки. Игрок

имеет стратегии
,
а игрок

— стратегии
.
Обозначим смешанную стратегию игрока

как
,
в которой стратегии

применяются с вероятностями

соответственно.
Очевидно для этих вероятностей справедливы
условия:

Смешанную
стратегию игрока

обозначим
,
в которой стратегии

применяются с вероятностями
.
Они удовлетворяют условиям:

Отметим, что
смешанных стратегии бесчисленное
множество, так как вероятностей
,
удовлетворяющих условиям (1)-(2) ((3)-(4))
бесчисленное множество.

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

Допустим игроки

и

используют соответственно свои смешанные
стратегии

и
.
Тогда среднее значение выигрыша будет
равно:

Пусть оптимальными
смешанными стратегиями игроков

и

будут соответственно:

и

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

называется ценой игры.

Из определения
оптимальной пары ()
следует неравенство:

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

и

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

Теорема
об активных стратегиях.

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

Доказательство.
Пусть найдено решение игры ()
в смешанных стратегиях, в которых первые

стратегий

игрока

и первые

стратегий

игрока

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

и
.

Для
найденных вероятностей справедливы
равенства

и
.
Выигрыш при этом равен цене игры:

Выигрыш игрока
,
если он пользуется оптимальной смешанной
стратегией
,
а игрок

— чистыми стратегиями
,
обозначим через
.
Из свойства оптимального решения игры
следует, что отклонение игрока

от оптимальной стратегии

может лишь увеличить его проигрыш.
Следовательно
.

Выразим теперь
цену игры

при оптимальной паре ()
через выигрыш
.
Так как в оптимальной смешанной стратегии

стратегии

применяются с вероятностями
,
то
.
При этом справедливо
.
Сумма

есть средневзвешенне

.
Но средневзвешенное значение было бы
больше
.
Следовательно
.

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Если игрок А выбирает смешанную стратегию SA=||p1, p2, …, pm||, а игрок В смешанную стратегию SB=||q1, q2, …, qn||,то средний выигрыш математическое ожидание выигрыша игрока А (проигрыша игрока В) определится суммой

,

Которая может рассматриваться в качестве характеристики выбранных SА и SB.

Формируя свою стратегию SА в антагонистической игре, игрок А в соответствии с принципом максимина должен выбрать такую стратегию, при которой минимально возможный выигрыш был бы максимален, т. е. такую стратегию, которая обеспечивает

(2.7)

Аналогичные рассуждения, связанные с поиском оптимальной смешанной стратегии игрока В, приводят к рекомендации выбрать такую стратегию SB, которая обеспечивает

. (2.8)

Весьма важным для теории и практики является вопрос о том, связаны ли между собой VА и VB. Ответ на него дает теорема о максимине.

Теорема о максимине. В конечной игре двух игроков (коалиций) с нулевой суммой (матричной игре) при Имеет место равенство

. (2.9)

Теорема о максимине указывает на существование равновесия для случая VА=VB, при и, следовательно, существования оптимальных смешанных стратегий.

Поэтому другая формулировка теоремы о максимине, называемая основной теоремой матричных игр определяется следующим образом.

Основная теорема матричных игр. Любая матричная игра имеет, по крайней мере, одно оптимальное решение, в общем случае, в смешанных стратегиях и соответствующую цену V.

Обе эти теоремы эквивалентны. Из этих теорем следует, что любая матричная игра имеет цену V. Цена игры V — средний выигрыш, приходящийся на одну партию, — всегда удовлетворяет условию

A£n£b, (2.10)

Т. е. лежит между нижней a и верхней b ценами игры.

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

Эта пара стратегий образует в игре положение равновесия: один игрок хочет обратить выигрыш в максимум, другой — в минимум, каждый “тянет” в свою сторону и, при оптимальном поведение обоих, устанавливается равновесие и устойчивый выигрыш n.

Определение. Те из чистых стратегий игроков А и В, которые входят в их оптимальные смешанные стратегии с вероятностями, не равными нулю, называются Активными стратегиями.

Существует теорема об активных стратегиях, применение которой позволяет упрощать решение некоторых матричных игр.

Теорема об активных стратегиях. Если один из участников матричной игры G (MXN), придерживается своей оптимальной смешанной стратегии, то это обеспечивает ему максимальный средний выигрыш, равный цене игры n, независимо от того, какие действия предпринимает другой игрок, если только он не выходит за пределы своих активных стратегий (т. е. пользуется любой из них в чистом виде или смешивает их в любых пропорциях), причем число активных стратегий каждого игрока, входящих в их оптимальные смешанные стратегии, не превосходит L, где L = min(m, n).

Использование данной теоремы позволяет в частности, упрощать решение матричных игр 2XN и MX2.

< Предыдущая		Следующая >

Постановка задачи и гипотеза исследования

В работе представлены результаты исследования возможности качественной модернизации итеративного метода Брауна-Робинсон с привлечением «теоремы об активных стратегиях» теории игр.

Метод фиктивного разыгрывания Брауна-Робинсон позволяет получить приближенную смешанную стратегию игроков на основе учета частоты выбора ими наиболее выгодных чистых стратегий на основе информации, интегрально содержащей результаты аналогичных предыдущих выборов. Многократное взаимодействие игроков рассматривается как последовательность отдельных актов, называемых партиями. В каждой партии игроки применяют какую-нибудь одну из конечного множества возможных стратегий, выбирая ее на основе обобщения всех данных о партиях, разыгранных до данной. Поведение игроков корректируется на каждом следующем шаге.

Метод Брауна – Робинсон иллюстрируется двумя театральными аналогиями. Первая театральная аналогия представляет собой известный прием драматургии – «Спектакль в спектакле», когда действие спектакля включает в себя розыгрыш «внутреннего» спектакля. Аналогично, для получения приближенного решения поставленной задачи теории игр, метод Брауна-Робинсон предполагает вспомогательную процедуру псевдорозыгрыша, в которой постепенно вырабатывается искомое решение исходной задачи. Вторая театральная аналогия – другой известный прием драматургии, как переплетенное развитие двух сюжетных линий, отношений между «трагической» и «комической» парами. Аналогично, для получения значимого решения исходной задачи между игроками, несклонными к риску предполагается рассмотреть вспомогательную процедуру принятия решений без попыток заглянуть вперед, на основе лишь продемонстрированного раньше поведения соперника.

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

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

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

Гипотеза исследования – в том, что с помощью сравнительно небольшого количества актов псевдорозыгрыша, реализуемого в процедуре метода Брауна-Робинсон, можно выявить множество активных стратегий обоих игроков (или выдвинуть гипотезы о них) и свести поиск ненулевых вероятностей стратегий к решению СЛАУ, составленных на основе ТАС.

Дизайн исследования

1. В электронной таблице MS Exel была реализована процедура метода Брауна-Робинсон для платежных матриц размерностью 4*4 (для первых выборов стратегий использованы средние значения в каждом ряду матрицы; при одинаковой ожидаемой величине платежа приоритет у стратегии с меньшим номером). Метод применялся к серии матриц, полученных с помощью встроенного генератора случайных чисел MS Exel. Фиксировались последовательности стратегий, выбираемые игроками в псевдорозыгрыше. На основании этих результатов выдвигались гипотезы о составе активных стратегий.

2. Для проверки гипотез составлялись и решались СЛАУ, позволяющие находить вероятности активных стратегий. Полное решение (неактивным стратегиям приписывалась нулевая вероятность) проходило полную проверку по всем предъявляемым к нему требованиям: а) значения вероятностей – из диапазона от 0 до 1; б) применение смешанной стратегии Получателя ко всем активным стратегиям приводит в среднему значению платежа, равному цене игры, а к неактивным – к величине платежа, невыгодной для Плательщика; в) аналогичным предыдущим свойствам смешанной стратегии Плательщика.

Результаты исследования

Типовой случай 1.

Рассматривается игра с платежной матрицей

5	9	5	8
3	9	9	5
3	9	8	4
1	5	3	9

При реализации псевдорозыгрышей в процедуре метода Брауна — Робинсон для первого игрока (Получателя) многократно выбирается стратегия А1. Выдвигается гипотеза о том, что множество активных стратегий Получателя включает в себя чистую стратегию А1.

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

Данные гипотезы подтверждаются наличием в платежной матрице седловой точки

Типовой случай 2.

Рассматривается игра с платежной матрицей

2	6	7	5
3	5	6	3
6	2	9	8
1	8	4	4

При реализации псевдорозыгрышей в процедуре метода Брауна — Робинсон для первого игрока (Получателя) выбираются стратегии А3, А4, А3, А4… Выдвигается гипотеза о том, что множество активных стратегий Получателя включает в себя стратегии А3, А4.

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

Исходя из выдвинутых гипотез, составляем и решаем две системы алгебраических уравнений

Результат проверки этого решения показывает, что для активных стратегий Плательщика и проверяемой стратегии Получателя средняя величина платежа равна цене игры, а для неактивных стратегий Плательщика В3 и В4 – 7,18 и 6,54, что явно невыгодно Плательщику и подтверждает вывод о невключении данных стратегий в его смешанную стратегию. В свою очередь, для неактивных стратегий Получателя А1 и А2 средняя величина платежа составит 3,81 и 3,90, что также явно невыгодно. Таким образом, все требования, предъявляемые к решению игры, удовлетворительно выполняются, и данное решение может быть принято.

Типовой случай 3.

Рассматривается игра с платежной матрицей

6	3	4	2
4	6	2	4
1	3	5	4
4	7	4	7

При реализации псевдорозыгрышей в процедуре метода Брауна — Робинсон для первого игрока (Получателя) выбираются стратегии А4, А1, А4, А3, А4, А3, А4, А1… Выдвигается гипотеза о том, что множество активных стратегий Получателя включает в себя стратегии А1, А3, А4.

Аналогично, для Плательщика в процедуре псевдорозыгрыша выбираются стратегии В1, В3, В4, В3, В1, В3, В4, В3, В1… Выдвигается гипотеза о том, что множество активных стратегий Плательщика включает в себя стратегии В1, В3, В4.

Исходя из выдвинутых гипотез, составляем и решаем две системы алгебраических уравнений

Результат проверки этого решения показывает, что для активных стратегий Плательщика и проверяемой стратегии Получателя средняя величина платежа равна цене игры, а для неактивной стратегии Плательщика В2 – 4,42, что явно невыгодно Плательщику и подтверждает вывод о невключении данной стратегии в его смешанную стратегию. В свою очередь, для неактивной стратегии Получателя А2 средняя величина платежа составит 2,5, что также явно невыгодно. Таким образом, все требования, предъявляемые к решению игры, удовлетворительно выполняются и данное решение может быть принято.

Типовой случай 4.

Рассматривается игра с платежной матрицей

8	1	7	6
6	6	3	7
8	8	6	3
9	7	1	8

Для Плательщика в процедуре псевдорозыгрыша выбираются стратегии В3, В4, В2, В4, В3, В2, В4, В2… Выдвигается гипотеза о том, что множество активных стратегий Плательщика включает в себя стратегии В2, В3, В4.

Для Получателя в процедуре псевдорозыгрыша выбирались все стратегии. Исходя из этого, были проверены четыре гипотезы о неактивных стратегиях Получателя и найдено решение игры

.

Основные выводы

• Комбинация итерационного метода, качественного решения и точного аналитического расчета позволяет существенно сократить количество вычислений и при этом получить не приближенное, а точное решение задачи.

• Во всех рассмотренных случаях не было получено данных против гипотезы исследования. Однако, получаемое решение носит гипотетический характер и всегда нуждается в скрупулезной проверке по всем налагаемым на него требованиям.

• Возможно, появление периода в чередовании стратегий, выбираемых игроками в псевдорозыгрыше, указывает на достижение искомого множества активных стратегий.

Литература

1. Вентцель Е. С. Исследование операций. – М. : Сов. Радио, 1972.

2. Гончарь П. С., Гончарь Л. Э., Завалищин Д. С. Теория игр. – Екатеринбург: Изд-во УрГУПС, 2011.