Strategic Abstention Based on Preference Extensions: Positive Results and Computer-Generated Impossibilities

Florian Brandl, Felix Brandt, Christian Geist, Johannes HofbauerIJCAI 2015

Introduction

In social choice theory, a fundamental desideratum for any voting rule is "participation-consistency": the principle that no voter should ever be incentivized to stay home to achieve a better outcome. When a rule fails this criterion, it is said to suffer from the no-show paradox. While this paradox has been extensively studied for single-winner rules, it becomes significantly more complex when considering "irresolute" social choice functions—rules that may output a set of winners (e.g., due to ties).

The primary challenge in evaluating set-valued outcomes is determining how a voter compares two sets of alternatives. This research explores two prominent preference extensions:

  1. Kelly’s Extension: A conservative model where the voter is assumed to have no knowledge of how ties are broken.
  2. Fishburn’s Extension: A more refined model assuming ties are broken by a fixed but unknown "chairman."

Methodology: SAT-Aided Social Choice

The authors employ a hybrid methodology that leverages modern computational power to tackle classic axiomatic questions. By reducing the existence of paradox-free voting rules to a finite propositional logic problem, they utilized SAT solvers (specifically PicoSAT) to explore the vast search space of majoritarian rules.

When the solver determined a set of axioms to be "unsatisfiable," the researchers extracted a Minimal Unsatisfiable Core (MUS). This technique allowed them to translate complex, computer-generated proofs into human-readable logical arguments, bridging the gap between automated reasoning and traditional mathematical proof.

The Computational Challenge

The search space for majoritarian voting rules grows exponentially with the number of alternatives ($|A|$). For instance, with 6 alternatives, there are approximately $6.8 \times 10^{38649}$ possible majoritarian rules. This scale makes manual analysis impossible and underscores the necessity of the SAT-solving approach used in this study to identify which rules, if any, satisfy the desired fairness and participation axioms.

Theoretical Findings and the No-Show Paradox

The research reveals a stark contrast between the two preference extensions. Fishburn’s extension, being a refinement of Kelly’s, makes it significantly harder for a rule to remain participation-consistent because voters have more specific reasons to prefer one set over another, creating more opportunities for strategic manipulation.

Figure 1: Preference profile $R$ and its corresponding tournament graphs, illustrating the impact of voter abstention on the collective preference relation.

Key Results:

  • Fishburn Impossibility: The authors prove that for 4 or more alternatives, no majoritarian and Pareto-optimal voting rule can satisfy Fishburn-participation. This impossibility holds for 5 alternatives even when preferences are strictly ordered.
  • Kelly Possibility: Conversely, the paper identifies a broad class of rules immune to the paradox under Kelly’s extension. Specifically, any social choice function satisfying set-monotonicity and Independence of Indifferent Voters (IIV) is Kelly-participation-consistent.
  • Rule Validation: Well-known rules such as the top cycle and the uncovered set were confirmed to be safe from strategic abstention under the Kelly model, even in the presence of weak preferences (ties in individual rankings).
  • New Discoveries: Using their SAT-based tool, the authors discovered a new, highly "discriminating" voting rule that satisfies Kelly-participation while picking fewer winners on average than established rules like the "bipartisan set."

Conclusion and Future Directions

This study highlights a fundamental tension in majoritarian systems between Pareto optimality and participation consistency under refined preference models. While Kelly-participation is achievable by many standard rules, Fishburn-participation is largely incompatible with majoritarianism.

Future research may look beyond majoritarian rules or explore "probabilistic" social choice, where outcomes are lotteries rather than sets, to see if participation is easier to satisfy in that domain. Additionally, scaling SAT-based methods to 7 or more alternatives remains a significant computational frontier in the field.

Summary updated

BibTeX
@inproceedings{brandl2015strategic,
  author = {Florian Brandl and Felix Brandt and Christian Geist and Johannes Hofbauer},
  title = {{Strategic Abstention Based on Preference Extensions: Positive Results and Computer-Generated Impossibilities}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure