Smooth path-following approaches to determining refinements of Nash equilibrium in strategic form

Abstract

Game theory studies how players make decisions in a game when they know that their actions affect each other and when each player takes this fact into account. It is a powerful mechanism for conflict modeling and analysis, and it has been successfully applied in a variety of fields, such as biology, business, computer science, economics, engineering, and political science. The concept of Nash equilibrium is one of the most important and elegant ideas in game theory and its applications. However, a game can have many Nash equilibria, some of which can be inconsistent with intuitive notions about the outcome of the game. The concept of perfect equilibrium was introduced to reduce this ambiguity and eliminate some of the counterintuitive equilibria. A perfect equilibrium is a Nash equilibrium that takes into account the possibility of off-the-equilibrium play by assuming that the players may choose unintended strategies with negligible probability. The introduction of perfect equilibrium substantially reduces the set of Nash equilibria. However, a game can still have many perfect equilibria, some of which are undesirable. To exclude some of these undesirable perfect equilibria, the concept of proper equilibrium was introduced. The formulation of proper equilibrium significantly reduces the set of perfect equilibria. The introduction of perfect equilibrium and proper equilibrium have significantly advanced the development of game theory and its application. Perfect equilibrium and proper equilibrium are two strict refinements of the Nash equilibrium concept and they always exist in a game. Computing perfect and proper equilibria plays an important role in the application of game theory. However, there are very few methods for these refinements of the Nash equilibrium. The existing generic approach for computing a perfect equilibrium is to compute Nash equilibria for a sequence of perturbed games and obtain a perfect equilibrium at a limit of these equilibria. However, this approach can be very time-consuming. Path-following methods have been proposed for computing Nash equilibria and numerical results show that these methods are very efficient. Unfortunately, no such approach exists for computing a perfect equilibrium. This deficiency naturally leads to the challenging question: Can a path-following method be found for computing a perfect equilibrium? A smooth path-following method is developed for determining perfect equilibria of finite n-person games in strategic form. The method closely approximates the Nash equilibria of a perturbed game by incorporating a barrier term into each player's payoff function with an appropriate convex combination. A desired property of the multi-linear form of the payoff function and an application of the problem's differentiability lead to the existence of a smooth path that starts from a totally mixed strategy profile and ends at a perfect equilibrium. A predictor-corrector method is used to follow the path. Numerical results confirm the effectiveness of the method. A smooth path-following method is also developed for determining proper equilibria for finite n-person games in strategic form. However, the notion of proper equilibrium can lead to a serious numerical problem in this computation. To remedy this deficiency, a perfect d-proper equilibrium, which is also a strict refinement of the concept of perfect equilibrium, is proposed for a finite n-person game in strategic form, where d is a positive number less than one and measures the degree of properness of an equilibrium. The smaller the value of d, the higher the degree of properness. It is shown that any finite n-person game in strategic form possesses at least one perfect d-proper equilibrium. This equilibrium is much easier to compute than a proper equilibrium. Applications to classic strategic form games illustrate that perfect d-proper equilibria are proper equilibria even when d is large. An effective smooth path-following method is developed to determine perfect d-proper equilibria for finite n-person games in strategic form.

Date of Award	3 Oct 2014
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Chuangyin DANG (Supervisor)