A Differentiable Path-Following Method with a Compact Formulation to Compute Proper Equilibria

作者：Cao, Yiyin; Chen, Yin; Dang, Chuangyin^*

来源：INFORMS JOURNAL ON COMPUTING, 2023.

DOI：10.1287/ijoc.2022.0148

• noncooperative game
• Nash equilibrium
• proper equilibrium
• perfect d-proper equilibrium
• differentiable path-following method

The concept of proper equilibrium was established as a strict refinement of perfect equilibrium. This establishment has significantly advanced the development of game theory and its applications. Nonetheless, it remains a challenging problem to compute such an equilibrium. This paper develops a differentiable path-following method with a compact formulation to compute a proper equilibrium. The method incorporates square root-barrier terms into payoff functions with an extra variable and constitutes a square root-barrier game. As a result of this barrier game, we acquire a smooth path to a proper equilibrium. To further reduce the computational burden, we present a compact formulation of an epsilon-proper equilibrium with a polynomial number of variables and equations. Numerical results show that the differentiable path-following method is numerically stable and efficient. Moreover, by relaxing the requirements of proper equilibrium and imposing Selten's perfection, we come up with the notion of perfect d-proper equilibrium, which approximates a proper equilibrium and is less costly to compute. Numerical examples demonstrate that even when d is rather large, a perfect d-proper equilibrium remains to be a proper equilibrium.

• 单位
  西安交通大学