Accountable Approval Sorting

Khaled Belahcène, Yann Chevaleyre, Christophe Labreuche, Nicolas Maudet, Vincent Mousseau, Wassila Ouerdane

Abstract

In committee-based decision-making, such as hiring or funding allocations, there is a fundamental tension between the privacy of individual voters and the need for public accountability. This paper proposes a formal framework for "Accountable Approval Sorting" using Noncompensatory Sorting (NCS). By mapping the inverse sorting problem to a Boolean Satisfiability (SAT) formulation, we demonstrate how to provide certificates of procedural regularity and logical justifications for specific outcomes without disclosing individual votes. Our approach simplifies complex power-set requirements into a pairwise characterization, enabling efficient auditing and justification schemes.

Introduction

Committees often sort candidates into binary categories like "accept" or "reject." While the final outcomes are public, the underlying votes are typically confidential to protect the integrity of the process and the privacy of the participants. This confidentiality, however, creates an "accountability gap": how can an external auditor or a rejected candidate be sure that the committee followed its own rules? This paper addresses this gap within the context of Noncompensatory Sorting (NCS), where a candidate is classified as "GOOD" if a sufficient coalition of voters approves them.

The Noncompensatory Sorting (NCS) Model

In the NCS model, a candidate $x$ is categorized as "GOOD" if the set of voters who approve $x$ constitutes a "sufficient coalition." This model is noncompensatory because a high number of approvals from a weak coalition cannot compensate for the lack of approval from a veto-holding minority. The challenge lies in the "Inverse NCS problem": given a set of outcomes, can we find a configuration of sufficient coalitions that explains these results?

Methodology: Pairwise Characterization and SAT Encoding

The core technical contribution is the simplification of the Inverse NCS problem. The authors prove that a set of decisions is consistent with the NCS model if and only if a specific pairwise condition is met.

Theorem 1 (Pairwise Characterization): A set of decisions is consistent with the NCS model if and only if, for every pair of candidates $(g, b)$ where $g$ is GOOD and $b$ is BAD, there exists at least one voter who approved $g$ but did not approve $b$.

Figure 1: A pairwise comparison matrix showing the number of voters who approve a 'GOOD' candidate (a, b, c) but not a 'BAD' candidate (d, e, f).

This characterization allows the problem to be encoded as a Boolean Satisfiability (SAT) problem. The SAT formulation is compact, with a complexity of $O(|N| \cdot |X|^2)$, where $|N|$ is the number of voters and $|X|$ is the number of candidates. This allows off-the-shelf SAT solvers to efficiently find "certificates of feasibility"—minimal sets of information that prove a decision's validity.

Argument Schemes for Accountability

The paper defines two primary argument schemes:

  1. Auditing (S1): This scheme proves that a set of decisions is possible under the rules. An auditor can use the SAT solver to find a valid model of sufficient coalitions that matches the observed outcomes.
  2. Justification (S2): This scheme proves that a specific decision was necessary. This is more complex, as it requires showing that any other outcome for that candidate would lead to a logical contradiction with previous "jurisprudence" or reference cases.

Key Insights and Results

  • Transparency vs. Accountability: The authors distinguish between full transparency (disclosing all votes) and accountability (providing a proof of consistency). Accountability can be achieved with minimal information disclosure.
  • Computational Feasibility: Despite the Inverse NCS problem being NP-hard in the general case, the specific SAT encoding provided is practical for real-world committee sizes.
  • The Complexity of "Why": Proving necessity is harder than proving possibility. In some "worst-case" scenarios, a complete justification might need to reference every voter in the committee, highlighting the inherent complexity of social choice logic.

Conclusion and Future Work

This framework provides a robust path toward "accountable by design" algorithms in social choice. Future research should expand the model to handle multi-threshold sorting (e.g., grading A through F) and incomplete voter preferences. Additionally, user studies are needed to evaluate the "cognitive burden" of these SAT-based justifications on human stakeholders.

Summary updated

Abstract

We consider decision situations in which a set of points of view (voters, criteria) are to sort a set of candidates to ordered classes (GOOD / BAD). Candidates are judged GOOD when approved by a sufficient set of points of view; this corresponds to noncompensatory sorting. To be accountable, such approval sorting should provide guarantees about the decision process and decisions concerning specific candidates. We formalize accountability using a feasibility problem expressed as a boolean satisfiability formulation. We illustrate different forms of accountability when a committee decides with approval sorting and study the information that should be disclosed by the committee.
BibTeX
@inproceedings{belahcene2018accountable,
  author = {Khaled Belahcène and Yann Chevaleyre and Christophe Labreuche and Nicolas Maudet and Vincent Mousseau and Wassila Ouerdane},
  title = {{Accountable Approval Sorting}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/10},
}
Figure