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

References

• [1] Aumann R (1974) Subjectivity and correlation in randomized strategies. J. Math. Econom. 1(1):67–96.Crossref, Google Scholar
• [2] Brown N, Sandholm T (2018) Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science 359(6374):418–424.Crossref, Google Scholar
• [3] Brown N, Sandholm T (2019) Superhuman AI for multiplayer poker. Science 365(6456):885–890.Crossref, Google Scholar
• [4] Carminati L, Cacciamani F, Ciccone M, Gatti N (2022) A marriage between adversarial team games and 2-player games: Enabling abstractions, no-regret learning, and subgame solving. Internat. Conf. Machine Learn. (ICML) (PMLR, Baltimore).Google Scholar
• [5] Celli A, Gatti N (2018) Computational results for extensive-form adversarial team games. AAAI Conf. Artificial Intelligence (AAAI) (Association for the Advancement of Artificial Intelligence (AAAI Press), Palo Alto, CA).Google Scholar
• [6] Celli A, Coniglio S, Gatti N (2019) Computing Optimal Ex Ante Correlated Equilibria in Two-Player Sequential Games. Autonomous Agents and Multi-Agent Systems (AAMAS) (International Foundation for Autonomous Agents and MultiAgent Systems (IFAAMAS), Richland, SC).Google Scholar
• [7] Celli A, Marchesi A, Farina G, Gatti N (2020) No-regret learning dynamics for extensive-form correlated equilibrium. Neural Inform. Proc. Systems (Neural Information Processing Systems Foundation, Inc. (NeurIPS)).Google Scholar
• [8] Chen J, Chor B, Fellows M, Huang X, Juedes D, Kanj IA, Xia G (2005) Tight lower bounds for certain parameterized NP-hard problems. Inform. Comput. 201(2):216–231.Crossref, Google Scholar
• [9] Chen X, Deng X, Teng SH (2009) Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3):14.Crossref, Google Scholar
• [10] Chu F, Halpern J (2001) On the NP-completeness of finding an optimal strategy in games with common payoffs. Internat. J. Game Theory 30:99–106.Crossref, Google Scholar
• [11] Conforti M, Cornuéjols G, Zambelli G (2010) Extended formulations in combinatorial optimization. 4OR 8(1):1–48.Crossref, Google Scholar
• [12] Dagan Y, Daskalakis C, Fishelson M, Golowich N (2024) From external to swap regret 2.0: An efficient reduction and oblivious adversary for large action spaces. Sympos. Theory Comput. (STOC) (Association for Computing Machinery, New York).Google Scholar
• [13] Farina G, Sandholm T (2020) Polynomial-time computation of optimal correlated equilibria in two-player extensive-form games with public chance moves and beyond. Neural Inform. Proc. Systems (Neural Information Processing Systems Foundation, Inc. (NeurIPS)).Google Scholar
• [14] Farina G, Bianchi T, Sandholm T (2020) Coarse correlation in extensive-form games. AAAI Conf. Artificial Intelligence (AAAI) (Association for the Advancement of Artificial Intelligence (AAAI Press), Palo Alto, CA).Google Scholar
• [15] Farina G, Celli A, Gatti N, Sandholm T (2021) Connecting optimal ex-ante collusion in teams to extensive-form correlation: Faster algorithms and positive complexity results. Internat. Conf. Machine Learn. (ICML) (PMLR, New York).Google Scholar
• [16] Farina G, Celli A, Marchesi A, Gatti N (2022) Simple uncoupled no-regret learning dynamics for extensive-form correlated equilibrium. J. ACM 69(6):41.Crossref, Google Scholar
• [17] Farina G, Ling CK, Fang F, Sandholm T (2019) Correlation in extensive-form games: Saddle-point formulation and benchmarks. Neural Inform. Proc. Systems (Neural Information Processing Systems Foundation, Inc. (NeurIPS), Vancouver, BC).Google Scholar
• [18] Ford LR, Fulkerson DR (1958) A suggested computation for maximal multi-commodity network flows. Management Sci. 5(1):97–101.Link, Google Scholar
• [19] Ginsberg ML (1999) GIB: Steps toward an expert-level bridge-playing program. Internat. Joint Conf. Artificial Intelligence (IJCAI) (Morgan Kaufmann Publishers Inc., Stockholm).Google Scholar
• [20] Gordon GJ, Greenwald A, Marks C (2008) No-regret learning in convex games. Internat. Conf. Machine Learn. (ICML) (Association for Computing Machinery (ACM), New York).Google Scholar
• [21] Huang W, von Stengel B (2008) Computing an extensive-form correlated equilibrium in polynomial time. Internat. Workshop Internet Network Econom. (WINE) (Springer, Berlin, Heidelberg).Google Scholar
• [22] Jakobsen SK, Sørensen TB, Conitzer V (2016) Timeability of extensive-form games. 2016 ACM Conf. Innovations Theoretical Comput. Sci. (Association for Computing Machinery (ACM), New York).Google Scholar
• [23] Jiang AX, Leyton-Brown K (2015) Polynomial-time computation of exact correlated equilibrium in compact games. Games Econom. Behav. 91:347–359.Crossref, Google Scholar
• [24] Koller D, Megiddo N (1992) The complexity of two-person zero-sum games in extensive form. Games Econom. Behav. 4(4):528–552.Crossref, Google Scholar
• [25] Koller D, Megiddo N, von Stengel B (1994) Fast algorithms for finding randomized strategies in game trees. Sympos. Theory Comput. (STOC) (Association for Computing Machinery (ACM), New York).Google Scholar
• [26] Kuhn HW (1950) A simplified two-person poker. Kuhn HW, Tucker AW, eds. Contributions to the Theory of Games, Annals of Mathematics Studies, 24, vol. 1 (Princeton University Press, Princeton, NJ), 97–103.Google Scholar
• [27] Lisỳ V, Lanctot M, Bowling MH (2015) Online Monte Carlo counterfactual regret minimization for search in imperfect information games. Autonomous Agents and Multi-Agent Systems (AAMAS) (International Foundation for Autonomous Agents and MultiAgent Systems (IFAAMAS), Richland, SC).Google Scholar
• [28] Moravčík M, Schmid M, Burch N, Lisý V, Morrill D, Bard N, Davis T, Waugh K, Johanson M, Bowling M (2017) DeepStack: Expert-level artificial intelligence in heads-up no-limit poker. Science 356(1667):508–513.Crossref, Google Scholar
• [29] Moulin H, Vial JP (1978) Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon. Internat. J. Game Theory 7(3–4):201–221.Crossref, Google Scholar
• [30] Papadimitriou CH, Roughgarden T (2008) Computing correlated equilibria in multi-player games. J. ACM 55(3):14.Crossref, Google Scholar
• [31] Peng B, Rubinstein A (2024) Fast swap regret minimization and applications to approximate correlated equilibria. Sympos. Theory Comput. (STOC) (Association for Computing Machinery (ACM), New York).Google Scholar
• [32] Romanovskii I (1962) Reduction of a game with complete memory to a matrix game. Soviet Mathematics 3:678–681.Google Scholar
• [33] Ross SM (1971) Goofspiel—The game of pure strategy. J. Appl. Probab. 8(3):621–625.Crossref, Google Scholar
• [34] Roughgarden T (2015) Intrinsic robustness of the price of anarchy. J. ACM 62(5):1–42.Crossref, Google Scholar
• [35] Southey F, Bowling M, Larson B, Piccione C, Burch N, Billings D, Rayner C (2005) Bayes’ bluff: Opponent modelling in poker. Conf. Uncertainty Artificial Intelligence (UAI) (Association for Uncertainty in Artificial Intelligence (AUAI) Press, Arlington, VA).Google Scholar
• [36] von Stengel B (1996) Efficient computation of behavior strategies. Games Econom. Behav. 14(2):220–246.Crossref, Google Scholar
• [37] von Stengel B, Forges F (2008) Extensive-form correlated equilibrium: Definition and computational complexity. Math. Oper. Res. 33(4):1002–1022.Link, Google Scholar
• [38] von Stengel B, Koller D (1997) Team-maxmin equilibria. Games Econom. Behav. 21:309–321.Crossref, Google Scholar
• [39] Zhang BH, Sandholm T (2022) Team correlated equilibria in zero-sum extensive-form games via tree decompositions. AAAI Conf. Artificial Intelligence (AAAI) (Association for the Advancement of Artificial Intelligence (AAAI Press), Palo Alto, CA).Google Scholar
• [40] Zhang BH, Farina G, Sandholm T (2023a) Team belief DAG: Generalizing the sequence form to team games for fast computation of correlated team max-min equilibria via regret minimization. Internat. Conf. Machine Learn. (ICML) (Proceedings of Machine Learning Research (PMLR), New York).Google Scholar
• [41] Zhang BH, Farina G, Anagnostides I, Cacciamani F, McAleer S, Haupt A, Celli A, Gatti N, Conitzer V, Sandholm T (2023b) Computing optimal equilibria and mechanisms via learning in zero-sum extensive-form games. Neural Inform. Proc. Systems (Neural Information Processing Systems Foundation, Inc. (NeurIPS), New Orleans).Google Scholar
• [42] Zhang Y, An B, Černỳ J (2021) Computing ex ante coordinated team-maxmin equilibria in zero-sum multiplayer extensive-form games. AAAI Conf. Artificial Intelligence (AAAI) (Association for the Advancement of Artificial Intelligence (AAAI Press), Palo Alto, CA).Google Scholar
• [43] Zhang Y, An B, Zeng DD (2024) DAG-based column generation for adversarial team games. Internat. Conf. Machine Learn. (ICML) (Proceedings of Machine Learning Research (PMLR), Vienna).Google Scholar