EUVIMEDEUVIMED entdecken
Crossref

Explaining Tournament Solutions with Minimal Supports

Clément Contet, Umberto Grandi, Jérôme Mengin

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (20) · 16770-16778

DOI: 10.1609/aaai.v40i20.38720 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Clément Contet und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Tournaments are widely used models to represent pairwise dominance between candidates, alternatives, or teams. We study the problem of providing certified explanations for why a candidate appears among the winners under various tournament rules. To this end, we identify minimal supports—minimal sub-tournaments in which the candidate is guaranteed to win regardless of how the rest of the tournament is completed (that is, the candidate is a necessary winner of the sub-tournament). This notion corresponds to an abductive explanation for the question,"Why does the winner win the tournament?"—a central concept in formal explainable AI. We focus on common tournament solutions: the top cycle, the uncovered set, the Copeland rule, the Borda rule, the maximin rule, and the weighted uncovered set. For each rule we determine the size of the smallest minimal supports, and we present polynomial-time algorithms to compute them for all solutions except for the weighted uncovered set, for which the problem is NP-complete. Finally, we show how minimal supports can serve to produce compact, certified, and intuitive explanations for tournament solutions.

Zitieren

APA

Contet, C., Grandi, U., & Mengin, J. (2026). Explaining Tournament Solutions with Minimal Supports. Proceedings of the AAAI Conference on Artificial Intelligence, 40(20), 16770-16778. https://doi.org/10.1609/aaai.v40i20.38720

Vancouver

Contet C, Grandi U, Mengin J. Explaining Tournament Solutions with Minimal Supports. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(20):16770-16778. doi:10.1609/aaai.v40i20.38720

BibTeX
@article{Contet2026,
  author = {Contet, Clément and Grandi, Umberto and Mengin, Jérôme},
  title = {Explaining Tournament Solutions with Minimal Supports},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {20},
  pages = {16770--16778},
  doi = {10.1609/aaai.v40i20.38720}
}
Kostenlos starten →