Characterizing Necessary Losers to Explain Tourname... | AI Research

This paper addresses the challenge of explaining why a specific candidate loses an election when tournament rules are used to determine the winner. By identifying "destructive minimal supports," the authors provide a formal method to justify why a candidate is a necessary loser—meaning they would lose regardless of how the remaining, undecided parts of the tournament are resolved.

Explaining Adverse Outcomes

The authors, Clément Contet, Umberto Grandi, and Jérôme Mengin, argue that while much of the research in computational social choice focuses on why a candidate wins, explaining why a candidate loses is equally important for procedural justice. Drawing on the theory that transparency in rationale increases trust in decision-making, the researchers apply abductive reasoning to identify the smallest possible sub-tournaments that force a candidate to lose. This approach allows authorities to provide clear, concise justifications for why a candidate was not selected.

Defining Destructive Minimal Supports

The core of the research is the "destructive minimal support" (dMS). A dMS is a partial sub-tournament that serves as an explanation for a loss; it is defined by two conditions: 1. The candidate is a necessary loser within that sub-tournament, meaning they lose in every possible completion of the tournament. 2. The sub-tournament is inclusion-minimal, meaning no smaller part of it can explain the loss.
The authors focus on finding the "smallest" such supports (SdMS) to ensure explanations are as brief as possible, aligning with communication principles that favor concise justifications.

Characterizing Tournament Solutions

The paper provides characterizations for when a candidate is a necessary loser across six common tournament solutions: the Top Cycle, Borda, Copeland, Maximin, Uncovered Set, and Weighted Uncovered Set.
For most of these rules, the researchers developed polynomial-time algorithms to compute the smallest destructive minimal supports. The exception is the Borda rule, where the problem of finding these supports is suspected to be NP-complete. The authors also established tight upper bounds on the size of these supports, providing a mathematical framework for how much information is required to justify a loss under each specific rule.

Practical Implications

This work bridges the gap between formal social choice theory and Explainable Artificial Intelligence (XAI). By providing a systematic way to generate "transparency in rationale," the authors offer a tool for developers of voting or decision-making systems to account for their outcomes. The research suggests that by identifying the specific pairwise comparisons that make a candidate a necessary loser, systems can provide stakeholders with understandable, evidence-based explanations for why their preferred candidate did not succeed.