# Public Information Representation for Adversarial Team Games

arXiv: https://arxiv.org/abs/2201.10377 · HTML: https://mlsanity.com/paper/2201.10377/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 28 references that are in the map.
- First posted on arXiv 25 Jan 2022.

## Builds on (most cited first, 12 of 12)

- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Combining Deep Reinforcement Learning and Search for Imperfect-Information Games](https://mlsanity.com/paper/2007.13544/) (2020)
- [Deep Counterfactual Regret Minimization](https://mlsanity.com/paper/1811.00164/) (2018)
- [Solving Large Imperfect Information Games Using CFR+](https://mlsanity.com/paper/1407.5042/) (2014)
- [Solving Imperfect-Information Games via Discounted Regret Minimization](https://mlsanity.com/paper/1809.04040/) (2018)
- [Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1811.01458/) (2018)
- [Computational Results for Extensive-Form Adversarial Team Games](https://mlsanity.com/paper/1711.06930/) (2017)
- [Solving Common-Payoff Games with Approximate Policy Iteration](https://mlsanity.com/paper/2101.04237/) (2021)
- [Team-maxmin equilibrium: efficiency bounds and algorithms](https://mlsanity.com/paper/1611.06134/) (2016)
- [Coordination in Adversarial Sequential Team Games via Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/1912.07712/) (2019)
- [Multi-Agent Coordination in Adversarial Environments through Signal Mediated Strategies](https://mlsanity.com/paper/2102.05026/) (2021)

## Built on by (most cited first, 4 of 4)

- [For Learning in Symmetric Teams, Local Optima are Global Nash Equilibria](https://mlsanity.com/paper/2207.03470/) (2022)
- [Abstracting Imperfect Information Away from Two-Player Zero-Sum Games](https://mlsanity.com/paper/2301.09159/) (2023)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [The Update-Equivalence Framework for Decision-Time Planning](https://mlsanity.com/paper/2304.13138/) (2023)

## Abstract (arXiv)

The peculiarity of adversarial team games resides in the asymmetric information available to the team members during the play, which makes the equilibrium computation problem hard even with zero-sum payoffs. The algorithms available in the literature work with implicit representations of the strategy space and mainly resort to Linear Programming and column generation techniques to enlarge incrementally the strategy space. Such representations prevent the adoption of standard tools such as abstraction generation, game solving, and subgame solving, which demonstrated to be crucial when solving huge, real-world two-player zero-sum games. Differently from these works, we answer the question of whether there is any suitable game representation enabling the adoption of those tools. In particular, our algorithms convert a sequential team game with adversaries to a classical two-player zero-sum game. In this converted game, the team is transformed into a single coordinator player who only knows information common to the whole team and prescribes to the players an action for any possible private state. Interestingly, we show that our game is more expressive than the original extensive-form game as any state/action abstraction of the extensive-form game can be captured by our representation, while the reverse does not hold. Due to the NP-hard nature of the problem, the resulting Public Team game may be exponentially larger than the original one. To limit this explosion, we provide three algorithms, each returning an information-lossless abstraction that dramatically reduces the size of the tree. These abstractions can be produced without generating the original game tree. Finally, we show the effectiveness of the proposed approach by presenting experimental results on Kuhn and Leduc Poker games, obtained by applying state-of-art algorithms for two-player zero-sum games on the converted games