Characterizing Necessary Losers to Explain Tournaments Losers

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.

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)

Artificial Intelligence (cs.AI)

arXiv:2608.23446 [cs.AI]

(or arXiv:2608.23446v1 [cs.AI] for this version)

https://doi.org/10.48550/arXiv.2608.23446 arXiv-issued DOI via DataCite (pending registration)