# An algorithmic solution to the Blotto game using multi-marginal couplings

arXiv: https://arxiv.org/abs/2202.07318 · HTML: https://mlsanity.com/paper/2202.07318/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 72 references that are in the map.
- First posted on arXiv 15 Feb 2022.

## Builds on (most cited first, 8 of 8)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [On the Complexity of Approximating Multimarginal Optimal Transport](https://mlsanity.com/paper/1910.00152/) (2019)
- [Polynomial-time algorithms for Multimarginal Optimal Transport problems with structure](https://mlsanity.com/paper/2008.03006/) (2020)
- [Hardness results for Multimarginal Optimal Transport problems](https://mlsanity.com/paper/2012.05398/) (2020)
- [Optimal Transportation Theory with Repulsive Costs](https://mlsanity.com/paper/1506.04565/) (2015)
- [From Duels to Battefields: Computing Equilibria of Blotto and Other Games](https://mlsanity.com/paper/1603.00119/) (2016)
- [Defensive Resource Allocation in Social Networks](https://mlsanity.com/paper/1507.08462/) (2015)

## Abstract (arXiv)

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 tildeO(n2 + 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.