Заметка об алгоритме локального поиска равновесия Нэша для игр с участием n лиц в мульти-матричных постановках

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

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

игра n лиц, мульти-матричная постановка, смешанные стратегии, равновесие Нэша, Python

Получено

10.01.2022

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

11.01.2022

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

14485

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

ГОСТ	Устав М. Заметка об алгоритме локального поиска равновесия Нэша для игр с участием n лиц в мульти-матричных постановках // Вестник ЦЭМИ – 2021. – Выпуск 3-4 [Электронный ресурс]. URL: https://cemi.jes.su/S265838870017210-4-1 (дата обращения: 05.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 руб.

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

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


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 стратегий.

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

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