标题： 关于扩展形式博弈中最优相关均衡的复杂性 显示英文标题

标题： On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games

摘要： 一个在算法博弈论中的重大开放性问题是，是否可以在如序贯形式博弈这样的紧凑博弈中高效计算正常形式相关均衡（NFCE）[DFF+25,6PR24,FP23,HvS08,VSF08,PR08]。 受这一问题的启发，我们研究了相关的阈值问题：判断是否存在一个价值超过给定阈值的相关均衡。 我们证明，对于具有完美回忆的多人序贯形式博弈中的NFCE，这个问题是PSPACE难的，即使对于固定阈值也是如此。 为了使这一结果更具背景意义，我们也建立了在此设置下纳什均衡的阈值问题的复杂度，表明它是ER完全的。 这些结果揭示了一个令人惊讶的复杂度反转：虽然在正常形式博弈中，最优相关均衡比最优纳什均衡在计算上更简单，但在序贯形式博弈中情况则相反，计算最优相关均衡被证明更困难。 在这一研究方向的基础上，我们还回答了[VSF08]提出的一个相关问题，他们引入了序贯形式相关均衡（EFCE）和参与者形式相关均衡（AFCE）的概念。 他们询问AFCE的阈值问题有多难；我们通过证明即使在没有机会节点的两人博弈中，该问题也是NP难的来回答这个问题。 除了我们的难解性结果外，我们还为几种相关均衡概念下的阈值问题建立了严格的复杂度分类——包括EFCE、AFCE、正常形式粗略、序贯形式粗略和参与者形式粗略相关均衡。 对于具有完美回忆的多人随机序贯形式博弈中的每一种解概念，我们通过提供与之前已知的难解性结果相匹配的NP上界，证明了NP完备性。 综上所述，我们的结果为序贯形式博弈中最优均衡计算的复杂度提供了迄今为止最完整的图景。 显示英文摘要

摘要： A major open question in algorithmic game theory is whether normal-form correlated equilibria (NFCE) can be computed efficiently in succinct games such as extensive-form games [DFF+25,6PR24,FP23,HvS08,VSF08,PR08]. Motivated by this question, we study the associated Threshold problem: deciding whether there exists a correlated equilibrium whose value exceeds a given threshold. We prove that this problem is PSPACE-hard for NFCE in multiplayer extensive-form games with perfect recall, even for fixed thresholds. To contextualize this result, we also establish the complexity of the Threshold problem for Nash equilibria in this setting, showing it is ER-complete. These results uncover a surprising complexity reversal: while optimal correlated equilibria are computationally simpler than optimal Nash in normal-form games, the opposite holds in extensive-form games, where computing optimal correlated equilibria is provably harder. Building on this line of inquiry, we also address a related question by [VSF08], who introduced the notions of extensive-form correlated equilibrium (EFCE) and agent-form correlated equilibrium (AFCE). They asked how difficult the Threshold problem is for AFCE; we answer this question by proving that it is NP-hard, even in two-player games without chance nodes. Complementing our hardness results, we establish tight complexity classifications for the Threshold problem across several correlated equilibrium concepts - including EFCE, AFCE, normal-form coarse, extensive-form coarse, and agent-form coarse correlated equilibria. For each of these solution concepts in multiplayer stochastic extensive-form games with perfect recall, we prove NP-completeness by providing matching NP upper bounds to the previously known hardness results. Together, our results provide the most complete landscape to date for the complexity of optimal equilibrium computation in extensive-form games.