A Note: Nash Equilibrium Local Search Algorithm for n-Person Games in Multi-Matrix Settings
Table of contents
Share
QR
Metrics
A Note: Nash Equilibrium Local Search Algorithm for n-Person Games in Multi-Matrix Settings
Annotation
PII
S265838870017210-4-1
Publication type
Article
Status
Published
Authors
Ustav Malkov 
Occupation: leading researcher
Affiliation: CEMI RAS
Address: Moscow, Nakhimovsky prospect, 47
Abstract

The effectivity of using the local search algorithm (mountain climbing) for searching Nash equilibrium in n-person games in multi-matrix settings using the Python software environment has been studied.  

Keywords
\keywords: n-person Game, Multi-matrix setting, Mixed strategies, Nash equilibrium, Python
Received
10.01.2022
Date of publication
11.01.2022
Number of purchasers
0
Views
181
Readers community rating
0.0 (0 votes)
Cite Download pdf
Additional services access
Additional services for the article
1

Введение

2 Поиск равновесия Нэша в играх с участием n лиц можно рассматривать как задачу нелинейного программирования, которая, фиксируя стратегии всех игроков, кроме одного, превращается в задачу линейного программирования (LP). Решая эти задачи, последовательно, мы получаем алгоритм локального поиска (LS), который сходится к локальному минимуму. Этот алгоритм, называемый «альпинизмом», был предложен в [1] и успешно применен для поиска равновесия Нэша в двух-матричных играх [7]. Тот же подход (LS) применим для игр трех лиц как в общих [4], так и в мульти-матричных постановках [5]. И применим для игр с n лицами.
3 В этой статье мы исследуем эффективность рассмотренного подхода для поиска равновесия по Нэшу для игр с n лицами в мульти-матричных постановках, предложенного в [5], где выигрыш каждого из участников конфликта представляет собой сумму n-1 выигрышей к остальным игрокам (8), и игра полностью описывается nn-1 матрицами. Поли-матричную игру с несколькими игроками можно представить, как совокупность биматричных игр, где игроки играют друг с другом попарно, а ищется коллективное равновесие. С помощью такой игры моделируются экономические конфликты на олигополистическом рынке с n участниками, каждый из которых имеет конечное число стратегий [12].
4 Имеется пример такой постановки [13], где исследуется одна задача конкуренции между тремя основными банками Монголии в секторе крупного кредитования предприятий. Моделирование конфликта проводится с помощью аппарата поли-(гекса)матричных игр трех лиц, где рассматриваемая попарно конкуренция между всеми тремя банками во всех возможных стратегиях кредитования по разным процентным ставкам представляется в виде гекса-матричной игры с шестью матрицами, элементы которых представляют собой возможные объемы кредитов. Авторы этой работы нашли равновесие в рассмотренной модели, применяя идеи глобального поиска, используя четыре итерации глобального поиска, 68 – локального спуска и решив 443 задачи ЛП за пять секунд. В то же время рассматриваемый в данной статье алгоритм получил результат за один локальный поиск, решив при этом три задачи ЛП, и это все за сотую долю секунды.
5 В каждой из выше приведенных публикаций описывается алгоритм и его программная реализация для конкретного количества игроков (трех, четырех и даже пяти). В данной работе предлагается алгоритм, при помощи программной реализации которого, можно решать игры с разным количеством участников (3, 4, 5, 6, 7).
6 Поли-матричная игра трех лиц подробно изучена в [2, 5, 6]. В [5] приведена постановка мульти-матричной игры нескольких лиц. В данной работе описан алгоритм решения мульти-матричной игры нескольких лиц и проверена эффективность его работы.
7 Предлагаемый алгоритм работает, что экспериментально подтверждено результатами тестовых расчетов, где лексикографически упорядоченным перебором стартовых точек (чистых стратегий игроков), применяя алгоритм локального поиска для поиска минимума функции Нэша, находим точку равновесия Нэша за приемлемое время в играх с тремя, четырьмя, пятью, шестью и семью игроками и до 20 стратегий.
8 Если для общей постановки при вычислении выигрышей игроков участвуют n  мерные матрицы, и тем самым объем информации и время поиска равновесия катастрофически растет (в m раз) при увеличении количества игроков и используемых m стратегий, то в случае мульти-матричной постановки из-за существенно меньшего объема исходной информации удается работать с постановками игр с большим количеством игроков и стратегий. Так как объем информации при переходе к n+1 игрокам растет в n+1/n-1 раз.
9 Поэтому, если бы можно было решить игры для трех человек размером до 100 (т. е. до 100 стратегий на каждого игрока), то в случае игр для четырех игроков можно было бы получить решение только в разумные сроки для нескольких десятков стратегий. В цитируемых публикациях реализовали алгоритм локального поиска в виде отдельной программы для каждого количества игроков. Оказалось, что в случае мульти-матричной постановки можно создать одну программу для игр с n игроками, например, в среде Python.
10 В этой статье для игр с участием n лиц мы описываем LS-алгоритм компактно при помощи формул (13), (14), (15), и все n задач LP формируются и решаются последовательно c использованием одного и того же набора формул. В случае трех лиц пришлось описать для каждой задачи отдельный набор формул и отдельную процедуру в программной реализации. Такое представление алгоритма позволило компактно писать и реализовывать программы в средах Matlab и Python.
11 Стало намного проще отлаживать программы, внося изменения в одном месте текста, а не в n . Используемая нами мульти-матричная постановка игр n лиц, представляет собой обобщение гекса-матричной постановки игр трех лиц, где таблицы выигрышей игроков определялись шестью матрицами. В нашем случае таблицы выигрышей n игроков определяются n-1n матрицами.
12 Собирая эти матрицы в одну блочную (14), мы можем представить саму игру n -лиц и алгоритм локального поиска равновесия Нэша в компактной форме. В этом случае игры n -лиц, как задачи нелинейного программирования, становятся задачами квадратичного программирования с линейными условиями.
13 Имеется несколько других подходов к решению игр для четырех лиц [9, 10], в том числе постановка с несколькими матрицами (трипло), где таблицы выигрышей игроков определяются 12 трехмерными таблицами. Эти подходы используют алгоритм глобальной оптимизации.
14

