Computational Results for Extensive-Form Adversarial Team Games
Computational Results for Extensive-Form Adversarial Team Games
复制标题
扩展形式对抗性团队博弈的计算结果
DOI：
10.1609/aaai.v32i1.11462
复制
发表时间：
2017
影响因子：
1.1
通讯作者：
N. Gatti
中科院分区：
文献类型：
--
作者：
A. Celli;N. Gatti
据我们所知，我们提供了第一个广泛形式的对抗性团队游戏的计算研究。这些游戏是连续的零和游戏，其中一组玩家共享相同的效用函数，面对对手。我们根据团队的沟通能力定义了三种不同的场景。在第一种情况下，队友可以在比赛前和比赛中沟通和联系他们的行动。在第二种情况下，他们只能在演出前交流。在第三种情况下，根本不可能进行通信。我们定义了最合适的解决方案的概念，我们研究了部分或空通信所造成的低效率，表明低效率可以是任意大的游戏树的大小。此外，我们研究了上述三种情况下的均衡寻找问题的计算复杂性，并为每种情况提供了一个精确的算法。最后，我们经验性地评估了算法在随机游戏中的可扩展性以及部分或零通信所造成的效率低下。
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.