Proving the Incompatibility of Efficiency and Strategyproofness via SMT Solving

Florian Brandl, Felix Brandt, Christian GeistIJCAI 2016

In the field of social choice theory, the search for a voting system that is both fair and immune to manipulation has been a central challenge for decades. While the Gibbard-Satterthwaite theorem long ago established the impossibility of these goals for deterministic systems (where a single winner is picked), the randomized domain—where outcomes are probability distributions or "lotteries"—remained a frontier of hope. This research, originally presented at IJCAI-16, utilizes automated reasoning to definitively close that door, proving a fundamental incompatibility between efficiency and strategyproofness in randomized voting systems.

The Core Conflict: Efficiency vs. Strategyproofness

To aggregate the preferences of multiple agents into a single outcome, researchers look for two "holy grail" properties:

  1. Efficiency (SD-Efficiency): The outcome should not be wasteful. If there is another outcome that every voter prefers (or at least no one likes less), the system should never choose the inferior option.
  2. Strategyproofness (SD-Strategyproofness): The system should be "honest." No agent should be able to achieve a better result for themselves by misrepresenting their true preferences.

For deterministic rules, these properties are impossible to achieve simultaneously without resorting to a dictatorship. To find a fairer middle ground, researchers turned to Social Decision Schemes (SDSs), which output a lottery over candidates. While randomization allows for anonymity (treating all voters equally), it was conjectured that the conflict between efficiency and strategyproofness would persist. This paper provides the formal proof that even with the flexibility of lotteries, these properties cannot coexist once a system reaches a certain size.

Methodology: The Shift to SMT Solving

The authors moved beyond traditional "pen-and-paper" proofs by employing computer-aided theorem proving. This approach involved several sophisticated steps:

  • Reduction to Finite Instances: The authors first proved a "reduction lemma," showing that if an impossibility exists for a small number of agents ($n=4$) and alternatives ($m=4$), it must also hold for any larger group. This turned an infinite problem into a finite, searchable one.
  • SMT Encoding: Unlike previous work that used SAT solvers (which deal with simple True/False logic), the authors used Satisfiability Modulo Theories (SMT). Specifically, they utilized the theory of linear real arithmetic. This was a critical innovation because lotteries involve continuous values (probabilities between 0 and 1) that standard SAT solvers cannot easily process.
  • Axiom Translation: The abstract concepts of efficiency and strategyproofness were translated into a massive system of linear inequalities.
  • Symmetry Breaking: To make the problem computationally feasible, the authors used "canonical representations" of preference profiles. This effectively told the computer to ignore redundant cases where voters or candidates are simply swapped, significantly narrowing the search space.
  • Verification: Once the SMT solver (such as z3 or MathSAT) found the constraints to be "unsatisfiable"—meaning no such function can mathematically exist—the authors extracted a Minimal Unsatisfiable Set (MUS). This core of 94 constraints represents the heart of the contradiction. Finally, they used the Isabelle/HOL formal proof assistant to verify that these constraints followed logically from the original axioms.

Key Insights and Results

The primary contribution of this work is the formalization of Theorem 1: If there are at least 4 alternatives and 4 agents, there is no anonymous and neutral Social Decision Scheme that satisfies both SD-efficiency and SD-strategyproofness.

This result is significant for several reasons:

  • Settling a Conjecture: It formally proves a mathematical conjecture made by Aziz et al. in 2013.
  • Identifying the Boundary: The paper identifies that the impossibility kicks in exactly at the "4x4" mark. For smaller cases (e.g., 3 alternatives), fair and efficient schemes like Random Serial Dictatorship do exist.
  • The Power of SMT: This was the first major application of SMT solvers in computational social choice, proving that SMT is a superior tool for randomized settings compared to standard logic solvers.

Limitations and Future Outlook

While the proof is a landmark achievement, it does have limitations. The current proof relies on a technical version of "neutrality" (treating all candidates equally) to keep the search space manageable. While the authors suspect the impossibility holds even without this requirement, proving it remains a task for future iterations.

Furthermore, there is the challenge of interpretability. While the proof is verified to be correct, a "Minimal Unsatisfiable Set" of 94 constraints is difficult for a human to intuitively grasp. Translating these computer-generated proofs into human-readable narratives remains an open area of research. Nonetheless, this work demonstrates a powerful new workflow for social choice: using computers to find the "needle in the haystack" of logical contradictions and using formal tools to ensure those findings are airtight.

Summary updated

BibTeX
@inproceedings{brandl2016proving,
  author = {Florian Brandl and Felix Brandt and Christian Geist},
  title = {{Proving the Incompatibility of Efficiency and Strategyproofness via SMT Solving}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure