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$.
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:
- 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.
- 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