Игра n лиц в общей постановке

15 Конечная бескоалиционная игра n лиц Γ определяется множествами X1,,Xn стратегий n игроков и их функциями выигрышей, заданными на компактном множестве X=X1××Xn евклидова пространства EM , где для rI={1,,n} стратегии xrXrEmr имеют размеры m1,,mn , вектор x=(x1,,xn)EM , M=m1++mn :
16 Xr=xr=x1r,,xmrrEmr:  xr,emr=p=1mrxpr=1,    xromr,            1
17 frx=fr(x1,,xn)=p1=1m1pn=1mnAp1pnrxp11 xpnn,                                  2
18 fx=f(x1,,xn)=p1=1m1pn=1mn Ap1 pnxp11 xpnn,                                     3
19 Ap1pnrn -мерная таблица выигрышей игрока r ( rI и Ap1pn=r=1nAp1pnr ) для любого целого числа q>0 векторы eq=(1,,1)Eq и om=(0,,0)Eq .
20 Введем функцию (показатель) Нэша N(x)=r=1nNr(x) ,
21 Nrx=maxxrXrfr(x1,,xr-1,xr,xr+1,,xn)-fr(x1,,xn),        rI.        4
22 Для всех стратегий xX выполняется неравенство N(x)0 , и для любой точки равновесия x*X должно соблюдаться условие Nx*=0 .
23 Локальный поиск минимума функции Нэша сводится к итеративному процессу, где на каждой итерации последовательно (одна за другой) решаются n задач линейного программирования (ЛП).
24 Для произвольного вектора xX фиксируем значения всех «координат» xi=x¯i , iI , кроме i=r . Определим множество
25 I\r=s1,,sn-1={2,3,,n},r=1,{1,2,,n-1},r=n,{1,,r-1,r+1,,n},1<r<n;    I=I\rr.
26 Тогда значение показателя N(x) как функции от xr может быть уменьшено (по крайней мере не увеличено) после решения задачи ЛП Pr(x¯1,,x¯r-1,xr,x¯r+1,,x¯n) :
27 pr=1mrps1=1ms1 psn-1=1msn-1Apr ps1psn-1 x¯ps1 s1x¯psn-1 sn-1xprr-uI\rαur maxxr,αur                       5
28 при ограничениях
29 pr=1mrpt1=1mt1 ptn-2=1mtn-2Apupr pt1ptn-2r x¯pt1 t1x¯ptn-2 tn-2xprrαur,    t=s\u,    uI\r,       6
30 xr,emr=1,        xromr,        αurE1,        uI\r.                                                              7
31 Для полученного оптимального плана xr* задачи (5)–(7) и произвольного вектора xrXr выполняется неравенство
32 0N(x¯1,,x¯r-1,xr*,x¯r+1,,x¯n)N(x¯1,,x¯r-1,xr,x¯r+1,,x¯n).
33

