An Algorithmic Solution to the Blotto Game Using Multimarginal Couplings

• 成果类型: Article
• 署名作者: Perchet, Vianney; Rigollet, Philippe; Le Gouic, Thibaut
• 署名单位: Institut Polytechnique de Paris; ENSAE Paris; Massachusetts Institute of Technology (MIT)
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2023.0049
• 发表日期: 2024
• 关键词: Blotto; equilibria computations; Optimal Transport

摘要

We describe an efficient algorithm to compute solutions for the general twoplayer Blotto game on n battlefields with heterogeneous values. Whereas explicit constructions for such solutions have been limited to specific, largely symmetric or homogeneous setups, this algorithmic resolution covers the most general situation to date: a valueasymmetric game with an asymmetric budget with sufficient symmetry and homogeneity. The proposed algorithm rests on recent theoretical advances regarding Sinkhorn iterations for matrix and tensor scaling. An important case that had been out of reach of previous attempts is that of heterogeneous but symmetric battlefield values with asymmetric budgets. In this case, the Blotto game is constant -sum, so optimal solutions exist, and our algorithm samples from an epsilon-optimal solution in time similar to O(n2 + battlefield values, up to some natural normalization. In the case of asymmetric values where optimal solutions need not exist but Nash equilibria do, our algorithm samples from an epsilon-Nash equilibrium with similar complexity but where implicit constants depend on various parameters of the game such as battlefield values.