A Note: Nash Equilibrium Local Search Algorithm for n-Person Games in Multi-Matrix Settings

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

Publication date

11.01.2022

Number of characters

14485

Cite Download pdf To download PDF you should sign in

GOST	Malkov U. A Note: Nash Equilibrium Local Search Algorithm for n-Person Games in Multi-Matrix Settings // Vestnik CEMI – 2021. – Issue 3-4 [Electronic resource]. URL: https://cemi.jes.su/S265838870017210-4-1 (circulation date: 26.07.2024). DOI: 10.33276/S265838870017210-4
MLA	Malkov, Ustav "A Note: Nash Equilibrium Local Search Algorithm for n-Person Games in Multi-Matrix Settings." Vestnik CEMI 3-4 (2021) DOI: 10.33276/S265838870017210-4
APA	Malkov U. (2021). A Note: Nash Equilibrium Local Search Algorithm for n-Person Games in Multi-Matrix Settings. Vestnik CEMI (3-4) DOI: 10.33276/S265838870017210-4

100 rub.

When subscribing to an article or issue, the user can download PDF, evaluate the publication or contact the author. Need to register.


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

Readers community rating: votes 0

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.