Search papers, labs, and topics across Lattice.
This paper investigates the formal explanation of why certain candidates are eliminated in tournament settings by identifying sub-tournaments where these candidates lose, independent of the overall tournament outcome. The authors introduce the concept of destructive minimal supports, which serve as minimal sub-tournaments that provide abductive explanations for a candidate's loss. Key findings include characterizations of necessary losers and possible winners across six common tournament solutions, along with polynomial-time algorithms for computing the smallest destructive minimal supports, except for the Borda rule, which remains NP-complete.
Identifying minimal sub-tournaments reveals why candidates lose, offering a structured approach to understanding tournament outcomes that could transform decision-making processes in competitive settings.
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.
