複数勝者投票

複数勝者投票、^[1] 全州選挙、または委員会投票^{[2] [3]は、一度に複数の候補者を選出する} 選挙制度を指します。このような方法は、議会や委員会の選挙に使用できます。

複数当選者投票が有用なシナリオは数多くある。それらは、委員会を選出する主な目的に基づいて、大きく3つのクラスに分類できる。^[4]

1. 優秀さ。ここでは、投票者は各候補者の質を個別に判断します。目標は、「客観的に」最良の候補者を見つけることです。アプリケーションの例としては、候補者リストの作成があります。つまり、候補者の従業員のリストから、最終評価段階 (面接など) に進む少数の最終候補者を選択します。ここでは、各候補者は他の候補者とは独立して評価されます。2 人の候補者が類似している場合、おそらく両方とも選出されるか、両方とも拒否されます。
2. 多様性。ここでは、選出される候補は可能な限り異なる必要があります。たとえば、候補が消防署などの施設を建設する可能性のある場所であるとします。ほとんどの市民は当然、市の中心部にある消防署を好みます。ただし、同じ場所に2 つの消防署を設置する必要はありません。選択を多様化し、2 番目の消防署をより離れた場所に配置する方がよいでしょう。「優秀」設定とは対照的に、2 つの候補が類似している場合は、おそらくそのうちの 1 つが選出されます。多様性が重要となる別のシナリオは、検索エンジンが表示する結果を選択する場合や、航空会社が飛行中に上映する映画を選択する場合です。
3. 比例性。ここでは、選出された候補者は、投票数によって測定される有権者の多様な意見を可能な限り代表する必要があります。これは議会選挙の共通の目標です。比例代表制を参照してください。

複数勝者投票の研究における主な課題は、単一勝者投票の概念を適切に適応させることです。これらは、承認投票と順位付け投票という投票タイプに基づいて分類できます。

いくつかの選挙制度では、個々の候補者間の競争によって複数の議員を選出します。このような制度は、移譲式多選投票と移譲式単選投票のいくつかのバリエーションです。

他のシステムでは、候補者は委員会（候補者リスト）にグループ化され、有権者は委員会（または候補者リスト）に投票します。

承認投票は、単独勝者選挙、場合によっては複数勝者選挙でよく使われる方法です。単独勝者選挙では、各有権者が承認する候補者に投票し、最も多くの票を獲得した候補者が勝利します。

複数当選者投票では、どの候補者を選出するかを決定する方法が多数あります。各投票者が候補者を順位付けする方法もあれば、X 票を投じる方法もあります。また、各投票者は 1 票または複数票を投じることもできます。

すでに 1895 年に、ティーレは重みベースのルール群を提案し、これをティーレの投票ルールと呼んでいます。^{[2] [5]}このルール群の各ルールは、 k 個の弱正の重みw ₁ ,..., w _kのシーケンスによって定義されます( kは委員会の規模)。各投票者は、投票者が承認したp 人の候補者を含む各委員会に、 w ₁ +...+ w _pに等しいスコアを割り当てます。合計スコアが最も高い委員会が選出されます。ティーレのルール群の一般的な投票ルールには次のものがあります。

• 複数譲渡可能投票(MNTV): 重みベクトルは (1,1,...,1) です。これは多数決承認投票とも呼ばれます。
• 承認-チェンバリン-クーラン (ACC): 重みベクトルは (1,0,...,0) です。つまり、各投票者は、委員会に自分が承認した候補者が含まれている場合にのみ、委員会に 1 ポイントを与えます。
• 比例承認投票（PAV）：重みベクトルは調和数列（1、1/2、1/3、...、1/ k）です。

^{ミニマックス承認投票[6]}とその一般化^{[7] 、}フラグメンの投票規則^[8]、均等割付法[9]など、他の原則に基づいた規則もあります。^{[10 ]}

勝者を決定する複雑さは様々である。MNTVの勝者は多項式時間で見つけられるが、Chamberlin-Courant ^[11]とPAVはどちらもNP困難である。

順位に基づく単独勝者投票では、順位によるスコアリング ルールが一般的です。各投票者は候補者を最良から最悪まで順位付けし、事前に指定された関数が各候補者の順位に基づいてスコアを割り当て、合計スコアが最も高い候補者が選出されます。

これらのシステムを使用して行われる複数勝者投票では、個々の候補者ではなく委員会にスコアを割り当てる必要があります。これを行うにはさまざまな方法があります。たとえば、^[1]

• 譲渡不可能な単一投票: 各投票者は、委員会に最も好ましい候補者がいる場合、委員会に 1 ポイントを与えます。言い換えると、各投票者は、複数の勝者を選出するコンテストで単一の候補者に投票し、最も多くの票を獲得したk 人の候補者が選出されます。これは、小選挙区制を一般化したものです。多項式時間で計算できます。

• 譲渡不能の多重投票（ブロック投票とも呼ばれる）：各有権者は、自分の上位k 個の空席ごとに委員会に 1 ポイントを与えます。言い換えると、各有権者はk 個の空席がある場合にk 人の候補者に投票し、得票数が最も多いk 人の候補者が選出されます。

• k-ボルダ: 各投票者は各委員会メンバーに自分のボルダカウントを与えます。各投票者は候補者をランク付けし、そのランク付けはまとめてスコア化されます。ボルダスコアの合計が最も高いk 人の候補者が選出されます。
• ボルダ・チェンバリン・クーラン（BCC）：各投票者は各委員会に、委員会内で最も支持する候補者のボルダカウントを提出する。^[12] BCCで勝者を計算するのはNP困難である。^[11]

単独勝者投票では、コンドルセ勝者とは、他の各候補者と直接対決する選挙で必ず勝利する候補者のことです。コンドルセ方式は、コンドルセ勝者が存在する場合は必ずそれを選択する方法です。コンドルセの基準を複数勝者投票に適応させる方法はいくつかあります。

• 最初の適応はピーター・フィッシュバーンによるものである: ^{[13] [14]}ある委員会がコンドルセ委員会であるとは、投票者の過半数によって他のどの委員会よりも好まれる場合である。フィッシュバーンは、投票者が委員会を承認セット内のメンバーの数でランク付けすると仮定した（つまり、二分法的な好みを持っている）。後の研究では、投票者が委員会をボルダ数などの他の基準でランク付けすると仮定した。委員会がこの基準を満たしているかどうかを確認することはcoNP完全であり、コンドルセ委員会が存在するかどうかを判断することはcoNP困難である。^[15]
• ^{もう一つの応用は、ゲールライン[16]とラトリフ[17]}によるものである。委員会は、その委員会内の各候補者が投票者の過半数によって委員会外の各候補者よりも好まれる場合、コンドルセ委員会である。複数勝者投票規則は、コンドルセ集合が存在する場合は常にそれを選択する場合、安定していると呼ばれることがある。 ^[18]安定した規則には次のようなものがある。^[19]
  • マルチウィナー・コープランド法: 各委員会は「外部敗北数」によって採点されます。つまり、c は委員会に属し、d は委員会に属しておらず、投票者の過半数がcをdより好むペア ( c、d ) の数です。
  • マルチウィナー・ミニマックス・コンドルセ法: 各委員会は「外部反対勢力の大きさ」、つまりすべてのペア ( c、d ) の中でc を好む投票者の数の最小値によって採点されます。
  • 他のコンドルセルールのマルチウィナー版。^[20]
• 3番目の適応はエルキンド、ラング、サフィディンによるものである^[21] 。コンドルセ勝利集合とは、集合に含まれない各要素dに対して、集合内のある要素cが多数決でdよりも好まれる集合である。この定義に基づいて、彼らはミニマックスコンドルセ法の異なるマルチウィナー変種を提示している。

優秀性とは、委員会に「最善の」候補者が含まれるべきであることを意味する。優秀性に基づく投票ルールは、しばしばスクリーニングルールと呼ばれる。^[18]これらは、最善の候補者を 1 人選ぶための最初のステップ、つまり候補者リストを作成する方法としてよく使用される。このようなルールが満たすべき基本的な特性は、委員会単調性(ハウス単調性とも呼ばれ、リソース単調性の変形) である。つまり、あるルールによってk 人の候補者が選出され、その後委員会のサイズがk +1 に増加してルールが再適用された場合でも、最初のk人の候補者は選出される必要がある。委員会単調性ルールのファミリーには次のようなものがある。

• 順次ルール: ^[18]単一勝者投票ルールを使用して、1人の候補者を選び、委員会に追加します。このプロセスをk回繰り返します。
• ベストkルール: ^[1]任意のスコアリングルールを使用して、各候補にスコアを割り当てます。スコアが最も高いk個の候補を選択します。

委員会の単調性という性質は、安定性という性質（コンドルセの基準の特定の適応）と両立しない。つまり、サイズ2のコンドルセ集合とサイズ3のコンドルセ集合を一意に認める単一の投票プロファイルが存在し、それらは互いに素である（サイズ2の集合はサイズ3の集合に含まれない）。^[18]

一方、委員会単調な位置スコアリングルールのファミリー（分離可能な位置スコアリングルール）が存在します。これらのルールも多項式時間で計算可能です（基礎となる単一勝者スコアリング関数が多項式時間で計算可能な場合）。^[1]たとえば、k-ボルダは分離可能ですが、複数の譲渡不可能な投票は分離できません。

多様性とは、委員会にはできるだけ多くの有権者から最も高い評価を受けた候補者が含まれるべきであることを意味します。正式には、多様性を重視したアプリケーションには次の原則が当てはまります。

• ナロートップ基準: ^[1]すべての有権者の最上位候補者を含むサイズkの委員会が存在する場合、その委員会が選出される必要がある。
• トップメンバーの単調性：^[22]委員会が選出され、ある有権者が自分の最も好ましい勝者の順位を上げた場合には、同じ委員会が選出されるはずである。

比例性とは、凝集性のある有権者グループ（つまり、同様の好みを持つ有権者グループ）が、その規模に比例した数の当選者によって代表されるべきであることを意味します。正式には、委員会の規模がkで、 n人の有権者がいて、L * n / k 人の有権者の一部が同じL人の候補者をトップにランク付け（または同じL人の候補者を承認）した場合、これらのL人の候補者が選出されることになります。この原則は、有権者が政党に投票する場合（政党名簿システム）には簡単に実装できますが、承認投票や順位付け投票にも適用できます。強固な連合に対する正当な代表と比例性を参照してください。

• 参加型予算編成は、候補者ごとに異なる費用がかかる複数当選者投票の一般化と見ることができる。