Efficiency of the Nash equilibrium search algorithm for n-person games in the general formulation

The efficiency of using the local search algorithm (а cutting plane algorithm ) to find the Nash equilibrium for n person games in a general formulation using Python software environments is studied. The use of multiplication of a multidimensional matrix by a vector in the local search procedure proved to be an effective tool.

Keywords

bimatric games, mixed strategies, Nash equilibrium, Python

Received

31.10.2022

Publication date

31.10.2022

Number of characters

9074

Cite Download pdf To download PDF you should sign in

GOST	Malkov U. Efficiency of the Nash equilibrium search algorithm for n-person games in the general formulation // Vestnik CEMI – 2022. – V. 5. – Issue 3 [Electronic resource]. URL: https://cemi.jes.su/S265838870022899-1-1 (circulation date: 20.07.2024). DOI: 10.33276/S265838870022899-1
MLA	Malkov, Ustav "Efficiency of the Nash equilibrium search algorithm for n-person games in the general formulation." Vestnik CEMI 5.3 (2022) DOI: 10.33276/S265838870022899-1
APA	Malkov U. (2022). Efficiency of the Nash equilibrium search algorithm for n-person games in the general formulation. Vestnik CEMI 5(3) DOI: 10.33276/S265838870022899-1

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	Метод локального поиска под названием “альпинизм” был предложен в [6] и успешно применен для поиска равновесия Нэша в биматричных играх [2]. Тот же подход применим для игр от трех лиц, как в общих [1; 5], так и в многоматричных [9] постановках. Были публикации об алгоритмах и их программных реализациях этих подходов для конкретного количества игроков: 3, 4 и даже 5, см. [1; 3; 4; 5; 9]. Ранее в программной среде Python нами было составлена программа поиска равновесия Нэша в играх $n$ лиц в мульти-матричной постановке [2]. В этой статье мы исследуем эффективность локального поиска для игр $n$ лиц в общей постановке.
3	Игра $n$ лиц в общей постановке
4	Рассмотрим игру Γ с $n$ игроками. Конечная некооперативная игра Γ $n$ лиц определяется $X_{1}$ , $X_{2}$ , ..., $X_{n}$ , т. е. $n$ стратегиями первого, второго, ..., $n$ -го игрока соответственно, где
5	$X_{r} = \{x_{r} = (x_{1}^{r}, \dots, x_{m_{r}}^{r}) {\in E}^{m_{r}} : x_{r} e_{m_{r}} = 1, x_{r} \geq 0_{m_{r}}\},$
6	и вместе с их функциями выигрышей следующим образом:
7	$f_{r} (x) = f_{r} (x_{1}, x_{2}, \dots, x_{n}) = \sum_{i_{1} = 1}^{m_{1}} ‍ \sum_{i_{2} = 1}^{m_{2}} ‍ \dots \sum_{i_{n} = 1}^{m_{n}} ‍ A_{i_{1} i_{2} \dots i_{n}}^{r} x_{i_{1}}^{1} x_{i_{2}}^{2} \dots x_{i_{n}}^{n},$ $f (x_{1}, x_{2}, \dots, x_{n}) = \sum_{i_{1} = 1}^{m_{1}} ‍ \sum_{i_{2} = 1}^{m_{2}} ‍ \dots \sum_{i_{n} = 1}^{m_{n}} ‍ A_{i_{1} i_{2} \dots i_{n}} x_{i_{1}}^{1} x_{i_{2}}^{2} \dots x_{i_{n}}^{n},$
8	где $A_{i_{1} i_{2} \dots i_{n}}^{r}$ являются $n$ -мерными матрицами выигрышей игроков
9	$A_{i_{1} i_{2} \dots i_{n}} = \sum_{r \in I} ‍ A_{i_{1} i_{2} \dots i_{n}}^{r}, I = \{1, 2, \dots, n\} .$
10	Стратегии $x_{1}$ , $x_{2}$ ,... $x_{n}$ имеют размерности $m_{1}$ , $m_{2}$ , ... , $m_{n}$ , а вектор $x = (x_{1}, x_{2}, \dots x_{n}) \in E^{M}$ , $M = m_{1} + m_{2} + \dots + m_{n}$ .
11	В дальнейшем, не снижая общности, для удобства представления, мы определяем
12	$m_{1} = m_{2} = \dots = m_{n} = m,$ $M = n * m$ .
13	Определим функцию Нэша ( Nash)
14	$\begin{array}{l} N (x) = N (x_{1}, x_{2}, \dots x_{n}) = \underset{{x'}_{1} \in X_{1}}{m a x} f_{1} ({x'}_{1}, x_{2}, \dots, x_{n}) + \underset{{x'}_{2} \in X_{2}}{m a x} f_{2} (x_{1}, {x'}_{2}, \dots, x_{n}) + \\ \dots + \underset{{x'}_{n} \in X_{n}}{m a x} f_{n} (x_{1}, x_{2}, \dots, {x'}_{n}) - f (x_{1}, x_{2}, \dots x_{n}) . \end{array}$
15	Локальный поиск минимума показателя Нэша есть последовательное решение $n$ задач линейного программирования (LP) с определением их решений $x_{i}^{*}$ ( $i \in I)$ , как смешанных стратегий игроков. Эти задачи решаются относительно стратегии одного из игроков при фиксированных стратегиях других игроков, которые были получены в предыдущих итерациях как оптимальные стратегии этих игроков.
16	Алгоритм локального поиска
17	В качестве начальной (стартовой) стратегии итеративного процесса обычно используется набор чистых стратегий, например, $x^{0} = ({\bar{x}}_{1}, \dots, {\bar{x}}_{n})$ , где ${\bar{x}}_{i} = (1, 0, \dots, 0) \in E^{m_{i}}$ , $i \in I - 1$ .
18	Итак, в качестве отправной точки давайте определим стратегии $x^{2}, x^{3}, \dots, x^{n}$ игроков 2, 3, ..., $n$ как их первые чистые стратегии ${\bar{x}}^{2} = (1, 0, 0, \dots), {\bar{x}}^{3} = (1, 0, 0, \dots), {\bar{x}}^{n} = (1, 0, 0, \dots)$ .
19	Мы решаем $n$ задач LP последовательно, одну за другой, пока не получим локальный минимум функции Нэша. Если этот минимум равен нулю, то равновесие найдено. В противном случае выберите другую стартовую точку и повторите процедуру еще раз.
20	Давайте решим $n$ задач LP:
21	для $r \in I$ (определив множество $I - r = {s_{1}, s_{2}, \dots, s_{n}}$ , то есть $i_{k} = s_{k}$ для $k = 1, . ., r - 1$ и $i_{k} = s_{k + 1}$ для $k = r + 1, . . ., n$ ) формируем функционал задачи $r$
22	$\sum_{i_{1}} ‍ \sum_{i_{2}} ‍ \dots \sum_{i_{n - 1}} ‍ \sum_{s_{r}} ‍ A_{s_{1} s_{2} \dots s_{n}} {\bar{x}}_{i_{1}}^{1} {\bar{x}}_{i}^{2} \dots {\bar{x}}_{i_{n - 1}}^{n - 1} x_{s_{r}}^{r} - \sum_{u \in I - r} ‍ α_{u}^{r} \to \underset{x_{r}, α_{u}^{r}}{m a x},$
23	или
24	$\sum_{s_{r}} ‍ h_{s_{r}} x_{s_{r}}^{r} - \sum_{u \in I - r} ‍ α_{u}^{r} \to \underset{x_{r}, α_{u}^{r}}{m a x}, где h_{s_{r}}$ = $\sum_{i_{1}} ‍ \sum_{i_{2}} ‍ \dots \sum_{i_{n - 1}} ‍ A_{s_{1} s_{2} \dots s_{n}} {\bar{x}}_{i_{1}}^{1} {\bar{x}}_{i_{2}}^{2} \dots {\bar{x}}_{i_{n - 1}}^{n - 1}$
25	и система $m$ неравенств (одна из $n - 1$ систем задачи $r$ ):
26	$\begin{array}{l} \{\sum_{s_{r}} ‍ \sum_{t_{1}} ‍ \sum_{t_{2}} ‍ \dots \sum_{t_{n - 2}} ‍ A_{i_{1} i_{2} \dots i_{n}}^{u} {\bar{x}}_{t_{1}}^{t_{1}} {\bar{x}}_{t_{2}}^{t_{2}} \dots {\bar{x}}_{t_{n - 2}}^{t_{n - 2}} x_{i_{r}}^{r} ⩽ α_{u}^{r}, \sum_{i_{r}} ‍ x_{i_{r}}^{r} = 1, x_{i_{r}}^{r} ⩾ 0_{m}\}, \\ s_{u} = 1, \dots, m, \end{array}$

Readers community rating: votes 0

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

2. Малков, У. Заметка об алгоритме локального поиска равновесия Нэша для игр с участием n лиц в мульти-матричных постановках // Вестник ЦЭМИ – 2021. – Выпуск 3-4. – URL: https://cemi.jes.su/S265838870017210-4-1 (дата обращения: 10.09.2022)

3. 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.

4. 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.

5. Golshtein, E. A Numerical Method for Solving Finite Three-Person Games / E. Golshtein // Economica I Matematicheskie Metody. – 2014. – 50(1). – p. 110–116.

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

7. Lemke, C. Equilibrium Points of Bimatrix Games/ C. Lemke, CJ. Howson // Journal of the Society for Industrial and Applied Mathematics. – 1964. – 12. – p. 778–780.

8. 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.

9. Strekalovsky, A. Polymatrix Games and Optimization Problems / A. Strekalovsky, R. Enkhbat // Avtomatika I Telemekhanika. – 2014. – 4. – p. 51–66.

Appendix (Приложение.pdf, 621 Kb) [Download]