Computation of Nash Equilibria for Finite n-Person Games in Normal Form

As a powerful mechanism for conflict modeling and analysis, game theory has been successfully applied in many fields including economics, management science, political science, and computer science. In these applications, the computation of Nash equilibria plays an important role and has attracted a lot of attention. Although several numerical procedures have been developed in the literature, how to efficiently compute Nash equilibria still remains to be a challenging problem and appeals for more efficient alternatives. This project aims to develop a more efficient path-following method for computing Nash equilibria of finite n-person games in normal form. The emphasis will be on fully exploiting differentiability of the problem in the development. As that in interior-point methods, a smooth path that leads to a Nash equilibrium will be constructed by introducing an extra variable for deforming a trivial game to the original game. Sard’s theorem and perturbations will be applied to derive the existence of the path. To follow the path numerically, an efficient predictor-corrector method will be proposed. Numerical comparisons with existing path-following methods will be carried out. The ultimately expected outcome of the project will be a more efficient path-following method for computing Nash equilibria.