From Duels to Battlefields: Computing Equilibria of Blotto and Other Games

• 成果类型: Article
• 署名作者: Ahmadinejad, AmirMahdi; Dehghani, Sina; Hajiaghayi, MohammadTaghi; Loder, Brendan; Mahini, Hamid; Seddighin, Saeed
• 署名单位: Stanford University; University System of Maryland; University of Maryland College Park; Microsoft; University of Tehran
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2018.0971
• 发表日期: 2019
• 页码: 1304-1325
• 关键词: colonel-blotto; complexity; borel; play

摘要

In the well-studied Colonel Blotto game, players must divide a pool of troops among a set of battlefields with the goal of winning a majority. Despite the importance of this game, only a few solutions for special variants of the problem are known. We provide a general technique for computing equilibria of the Colonel Blotto game. Our approach applies to variations of the Colonel Blotto game as well, including an infinite-strategy variant called the General Lotto game. We also apply our technique beyond Colonel Blotto games to create the first polynomial-time algorithms for computing equilibria for a variety of other zero-sum games. Our approach is to reformulate each zero-sum game into a bilinear form, then reduce equilibrium computation to linear optimization over a game-specific polytope.