Last-Iterate Convergence to Approximate Nash Equilibria in Multiplayer Imperfect Information Games

Area of Science:

• Game Theory
• Artificial Intelligence
• Reinforcement Learning

Background:

• Real-world games often involve imperfect information and multiple players, posing challenges for traditional game-theoretic methods.
• Existing Nash equilibrium-finding algorithms struggle with multiplayer imperfect information games (IIGs) and deep reinforcement learning (DRL) due to convergence issues.

Purpose of the Study:

• To develop a novel continuous-time dynamic for finding Nash equilibria in multiplayer IIGs.
• To address the limitations of average-iterate convergence methods in DRL contexts.

Main Methods:

• Constructed Imperfect-Information Exponential-Decay Score-based Learning (IESL), incorporating Nash distribution and quantal response equilibrium (QRE).
• Theoretically proved last-iterate convergence of IESL to approximate Nash equilibria under individual concavity.
• Empirically validated IESL in six poker scenarios and multiplayer normal-form games (NFGs).

Main Results:

• IESL demonstrated faster convergence (lower NashConv) than comparative methods like counterfactual regret minimization (CFR) and replicator dynamics (RDs) in multiplayer Leduc hold'em.
• IESL exhibited more stable performance compared to existing equilibrium-finding algorithms in multiplayer NFGs.
• Observed a trade-off between convergence difficulty and NashConv, consistent with hypomonotonicity analysis.

Conclusions:

• IESL offers a promising approach for solving complex multiplayer imperfect information games, particularly within DRL frameworks.
• The method provides theoretical guarantees for convergence and empirical evidence of superior performance.
• IESL advances the field of game theory by offering a more efficient and stable equilibrium-finding solution.