Мульти-матричная постановка

34 Используемая нами мульти-матричная постановка игр n лиц представляет собой обобщение гекса-матричной постановки игр трех лиц [5], где таблицы выигрышей игроков определялись шестью матрицами. В нашем случае таблицы выигрышей игроков определяются n-1n матрицами.
35 Оказалось, что мульти-матричная постановка после сборки всех матриц, определяющих таблицы игроков в одну блочную матрицу, позволяет написать одну программу для поиска равновесия в играх нескольких лиц, что невозможно делать в случае общей постановки, где для каждого количества игроков надо написать отдельную программу.
36 Рассмотрим игру Υ с n игроками. Конечная некооперативная игра n лиц Υ определяется n множествами Xr ( 1 rn ) стратегий игроков соответственно,
37 Xr = xr=(x1r,,xmrr)Emr:   xr,emr =1, xr 0mr ,
38 вместе с их функциями выигрышей по формуле
39 frx=frx1,,xn=xr, qI\rnamr,m(q)r,qxq,  1 r n,            8
40 где amr,m(q)r,qmr×m(q) -матрица, I=1,2,,n,  r,q I,  amr,m(r)r,r – нуль матрицы.
41 Т.е. коэффициенты матрицы выигрышей игрока r определяются как суммы коэффициентов n-1 матриц по формуле
42 Ai1,,inr=qI-rair,iqr,q,  1rn.               9
43 ( amr,m(q)r,q, amq,m(r)q,r – матрицы выигрышей в биматричной игре участников r и q ).
44 Введем функцию (индикатор) Нэша Nx=r=1nNrx,
45 Nrx=maxxrXrfrx1,,xr-1,xr,xr+1,,xn-frx1,,xn.                    10
46 Мульти-матричная игра n лиц в этих обозначениях представляется как задача квадратичного программирования
47 r=1n{xr, qI\ramr,m(q)r,qxq-αr}maxx ,α             11
48 при ограничениях
49 xr,sI\r amr,msr,s αrem,    rI.                   12
50 xr,em(r) = 1,  xr 0mr,   αr01.                       13
51

Алгоритм локального поиска

