Characterizing Necessary Losers to Explain Tournaments Losers
2026-08-24 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors explore why a specific player doesn't win in a tournament by finding small parts of the competition where that player always loses, no matter what happens elsewhere. They call these parts 'destructive minimal supports,' which serve as clear explanations for a player's loss. The study focuses on six common ways to decide winners in tournaments, figuring out when a player is definitely out or still has a chance. The authors also find the smallest such explanations and provide efficient methods to find them for most cases, except for one method that seems much harder to solve.
tournament ruledestructive minimal supportabductive explanationmaximinuncovered settop-cycleCopelandBorda ruleNP-completepolynomial-time algorithm
Authors
Contet Clément, Umberto Grandi, Jérôme Mengin
Abstract
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.