ケメニー・ヤング法

ケメニー・ヤング法は、順位付けされた投票と一対比較カウントを使用して、選挙で最も人気のある選択肢を特定する選挙システムです。コンドルセ方式は、コンドルセ勝者がいる場合、常に最も人気のある選択肢としてランク付けされるため、 コンドルセ方式と呼ばれます。

この方法では、各シーケンスにスコアが割り当てられます。各シーケンスでは、どの選択肢が最も人気があるか、どの選択肢が 2 番目に人気があるか、どの選択肢が 3 番目に人気があるか、そしてどの選択肢が最も人気がないかが考慮されます。スコアが最も高いシーケンスが優勝シーケンスとなり、優勝シーケンスの最初の選択肢が最も人気のある選択肢となります (以下で説明するように、どのランキング レベルでも同点が発生する可能性があります)。

Kemeny–Young 法は、 Kemeny ルール、VoteFair 人気ランキング、最尤法、中央値関係とも呼ばれます。

ケメニー・ヤング法では、投票者が自分の好みの順番に従って選択肢をランク付けする優先順位投票を使用します。投票者は、同じ優先順位で複数の選択肢をランク付けできます。 ^[要出典]ランク付けされていない選択肢は通常、最も好まれない選択肢として解釈されます。

Kemeny-Young の計算は通常 2 つのステップで行われます。最初のステップでは、ペアワイズ投票者の好みをカウントするマトリックスまたは表を作成します。2 番目のステップでは、すべての可能なランキングをテストし、各ランキングのスコアを計算して、スコアを比較します。各ランキング スコアは、そのランキングに適用されるペアワイズ カウントの合計に等しくなります。

最も高いスコアを持つランキングが、総合ランキングとして決定されます。(複数のランキングで同じ最大スコアを持つ場合、これらの可能性のあるランキングはすべて同点となり、通常、総合ランキングには 1 つ以上の同点が含まれます。)

順序付けを別の観点から見ると、それは有権者のリストまでの ケンドール タウ距離(バブル ソート距離)の合計を最小化する順序付けです。

個人の優先順位が集計表にどのように変換されるかを示すために、次の例を検討する価値があります。 1 人の有権者が 4 人の候補者 (エリオット、メレディス、ローランド、セルデン) から選択し、次の優先順位を持っているとします。

これらの優先順位は、集計表で表すことができます。集計表は、すべてのペアワイズカウントを 3 つの列に並べたもので、投票の優先順位を数え (集計)、ランキングスコアを計算するのに役立ちます。中央の列は、投票者が同じ優先順位で複数の選択肢を示した場合を追跡します。上記の優先順位は、次の集計表で表すことができます。^{[引用が必要]}

ここで、複数の有権者が 4 人の候補者に投票したと仮定します。すべての投票が集計された後、同じタイプの集計表を使用して、すべての有権者のすべての好みをまとめることができます。以下は、100 人の有権者がいる場合の例です。

各行のカウントの合計は、投票総数と等しくなければなりません。

集計表が完成したら、選択肢の可能な順位を順に調べ、集計表の各行から適切な数字を加算して順位スコアを計算します。たとえば、可能な順位は次のようになります。

1. エリオット
2. ローランド
3. メレディス
4. セルデン

Elliot > Roland、Elliot > Meredith、Elliot > Selden、Roland > Meredith、Roland > Selden、および Meredith > Selden の優先順位を満たしています。表から取得したそれぞれのスコアは、

• エリオット > ローランド: 30
• エリオット > メレディス: 60
• エリオット > セルデン: 60
• ローランド > メレディス: 70
• ローランド > セルデン: 60
• メレディス > セルデン: 40

合計ランキングスコアは 30 + 60 + 60 + 70 + 60 + 40 = 320 になります。

すべての可能なランキングのスコアが計算された後、最も高いスコアを持つランキングが特定され、それが全体のランキングになります。この場合、全体のランキングは次のようになります。

1. ローランド
2. エリオット
3. セルデン
4. メレディス

