Title: Computational Results for Extensive-Form Adversarial Team Games,
Abstract: We provide, to the best of our knowledge, the first computational study of
extensive-form adversarial team games. These games are sequential, zero-sum
games in which a team of players, sharing the same utility function, faces an
adversary. We define three different scenarios according to the communication
capabilities of the team. In the first, the teammates can communicate and
correlate their actions both before and during the play. In the second, they
can only communicate before the play. In the third, no communication is
possible at all. We define the most suitable solution concepts, and we study
the inefficiency caused by partial or null communication, showing that the
inefficiency can be arbitrarily large in the size of the game tree.
Furthermore, we study the computational complexity of the equilibrium-finding
problem in the three scenarios mentioned above, and we provide, for each of the
three scenarios, an exact algorithm. Finally, we empirically evaluate the
scalability of the algorithms in random games and the inefficiency caused by
partial or null communication.