Computing Nash Equilibria, Subgame Perfect Equilibria, Sequential Equilibria, and Perfect Bayesian Equilibria in Extensive-Form Games

Project: Research

View graph of relations

Description

As a broad class of noncooperative games in game theory, extensive-form games have many applications. To model the rational behavior of players, the creation of Nash equilibrium in behavioral strategies has significantly advanced the development of extensive-form games. Nonetheless, an extensive-form game can have many Nash equilibria in behavioral strategies and some of these equilibria may be inconsistent with our intuitive notions about what should be the outcome of an extensive-form game, especially along the off-the-equilibrium paths. To alleviate this deficiency, several refinements of Nash equilibrium in behavioral strategies such as subgame perfect equilibrium in behavioral strategies, sequential equilibrium, and perfect Bayesian equilibrium have been formulated in the literature. To further boost the applications of extensive-form games, this project aims to develop effective and efficient differentiable path-following methods to compute Nash equilibria and subgame perfect equilibria in behavioral strategies, sequential equilibria, and perfect Bayesian equilibria in finite extensive-form games with perfect recall. To accomplish these objectives, we will formulate equivalent definitions of these equilibrium concepts from a computational perspective. To construct an effective smooth path to a specific equilibrium, we will assign one agent to each information set of a player and constitute with an extra variable ranging between zero and one an entropy-barrier agent extensive-form game in which each agent solves against given behavioral strategy profiles and belief systems a strictly convex optimization problem. With this barrier game, we will establish the existence of an effective smooth path intersecting both the top and bottom levels of the extra variable and satisfying that every limit point of the path yields the desired equilibrium as the extra variable approaches zero. As an alternative scheme, we will devise differentiable linear tracing procedures to select Nash equilibria and subgame perfect equilibria in behavioral strategies, sequential equilibria, and perfect Bayesian equilibria. We will fully benefit from the special structures of extensive-form games in the development of efficient procedures for numerically following the smooth paths to Nash equilibria and subgame perfect equilibria in behavioral strategies, sequential equilibria, and perfect Bayesian equilibria, and make a software package available for applications of the methods. 

Detail(s)

Project number9043544
Grant typeGRF
StatusActive
Effective start/end date1/01/24 → …