Research map / Learning theory and algorithms / Submodular and game algorithms
Equilibria of the Colonel Blotto Games with Costs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that Colonel Blotto games with assignment and obtainment costs are strategically equivalent to zero-sum sunk-cost Blotto games with one extra battlefield, yielding polynomial-time Nash equilibrium computation via an LP.
Problem
Classic Colonel Blotto games assume fixed, use-it-or-lose-it budgets and ignore costs of obtaining and assigning resources; the non-zero-sum game with costs lacks known equilibrium computation methods.
Approach
Add an artificial battlefield that absorbs unused resources and encodes obtainment costs, and shift opponent costs into payoffs to make the game strategically equivalent to a zero-sum sunk-cost Blotto game with n+1 battlefields, so the BDDHS LP applies.
Key results
- Every Colonel Blotto game with costs is strategically equivalent to a sunk-cost Colonel Blotto game with one extra battlefield, so Nash equilibria are computable in polynomial time via an LP with Theta(D^2 n) constraints and variables.
- Experiments with linear obtainment costs show equilibrium resources obtained increase as unit cost decreases, consistent with a hypothesis on the structure of equilibrium resource counts.
- Running times were reported for two cost settings on an Apple M3 Pro machine using Gurobi.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| decrease the unit resource cost | Colonel Blotto game with linear costs · equilibrium | expected resources obtained | Helped |
Surprising findings
- When the inverse unit cost is an integer and resources are sufficiently large, the equilibrium number of resources is not unique, yielding a range of equilibrium resource amounts.
Limitations
- Results are for discrete two-player games with specific cost structures; the hypothesis on equilibrium resources is only supported by preliminary experiments.
- Experiments are limited to linear obtainment costs and squared assignment costs with fixed parameters.
Experimental setup
Metrics: equilibrium resources obtained by player equilibrium expenditure LP running time
Baselines: Roberson and Kvasov continuous model
Builds on: BDDHS linear program (Behnezhad et al.) Moulin and Vial strategic equivalence lemma Roberson and Kvasov continuous Blotto with costs
Closest papers by meaning
- Colonel Blotto with Battlefield Games (AAAI 2026 · similarity 0.91)
- From Duels to Battlefields: Computing Equilibria of Blotto and Other Games (AAAI 2016 · similarity 0.90)
- Faster and Simpler Algorithm for Optimal Strategies of Blotto Game (AAAI 2017 · similarity 0.87)
- Computational Analyses of the Electoral College: Campaigning Is Hard But Approximately Manageable (AAAI 2021 · similarity 0.85)
- Cost Minimization for Equilibrium Transition (AAAI 2024 · similarity 0.83)
- The Complexity of Computing Robust Mediated Equilibria in Ordinal Games (AAAI 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.