ランキングスコアは370。

循環または同点がある場合、複数のランキングで同じ最大スコアが設定されることがあります。循環は、いくつかの選択肢が同点の場合に単一の総合ランキングを生成することで解決されます。^{[説明が必要]}

全体の順位が計算された後、ペアワイズ比較カウントは、以下に示すように、最も人気のあるもの（上部と左）から最も人気のないもの（下部と右）までの勝利の順序で選択肢が表示される要約マトリックスに並べることができます。このマトリックスレイアウトには、集計表に表示される同等の好みのペアワイズカウントは含まれていません。^[1]

この要約マトリックスでは、最大のランキング スコアは、マトリックスの右上の三角形の半分 (ここでは太字で表示され、背景は緑色) のカウントの合計に等しくなります。要約マトリックスで右上の三角形の半分の数字の合計がこれより高くなるランキングは他に考えられません (もし高くなるとしたら、それが全体のランキングになります)。

この要約マトリックスでは、マトリックスの左下の三角形の半分（ここでは赤い背景で表示）の数字の合計が最小値です。ジョン・ケメニーとペイトン・ヤングの学術論文^{[2] [3]}では、この最小値を見つけることについて言及しています。これはケメニースコアと呼ばれ、各ペアワイズオーダーに反対する（支持するのではなく）有権者の数に基づいています。

テネシー州が州都の場所を決める選挙を行っているとします。人口は 4 つの主要都市に集中しています。すべての有権者は州都ができるだけ近くにあることを望んでいます。選択肢は次のとおりです。

• メンフィスは最大の都市だが、他の都市からは遠い（投票者の42％）
• 州の中心部に近いナッシュビル（有権者の26%）
• チャタヌーガ、やや東（有権者の15％）
• ノックスビル、はるか北東（投票者の17％）

各地域の有権者の好みは次のとおりです。

このマトリックスは、対応するペアワイズ比較カウントをまとめたものです。

Kemeny–Young 法では、ペア比較のカウントを次の集計表に並べます。

メンフィスが第 1 位、ナッシュビルが第 2 位、チャタヌーガが第 3 位、ノックスビルが第 4 位となる場合のランキング スコアは (単位のない数値) 345 となり、これは次の注釈付き数値の合計です。

42%（投票者）はナッシュビルよりもメンフィスを好む

42%がチャタヌーガよりメンフィスを好む

42%がノックスビルよりメンフィスを好む

68%がチャタヌーガよりナッシュビルを好む

68%がノックスビルよりもナッシュビルを好む

83%がノックスビルよりもチャタヌーガを好む

この表にはすべてのランキングスコアがリストされています。

最大のランキングスコアは 393 で、このスコアは次のランキングに関連付けられているため、このランキングは全体のランキングでもあります。

単一の勝者が必要な場合は、最初の選択肢であるナッシュビルが選択されます。(この例では、ナッシュビルがコンドルセの勝者です。)

以下の要約マトリックスは、最も人気のあるもの (上部と左) から最も人気のないもの (下部と右) の順にペアワイズカウントを並べたものです。

この配置では、最大のランキング スコア (393) は、マトリックスの右上の三角形の半分 (緑の背景) にある太字のカウントの合計に等しくなります。

完全に同点にならないすべてのケースでは、Kemeny–Young 法によって最も人気のある選択肢、2 番目に人気のある選択肢などが特定されます。

どの選好レベルでも同点が発生する可能性があります。循環的な曖昧さが関係する一部のケースを除き、ケメニー・ヤング法では、ある選好を持つ投票者の数が反対の選好を持つ投票者の数と正確に一致する場合にのみ、選好レベルで同点が発生します。

ケメニー・ヤング法を含むすべてのコンドルセ法は、次の基準を満たしています。

非課税^{[壊れたアンカー]}

あらゆる優先順位の組み合わせで同点となる場合も含め、あらゆる全体的な優先順位の結果をもたらす可能性のある有権者の優先順位があります。

コンドルセ基準

