Efficient Equilibrium Computation in Colonel Blotto Games

Martin Bichler and Abheek Ghosh

Papers from arXiv.org

Abstract: Colonel Blotto is a fundamental resource-allocation game in which two players divide their budgets across battlefields, and the higher allocation on each battlefield wins its value. The problem of computing an equilibrium efficiently has remained unresolved for its classical continuous version with arbitrary budgets and with values that may vary across battlefields but are the same for both players. We give a fully polynomial-time approximation scheme that computes an $\varepsilon$-Nash equilibrium in time polynomial in the input length and $1/\varepsilon$, and nearly linear in the input length for fixed $\varepsilon$. For sufficiently balanced budgets and battlefield values, we also compute exact equilibria in linear time.

Date: 2026-11
References: Add references at CitEc
Citations:

Downloads: (external link)
https://arxiv.org/pdf/2611.05221 Latest version (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:arx:papers:2611.05221

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().