Multi-Party Campaigning

Martin Koutecký, Nimrod Talmon

Introduction

In the field of Computational Social Choice (COMSOC), researchers have long studied how external agents might influence election outcomes through bribery (altering votes) or control (modifying the voter pool). However, traditional models typically rely on two simplifying assumptions: they involve a single manipulator and occur in a single, static round.

In reality, political campaigning is a dynamic, multi-agent process. Competing parties react to one another’s moves over multiple rounds, adjusting their strategies based on shifting voter sentiment and remaining budgets. This paper introduces a formal model for Multi-Party Campaigning, framing these complex interactions as a game-theoretic problem and providing a computationally efficient solution using the logic of Presburger Arithmetic.

The Multi-Party Campaigning Model

The authors move beyond the "lone briber" paradigm by modeling elections as a series of rounds $\ell$ involving multiple agents. Each agent has a specific budget and a goal (e.g., ensuring their candidate wins or a rival loses). This creates a "back-and-forth" environment where agents must anticipate counter-moves.

To manage the complexity of large electorates, the paper utilizes Society Vectors. Instead of tracking individual voters, the model groups voters into "types" based on their preference orders. This ensures that the number of variables in the system depends on the number of possible candidate rankings rather than the total population size ($n$), allowing the model to scale to elections with millions of voters.

Methodology: Presburger Arithmetic

The core of the paper’s technical contribution is the translation of these multi-round games into Presburger Arithmetic (PA)—a first-order logic of integers involving addition and comparison, but excluding multiplication.

Constructing the Formula

The authors construct a PA formula $\Phi$ that encapsulates the rules of the game. They use existential quantifiers ($\exists$) to represent the moves of the primary agent and universal quantifiers ($\forall$) to account for any possible adversarial counter-moves. This logical structure allows the model to find a strategy that is robust against the best possible response from opponents.

Algorithmic Efficiency

One of the primary challenges in using PA is that general quantifier elimination can be computationally expensive. However, the authors prove Theorem 1: minimizing a convex function over the satisfying assignments of a PA formula is Fixed-Parameter Tractable (FPT) when parameterized by the formula's length and its largest coefficient.

By ensuring the formula remains "short" (which happens when the number of candidates $m$ and rounds $\ell$ are small), the authors demonstrate that an optimal campaigning strategy can be found in time that is polynomial in the number of voters $n$. This is achieved through a combination of Cooper’s algorithm for quantifier elimination and techniques from convex integer optimization.

Key Insights and Modularity

Beyond the core complexity results, the paper offers several insights into the nature of strategic campaigning:

  • The Collusion Simplification: The authors show that in a worst-case adversarial setting, multiple opponents can be treated as a single "super-opponent" with a pooled budget. This simplification makes the logic more tractable without sacrificing the robustness of the resulting strategy.
  • Modular "Hooks": The PA framework is designed to be highly adaptable. Researchers can "plug in" different modules to account for specific real-world variables:
  • Voter Behavior: Modeling "loyal" voters who cannot be influenced twice, or "greedy" voters who simply follow the highest bidder.
  • Adaptive Budgeting: Modeling scenarios where a candidate’s budget increases if they perform well in intermediate polling.
  • Opinion Diffusion: Incorporating how voters influence their neighbors within a social network.
  • PA as an AI Tool: The paper highlights Presburger Arithmetic as a powerful, underutilized tool for AI problems involving nested "what-if" scenarios, particularly those that sit above NP in the polynomial hierarchy.

Results and Versatility

The authors demonstrate that their framework is not limited to simple plurality voting. It can handle complex rules such as the Borda count, multi-winner elections, and "far-sighted" agents who plan their moves several rounds in advance. The FPT result ensures that as long as the number of candidates and rounds remains relatively small, the optimal strategy remains computable even for very large electorates.

Limitations and Future Directions

While the theoretical bounds are promising, the authors note several areas for future research:

  1. Scaling Rounds: The current FPT result relies on the number of rounds $\ell$ being a fixed parameter. If the number of rounds grows significantly, the problem may become super-exponential.
  2. Budget Fluctuations: The authors conjecture that if budgets vary wildly between rounds, the problem might become NP-hard even for a small number of candidates.
  3. Practical Implementation: While the algorithm is "efficient" in a complexity-theoretic sense, the constant factors in PA solvers can be large. Future work is needed to develop practical heuristics that can solve these formulas in real-time simulations.

Conclusion

By bridging the gap between social choice theory and integer logic, this paper provides a robust mathematical foundation for understanding multi-party competition. The use of Presburger Arithmetic allows for a flexible, modular approach to modeling the complexities of modern political campaigns, offering a path toward more realistic simulations of democratic processes.

Summary updated

Abstract

We study a social choice setting of manipulation in elections and extend the usual model in two major ways: first, instead of considering a single manipulating agent, in our setting there are several, possibly competing ones; second, instead of evaluating an election after the first manipulative action, we allow several back-and-forth rounds to take place. We show that in certain situations, such as in elections with only a few candidates, optimal strategies for each of the manipulating agents can be computed efficiently. Our algorithmic results rely on formulating the problem of finding an optimal strategy as sentences of Presburger arithmetic that are short and only involve small coefficients, which we show is fixed-parameter tractable -- indeed, one of our contributions is a general result regarding fixed-parameter tractability of Presburger arithmetic that might be useful in other settings. Following our general theorem, we design quite general algorithms; in particular, we describe how to design efficient algorithms for various settings, including settings in which we model diffusion of opinions in a social network, complex budgeting schemes available to the manipulating agents, and various realistic restrictions on adversary actions.
BibTeX
@inproceedings{koutecky2021multi,
  author = {Martin Koutecký and Nimrod Talmon},
  title = {{Multi-Party Campaigning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16693},
}
Figure