• Recherche,

Explaining Tournament Solutions with Abductive Reasoning

le 15 avril 2025

12h45
Manufacture des Tabacs
Salle MH003

Clément Contet

Abstract : Tournaments are widely used models to represent pairwise notions of dominance between candidates, alternatives, or teams. Tournament solutions associate a winning alternative with a tournament, notable examples including the Copeland and the Borda rules on unweighted and weighted tournaments respectively. 
   While both rules have a clear intuitive appeal, from an explainable AI perspective the process of explaining why a given alternative is chosen as the tournament winner still lacks formal foundations.
   We study abductive explanations for tournament solutions defined as minimal sub-tournaments that support the winning alternative.
   We develop polynomial algorithms to compute smallest abductive explanations for the Copeland an the Borda rules, and we characterize and provide bounds on the size of such explanations, showing that our approach provides human-readable explanations supporting winning alternatives in tournaments.
Mis à jour le 3 avril 2025