Source-linked AI summary
Characterizing Necessary Losers to Explain Tournaments Losers
Contet Clément, Umberto Grandi, Jérôme Mengin
TL;DR
The paper asks how to formally explain why a candidate was not selected when the rest of a tournament is incompletely specified. It defines destructive minimal supports and characterizes necessary losers or possible winners across six tournament solutions. The results provide polynomial-time computation for the weighted uncovered set and other rules, while Borda remains suspected to be NP-complete and user preferences among explanations remain open.
Problem
Existing election explanations motivate a more focused abductive account of why a losing candidate was not selected, rather than merely exposing decision information.
Method
The paper defines destructive minimal supports as inclusion-minimal partial tournaments where the candidate is a necessary loser in every completion, then characterizes this property for six tournament solutions.
Results
The paper gives characterizations and smallest-support bounds, with polynomial-time computation for the covered rules except that Borda’s computation is suspected to be NP-complete.
Takeaways & Limitations
Only a fraction of the tournament may be needed to explain a loss, with smallest-support sizes bounded by O(m^2) for top cycle and O(nm) for the remaining rules.
Takeaways & Limitations
The paper does not know whether computing a smallest destructive minimal support for Borda is in P and calls for empirical study of which explanations users prefer.
Abstract
from arXiv · showhide
We study the problem of formally explaining why a candidate was not selected by a given tournament rule, by identifying sub-tournaments in which the candidate loses independently of how the rest of the tournament is completed. We define destructive minimal supports as any minimal sub-tournaments satisfying this property, which in formal explainable artificial intelligence correspond to abductive explanations for the question "Why does the loser lose the tournament?". For six common tournament solutions (maximin, uncovered set and its weighted variant, top-cycle, Copeland, and Borda) we provide characterizations of when a candidate is either a necessary loser or a possible winner, we determine the size of the smallest destructive minimal supports, complemented by polynomial-time algorithms for their computation except for the case of the Borda rule which is suspected to be NP-complete.
1 Introduction
The paper situates tournament explanations within procedural fairness and XAI, arguing that publishing decision information alone may not provide understandable rationales. It introduces destructive minimal supports as abductive explanations for why a candidate was not selected.
- Procedural fairness can increase the legitimacy and acceptance of unfavorable collective decisions.Explanations for election outcomes have been reported to increase voter satisfaction and acceptance, especially after unfavorable outcomes.
- Simply publishing vote counts and the decision rule may be insufficient to foster trust in collective decisions.The paper distinguishes transparency through full information from transparency in rationale, which provides dedicated justification or explanation.
- Computational social choice has explored axiomatic reasoning, curated preference statistics, and abductive explanations for election outcomes.
- Destructive minimal supports answer “Why was this candidate not selected?” by using minimal tournament substructures that certify the candidate’s loss.The approach adapts the constructive/destructive distinction from control and bribery and represents pairwise comparisons with tournaments.
2 Preliminaries
The preliminaries define weighted, unweighted, complete, and partial tournaments and introduce the classical tournament solutions used in the paper. These solutions select candidates according to dominance structure or score-based criteria.
- A partial n-weighted tournament assigns pairwise weights whose two directions sum to at most n, while a complete one sums to n.An unweighted tournament is the special case of a 1-weighted tournament.
- An edge weight records the number of voters preferring one alternative to another in a weighted tournament.In an unweighted tournament, edge labels are omitted; zero-weight edges are not shown.
- Top cycle: The top cycle is the unique minimal dominant set, equivalently the candidates that can reach every other candidate by directed paths.
- Uncovered sets: The weighted uncovered set contains candidates not strictly covered by another candidate, with the unweighted case called the uncovered set.
- Score-based rules: Maximin and Copeland select candidates with maximal respective scores, while Borda selects candidates with maximal Borda score.Copeland is the restriction of Borda to unweighted tournaments.
3 (Smallest) Destructive Minimal Supports for Tournaments
Destructive minimal supports are inclusion-minimal partial sub-tournaments that guarantee a losing candidate remains excluded under every completion. The paper measures their compactness by the number of specified pairwise comparisons and illustrates that multiple supports may exist.
- The approach extracts a subset-minimal set of tournament features that ensures the scrutinized candidate loses independently of the remaining comparisons.
- A candidate is a necessary loser when it is excluded by the tournament solution in every complete extension of a partial tournament.This is equivalent to not being a possible winner.
- A destructive minimal support is a partial sub-tournament contained in the original tournament where the candidate is necessarily a loser and every proper sub-tournament loses that guarantee.
- Copeland example: In a Copeland example, a support combines defeats of the losing candidate with wins by a stronger candidate, guaranteeing a better score in every completion.Removing one of the losing candidate’s defeats breaks the guarantee, demonstrating subset minimality.
- Multiple destructive minimal supports can explain the same loss, so the paper focuses on smaller supports and measures size by specified pairwise comparisons.This preference follows a brief-explanation criterion and parallels the measurement used in related bribery work.
4 Characterizing Necessary Losers
The section characterizes necessary losers through structural conditions and deficient-incidence-graph matchings, yielding tree-based criteria for maximin and weighted uncovered set. It also gives a frontier characterization for top-cycle losers and recalls Schwartz’s Borda characterization.
- Top Cycle: A candidate is a necessary top-cycle loser exactly when a nonempty subset K excludes it and every edge from K to its complement is present.This is the required one-way frontier separating K from the rest of the partial tournament.
- Borda: For Borda, Schwartz’s flow-network characterization states that necessary-loser status is equivalent to the existence of a subset K excluding the candidate satisfying the theorem’s stated condition.The paper translates Schwartz’s 1960s characterization into its framework.
- Maximin and Weighted Uncovered Set: The l-deficient incidence graph reduces necessary-loser testing for maximin and weighted uncovered set to finding a perfect matching.The construction is analyzed using Hall’s marriage theorem and generalizes an approach for possible winners under maximin.
- Maximin and Weighted Uncovered Set: A deficient incidence graph lacks an X-perfect matching exactly when a tree excluding the scrutinized vertex satisfies the corresponding edge-absence condition.Hall’s theorem supplies the obstruction, while the proof identifies a tree whose vertices have too few eligible incident edges.
- Maximin and Weighted Uncovered Set: A candidate is a necessary maximin loser exactly when a tree of other candidates meets the threshold µ(c, c′) > n − max_c′′∈C µ(c′′, l) for every excluded tree edge.The threshold is determined by the strongest specified comparison against the candidate l.
- Maximin and Weighted Uncovered Set: A candidate is a necessary weighted-uncovered-set loser exactly when a tree satisfies µ(c, l) ≥ n/2 and µ(c, c′) + µ(c′, l) ≥ n, with at least one strict inequality.The condition applies to each tree vertex c and every other candidate c′ outside the relevant pair.
5 Smallest Destructive Minimal Supports
The section derives smallest destructive minimal supports for several tournament rules, giving exact size characterizations and polynomial-time computation results. Borda remains the main computational uncertainty, while support sizes are bounded by O(m^2) for top cycle and O(nm) for the remaining rules.
- Top Cycle: The smallest top-cycle support has size min_{t∈{α,β}} t(m−t), where α=|TC(G)| and β counts candidates reachable from the loser.The support can be computed in polynomial time; the construction separates the top cycle and the loser across strongly connected components.
- Borda: For Borda, the construction either places the loser strictly below average or uses a coalition with a stronger average Borda score, but finding a smallest support is suspected NP-complete.A coalition of size one always supplies an upper bound, while the computational status of the decision problem remains unresolved.
- Overall Bounds: Across the rules, support sizes are O(m^2) for top cycle and O(nm) for the remaining rules, so even unfavorable instances require only a fraction of the tournament.The weighted uncovered-set case is polynomial-time computable, unlike the associated smallest constructive-support problem, while Borda's complexity is unknown.
- Copeland: For Copeland, the smallest support has size m−1 when a directly defeating candidate has a higher Copeland score, and m otherwise.Except for one case, a coalition of size one is optimal; the result follows from the Borda characterization when n=1.
- Maximin: For maximin, the support size is (σMM(l)+1)(m−3)+n+1 when a stronger candidate sufficiently defeats l, and (σMM(l)+1)(m−2)+n+1 otherwise.The supports can be computed in polynomial time, and the construction preserves comparisons that bound l's maximin score while certifying a candidate with a higher score.
- Uncovered Set and Weighted Uncovered Set: For the uncovered set, every smallest destructive minimal support has size m−1 and can be computed in polynomial time.The weighted uncovered-set analysis uses a covering candidate or completion-dependent covering candidates to certify that the loser remains excluded.
6 Conclusion
The conclusion contrasts computational tractability across destructive supports and notes that minimizing comparisons can produce structurally complex explanations whose user preferences remain unknown.
- Polynomial-time algorithms compute smallest destructive supports for the weighted uncovered set, unlike the NP-complete constructive-support decision problem.
- Borda destructive-support computation remains unresolved, while smallest supports have size O(m^2) for top cycle and O(nm) for the other rules.
- Minimizing pairwise comparisons does not always produce the structurally simplest destructive support.
- Further empirical work is needed to determine which explanations users prefer.
A.1 Proofs for Section 4.1
For the top cycle, a candidate is a necessary loser exactly when a nonempty coalition of other candidates defeats every candidate outside that coalition in the partial tournament.
- A candidate l is a necessary top-cycle loser exactly when some nonempty K excluding l beats every candidate outside K.Formally, µ(c,c′)=1 for every c∈K and c′∈C\K.
- The proof assumes every nonempty K has an unresolved or unfavorable cross-pair and minimizes the set of candidates unreachable from l.Reversing one such cross-pair in a completion reduces that unreachable set, contradicting necessary-loser status.
- Conversely, the coalition condition prevents l from reaching K in every completion, excluding l from the top cycle.
A.2 Proofs for Section 4.2
The Borda proof reformulates necessary elimination through coalition score deficits, translating half-game-behind quantities and remaining comparisons into the weighted tournament representation.
- Schwartz’s characterization states that Borda elimination is equivalent to the existence of a subset K satisfying a coalition-based inequality.The original formulation uses l’s deficit against K, games remaining for l, and games remaining for K outside internal matches.
- The proof then substitutes these score and comparison identities into the original necessary-elimination condition to obtain the new formulation.
- The half-game-behind score H(c) assigns each comparison a baseline half-game and adjusts it by the observed pairwise outcome.This yields N(l,K) as the sum of H(c)−H(l) over c∈K.
- Remaining-game counts are expressed using the total number of comparisons minus already recorded pairwise weights.For coalitions, only comparisons with candidates outside K are counted.
- Within-coalition comparisons cancel in the aggregate, leaving only wins by coalition members over non-members to affect their average Borda score.
A.3 Proofs for Section 4.3
The weighted uncovered-set proof characterizes necessary losers using a tree of covering inequalities, with strictness required for strict weighted coverage and matching arguments establishing the completion conditions.
- The graph construction and completion arguments show how matched edges encode comparisons that preserve l’s non-coverage against each competing candidate.
- A necessary weighted-uncovered-set loser l exists exactly when a tree over candidates excluding l satisfies threshold inequalities against l and nonadjacent candidates.Each tree member must meet the n/2 threshold against l; non-tree-edge constraints compare pairwise weights through l.
- The relaxed weighted-coverage case is analyzed by reducing completion-independent coverage to a perfect-matching problem in a constructed bipartite graph.
- At least one tree inequality must be strict so that coverage is strict in every completion rather than merely weak.
- If all inequalities are equalities, a completion where l wins its remaining comparisons can avoid strict weighted coverage.
- When a strict inequality exists, repeatedly restricting the tree transfers strictness until a one-vertex tree strictly weighted covers l in every completion.
B Proofs for Section 5
The proofs characterize smallest destructive minimal supports for several tournament rules and establish polynomial-time computability. They derive rule-specific support sizes, including formulas for the top cycle, Borda, Copeland, maximin, weighted uncovered set, and uncovered set.
- Top cycle: For the top-cycle rule, the smallest support has size min_{t∈{α,β}} t(m−t), where α=|TC(G)| and β counts candidates reachable from the loser.The proof constructs supports from strongly connected-component boundaries and uses concavity to identify the minimum.
- Top cycle: Top-cycle supports can be computed in polynomial time, with the worst case occurring when candidates split into two equal parts.The construction fixes all comparisons across the selected component boundary and leaves other comparisons unspecified.
- Borda: For Borda, an SdMS can be computed in polynomial time and has size at most n(m−1)+1−max_{c∈A}µ(c,l), where A contains candidates scoring above l.Fixing the comparisons against a highest-weighted stronger candidate ensures that candidate remains above l in every completion.
- Copeland: For Copeland, the smallest support has size determined by whether the loser already has a fixed defeating candidate, yielding cases of m−1 or m comparisons.The construction is polynomial-time and always uses at most m comparisons.
- Maximin: For maximin, support sizes depend on score and comparison conditions, with formulas (σMM(l)+1)(m−3)+n+1 or (σMM(l)+1)(m−2)+n+1.The proof fixes one candidate’s minimum score above the loser and a strongest comparison against the loser.
- Uncovered sets: For the weighted uncovered set, polynomial-time supports satisfy rule-specific upper bounds, while for the unweighted uncovered set every smallest support has size m−1.The weighted construction can use one or two covering candidates; the unweighted result is exact.