『なぜこの候補は選ばれなかったのか』を数学的に説明する──説明可能AIの新概念『Destructive Minimal Supports』

複数の候補をペアごとに対戦させ、その勝敗の集計からランキングや勝者を決める「トーナメント」方式は、スポーツの順位決定だけでなく、LLM同士をペアで比較して優劣をつけるベンチマーク(Chatbot Arenaのような対戦型ランキング)にも使われる仕組みだ。この方式で「なぜある候補が選ばれなかったのか」を数学的に説明する枠組みを提案した論文が、2026年8月24日にarXivで公開された。第9回国際アルゴリズム意思決定理論会議(ADT 2026)に採択された論文の拡張版だ。

「落選した理由」を最小の証拠で示す

論文の目的はこう説明されている。

"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?'"

この性質を満たす最小の部分トーナメントを「destructive minimal supports(破壊的な最小根拠)」と定義する。これは形式的な説明可能AI(XAI)の文脈では、「なぜこの敗者はトーナメントに負けたのか」という問いに対するアブダクティブな説明(結果から最も妥当な理由を推論する形の説明)に相当する。

6つの代表的なトーナメント解を分析

論文は、maximin・uncovered set(その加重版含む)・top-cycle・Copeland・Bordaという6つの代表的なトーナメント解を対象に分析している。

"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."

これら6つのルールについて、ある候補が「必然的な敗者」あるいは「可能な勝者」であるための条件の特徴づけを提示し、最小の破壊的根拠のサイズを決定し、その計算のための多項式時間アルゴリズムを補完している。ただしBordaルールについては、NP完全である可能性が疑われており、多項式時間アルゴリズムの対象外となっている。

6つのルールのうち、maximin・Copeland・top-cycleのように比較的単純な集計方法では効率的に説明を計算できる一方、Bordaのように各候補の得点を細かく積み上げていく方式では、計算量そのものが跳ね上がる可能性がある、という対比が興味深い。これは、集計ルールの「複雑さ」が、単に勝者を決める計算コストだけでなく、「なぜ負けたのか」を説明するためのコストにも跳ね返ってくることを示唆している。説明可能性を重視するなら、集計方法の選び方自体が、後から説明を出せるかどうかを左右しうる、ということだ。

ランキングの集計ルールを意識する

この論文は数理的な色合いが強く、実装にすぐ転用できる話ではない。だが、LLM同士のペア比較によるランキング(Chatbot Arenaのような仕組み)を業務で参考にしている場合、「勝敗の集計方法(どのトーナメント解を使うか)によって、同じ対戦結果からでも異なる順位が導かれうる」という前提を、この論文は形式的な裏付けとともに示している。ベンチマークの順位を鵜呑みにする前に、それがどの集計ルールに基づいているかを意識する価値がある。ベンチマークの読み方全般についてはLLMベンチマークの読み方を参照してほしい。

Borda ruleのNP完全性は「疑われている」段階

本記事は、当サイトが論文の要旨を読んで書いている。この論文はAI・LLMを直接の主題とはしておらず、社会的選択理論・アルゴリズム意思決定理論の数理研究である点をまず明記しておく。ChatBot Arenaのような実際のLLM評価サービスが、この論文で扱う6つのトーナメント解のどれかを実際に採用しているかどうかは、本記事側で確認できておらず、あくまで概念的な関連づけにとどまる。Borda ruleの計算複雑性についても、論文自身が「NP完全であることが疑われている(suspected)」という未確定の表現を使っており、証明済みの事実ではない。本文PDFを読み込んでおらず、6つのトーナメント解それぞれの正確な数学的定義は本記事では踏み込んでいない。Zenn記事検索(2026年8月27日実施)では該当する日本語記事は見つからなかった。