Back to Search Start Over

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

Authors :
Cao, Yiyin
Chen, Yin
Dang, Chuangyin
Source :
INFORMS Journal on Computing; Mar/Apr2024, Vol. 36 Issue 2, p377-396, 20p
Publication Year :
2024

Abstract

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 ε-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. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms-Continuous. Funding: This work was partially supported by General Research Fund (GRF) CityU 11306821 of Hong Kong SAR Government. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0148) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0148). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
10919856
Volume :
36
Issue :
2
Database :
Complementary Index
Journal :
INFORMS Journal on Computing
Publication Type :
Academic Journal
Accession number :
176567436
Full Text :
https://doi.org/10.1287/ijoc.2022.0148