Timezone: »
\emph{Ex ante} correlation is becoming the mainstream approach for \emph{sequential adversarial team games}, where a team of players faces another team in a zero-sum game. It is known that team members' asymmetric information makes both equilibrium computation \textsf{APX}-hard and team's strategies not directly representable on the game tree. This latter issue prevents the adoption of successful tools for huge 2-player zero-sum games such as, \emph{e.g.}, abstractions, no-regret learning, and subgame solving. This work shows that we can recover from this weakness by bridging the gap between sequential adversarial team games and 2-player games. In particular, we propose a new, suitable game representation that we call \emph{team-public-information}, in which a team is represented as a single coordinator who only knows information common to the whole team and prescribes to each member an action for any possible private state. The resulting representation is highly \emph{explainable}, being a 2-player tree in which the team's strategies are behavioral with a direct interpretation and more expressive than the original extensive form when designing abstractions. Furthermore, we prove payoff equivalence of our representation, and we provide techniques that, starting directly from the extensive form, generate dramatically more compact representations without information loss. Finally, we experimentally evaluate our techniques when applied to a standard testbed, comparing their performance with the current state of the art.
Author Information
Luca Carminati (Politecnico di Milano)
Federico Cacciamani (Politecnico di Milano)
Marco Ciccone (Politecnico di Milano)
Nicola Gatti (Politecnico di Milano)
Related Events (a corresponding poster, oral, or spotlight)
-
2022 Poster: A Marriage between Adversarial Team Games and 2-player Games: Enabling Abstractions, No-regret Learning, and Subgame Solving »
Thu. Jul 21st through Fri the 22nd Room Hall E #1224
More from the Same Authors
-
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: Online Mechanism Design for Information Acquisition »
Federico Cacciamani · Matteo Castiglioni · Nicola Gatti -
2023 Poster: Constrained Phi-Equilibria »
Martino Bernasconi · Matteo Castiglioni · Alberto Marchesi · Francesco Trovò · Nicola Gatti -
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 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ò -
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 -
2021 Poster: Connecting Optimal Ex-Ante Collusion in Teams to Extensive-Form Correlation: Faster Algorithms and Positive Complexity Results »
Gabriele Farina · Andrea Celli · Nicola Gatti · Tuomas Sandholm -
2021 Spotlight: Connecting Optimal Ex-Ante Collusion in Teams to Extensive-Form Correlation: Faster Algorithms and Positive Complexity Results »
Gabriele Farina · Andrea Celli · Nicola Gatti · Tuomas Sandholm