52 Для компактного представления алгоритма локального поиска мы собрали эти матрицы в блочную матрицу
53 H=Om(1)am1,m(2)1,2am1,m(3)1,3am1,m(n)1,nam2,m(1)2,1Om(2)am2,m(3)2,3am2,m(n)2,nam3,m(1)3,1am3,m(2)3,2 Om(3)am3,m(n)3,namn,m(1)n,1amn,m(2)n,2amn,m(3)n,3Om(n),           14
54 где, например, подматрица H1,2=am1,m(2)1,2 .
55 Алгоритм локального поиска равновесия Нэша для игры n -лиц в мульти-матричной постановке принимает следующий вид.
56 Фиксируя все стратегий x-v   кроме одной xr в представлении функции Нэша в цикле мы построим функционалы (15) и матрицы (17, 18) условий задач линейного программирования (ЛП) Pr (r=1, 2, , n)  n  игроков и будем решать эти задачи последовательно 1,2,, n друг за другом до тех пор, пока не будет достигнут минимум функции Нэша N(x) .   
57 После решения очередной задачи Pr фиксируем полученную стратегию xr  как  x-r  , при этом значение показателя N(x) как функция от xr может уменьшится (по крайней мере не увеличиватся). Т.е. функция Нэша монотонно сходится к локальному минимуму.
58 В этих задачах функционал задачи Pr , полученной фиксацией всех стратегий   кроме одной в выше приведённой задаче квадратичного программирования (11, 12, 13), задается формулой
59  xr,vI\ramr,m(v)r,v+(amv,mrv,r)Tx-v- vI\rαvrmaxxr,αvr                           15
60 или, используя вместо обозначении amr,m(v)r,v символы Hr,v .
61  {xr,vI\rHr,v+Hv,rTx-v-vI\rαvr}  maxxr,αvr .                                                 16
62 И n-1 систем неравенств ( uI\r ) описываются формулой
63 Hu,rxr +sI\r,uHu,sx-sαur em,  uI\r,                                                                 17
64 xr,em(r) = 1,  xr 0mr,  αur 01.                                                                        18
65 При помощи формул (15, 16, 17, 18) описываются n (r=1, 2, , n) задач и их n-1 (uI\r) систем неравенств. При написании алгоритма в среде Питон эти же формулы реализуются при помощи одной процедуры с параметрами r и u .
66 Решение, т. е. равновесие Нэша, ищется путем целенаправленного перебора начальных точек, наборов чистых стратегий игроков, с использованием локального поиска, пока мы не найдем точку, для которой минимум функции Нэша равен нулю, т. е. найдено равновесие. Упорядоченное лексикографическое генерирование начальных точек может быть выполнено следующим образом.
67 Пусть будет m стратегий и n игроков. Используя начальный список (счетчик) start [1: n]= [1, ...,1], мы устанавливаем начальный набор стартовых точек, то есть первые чистые стратегии игроков. Переход к следующему набору стартовых точек, начиная со второго игрока, осуществляется путем циклического просмотра стартового списка от двух до n путем увеличения рассматриваемого компонента на единицу, еcли он меньше предельного значения m , и переходим к следующему набору. При обнаружении предельного значения присвоим этому компоненту списка номер первой чистой стратегии и продолжим просмотр списка. Тем самым осуществим лексикографическое продвижение по стартовому списку.
68 В среде Python (где нумерация компонентов списка начинается с 0) переход к следующему набору начальных точек выполняется с помощью следующего цикла:
69

70 Мы будем перебирать начальные точки, пока не найдем равновесие или не исчерпаем список этих точек, т. е. start[n] = m.
71

Результаты тестовых расчетов

72 В среде Python была составлена программа для поиска равновесия Нэша в играх с n лиц и m стратегиями с мульти старт, где локальный поиск начинался с набора чистых стратегий игроков с последующим лексикографическим сканированием этого набора, пока результат не был найден или этот набор не был исчерпан. Такая программа может быть написана для мульти-матричной постановки, но не для общей постановки.
73 Как вы можете видеть, результаты в таблице показывают, что увеличение числа лиц и стратегий значительно увеличивает время нахождения равновесия.
74 Более того, для тех игр, у которых более десяти стратегий, невозможно получить результаты с приемлемым временем для игр более пяти лиц.
75 В таблице результатов тестирования показана сумма количества начальных точек, итераций и времени решения пяти игр, сгенерированных с использованием датчика случайных чисел в серии трех, четырех, пяти, шести, семи лиц и 3, 5, 10, 20 стратегий (рис. 1).
76

