Экономические науки

EVOLVING STRATEGIES: A NUMERICAL APPROACH TO GAME-THEORETIC EQUILIBRIUM ANALYSIS [РАЗВИВАЮЩИЕСЯ СТРАТЕГИИ: ЧИСЛЕННЫЙ ПОДХОД К ТЕОРЕТИКО-ИГРОВОМУ АНАЛИЗУ РАВНОВЕСИЯ]

Rykunov D.P. 

Rykunov Dmitrii Pavlovich – BSc in Economics, FACULTY OF ECONOMICS, NATIONAL RESEARCH UNIVERSITY HIGHER SCHOOL OF ECONOMICS, MOSCOW

Abstract: this article investigates a general-purpose framework to numerically analyze game theoretic models in terms of the stability of equilibria and individual decision-maker behavior. It focuses on models equivalent to finite non-cooperative games. We start with a mathematical formalization of such models and their equilibria and outline an approach to analyze them, based on evolutionary game theory concepts. We proceed by implementing the approach in an algorithm inspired by evolutionary optimization algorithms, capable of locating multiple equilibria with an iterated local search procedure. The algorithm’s convergence to equilibria concepts traditional for evolutionary game theory studies, namely evolutionary stable strategy and evolutionary stable set, is demonstrated by empirical results.

Keywords: game theory, evolutionary algorithms, Nash equilibrium, prisoner's dilemma, computational modeling, strategic interactions, multiple equilibria, genetic algorithm, evolutionary game theory, algorithmic game theory, agent-based modeling.

Рыкунов Д.П. 

Рыкунов Дмитрий Павлович – бакалавр экономики, Факультет экономики, Национальный исследовательский университет «высшая школа экономики», г. Москва

Аннотация: в этой статье исследуется универсальная структура для численного анализа теоретико-игровых моделей с точки зрения устойчивости равновесий и поведения отдельных лиц, принимающих решения. Основное внимание уделяется моделям, эквивалентным конечным некооперативным играм. Мы начнем с математической формализации таких моделей и их равновесий и наметим подход к их анализу, основанный на концепциях эволюционной теории игр. Мы продолжим реализацию подхода в алгоритме, вдохновленном алгоритмами эволюционной оптимизации, способном находить множественные равновесия с помощью повторяющейся процедуры локального поиска. Эмпирические результаты демонстрируют сходимость алгоритма к традиционным для исследований эволюционной теории игр понятиям равновесия, а именно к эволюционно устойчивой стратегии и эволюционно устойчивому множеству.

Ключевые слова: теория игр, эволюционные алгоритмы, равновесие Нэша, дилемма заключённого, компьютерное моделирование, Стратегические взаимодействия, множественные равновесия, генетический алгоритм, эволюционная теория игр, алгоритмическая теория игр, агентное моделирование.

References / Список литературы

