Эффективность алгоритма поиска равновесия Нэша (Nash) для игр n лиц в общей постановке

Изучена эффективность использования алгоритма локального поиска (альпинизм) для нахождения равновесия Нэша в играх n лиц в общей постановке с использованием программных сред Python. Применение умножения многомерной матрицы на вектор в процедуре локального поиска оказалась эффективным инструментом.

Ключевые слова

биматричные игры, смешанные стратегии, равновесие Нэша, Python

Получено

31.10.2022

Дата публикации

31.10.2022

Кол-во символов

9074

Цитировать Скачать pdf Для скачивания PDF необходимо авторизоваться

ГОСТ	Малков У. Х. Эффективность алгоритма поиска равновесия Нэша (Nash) для игр n лиц в общей постановке // Вестник ЦЭМИ – 2022. – Tом 5. – Выпуск 3 [Электронный ресурс]. URL: https://cemi.jes.su/S265838870022899-1-1 (дата обращения: 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 руб.

При оформлении подписки на статью или выпуск пользователь получает возможность скачать PDF, оценить публикацию и связаться с автором. Для оформления подписки требуется авторизация.

Оператором распространения коммерческих препринтов является ООО «Интеграция: ОН»


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}$

всего просмотров: 201

Оценка читателей: голосов 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.

Приложение (Приложение.pdf, 621 Kb) [Скачать]