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 \eps-optimal solution in time O(n^2 + \eps^{-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 \eps-Nash equilibrium with similar complexity but where implicit constants depend on various parameters of the game such as battlefield values.
翻译:我们描述一种有效的算法,用于计算具有不同价值的在n战场上的普通双玩者布洛托游戏的解决方案。 虽然这种解决方案的清晰构建仅限于特定、主要是对称或同质的设置, 但这一算法分辨率涵盖迄今为止最普遍的情况: 价值非对称游戏, 预算不对称。 提议的算法基于Sinkhorn矩阵和推力缩缩缩缩缩略图方面的最新理论进步。 以前尝试无法触及的一个重要案例是不同但对称的战场值, 且预算不对称。 在这种情况下, 布洛托游戏是恒定和最佳的解决方案, 而我们的算法样本在时间 O (n) 2 +\ \ eps ⁇ -4}, 独立于预算和战场价值。 在不对称值方面, 不需要最佳解决方案, 但是 Nash equilibria do, 我们的算法样本来自类似复杂但隐含恒定值取决于游戏的各种参数, 例如战场值 。