Timezone: »
We focus on the problem of finding an optimal strategy for a team of players that faces an opponent in an imperfect-information zero-sum extensive-form game. Team members are not allowed to communicate during play but can coordinate before the game. In this setting, it is known that the best the team can do is sample a profile of potentially randomized strategies (one per player) from a joint (a.k.a. correlated) probability distribution at the beginning of the game. In this paper, we first provide new modeling results about computing such an optimal distribution by drawing a connection to a different literature on extensive-form correlation. Second, we provide an algorithm that allows one for capping the number of profiles employed in the solution. This begets an anytime algorithm by increasing the cap. We find that often a handful of well-chosen such profiles suffices to reach optimal utility for the team. This enables team members to reach coordination through a simple and understandable plan. Finally, inspired by this observation and leveraging theoretical concepts that we introduce, we develop an efficient column-generation algorithm for finding an optimal distribution for the team. We evaluate it on a suite of common benchmark games. It is three orders of magnitude faster than the prior state of the art on games that the latter can solve and it can also solve several games that were previously unsolvable.
Author Information
Gabriele Farina (Carnegie Mellon University)
Andrea Celli (Facebook CDS)
Nicola Gatti (Politecnico di Milano)
Tuomas Sandholm (Carnegie Mellon University)
Tuomas Sandholm is Angel Jordan Professor of Computer Science at Carnegie Mellon University. He is Founder and Director of the Electronic Marketplaces Laboratory. He has published over 450 papers. With his student Vince Conitzer, he initiated the study of automated mechanism design in 2001. In parallel with his academic career, he was Founder, Chairman, and CTO/Chief Scientist of CombineNet, Inc. from 1997 until its acquisition in 2010. During this period the company commercialized over 800 of the world's largest-scale generalized combinatorial multi-attribute auctions, with over $60 billion in total spend and over $6 billion in generated savings. He is Founder and CEO of Optimized Markets, Strategic Machine, and Strategy Robot. Also, his algorithms run the UNOS kidney exchange, which includes 69% of the transplant centers in the US. He has developed the leading algorithms for several general classes of game. The team that he leads is the two-time world champion in computer Heads-Up No-Limit Texas Hold’em poker, and Libratus became the first and only AI to beat top humans at that game. Among his many honors are the NSF Career Award, inaugural ACM Autonomous Agents Research Award, Sloan Fellowship, Carnegie Science Center Award for Excellence, Edelman Laureateship, Newell Award for Research Excellence, and Computers and Thought Award. He is Fellow of the ACM, AAAI, and INFORMS. He holds an honorary doctorate from the University of Zurich.
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Spotlight: Connecting Optimal Ex-Ante Collusion in Teams to Extensive-Form Correlation: Faster Algorithms and Positive Complexity Results »
Wed. Jul 21st 01:25 -- 01:30 PM Room
More from the Same Authors
-
2023 : Game-Theoretic Robust Reinforcement Learning Handles Temporally-Coupled Perturbations »
Yongyuan Liang · Yanchao Sun · Ruijie Zheng · Xiangyu Liu · Tuomas Sandholm · Furong Huang · Stephen Mcaleer -
2023 Poster: Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion »
Martino Bernasconi · Matteo Castiglioni · Andrea Celli · Alberto Marchesi · Francesco Trovò · Nicola Gatti -
2023 Poster: Near-Optimal $\Phi$-Regret Learning in Extensive-Form Games »
Ioannis Anagnostides · Gabriele Farina · Tuomas Sandholm -
2023 Poster: Online Mechanism Design for Information Acquisition »
Federico Cacciamani · Matteo Castiglioni · Nicola Gatti -
2023 Poster: Team Belief DAG: Generalizing the Sequence Form to Team Games for Fast Computation of Correlated Team Max-Min Equilibria via Regret Minimization »
Brian Zhang · Gabriele Farina · Tuomas Sandholm -
2023 Poster: Constrained Phi-Equilibria »
Martino Bernasconi · Matteo Castiglioni · Alberto Marchesi · Francesco Trovò · Nicola Gatti -
2022 Poster: On Last-Iterate Convergence Beyond Zero-Sum Games »
Ioannis Anagnostides · Ioannis Panageas · Gabriele Farina · Tuomas Sandholm -
2022 Poster: Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games »
Gabriele Farina · Chung-Wei Lee · Haipeng Luo · Christian Kroer -
2022 Poster: Safe Learning in Tree-Form Sequential Decision Making: Handling Hard and Soft Constraints »
Martino Bernasconi · Federico Cacciamani · Matteo Castiglioni · Alberto Marchesi · Nicola Gatti · Francesco Trovò -
2022 Poster: A Marriage between Adversarial Team Games and 2-player Games: Enabling Abstractions, No-regret Learning, and Subgame Solving »
Luca Carminati · Federico Cacciamani · Marco Ciccone · Nicola Gatti -
2022 Spotlight: A Marriage between Adversarial Team Games and 2-player Games: Enabling Abstractions, No-regret Learning, and Subgame Solving »
Luca Carminati · Federico Cacciamani · Marco Ciccone · Nicola Gatti -
2022 Spotlight: Safe Learning in Tree-Form Sequential Decision Making: Handling Hard and Soft Constraints »
Martino Bernasconi · Federico Cacciamani · Matteo Castiglioni · Alberto Marchesi · Nicola Gatti · Francesco Trovò -
2022 Spotlight: Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games »
Gabriele Farina · Chung-Wei Lee · Haipeng Luo · Christian Kroer -
2022 Spotlight: On Last-Iterate Convergence Beyond Zero-Sum Games »
Ioannis Anagnostides · Ioannis Panageas · Gabriele Farina · Tuomas Sandholm -
2022 Poster: Modeling Strong and Human-Like Gameplay with KL-Regularized Search »
Athul Paul Jacob · David Wu · Gabriele Farina · Adam Lerer · Hengyuan Hu · Anton Bakhtin · Jacob Andreas · Noam Brown -
2022 Spotlight: Modeling Strong and Human-Like Gameplay with KL-Regularized Search »
Athul Paul Jacob · David Wu · Gabriele Farina · Adam Lerer · Hengyuan Hu · Anton Bakhtin · Jacob Andreas · Noam Brown -
2021 Poster: Multi-Receiver Online Bayesian Persuasion »
Matteo Castiglioni · Alberto Marchesi · Andrea Celli · Nicola Gatti -
2021 Spotlight: Multi-Receiver Online Bayesian Persuasion »
Matteo Castiglioni · Alberto Marchesi · Andrea Celli · Nicola Gatti -
2020 Poster: Refined bounds for algorithm configuration: The knife-edge of dual class approximability »
Nina Balcan · Tuomas Sandholm · Ellen Vitercik -
2020 Poster: Sparsified Linear Programming for Zero-Sum Equilibrium Finding »
Brian Zhang · Tuomas Sandholm -
2020 Poster: Stochastic Regret Minimization in Extensive-Form Games »
Gabriele Farina · Christian Kroer · Tuomas Sandholm -
2019 Poster: Deep Counterfactual Regret Minimization »
Noam Brown · Adam Lerer · Sam Gross · Tuomas Sandholm -
2019 Poster: Stable-Predictive Optimistic Counterfactual Regret Minimization »
Gabriele Farina · Christian Kroer · Noam Brown · Tuomas Sandholm -
2019 Poster: Regret Circuits: Composability of Regret Minimizers »
Gabriele Farina · Christian Kroer · Tuomas Sandholm -
2019 Oral: Deep Counterfactual Regret Minimization »
Noam Brown · Adam Lerer · Sam Gross · Tuomas Sandholm -
2019 Oral: Stable-Predictive Optimistic Counterfactual Regret Minimization »
Gabriele Farina · Christian Kroer · Noam Brown · Tuomas Sandholm -
2019 Oral: Regret Circuits: Composability of Regret Minimizers »
Gabriele Farina · Christian Kroer · Tuomas Sandholm -
2018 Poster: Learning to Branch »
Nina Balcan · Travis Dick · Tuomas Sandholm · Ellen Vitercik -
2018 Oral: Learning to Branch »
Nina Balcan · Travis Dick · Tuomas Sandholm · Ellen Vitercik -
2018 Tutorial: Machine Learning in Automated Mechanism Design for Pricing and Auctions »
Nina Balcan · Tuomas Sandholm · Ellen Vitercik -
2017 Poster: Regret Minimization in Behaviorally-Constrained Zero-Sum Games »
Gabriele Farina · Christian Kroer · Tuomas Sandholm -
2017 Poster: Reduced Space and Faster Convergence in Imperfect-Information Games via Pruning »
Noam Brown · Tuomas Sandholm -
2017 Talk: Reduced Space and Faster Convergence in Imperfect-Information Games via Pruning »
Noam Brown · Tuomas Sandholm -
2017 Talk: Regret Minimization in Behaviorally-Constrained Zero-Sum Games »
Gabriele Farina · Christian Kroer · Tuomas Sandholm