IX Международная студенческая научная конференция Студенческий научный форум - 2017

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

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

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

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

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

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

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

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

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

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.

Код для цитирования: Скопировать