Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation

• 成果类型: Article; Early Access
• 署名作者: Zhang, Brian Hu; Farina, Gabriele; Celli, Andrea; Sandholm, Tuomas
• 署名单位: Carnegie Mellon University; Massachusetts Institute of Technology (MIT); Bocconi University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.0226
• 发表日期: 2025
• 关键词: computation

摘要

We study the problem of finding optimal correlated equilibria of various sorts in extensive-form games: normal-form coarse correlated equilibrium (NFCCE), extensive-form coarse correlated equilibrium (EFCCE), and extensive-form correlated equilibrium (EFCE). We make two primary contributions. First, we introduce a new algorithm for computing optimal equilibria in all three notions. Its runtime depends exponentially only on a parameter related to the information structure of the game. We also prove a fundamental complexity gap between NFCCE and the other two concepts. Second, we propose a two-sided column generation approach for use when the runtime or memory usage of the previous algorithm is prohibitive. Our algorithm improves upon an earlier one-sided approach by means of a new decomposition of correlated strategies which allows players to reoptimize their sequence-form strategies with respect to correlation plans which were previously added to the support. Experiments show that our techniques outperform the prior state of the art for computing optimal general-sum correlated equilibria.