We describe an efficient algorithm to compute solutions for the general two-player Blotto game on n battlefields with heterogeneous values. While 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: value-asymmetric game with asymmetric budget. The proposed algorithm rests on recent theoretical advances regarding Sinkhorn iterations for matrix and tensor scaling. An important case which had been out of reach of previous attempts is that of heterogeneous but symmetric battlefield values with asymmetric budget. In this case, the Blotto game is constant-sum so optimal solutions exist, and our algorithm samples from an $\varepsilon$-optimal solution in time $\tilde{\mathcal{O}}(n^2 + \varepsilon^{-4})$, independently of budgets and battlefield values. In the case of asymmetric values where optimal solutions need not exist but Nash equilibria do, our algorithm samples from an $\varepsilon$-Nash equilibrium with similar complexity but where implicit constants depend on various parameters of the game such as battlefield values.
翻译:我们描述一种有效的算法,用于计算具有不同价值的战场上普通双玩者布洛托游戏的解决方案。 虽然这种解决方案的清晰构建仅限于特定、主要是对称或同质的设置, 但这一算法分辨率覆盖了迄今为止最普遍的情况: 价值非对称游戏, 预算不对称。 提议的算法依据的是Sinkhorn 矩阵和推力缩缩放方面的最新理论进步。 以前尝试无法触及的一个重要案例是不同但对称的战场值, 预算不对称。 在这种情况下, 布洛托游戏是恒定和最佳的解决方案, 而我们的算法样本来自 $\ varepsilon$- 最优化的解决方案, 在时间上 $\ valepde\ mathcal{O} (nä2 +\ varepslon ⁇ 4} 。 在不对称值的情况下, 我们的算法样本来自 $\ varepslon$- Nash 平衡, 具有类似的复杂性, 隐含的常数取决于各种游戏的参数, 如游戏的战场。