论文标题
使用多核心耦合的算法解决算法解决方案
An algorithmic solution to the Blotto game using multi-marginal couplings
论文作者
论文摘要
我们描述了一种有效的算法来计算具有异质价值的N战场上的一般两人blotto游戏的解决方案。尽管此类解决方案的显式结构仅限于特定的，很大程度上对称或同质的设置，但这种算法分辨率涵盖了迄今为止最一般的情况：具有不对称预算的价值 - 对称游戏。提出的算法取决于有关矩阵和张量缩放的凹痕迭代的最新理论进步。以前的尝试不足的一个重要案例是具有不对称预算的异质但对称的战场价值观。在这种情况下，blotto游戏是恒定的，因此存在最佳的解决方案，并且我们的算法样本来自$ \ varepsilon $ -optimal解决方案，以$ \ tilde {\ tilde {\ Mathcal {o}}}（n^2 + \ varepsilon^{ - varepsilon^{ - 4}）$，独立于预算值。在不需要最佳解决方案但纳什均衡的情况下，我们的算法样本来自$ \ varepsilon $ nash平衡，具有相似的复杂性，但隐式常数取决于游戏的各种参数，例如战场值。
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.
