Finding the Strong Nash Equilibrium: Computation, Existence and Characterization for Markov Games
- PDF / 555,679 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 75 Downloads / 213 Views
Finding the Strong Nash Equilibrium: Computation, Existence and Characterization for Markov Games Julio B. Clempner1
· Alexander S. Poznyak2
Received: 13 June 2018 / Accepted: 22 July 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This paper suggests a procedure to construct the Pareto frontier and efficiently computes the strong Nash equilibrium for a class of time-discrete ergodic controllable Markov chain games. The procedure finds the strong Nash equilibrium, using the Newton optimization method presenting a potential advantage for ill-conditioned problems. We formulate the solution of the problem based on the Lagrange principle, adding a Tikhonov’s regularization parameter for ensuring both the strict convexity of the Pareto frontier and the existence of a unique strong Nash equilibrium. Then, any welfare optimum arises as a strong Nash equilibrium of the game. We prove the existence and characterization of the strong Nash equilibrium, which is one of the main results of this paper. The method is validated theoretically and illustrated with an application example. Keywords Strong equilibrium · Game theory · Markov processes · Pareto · algorithms · Optimizations Mathematics Subject Classification 91A12 · 91A40 · 91A80
Communicated by Kyriakos G. Vamvoudakis.
B
Julio B. Clempner [email protected] Alexander S. Poznyak [email protected]
1
School of Physics and Mathematics, National Polytechnic Institute, Edificio 9 U.P. Adolfo Lopez Mateos, Col. San Pedro Zacatenco, 07730 Mexico City, Mexico
2
Department of Control Automatics, Center for Research and Advanced Studies, Av. IPN 2508, Col. San Pedro Zacatenco, 07360 Mexico City, Mexico
123
Journal of Optimization Theory and Applications
1 Introduction 1.1 Brief Review Being a fundamental concept in game theory, Nash equilibrium is one of the most important research topics in several areas of applications such as economics, social science, political science, decision making and engineering. It is based on the idea of stability against any unilateral deviations. Many algorithms have been developed to compute the Nash equilibrium [1,2] since this solution concept was proposed by Nash [3]. When players cooperate with each other to achieve a goal and they can conform coalitions in a game, then the corresponding solution concept is that of strong Nash equilibrium (SNE) [4]. Many refinements of Nash equilibrium have been proposed, to better model applied welfare economies in the real world. Ichiishi [5] proposed a social coalition equilibrium with an abstract model of society in which each member can cooperate with others by forming a coalition. Guesnerie and Oddou [6] proposed a solution that reflects the power of the different players in a negotiation process for the second best taxation theory. Greenberg and Weber [7] identified a class of economic and political environments that admit an J -equilibrium. Demange [8] proposed two forces that are at work to explain the formation of coalitions that partition the s
Data Loading...
