論文の概要: Explaining Tournament Solutions with Minimal Supports
- arxiv url: http://arxiv.org/abs/2509.09312v1
- Date: Thu, 11 Sep 2025 09:55:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-12 16:52:24.327899
- Title: Explaining Tournament Solutions with Minimal Supports
- Title（参考訳）: ミニマルサポートによるトーナメントソリューションの解説
- Authors: Clément Contet, Umberto Grandi, Jérôme Mengin,
- Abstract要約: 各種大会ルールにおいて,候補者が勝者に現れる理由について,認定された説明を提供するという課題について検討する。
我々は、大会の残りがどうやって終わるかに関わらず、候補者が勝つことが保証される、最小限のサポートと最小限のサブターナメントを識別する。
- 参考スコア（独自算出の注目度）: 5.646709810999712
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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 but 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.
- Abstract（参考訳）: トーナメントは、候補、代替案、チーム間のペアワイズ優位を表すモデルとして広く使用されている。
各種大会ルールにおいて,候補者が勝者に現れる理由について,認定された説明を提供するという課題について検討する。
この目的のために、トーナメントの残りがどれだけ完了したかに関わらず、候補者が勝つことが保証される最小のサブトーナメント(つまり、候補者はサブトーナメントの必要な勝者である)を識別する。
この概念は、公式な説明可能なAIにおける中心的な概念である「なぜ勝者がトーナメントに勝つのか」という質問に対する誘惑的な説明に対応する。
我々は,トップサイクル,未発見セット,コープランドルール,ボルダルール,最大値ルール,加重未発見セットなど,一般的なトーナメントソリューションに注目している。
各ルールに対して最小の最小サポートのサイズを決定し、問題をNP完全とする重み付き未発見集合以外の全てに対して多項式時間アルゴリズムで計算する。
最後に、最小限のサポートがいかにコンパクトで、認定され、直感的な説明を生み出すかを示す。
関連論文リスト
- Abductive and Contrastive Explanations for Scoring Rules in Voting [5.928530455750507]
我々は、ルールの採点のための帰納的および対照的な説明を計算するためのアルゴリズムを設計する。
ボルダの法則では、最小の導出的説明の大きさの低い境界を求める。
選好プロファイルの特性と最小誘引的説明の大きさの相関関係をシミュレーションにより同定する。
論文 参考訳（メタデータ） (2024-08-23T09:12:58Z) - On Efficient Computation of DiRe Committees [4.8951183832371]
ほぼ2つの大きさの任意のグループに分けられる候補者からなる委員会選挙を考えてみましょう。
多様性制約は、各グループから少なくとも1つの候補を選択することを規定する。
表現制約は、承認された候補の非無効なセットを持つ各集団から少なくとも1人の候補者を選択することを規定している。
論文 参考訳（メタデータ） (2024-02-29T17:13:30Z) - Towards Generative Abstract Reasoning: Completing Raven's Progressive Matrix via Rule Abstraction and Selection [52.107043437362556]
Raven's Progressive Matrix (RPM) は、マシンインテリジェンスにおける抽象的な視覚的推論を探索するために広く使われている。
RPMテストの参加者は、属性変更ルールを推論し、組み合わせることで、強力な推論能力を示すことができる。
本稿では,ルール AbstractIon と Selection を用いて,回答生成問題に対する潜時変数モデルを提案する。
論文 参考訳（メタデータ） (2024-01-18T13:28:44Z) - ApproxED: Approximate exploitability descent via learned best responses [61.17702187957206]
連続的なアクションセットを持つゲームの近似的ナッシュ均衡を求める問題について検討する。
本稿では,戦略プロファイルに対するエクスプロイラビリティの近似を最小化する2つの新しい手法を提案する。
論文 参考訳（メタデータ） (2023-01-20T23:55:30Z) - A Theory of Tournament Representations [4.969254618158096]
我々はパラメトリックトーナメント表現を理解するための新しい理論を開発した。
私たちの最初の貢献は、$d$次元表現から生じるトーナメントのクラスを構造的に特徴づけることです。
さらに2ドルのトーナメントは、関連する禁止されたフリップクラスがわずか2ドルのトーナメントを含むことを示すことで、完全にランク付けします。
論文 参考訳（メタデータ） (2021-10-06T09:08:00Z) - Surface Form Competition: Why the Highest Probability Answer Isn't
Always Right [70.71122438366142]
Domain Conditional Pointwise Mutual Informationは、サーフェスフォームの競争を補償します。
キャリブレーション機能とアンキャリブレーション機能の両方でゼロショット性能の一貫したゲインを実現します。
論文 参考訳（メタデータ） (2021-04-16T18:57:19Z) - Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit
Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。
我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。
有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文 参考訳（メタデータ） (2021-01-21T10:35:09Z) - MS-Ranker: Accumulating Evidence from Potentially Correct Candidates for
Answer Selection [59.95429407899612]
そこで我々は,MS-Ranker という,新しい強化学習に基づくマルチステップランキングモデルを提案する。
我々は、候補の潜在的な正しさを明示的に考慮し、ゲーティング機構で証拠を更新する。
我々のモデルは、外部リソースに依存しない既存の手法を著しく上回ります。
論文 参考訳（メタデータ） (2020-10-10T10:36:58Z) - Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies
in Extensive-Form Zero-Sum Games [123.76716667704625]
我々は,不完全情報ゼロサム拡張形式ゲームにおいて,対戦相手と対決する2人の選手のチームにとって最適な戦略を見つけることの課題に焦点をあてる。
この設定では、チームができる最善のことは、ゲーム開始時の関節(つまり相関した)確率分布から潜在的にランダム化された戦略(プレイヤー1人)のプロファイルをサンプリングすることである。
各プロファイルにランダム化されるのはチームメンバーの1人だけであるプロファイルのみを用いることで、そのような最適な分布を計算するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-21T17:51:57Z) - Query Complexity of Tournament Solutions [12.192470787877594]
我々は、コペランド集合、スレーター集合、マルコフ集合、バイパルチザン集合、未発見集合、バンクス集合、および最上位サイクルを見つけるアルゴリズムが、最悪の場合、$Omega(n2)$ edgesを問う必要があることを示す。
肯定的な面では、入力トーナメントの上位サイクルのサイズが最大で1kドルであれば、上記のすべてのトーナメントソリューションが見つかることを証明して、クエリの複雑さを低く抑えることができる。
論文 参考訳（メタデータ） (2016-11-18T18:19:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。