用最小子竞赛解释候选人必胜原因，提升决策透明度。
Explaining Tournament Solutions with Minimal Supports
- 定义最小支持：候选人在子竞赛中必然获胜的最小子结构
- 给出六种常见规则下最小支持的规模与计算方法
- 除加权无覆盖集外，其余均可多项式时间求解
锦标赛广泛用于表示候选人、选项或队伍间的两两优劣关系。本文研究如何为不同锦标赛规则下的胜者提供可认证的解释。为此，我们引入最小支持——即在该子锦标赛中，无论其余部分如何完成，候选人都能确保获胜的最小子锦标赛。这一概念对应于‘为何胜者能胜’的溯因解释，是形式化可解释AI的核心。我们针对主流锦标赛解法：拓扑循环、无覆盖集、Copeland规则、Borda规则、最大最小规则及加权无覆盖集，分别确定了最小支持的最小尺寸，并给出了除加权无覆盖集外所有规则的多项式时间算法。最后表明，最小支持可用于生成简洁、可认证且直观的解释。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。