Recent Advancements in Equilibrium Computation for Adversarial Team Games
Nicola Gatti (Politecnico di Milano)
Venerdì, 17 February, 2023 - 15:00
DIAG - Aula Magna
Abstract: In adversarial team games, a team of players sequentially faces a team of adversaries. These games are the simplest setting with multiple players where cooperation and competition coexist, and it is known that the information asymmetry among the team members makes equilibrium approximation computationally hard. Although much effort has been spent designing scalable algorithms, the problem of solving large game instances is open. 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 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 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 the 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.
Bio sketch: Nicola Gatti is an associate professor of Computer Science and Engineering in the Department of Electronics, Information, and Bioengineering at Politecnico di Milano. His main achievements come from algorithmic game theory, allocation problems and incentives, algorithmic social choice theory, multiagent learning, and online learning. He received several awards, including the 2011 AIxIA Marco Somalvico Award as the best Italian young researcher in AI, the best paper award in several conferences, including the prestigious NeurIPS 2020 and Cooperative AI 2021 funded by Google Deepmind. In 2021 he was elected as a EurAi Fellow (top <3% of the European AI scientists) and awarded at IJCAI 2022, and he is also AIAA Fellow since 2022. He is one of the ten spoke coordinators of the PNRR-PE project (FAIR) on AI.
gruppo di ricerca: