Characterizing Necessary Losers to Explain Tournaments Solutions

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-tournament satisfying this property, which in formal explainable artificial intelligence corresponds 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 Borda and Copeland rules which we conjecture to also be polynomial.

This paper is the extended version of Contet, Grandi, Mengin. Characterizing Necessary Losers to Explain Tournaments Losers. In: Proceedings of the 9th International Conference on Algorithmic Decision Theory (ADT) (2026)