1. K.T.B. Paul Frihauf "Nash Equilibrium Seeking in Noncooperative Games," IEEE TRANSACTIONS ON AUTOMATIC CONTROL, vol. 57, no. 5, pp. 1192-1207, May 2012.
2. Richard, D. McKelvey "Computation of Equilibria in Finite Games," in Handbook of Computational Economics, Elsevier, 1996, pp. 87-142.
3. W. Srihari Govindan "Computing Nash equilibria by iterated polymatrix approximation," Journal of Economic Dynamics & Control, pp. 1229-1241, 2004.
4. W. Srihari Govindan "Computing Nash equilibria by iterated polymatrix approximation," Journal of Economic Dynamics & Control, pp. 1229-1241, 2004.
5. U. Jacek, B. Krawczyk "Relaxation algorithms to find Nash equilibria with economic applications," Environmental Modeling and Assessment, pp. 63-73, 2000.
6. J. Neely "A Lyapunov Optimization Approach to Repeated," in Proc. Allerton Conference on Communication, Control, and Computing, 2013
7. H.J. a. D.M.S. Milos S. Stankovic "Distributed Seeking of Nash Equilibria With," IEEE TRANSACTIONS ON AUTOMATIC CONTROL, pp. 904-919, 2012.
8. Stengel "Computation of Nash equilibria in finite games: introduction to the symposium," Economic Theory, 2010.
9. B.E.B.K. Mattheos, K. Protopapas "Coevolutionary Genetic Algorithms for Establishing Nash Equilibrium in Symmetric Cournot Games," Advances in Decision Sciences, 2010.
10. D. Rodica Lung "An Evolutionary Model for Solving Multiplayer Noncooperative Games," in Knowledge Engineering: Principles And Techniques; Proceedings of the International Conference on Knowledge Engineering, Principles and Techniques, KEPT2007, Cluj-Napoca (Romania), 2007.
11. -L.Y. Wei-Kai Lin "The Co-Evolvability of Games in Coevolutionary Genetic Algorithms," Taiwan Evolutionary Intelligence Laboratory (TEIL), Taiwan, 2009.
12. A. Ismail "Game Theory Using Genetic Algorithms," in Proceedings of the World Congress on Engineering 2007, WCE 2007, London, U.K., 2007.
13. C. Olivier Bournez "Learning Equilibria in Games by Stochastic Distributed Algorithms," in Computer and Information Sciences III, London, UK, Springer-Verlag London, 2013, pp. 31-38.
14. G. Veisi "A Multi-Modal Coevolutionary Algorithm for Finding All Nash Equilibria," Ubiquitous Information Technologies and Applications, pp. 21-29, 2012.
15. E. Marks "Playing Games with Genetic Algorithms," Evolutionary Computation in Economics and Finance, pp. 31-44, 2002.
16. A. Suheyla Ozyildirim "Learning the optimum as a Nash equilibrium," Journal of Economic Dynamics & Control, pp. 483-499, 2000.
17. Axelrod "The Evolution of Strategies in the Iterated Prisoner's Dilemma," in Genetic Algorithms and Simulated Annealing, Los Altos, CA, Morgan Kaufman, 1987, pp. 32-41.
18. M. John von Neumann Theory of Games and Economic Behavior, Princeton University Press, 1944.
19. Nash "Non-Cooperative Games," The Annals of Mathematics, pp. 286-296, 1951.
20. Preuss Multimodal Optimization by Means of Evolutionary Algorithms, Münster, Germany: Springer International Publishing Switzerland, 2015.
21. A.D. Jong Evolutionary Computation, Cambridge, Massachusetts; London, England: The MIT Press, 2006.
22. Peters Game Theory, A Multi-Leveled Approach, Berlin, Germany: Springer-Verlag Berlin Heidelberg, 2015.
23. Bull "On coevolutionary genetic algorithms," Soft Computing, pp. 201-207, 2001.
24. B.C. Fogarty "Co-Evolving Communicating Classifier Systems for Tracking," in Artificial Neural Nets and Genetic Algorithms, Vienna, Springer, 1993.
25. Husbands "Distributed Coevolutionary Genetic Algorithms for Multi-Criteria and Multi-Constraint Optimisation," in Evolutionary Computing. AISB EC 1994. Lecture Notes in Computer Science, vol 865, Berlin, Heidelberg, Springer, 1994.
26. B.P. Sevan, G. Ficici "A Game-Theoretic and Dynamical-Systems Analysis of Selection Methods in Coevolution," IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, pp. 580-601, 2005.
27. M. Smith Evolution and the Theory of Games, Cambridge University Press, 1982.
28. B.B. Morsky "Truncation selection and payoff distributions applied to the replicator equation," Journal of Theoretical Biology, pp. 383-390, 2016.
29. Roughgarden "Computing equilibria: a computational complexity perspective," Economic Theory, pp. 193-236, January 2010.
30. V. Noam Nisan Algorithmic Game Theory, New York, USA: Cambridge University Press, 2007.
31. Ken’ichiro Tanakaa "Discrete approximations of continuous distributions by maximum entropy," Economics Letters, pp. 445-450, 2012.
32. L. Jian Chi "Multi-objective Genetic Algorithm based on Game Theory and its Application," in 2nd International Conference on Electronic & Mechanical Engineering and Information Technology (EMEIT-2012), Paris, France, 2012.
33. P.M. Sefrioui "Nash Genetic Algorithms : examples and applications," in Proceedings of the 2000 Congress on Evolutionary Computation. CEC00 (Cat. No.00TH8512), La Jolla, CA, USA, 2000.
34. .-K. Kwee-Bo Sim "Solution of multiobjective optimization problems: coevolutionary algorithm based on evolutionary game theory," Artificial Life and Robotics, pp. 174-185, 2004.
35. Cantú-Paz Efficient and Accurate Parallel Genetic Algorithms, Springer US, 2001.
36. Thomas "On evolutionarily stable sets," Journal of Mathematical Biology, pp. 105-115, 1985.
37. Thomas "Evolutionary stability: States and strategies," Theoretical Population Biology, pp. 49-67, 1984.
38. Maynard Smith and G. Price "The logic of animal conflict," Nature, pp. 15-18, 1973.
39. Thomas "Evolutionarily Stable Sets in Mixed-Strategist Models," Theoretical Population Biology, pp. 332-341, 1985.
40. Selten "A Note on Evolutionarily Stable Strategies in Asymmetric Animal Conflicts," in Models of Strategic Rationality, Springer Netherlands, 1988, pp. 67-75.
41. Samuelson Evolutionary Games and Equilibrium Selection, Cambridge, MA: The MIT Press, 1997.
42. G. Daniel Kahneman, Heuristics and Biases : The Psychology of Intuitive Judgment, New York, NY, USA: Cambridge University Press, 2002.
43. Smith The Wealth of Nations, London, UK: W. Strahan and T. Cadell, 1776.
44. Murphy "John Law and Richard Cantillon on the circular flow of income," Journal of the History of Economic Thought, pp. 47-62, 1993.
45. M. Keynes The General Theory of Employment, Interest and Money, Palgrave Macmillan, 1936.
46. Marshall Principles of Economics, London, UK: Macmillan, 1890.
47. Lucas "Econometric Policy Evaluation: A Critique," in The Phillips Curve and Labor Markets, New York, American Elsevier, 1976, pp. 19-46.
48. A.T. Rizvi "The Sonnenschein-Mantel-Debreu," History of Political Economy, pp. 228-245, 2006.
49. R. Nelson "Behavior and cognition of economic actors in evolutionary economics," Journal of Evolutionary Economics, 2015.
50. N. Moshe Hoffman "An experimental investigation of evolutionary dynamics in the Rock-Paper-Scissors game," Scientific Reports, 2005.
51. Morrison "Cournot, Bertrand, and modern game theory," Atlantic Economic Journal, pp. 172-174, 1998.
52. M. Iris Lorscheid "Agent-based mechanism design – investigating bounded rationality concepts in a budgeting context," Team Performance Management, pp. 13-27, 2017.

ССЫЛКА ДЛЯ ЦИТИРОВАНИЯ ДАННОЙ СТАТЬИ

		Тип лицензии на данную статью – CC BY 4.0. Это значит, что Вы можете свободно цитировать данную статью на любом носителе и в любом формате при указании авторства.
Cсылка для цитирования на русском языке. Rykunov D.P.  EVOLVING STRATEGIES: A NUMERICAL APPROACH TO GAME-THEORETIC EQUILIBRIUM ANALYSIS [РАЗВИВАЮЩИЕСЯ СТРАТЕГИИ: ЧИСЛЕННЫЙ ПОДХОД К ТЕОРЕТИКО-ИГРОВОМУ АНАЛИЗУ РАВНОВЕСИЯ] // European science № 1(69), 2024. C. {см. журнал}

Поделитесь данной статьей, повысьте свой научный статус в социальных сетях