Differentiable PathFollowing Methods to Compute Refinements of Nash Equilibrium in Robust NormalForm Games
計算魯棒正則博弈中若幹納什均衡精煉的可微路徑追蹤法
Student thesis: Doctoral Thesis
Author(s)
Related Research Unit(s)
Detail(s)
Awarding Institution  

Supervisors/Advisors 

Award date  19 Feb 2024 
Link(s)
Permanent Link  https://scholars.cityu.edu.hk/en/theses/theses(19bf9724b41f4043862a98ab217baa35).html 

Other link(s)  Links 
Abstract
Game theory studies how players interact in a game when they consider that their actions will affect each other. Based on various realworld applications, it is now certain that game theory is a powerful method of conflict modeling and analysis. Areas to which it is applicable include biology, business, computer science, economics, engineering, and political science. As an effective way of dealing with payoff uncertainty, robust game theory was formulated by integrating robust optimization into game theory. The concept of Nash equilibrium was formulated based on the principle that no player has anything to gain by changing only their own strategy in an equilibrium. Although the concept has significantly advanced the application of game theory, a game can have multiple Nash equilibria, some of which may be counterintuitive about the game’s outcome. Thus, the notion of perfect equilibrium was introduced to exclude some counterintuitive Nash equilibria, and a normalform game exists at least one perfect equilibrium. A perfect equilibrium is a Nash equilibrium that considers the possibility of offtheequilibrium play by assuming that the players may choose unintended strategies with a negligible probability. The introduction of perfect equilibria substantially reduces the set of Nash equilibria. However, a game can still have many perfect equilibria, some of which are undesirable. Thus, the concept of proper equilibrium was introduced to exclude some undesirable perfect equilibria. Nevertheless, the proper equilibrium suffers in terms of computational precision from inherent numerical difficulty, even with a moderate number of pure strategies. To overcome this difficulty, the notion of perfect dproper equilibrium was introduced to approximate a proper equilibrium with considerably less computational precision. The introduction of these refinements of Nash equilibrium has significantly advanced the development and application of game theory. However, although these refinements play an essential role in the theory's application, computing them in a robust finite nperson game in a normalform remains challenging. To tackle this problem, we develop differentiable pathfollowing methods for computing refinements of Nash equilibrium in robust normalform games when the payoff uncertainty can be characterized as a bounded polyhedron with an interior point. By introducing an extra variable ranging between zero and one, we incorporate logarithmic barrier terms into the players’ payoff functions and construct a robust logarithmicbarrier game. In this barrier game, each player solves a strictly convex optimization problem against a given mixed strategy profile. Applying the optimization conditions to the barrier game and the equilibrium condition yields a polynomial equilibrium system. With this equilibrium system, we establish the existence of a smooth path that starts from a given completely mixed strategy profile and ends in a Nash equilibrium as the extra variable vanishes, and we acquire three different smooth paths from simple manipulations. We use the predictor–corrector method to follow the paths. Numerical results confirm the method’s effectiveness. To rule out some counterintuitive Nash equilibria, we add logarithmic barrier terms into each player's payoff function by introducing an extra variable ranging from zero to one to construct another robust logarithmicbarrier game for computing perfect equilibria. In this barrier game, each player solves a strictly convex optimization problem for a given mixed strategy profile. Applying optimization conditions to the barrier game along with a fixedpoint argument yields a polynomial equilibrium system. Using this system, we can establish the existence of a smooth path from a given completely mixed strategy profile to a perfect equilibrium, with the extra variable approaching zero. To facilitate numerical comparisons, we present an additional globally convergent convexquadraticpenalty differentiable pathfollowing method to find perfect equilibria in robust normalform games. Numerical results indicate that the logarithmicbarrier pathfollowing method significantly outperforms the convexquadraticpenalty pathfollowing method. We also develop differentiable pathfollowing methods for computing proper equilibria and perfect dproper equilibria for finite nperson robust normalform games. Numerical experiments demonstrate that the differentiable pathfollowing method is numerically efficient and that the average computational cost of a perfect dproper equilibrium is lower than that of a proper equilibrium.