トーナメントソリューション

トーナメント解は、有向完全グラフをその頂点の空でない部分集合に写像する関数である。トーナメント解は、トーナメントで互いに「競合」しているすべての選択肢の中から「最善の」選択肢を見つける方法と非公式に考えることができる。トーナメント解は、社会的選択理論^{[1] [2] [3] [4]に由来するが、}スポーツ競技、ゲーム理論[ ^5]多基準意思決定分析、生物学[ ^{6] [7]}ウェブページランキング^[8]および決闘盗賊問題^[9]でも検討されてきた。

社会的選択理論の文脈では、トーナメント解はフィッシュバーンのC1社会的選択関数^[10]と密接に関連しており、ある意味で誰が最も強い候補者であるかを示すことを目指しています。

トーナメント グラフは 、が頂点の集合 (選択肢と呼ばれる)であり、 が頂点上の連結された非対称の 2 項関係であるタプルです。社会選択理論では、2 項関係は通常、選択肢間のペアワイズ多数決比較を表します。 ${\displaystyle T}$${\displaystyle (A,\succ )}$${\displaystyle A}$${\displaystyle \succ }$

トーナメント解は、各トーナメントを選択肢の空でない部分集合（選択集合^[2]と呼ばれる）にマッピングし、同型トーナメントを区別しない 関数である。 ${\displaystyle f}$${\displaystyle T=(A,\succ )}$${\displaystyle f(T)}$${\displaystyle A}$

が2つのトーナメントと間のグラフ同型である場合、${\displaystyle h:A\rightarrow B}$${\displaystyle T=(A,\succ )}$${\displaystyle {\widetilde {T}}=(B,{\widetilde {\succ }})}$${\displaystyle a\in f(T)\Leftrightarrow h(a)\in f({\widetilde {T}})}$

トーナメントソリューションの一般的な例は次のとおりです。^{[1] [2]}

• コープランド集合
• トップサイクル
• スレーターセット^{[説明が必要]}
• 超党派セット
• ランダウ集合
• 銀行が設定
• 最小限のカバーセット
• トーナメント均衡セット^{[説明が必要]}