Successful algorithms have been developed for computing Nash equilibrium in a variety of finite game classes. However, solving continuous games -- in which the pure strategy space is (potentially uncountably) infinite -- is far more challenging. Nonetheless, many real-world domains have continuous action spaces, e.g., where actions refer to an amount of time, money, or other resource that is naturally modeled as being real-valued as opposed to integral. We present a new algorithm for computing Nash equilibrium strategies in continuous games. In addition to two-player zero-sum games, our algorithm also applies to multiplayer games and games of imperfect information. We experiment with our algorithm on a continuous imperfect-information Blotto game, in which two players distribute resources over multiple battlefields. Blotto games have frequently been used to model national security scenarios and have also been applied to electoral competition and auction theory. Experiments show that our algorithm is able to quickly compute close approximations of Nash equilibrium strategies for this game.
翻译:在各种有限的游戏类别中,为计算纳什平衡制定了成功的算法。然而,解决连续游戏 -- -- 纯战略空间是(可能无法想象的)无限的 -- -- 则更具挑战性。尽管如此,许多现实世界域有持续的行动空间,例如,行动是指一定数量的时间、金钱或其他资源,这些行动自然被模拟为实际价值而不是整体价值。我们在连续游戏中为计算纳什平衡战略提供了一种新的算法。除了两个玩家零和游戏外,我们的算法还适用于多玩家游戏和不完善信息的游戏。我们用一种连续不完善的信息布洛托游戏来试验我们的算法,在这个游戏中,两个玩家在多个战场上分配资源。布洛托游戏经常被用来模拟国家安全情景,并被用于选举竞争和拍卖理论。实验显示,我们的算法能够快速计算出纳什平衡战略的近似值。