Section: Computer Science and Engineering
Tutor: ALIPPI CESARE
Advisor: GATTI NICOLA Major Research topic
:Coordination and Correlation in Multi-player Sequential GamesAbstract:
The analysis of games allowing some form of coordination among players is a largely unexplored topic in the algorithmic game theory literature. These game models are essential to describe strategic interactions between rational agents that may organize themselves in a team (i.e., a group of agents sharing the same utility function).
We first analyze normal-form games in which a single team plays against a single adversary. The different possible correlation capabilities of the team lead to different solution concepts. In particular, when teammates cannot communicate during the execution of the game, the Team-maxmin equilibrium is the solution concept prescribing optimal strategies for the team. We study the theoretical properties of this solution concept, analyzing classical inefficiency indexes, and introducing the Price of Uncorrelation as a way to characterize the value of intra-team communication. We devise algorithms to find and/or approximate the equilibrium, providing both a theoretical and experimental evaluation.
Then, we provide a study of extensive-form adversarial team games. Specifically, we introduce new correlation capabilities for teammates and study the corresponding solution concepts. Also, in this setting, a theoretical and computational characterization of the different equilibria is provided.