找出比赛规则下被淘汰者的必败子赛程，解释其落选原因。
Characterizing Necessary Losers to Explain Tournaments Solutions
- 定义破坏性最小支撑：无论其他比赛如何进行，候选者必输的最小子赛程。
- 对六种常见规则（如最大最小、拓扑循环等）给出必败/可能胜者判定方法。
- 提供除博达和科佩兰德外的多项式算法，适合可解释AI与决策分析场景。
我们研究如何形式化解释为何某候选人被特定锦标赛规则淘汰，通过识别在任何完整赛事条件下均导致该候选人失败的子锦标赛。我们定义了破坏性最小支撑，即满足此性质的最小子锦标赛，对应可解释人工智能中的溯因解释：‘为何失败者会落选？’针对六种常见锦标赛解法（最大最小、未覆盖集及其加权版本、拓扑循环、科佩兰德、博达），我们给出了候选人是必要淘汰者或可能获胜者的刻画，并确定了最小破坏性最小支撑的规模，其余情况提供了多项式时间算法计算，仅博达与科佩兰德规则的复杂度尚待证明为多项式。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。