すべてのペアワイズコンテストで勝利する選択肢がある場合は、その選択肢が勝利します。

多数決基準

投票者の大多数が選択肢 X を他のすべての選択肢よりも確実に好む場合、選択肢 X が最も人気があると判断されます。

非独裁

一人の有権者がすべてのケースで結果をコントロールすることはできません。

Kemeny-Young 法は次の基準も満たします。

無制限のドメイン

すべての選択肢の全体的な優先順位を識別します。この方法は、すべての可能な投票者の好みのセットに対してこれを実行し、同じ投票者の好みのセットに対しては常に同じ結果を生成します。

パレート効率

各有権者が表明したペアワイズな好みの結果、好まれる選択肢は好まれない選択肢よりも高い順位にランク付けされます。

単調性

投票者が選択肢の優先レベルを上げると、ランキング結果は変わらないか、または、推奨された選択肢の全体的な人気が高まります。

スミス基準

最も人気のある選択肢は、スミス集合のメンバーです。スミス集合は、その集合のすべてのメンバーがスミス集合に含まれないすべての選択肢よりも一対一で好まれるような、空でない選択肢の最小の集合です。

スミス優位の選択肢の独立性

選択肢 X がスミス集合に含まれていない場合、選択肢 X を追加または削除しても、選択肢 Y が最も人気があると特定される結果は変わりません。

強化

すべての投票が別々のレースに分割され、個々のレースの総合順位が同じである場合、すべての投票を結合したときに同じ順位になります。^[4]

反転対称性

すべての投票で優先順位が逆転した場合、以前最も人気があった選択肢が、最も人気のある選択肢のままではあってはならない。

すべてのコンドルセ法と同様に、ケメニー・ヤング法も以下の基準を満たしていません(つまり、説明した基準はケメニー・ヤング法には適用されません)。

無関係な選択肢の独立性

選択肢 X を追加または取り消しても、選択肢 Y が最も人気があると判断された結果は変わりません。

埋葬に対する無敵性

有権者は、不誠実に低い順位を選択肢に与えることによって、その選択肢を最も人気のある選択肢から外すことはできません。

妥協に対する無敵

有権者は、ある選択肢に不誠実に高い順位を与えることによって、その選択肢が最も人気が出るようにすることはできません。

参加

選択肢 X を選択肢 Y より上位にランク付けする投票を追加しても、選択肢 X ではなく選択肢 Y が最も人気になることはありません。

後で害はない

追加の選択肢（それ以外ではランク付けされていない選択肢）をランク付けしても、選択肢が最も人気があると識別されることは変わりません。

一貫性

すべての投票が別々のレースに分割され、選択肢 X がすべてのレースで最も人気があると特定された場合、すべての投票を結合すると選択肢 X が最も人気があることになります。

心からの好みの基準

個人にとって最適な投票戦略には、常に自分の好きな候補者に最大限の支持を与えることが含まれるべきです。

Kemeny–Young 法も次の基準を満たしていません(つまり、説明した基準は Kemeny–Young 法には適用されません)。

クローンの独立

類似の選択肢を 1 つだけ提供するのではなく、より多数の類似の選択肢を提供しても、これらの選択肢のうちの 1 つが最も人気があると特定される確率は変わりません。

押し倒されない無敵

投票者は、選択肢 Y に不誠実に高い順位を与えることによって、選択肢 X が最も人気になるようにすることはできません。

シュワルツ

最も人気があると判断された選択肢は、シュワルツ集合のメンバーです。

多項式ランタイム^[5]

この方法を使用して、選択肢の数の多項式である実行時間で勝者を決定するアルゴリズムが知られています。

ケメニー・ヤングランキングを候補者数の多項式時間で計算するアルゴリズムは知られておらず、投票者が4人（偶数）^{[6] [7]}または7人（奇数）^{[8]の場合でも、この問題は}NP困難であるため、存在する可能性は低い^。

