ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2012, том 48, № 4, с. 113-118
МЕТОДЫ ОПТИМИЗАЦИИ
ДВОЙСТВЕННЫЙ МЕТОД РЕШЕНИЯ БИМАТРИЧНЫХ ИГР
© 2012 г. А.А. Заславский, А.Н. Липатова
(Москва)
Работа посвящена исследованию двойственного метода нахождения равновесия в бимат-ричной игре. Хотя теоретического доказательства сходимости метода получить не удалось, проведенные вычислительные эксперименты показали, что он может использоваться для решения биматричных игр, возможно, в сочетании с другими методами.
Ключевые слова: биматричные игры, линейное программирование, двойственная задача.
1. ПОСТАНОВКА ЗАДАЧИ
Биматричной игрой называется конечная бескоалиционная игра двух лиц. Ее можно описать системой Г = (I, J, h1, h2), где I = {1,..., m}, J = {1,..., n} - множества чистых стратегий игроков 1 и 2 соответственно. Если ввести для значений функций выигрыша на каждой паре стратегий обозначения h1(i, j) = aip h2(i, j) = by, то вся информация об игре будет задаваться матрицами A = (ay) и B = (by), элементы которых суть значения выигрыша игроков на допустимых ситуациях. Отсюда следует еще одно часто используемое обозначение биматричной игры Г(А, B). Как обычно, игроки стремятся максимизировать свой выигрыш.
Ситуацией равновесия по Нэшу в смешанных стратегиях в биматричной игре Г(А, B) называется ситуация (x*,y*) ! Sm х Sn, которая удовлетворяет неравенствам H1(x, y*) < H1(x*, y*), H2(x*, у) <
< Щх\ у) Ух ! Sm, у ! Sn, где Sm = {x ! Rm: xt > 0, /xt = 1}, Sn = {y ! Rn: yy > 0, / уу = 1} -
i j
стандартные симплексы; H1(x, y) = (xA, y), H2(x, y) = (xB, y) - выигрыши игроков в смешанном
расширении игры Г(А, B). При этом стратегии x*, y* называются равновесными.
Везде ниже, если не указано обратное, будем рассматривать только смешанное расширение биматричных игр, под термином "стратегия" будет пониматься смешанная стратегия, а под "ситуацией равновесия" - ситуация равновесия в смешанных стратегиях. Из доказанной Дж. Нэшем (Nash, 1950) теоремы следует, что в любой биматричной игре существует ситуация равновесия. Однако теорема Нэша указывает лишь на существование ситуации равновесия в биматричной игре, но не дает никакого алгоритма для ее нахождения. При этом в отличие от матричных игр, решение которых сводится к решению пары двойственных задач линейного программирования, решение биматричных игр приводит к невыпуклой оптимизационной задаче и, следовательно, является существенно более сложным.
2. ОПИСАНИЕ ДВОЙСТВЕННОГО МЕТОДА
Пусть дана биматричная игра с матрицами A, B 1 RmXn. Известно (Mills, 1960; Стрекалов-ский, Орлов, 2007), что ее решение сводится к решению билинейной задачи оптимизации:
x(А + B)y - a - 3 " max(= 0);
xB < ben;
Ay < em a; ^
xem = 1;
eny =1; x, y >0.
Здесь через ет, еп обозначаются векторы соответствующих размерностей, все координаты которых равны единице. Все векторы рассматриваются как строки или столбцы так, чтобы соответствующие матричные произведения имели смысл.
Если зафиксировать вектор у и число а = шах(Ау), получим задачу линейного программирования ЬР(у)\ '
х(А + В)у - 3 " шах(< а);
хВ - 3еп < 0;
(2)
xem
= 1;
х >0.
Очевидно, что задача (2) имеет решение при любом у и ее значение непрерывно зависит от у. Составим двойственную к (2) задачу DLP(y):
t" min;
Bu + ent > (A + B)y; - enu = -1;
(3)
и >0.
Очевидно, что вектор и = у и t = а удовлетворяют ограничениям задачи (3). Следовательно, ее оптимальное значение не больше а, причем равенство достигается тогда и только тогда, когда вектор у является оптимальным. Обозначив множество оптимальных векторов задачи (3) через и(у), получим, что решение биматричной игры сводится к нахождению неподвижной точки полунепрерывного сверху многозначного отображения и(у) стандартного симплекса Бп = {у ! Яп+, епу = 1} в себя. Для поиска неподвижной точки можно использовать метод простой итерации. Однако задача (3) может иметь не единственное решение, поэтому в качестве критерия остановки лучше использовать не близость найденного решения к у, а значение целевой функции задачи (1). Поскольку теоретически обосновать сходимость этого метода не удалось, для исследования его эффективности был проведен ряд вычислительных экспериментов.
3. ОПИСАНИЕ ВЫЧИСЛИТЕЛЬНОГО ЭКСПЕРИМЕНТА
3.1. Основные результаты. В проведенных экспериментах случайным образом генерировались матрицы A, B размера от 10 х 10 до 100 х 100. В качестве начальных значений выбирались чистые стратегии второго игрока. Алгоритм заканчивал работу либо когда значение целевой функции задачи (1) при выбранном векторе y и соответствующем ему решении задачи (2) x оказывалось меньше заданной точности s (как правило, выбиралось значение е = 10-6), либо, если число сделанных итераций превышало заданное значение (1000). В последнем случае менялась начальная стратегия второго игрока и работа алгоритма возобновлялась. На рис. 1-5 показано распределение числа задач по числу использованных начальных стратегий.
Как видно из приведенных графиков, двойственный метод дает 100%-ную сходимость (за исключением матриц размера 10 х 10). Однако она достигается за счет выбора разных начальных стратегий. Так, например, для матриц 100 х 100 при выборе одной начальной стратегии результат достигается менее чем в половине случаев, а при выборе из нескольких альтернатив решение находится всегда. Доля решенных задач при выборе одной из четырех первых стратегий велика -не менее 75%, однако есть тенденция к снижению этого показателя с ростом размерности игры.
На рис. 6-8 показана зависимость количества и длительности итераций от размера задачи. Как видно из графиков, число итераций и время выполнения одной итерации не носят экспоненциальный характер, а скорее имеют вид линейных функций.
3.2. Сравнение с алгоритмом Лемке-Хоусона. Метод Лемке-Хоусона был исторически одним из первых подходов для решения биматричных игр. Он был разработан в начале 1960-х годов. Как показали исследования (McKelvey, McLennan, 1996), на сегодняшний день он яв-
двойственный метод решения биматричных игр
115
900 800 700 600 500 400 300 200 100 0
□ Число решенных задач
--
-- .П ГП !-! —. -. -. -. -. -. -.
0
10
200 180 160 + 140 + 120 100 80 60 + 4020 + 0
□ Число решенных задач
л
0 1 2 3 4 5
11111111 6 7 8 9 13 15 18 21 26
Рис. 1. Распределение числа задач по количеству использованных начальных стратегий для матриц 10 х 10
Рис. 2. Распределение числа задач по количеству использованных начальных стратегий для матриц 50 х 50
25 20 15 10 5 0
□ Число решенных задач
л
л.
"I I I I I I
0 1 2 3 4 5 6
-г—^-г-'-г-'-г-'т—' 9 12 13 14 15 25
1 0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2 ОД 0
□ Доля решенных задач
10x10
50x50
100x100
Рис. 3. Распределение числа задач по количеству использованных начальных стратегий для матриц 100 х 100
Рис. 4. Доля решенных задач при выборе одной из первых четырех стратегий
1,2 1 0,8 0,6 0,4 0,2 0
10x10 50x50 100x100
□ Одна начальная стратегия ■ Несколько начальных стратегий
^120
10 50 — 50x50
100 ' 200 ' 400 ■ 100x100 —А-10x10
600 800
Рис. 5. Зависимость числа решенных задач от числа использованных начальных стратегий
Рис. 6. Зависимость числа решенных задач от максимального числа итераций
£ Г? # # Л* # # ^
^ £ Л* Ф
- Последовательный алгоритм
ЛС5+
/
Рис. 7. Среднее время выполнения одной итерации
Рис. 8. Среднее число итераций
101 100 99 98 97 96 95 94 93 92 91
■К*
г»
^ V
4+'
л4
-«р-
□ Доля найденных решений, %
Рис. 9. Доля задач, решенных методом Лемке-Хоусона
-Алгори™ Лемке-Хоусона
Рис. 11. Сравнительное время работы алгоритмов
-Последовательный алгоритм (верная начальная стратегия)
Рис. 10. Среднее время работы метода Лемке-Хоусона (ось абсцисс - размерность задачи, деленная на 10)
43,53-
и 2;
И '1. 0,50
16
Рис. 12. Зависимость длительности итерации от числа потоков
и а. 05
2 4 6
—♦— Время поиска решения
Рис. 13. Зависимость среднего времени решения от числа потоков
6000 5000 4000 3000 2000
1000
2 4
♦— Число итераций
Рис. 14. Зависимость количества итераций от числа потоков
ляется одним из наиболее быстрых алгоритмов отыскания равновесий в биматричной игре и показывает неплохую, хотя и не 100%-ную, сходимость. Есть тенденция к снижению сходимости метода с ростом размера игры (рис. 9).
На тестовом массиве данных время работы двойственного алгоритма уступает времени работы алгоритма Лемке-Хоусона, однако здесь требуется дополнительный анализ на больших размерностях игр, так как у второго алгоритма, возможно, есть тенденция к быстрому росту при увеличении размерности задач (рис. 10, 11).
3.3. Параллельная модификация двойственного метода. Так как на сходимость в значительной мере влияет выбор начального решения (стратегии второго игрока), то отсюда следует вывод:
ДВОЙСТВЕННЫЙ МЕТОД РЕШЕНИЯ БИМАТРИЧНЫХ ИГР 117
%
—♦—2 —■—4 —к-в —*—16 --*--■ 1
Рис. 15. Зависимость доли решенных задач от максимального числа итераций и числа потоков
если искать решение, взяв сразу несколько стратегий в качестве начальных, можно сократить время поиска, увеличив вероятность нахождения решения. Данный алгоритм позволяет достаточно простое распараллеливание: необходимо запустить некоторое число потоков, например, равное числу ядер процессора, в каждом из которых искать решение, отталкиваясь от разных начальных стратегий второго игрока. В случае если решение найдено одним из потоков, все остальные потоки завершаются; если же поток не нашел решения, то он выбирает следующую свободную чистую стратегию второго игрока (если такой нет, поток завершает свою работу).
В результате распараллеливания алгоритма время поиска решения существенно сократилось. При увеличении числа потоков увеличивается вероятность нахождения решения на меньшем номере итерации. Но увеличение числа потоков (больше числа ядер процессора) негативно сказывается на среднем времени продолжительности итерации (рис. 12-15).
4. ОСНОВНЫЕ ВЫВОДЫ И ВОЗМОЖНЫЕ НАПРАВЛЕНИЯ ДАЛЬНЕЙШИХ ИССЛЕДОВАНИЙ
Проведенные вычислительные эксперименты показали, что для случайно выбираемых матриц
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.