Hidden-Role Games: Equilibrium Concepts and Computation

本文研究隐藏角色游戏这一类别的游戏，其中玩家被私下分配到不同的队伍，并面临着识别和与队友合作的挑战。这个模型包括了许多流行的娱乐游戏，例如“狼人杀”、“抵抗组织”等，以及许多实际应用，例如分布式系统中需要节点共同完成目标的情况。文献中对这种情况的形式化数学基础很少或根本没有，以前甚至不清楚合适的解决方案概念（均衡的概念）应该是什么。合适的均衡概念应该考虑到玩家可用的通信渠道（例如，他们能够相互通信吗？他们能够私下通信吗？）。定义这些合适的概念是一个非常棘手的任务，会产生一些令人惊讶的后果。在本文中，我们提供了隐藏角色游戏的第一个严格的均衡定义，克服了其他不适用于隐藏角色游戏的解决方案概念的严重限制。然后，我们展示了在某些情况下，包括上述娱乐游戏，最优均衡可以高效地计算。在大多数其他情况下，我们展示了计算最优均衡至少是NP难的或coNP难的。最后，我们通过计算完整的5和6人Avalon实例的确切均衡来实验验证我们的方法，这些实例的信息集数量大于$10^{56}$。

本文研究隐藏角色游戏，探讨玩家如何识别和合作。这种模型包括众所周知的休闲游戏和分布式系统等实际应用场景。此前该领域缺乏正式的数学基础和合适的解决方案，本文提出了适用于隐藏角色游戏的均衡概念，并探讨了其计算难度。

本文提出了适用于隐藏角色游戏的均衡概念，该概念考虑了玩家之间的通信渠道，并在某些情况下可以高效计算出最优均衡。

本文的亮点包括提出了适用于隐藏角色游戏的均衡概念、在某些情况下可以高效计算出最优均衡、通过实验验证了方法的有效性。

最近在该领域的相关研究包括：《A Survey of Game Theory as Applied to Network Security》、《Game Theory for Security and Risk Management: From Theory to Practice》等。