Differentiable Path-Following Methods to Compute Refinements of Nash Equilibrium in Robust Normal-Form Games

計算魯棒正則博弈中若幹納什均衡精煉的可微路徑追蹤法

Student thesis: Doctoral Thesis

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Awarding Institution
Supervisors/Advisors
Award date19 Feb 2024

Abstract

Game theory studies how players interact in a game when they consider that their actions will affect each other. Based on various real-world 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 normal-form game exists at least one perfect equilibrium. A perfect equilibrium is a Nash equilibrium that considers the possibility of off-the-equilibrium 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 d-proper 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 n-person game in a normal-form remains challenging. To tackle this problem, we develop differentiable path-following methods for computing refinements of Nash equilibrium in robust normal-form 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 logarithmic-barrier 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 logarithmic-barrier 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 fixed-point 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 convex-quadratic-penalty differentiable path-following method to find perfect equilibria in robust normal-form games. Numerical results indicate that the logarithmic-barrier path-following method significantly outperforms the convex-quadratic-penalty path-following method. We also develop differentiable path-following methods for computing proper equilibria and perfect d-proper equilibria for finite n-person robust normal-form games. Numerical experiments demonstrate that the differentiable path-following method is numerically efficient and that the average computational cost of a perfect d-proper equilibrium is lower than that of a proper equilibrium.