整数計画法に基づく計算方法により、最大40人の候補者の投票順位を数秒で計算できる場合があることが報告されている^[9]。しかし、ランダムに生成された40人の候補者と5人の投票者によるケメニー選挙は、2006年には3GHzのPentiumコンピュータでは実用的な時間内に解くことができなかった^[9]。

Kemeny–Young 法は、トーナメント グラフで重み付けされたフィードバック アーク セットを見つけるという、より抽象的な問題の例として定式化できます。^[10]そのため、フィードバック アーク セットを計算するための多くの方法がこの問題に適用できます。これには、候補の Kemeny–Young ランキングを時間 で計算できるHeld–Karp アルゴリズムのバリエーションが含まれます。これは、すべてのランキングをテストする階乗時間よりも多くの候補に対して大幅に高速です。^{[11] [12] Kemeny–Young ランキングを計算するための}多項式時間近似スキームが存在し、^{[13]また、そのようなランキングを計算するための実行時間が O *} (2 ^{O( √ OPT )} )であるパラメーター化されたサブ指数時間アルゴリズムも存在します。^[10]${\displaystyle n}$${\displaystyle O(n2^{n})}$

ケメニー・ヤング法は1959年にジョン・ケメニーによって開発された。 ^[2]

1978年、ペイトン・ヤングとアーサー・レベンリックは、この方法を公理的に特徴づけ、一貫性といわゆる準コンドルセ基準を満たす唯一の中立的方法であることを示した。^[3]また、一貫性と単調性特性を使用して特徴づけることもできる。^[14]他の論文^{[15] [16] [ 17] [18]では、ヤングは、選好の集約に}認識論的アプローチを 採用した。つまり、選択肢に対して客観的に「正しい」が未知の選好順序があり、投票者はこの真の選好順序のノイズの多い信号を受け取ると仮定した（コンドルセの陪審定理を参照）。これらのノイズの多い信号に単純な確率モデルを使用して、ヤングは、ケメニー–ヤング法が真の選好順序の最大尤度推定量であることを示した。ヤングはさらに、コンドルセ自身もケメニー＝ヤング則とその最大尤度解釈を認識していたが、自分の考えを明確に表現できなかったと主張している。

ジョン・ケメニーとペイトン・ヤングの論文では、ケメニースコアは、各ペアワイズ選好を支持する有権者の数ではなく、反対する有権者の数を使用していますが、^{[2] [3]}最も小さいスコアは、同じ全体的な順位を示しています。

1991年以来、この方法はリチャード・フォーブスによって「VoteFair人気ランキング」という名前で推進されてきた。^[19]

次の表は、ケメニー・ヤング方式と他の単独勝者選挙方式を比較したものです。

• VoteFair.org — ケメニー・ヤングの結果を計算するウェブサイト。比較のために、多数決、コンドルセ、ボルダカウント、その他の投票方法による勝者も計算します。
• VoteFair_Ranking.cpp — Condorcet-Kemeny 計算を含む VoteFair ランキング結果を計算する C++ プログラム。MIT ライセンスの下で GitHub で入手可能。
• Kemeny-Young 法を含む複数の Condorcet 法をサポートするCondorcet クラスPHP ライブラリ。
• Kemeny-Young 選好集約のための C++ プログラム — Kemeny-Young の結果を高速に計算するためのコマンドライン プログラム。Windows および Linux 用のソース コードおよびコンパイル済みバイナリとして提供されています。Numerical Recipes を使用している点を除いてオープン ソースです。
• Kemeny-Young 選好集約の C プログラム — 他のライブラリに依存しない Davenport のアルゴリズムを実装します。オープン ソース、LGPL ライセンス。ライブラリへの Ruby バインディングもオープン ソース、LPGL ライセンスです。
• Python での Kemeny-Young 最適ランク集約 — 整数計画法として単純な定式化を使用し、lpsolve へのバインディングを使用して他の言語に適応できるチュートリアル。
• QuickVote — Kemeny–Young の結果を計算し、その概念の詳細な説明と例を提供する Web サイト。また、多数決、ボルダ カウント、即時決選投票、その他の投票方法に従って勝者を計算します。