Рис. 1. Поиск равновесия по Нэшу (начальные точки startp, итерации itn и время time) для пяти игр с участием трех, четырех, пяти, шести, семи лиц и 3, 5, 10, 20 стратегий по локальному алгоритму поиска.

77 Здесь itn – это шаги алгоритма локального поиска, где на каждом шаге решается n задач линейного программирования, а время указывается в секундах.
78

Заключение

79 В рассмотренных выше публикациях алгоритм локального поиска был реализован в виде отдельной программы для каждого числа (трех, четырех) лиц. В случае мульти-матричной постановки мы реализовали алгоритм LS как одну программу в среде Python для игр с n лиц n=3, 4, 5, 6, 7 . Это работает!
80 Модификация [8] метода Лемке-Хаусона [7] хорошо работает для игр с участием трех лиц в мульти-матричной постановке. Мы попытались реализовать этот алгоритм для игр с несколькими участниками в виде одной программы. Оказалось, что в случае более чем четырех игроков эта программа работает плохо.

References

1. Konno, H. A cutting plane algorithm for solving bilinear programs / H. Konno // Mathematical Programming. – 1976. – V. 11, Issue 1. – p. 14–27.

2. Orlov, A. V. Numerical search for equilibria in bimatrix games / A. V.Orlov, A. S. Strekalovskii // Comput. Math. Math. Phys. – 2005. – V. 45, N6. – p. 947–960.

3. Porter, R. W. Simple Search Methods for Finding a Nash Equilibrium / R. W. Porter, E. Nudelman, Y. Shoham // Games and Economic Behavior. – 2009. – V. 63, N. 2. – p. 642-662.

4. Гольштейн, Е. Г. Приближенный метод решения конечной игры трех лиц / Е. Г. Гольштейн // Экономика и математические методы. – 2014. – Т. 50, № 1. – с. 110-116.

5. Strekalovskii, A. S. Polymatrix games and optimization problems / A. S. Strekalovskii, R. Enkhbat // Autom. Remote Control. – 2014. – V. 75, N4. – p. 632–645.

6. Orlov, A. On computational search for Nash equilibrium in hexamatrix games / A.Orlov, A.Strekalovsky, S.Batbileg // Optimization Letters. – 2014. – V.10, No.2. p. 369-381.

7. Lemke, C. Equilibrium Points of Bimatrix Games / C. Lemke, C. J. Howson // Journal of the Societyfor Industrial and Applied Mathematics. – 1964. – V. 12. – p. 778-780.

8. Golshteyn, E. The Lemke–Howson Algorithm Solving Finite Non-Cooperative Three-Person Games in a Special Setting / E. Golshteyn, U. Malkov, N. Sokolov // DEStech Transactions on Computer Science and Engineering. – 2018.

9. Batbileg, S. A global optimization algorithm for solving a four-person game / S. Batbileg, N. Tungalag, A. Anikin [and others] // Optimization Letters. – 2019. – V.13. – p.587-596.

10. Enkhbat, R. A Note on Four-Players Triple Game/ R. Enkhbat, S. Bathileg, A. Anikin [and others] // Contributions to Game Theory and Management. – 2019. – V.XII. – p.100-112.

11. Гольштейн, Е. Г. Эффективность приближенного метода решения конечной игры трех лиц (вычислительный опыт) / Е. Г. Гольштейн, У. Х. Малков, Н. А. Соколов // Экономика и математические методы. – 2017. – Т. 53, № 1. – с. 94-107.

12. Neumann, John Von. Theory of games and economic behavior / John Von Neumann, O. Morgenstern. – Princeton University Press, 1944. – 674 p.

13. Орлов, А. В. С. Батбилэг, Олигополистический банковский сектор Монголиии и полиматричные игры трех лиц / А. В. Орлов, С. Батбилэг // Известия Иркутского государственного университета. – 2015. – Т. 11. Серия «Математика». – С. 80–95.

Comments

No posts found

Write a review
Translate