Selecting Normal-Form Nash Equilibria in Extensive-Form Games via a Sequence-Form Variant of Logit Quantal Response Equilibrium
For game theorists and AI researchers, this provides an efficient equilibrium selection mechanism for extensive-form games, addressing a key computational bottleneck.
The paper develops a sequence-form formulation of logit QRE for extensive-form games, enabling compact computation without normal-form explosion, and proposes a differentiable path-following method that yields a Nash equilibrium as the rationality parameter tends to infinity. The method is validated theoretically and numerically.
Although logit quantal response equilibrium (logit QRE) offers a natural equilibrium selection mechanism and converges to Nash equilibrium as the rationality parameter tends to infinity, its computation in extensive-form games is generally intractable when based on the normal-form representation, due to the exponential growth of the strategy space. To address this difficulty, this paper develops a sequence-form formulation of logit QRE for finite n-player extensive-form games with perfect recall, which avoids explicit construction of the normal form and enables compact computation. Based on this formulation, we further develop a differentiable path-following method starting from an arbitrary initial point, such that each point on the path corresponds to a logit QRE associated with a particular value of the rationality parameter, and the limiting point yields a Nash equilibrium. In this way, the proposed method provides an efficient computational framework for exploiting the equilibrium selection property of logit QRE in extensive-form games. The effectiveness of the proposed method is validated by theoretical analysis and numerical experiments.