On the Complexity of Finding Justifications for Collective Decisions

Arthur Boixel, Ronald de HaanAAAI 2021 · DOI

Introduction

In the field of social choice theory, voting rules aggregate individual preferences into a single collective decision. However, for non-experts, the reasoning behind a specific outcome can often feel arbitrary or opaque. To enhance transparency, researchers have proposed the concept of a justification: a step-by-step explanation demonstrating that a specific outcome is the unique result satisfying a set of desirable "normative axioms" (e.g., "if everyone prefers A over B, B should not win").

While the theoretical framework for these justifications is established, their practical feasibility remained an open question. This paper provides a rigorous theoretical map of the computational hurdles involved in automatically explaining collective decisions.

Problem Definition

The authors analyze the computational complexity of two fundamental tasks:

  1. CHECK-JUST: Given a justification, is it correct?
  2. EXISTS-JUST: Given a voting scenario, does a valid justification exist?

To formalize these tasks, the authors utilize a many-sorted first-order logic language to encode agents, alternatives, profiles, and axioms. They distinguish between two versions of this language:

  • Quantifier-free fragment: A simpler version where every instance of a rule must be listed explicitly.
  • Full first-order language: A succinct version using quantifiers (e.g., "For all possible votes..."), allowing for more compact but potentially more complex expressions.

Methodology

The study determines the exact difficulty of these problems by reducing known "hard" problems from complexity theory—such as CRITICAL-SAT and SUCCINCT-3COL—to the justification tasks. This approach allows the authors to pinpoint where these problems sit within the polynomial and exponential hierarchies.

Key Results

The paper’s findings reveal a hierarchy of "hardness" that suggests significant computational barriers. A critical insight is the bottleneck of "nontriviality": a justification must not only show an outcome follows from rules but also prove that the rules themselves are not contradictory. This requirement significantly increases complexity.

Furthermore, succinctness breeds complexity. When axioms are described using quantifiers, the complexity jumps from the polynomial hierarchy to exponential levels. This is because a single succinct axiom can represent an exponential number of concrete voting instances.

Summary of complexity results for CHECK-JUST and EXISTS-JUST across different language fragments.

As shown in the table above, the tasks range from DP-complete to NEXP-hard. To put this in perspective, NEXP-hard problems are significantly more difficult than the famous NP-complete problems (like the Traveling Salesperson Problem), requiring non-deterministic exponential time. This suggests that finding justifications is likely intractable for anything but very small-scale voting scenarios.

Implications and Future Work

These "negative" results explain why previous researchers relied on "exponential-time" approaches like SAT solvers—they are likely the best we can fundamentally do. However, the authors suggest several paths toward tractability:

  • Restricting Axioms: Focusing on "small-mention" axioms that only refer to a few voting profiles at a time might bring complexity down to NP.
  • Structural Restrictions: Exploring "width measures" on voting profile graphs to identify easier election structures.
  • Practical Tools: The $\Sigma^P_2$ result for the quantifier-free version suggests that Answer Set Programming (ASP) could be an effective practical tool for finding justifications in restricted settings.

Summary updated

BibTeX
@inproceedings{boixel2021complexity,
  author = {Arthur Boixel and Ronald de Haan},
  title = {{On the Complexity of Finding Justifications for Collective Decisions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16656},
}
Figure