Computational Analyses of the Electoral College: Campaigning Is Hard But Approximately Manageable

Sina Dehghani, Hamed Saleh, Saeed Seddighin, Shang-Hua Teng

Abstract

This paper investigates the computational complexity of "Multifaceted Colonel Blotto Games," a game-theoretic framework for resource allocation in competitive environments such as the U.S. Electoral College. While finding an optimal strategy with diverse, heterogeneous resources is proven to be NP-hard, the authors demonstrate that the problem becomes "approximately manageable." By allowing for slight over-allocation of resources—a "fight harder" approach—near-optimal strategies can be efficiently computed.

Introduction

The classical Colonel Blotto game, introduced in 1921, serves as a fundamental model for strategic resource distribution. In this zero-sum game, two players allocate a fixed budget of troops across multiple battlegrounds. The player with the higher allocation in a specific battlefield wins that field, and the overall objective is to maximize the total weight of won battlefields. While a polynomial-time solution for the classical version with homogeneous resources was found in 2016, real-world scenarios—such as U.S. Presidential campaigns—involve multifaceted resources.

The Multifaceted Challenge

In a modern campaign, resources are not identical units. They include candidate time, television advertising spend, and ground-level staffing, each possessing varying degrees of effectiveness across different states. This paper addresses the gap between simplified models and the heterogeneous reality of strategic planning, asking whether optimal strategies remain computable when resources have varying strengths across battlegrounds.

The U.S. Electoral College serves as the primary motivating example for multifaceted resource allocation, where states act as battlegrounds with varying historical leanings and strategic weights.

Methods

The researchers utilized a combination of computational complexity theory and algorithmic design:

  1. Complexity Analysis: Through reductions from welfare maximization problems, the authors established the hardness of finding a "best response" in multifaceted games.
  2. Bi-criteria Approximation: To circumvent NP-hardness, they introduced a framework measuring approximation via resource elasticity ($\alpha$) and utility loss ($\beta$). This allows for finding strategies that are near-optimal if a player can slightly exceed their budget.
  3. Ellipsoid Method: Given the exponentially large strategy space, the game was represented as a massive Linear Program (LP). The Ellipsoid method, paired with an approximate separation oracle, was used to identify near-optimal mixed strategies.
  4. Dynamic Programming: For "Symmetric" battlegrounds—where states are identical but resources remain diverse—a specialized DP approach was developed using resource discretization to maintain polynomial runtime.

Key Insights

A critical shift occurs when moving from classical to multifaceted Blotto: the problem changes from "how many" resources to "which" specific resources are sent where. This transition is what drives the problem into the realm of NP-hardness. However, the authors show that "fighting harder"—using a small constant factor more resources—allows for the efficient discovery of strategies as effective as the theoretical optimum of the original budget.

Results

The study yields several significant findings:

  • Hardness: Finding the best response in a multifaceted Colonel Blotto game is NP-complete and hard to approximate within a factor of $O(\sqrt{\min(m, n)})$.
  • General Approximation: A polynomial-time algorithm can achieve an $(\alpha, \epsilon)$-maxmin strategy, providing near-optimal utility through constant-factor over-allocation.
  • Symmetry: In symmetric multifaceted games, a $(1+\epsilon, 0)$-maxmin strategy is achievable, yielding near-optimal results with minimal resource violation.
  • Complexity Bounds: Dropping constant-sum or linearity requirements renders the problem PPAD-hard, suggesting that general non-linear or multi-player versions are computationally intractable.

Conclusion and Future Work

While the "over-allocation" solution is theoretically robust, its practical implementation for campaign managers with rigid budgets remains a challenge. Furthermore, the assumption of linear resource strength ignores the reality of diminishing returns. Future research should explore non-linear utility functions and multi-player scenarios to better reflect the complexities of modern political and strategic competition.

Summary updated

Abstract

In the classical discrete Colonel Blotto game—introduced by Borel in 1921—two colonels simultaneously distribute their troops across multiple battlefields. The winner of each battlefield is determined by a winner-take-all rule, independently of other battlefields. In the original formulation, each colonel’s goal is to win as many battlefields as possible. The Blotto game and its extensions have been used in a wide range of applications from political campaign—exemplified by the U.S presidential election—to marketing campaign, from (innovative) technology competition to sports competition. Despite persistent efforts, efficient methods for finding the optimal strategies in Blotto games have been elusive for almost a century—due to exponential explosion in the organic solution space—until Ahmadinejad, Dehghani, Hajiaghayi, Lucier, Mahini, and Seddighin developed the first polynomial-time algorithm for this fundamental gametheoretical problem in 2016. However, that breakthrough polynomial-time solution has some structural limitation. It applies only to the case where troops are homogeneous with respect to battlegruounds, as in Borel’s original formulation: For each battleground, the only factor that matters to the winner’s payoff is how many troops as opposed to which sets of troops are opposing one another in that battleground. In this paper, we consider a more general setting of the two-player-multi-battleground game, in which multifaceted resources (troops) may have different contributions to different battlegrounds. In the case of U.S presidential campaign, for example, one may interpret this as different types of resources—human, financial, political—that teams can invest in each state. We provide a complexity-theoretical evidence that, in contrast to Borel’s homogeneous setting, finding optimal strategies in multifaceted Colonel Blotto games is intractable. We complement this complexity result with a polynomial-time algorithm that finds approximately optimal strategies with provable guarantees. We also study a further generalization when two competitors do not have zerosum/ constant-sum payoffs. We show that optimal strategies in these two-player-multi-battleground games are as hard to compute and approximate as Nash equilibria in general noncooperative games and economic equilibria in exchange markets.
BibTeX
@inproceedings{dehghani2021computational,
  author = {Sina Dehghani and Hamed Saleh and Saeed Seddighin and Shang-Hua Teng},
  title = {{Computational Analyses of the Electoral College: Campaigning Is Hard But Approximately Manageable}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16668},
}
Figure