Differentiable Path-Following Methods with Compact Formulations to Compute Extended and Perfect d-Extended Proper Equilibria in Robust Games
DescriptionGame theory, as a powerful tool for conflict modeling and analysis, has been successfully applied in various areas. In these applications, the computation of Nash equilibrium and its refinements plays a significant role. By incorporating robust optimization into games in normal form, robust game theory was recently developed in the literature, which provides an effective paradigm to address payoff uncertainty that frequently occurs in the applications. When robust games are finite, one can naturally generalize to them the concepts of Nash equilibrium and its refinements. As a strict refinement of proper equilibrium, the concept of extended proper equilibrium was formulated by Milgrom and Mollner (2020). However, this concept has an inherent numerical difficulty in terms of computation even when the number of pure strategies is moderate. To alleviate this difficulty, we come up with the notion of perfect d-extended proper equilibrium. This project aims to develop effective and efficient differentiable path-following methods to compute extended or perfect d-extended proper equilibria in robust games when the payoff uncertainty can be characterized as a bounded polyhedron. To accomplish this goal, we will introduce an extra variable ranging between zero and one and a differentiable increasing function of the extra variable, which takes values between zero and one and vanishes before the extra variable decreases to zero. We will constitute a perturbed robust game in which all players jointly solve against a given mixed strategy profile a linear programming problem and ensure that every Nash equilibrium of the perturbed game is an epsilon-extended or epsilon-perfect d-extended proper equilibrium. With this perturbed game and the increasing function, we will make up barrier or penalty robust games, which can be utilized to establish the existence of smooth paths that lead to extended or perfect d-extended equilibria in robust games. To reduce computational burden especially when the number of pure strategies is large, we will capitalize on the sorting networks and attain compact formulations of the linear programing problem, which have a polynomial number of variables and a polynomial number of inequalities or equalities. By making use of special structures and scaling techniques, efficient procedures will be proposed to numerically follow the smooth paths and a software package will be made available for applications of the methods.
|Effective start/end date||1/01/22 → …|