An Algorithmic Solution to the Blotto Game Using Multimarginal Couplings

Vianney Perchet (), Philippe Rigollet () and Thibaut Le Gouic ()
Additional contact information
Vianney Perchet: Centre de Recherche en Économie et Statistique (CREST), ENSAE, 91120 Palaiseau, France; Criteo AI Laboratory, Team Fairplay, 75009 Paris, France
Philippe Rigollet: Mathematics Department, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139l
Thibaut Le Gouic: Institut de Mathématiques de Marseille, Ecole Centrale de Marseille, 13453 Marseille, France

Operations Research, 2024, vol. 72, issue 5, 2061-2075

Abstract: We describe an efficient algorithm to compute solutions for the general two-player 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 value-asymmetric 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 ε -optimal solution in time O ˜ ( n 2 + ε − 4 ) , independent of budgets and 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 ε -Nash equilibrium with similar complexity but where implicit constants depend on various parameters of the game such as battlefield values. Funding: V. Perchet acknowledges support from the French National Research Agency (ANR) [Grant ANR-19-CE23-0026] as well as the support grant, and Investissements d’Avenir [Grant LabEx Ecodec/ANR-11-LABX-0047]. P. Rigollet is supported by the NSF [Grants IIS-1838071, DMS-2022448, and CCF-2106377]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2023.0049 .

Keywords: Machine Learning and Data Science; Blotto; equilibria computations; optimal transport (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2023.0049 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:72:y:2024:i:5:p:2061-2075

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().