Loading article…
選挙科学では、投票方式は、選挙区ごとに選挙結果を集計し、すべての票を合計して結果を計算できる場合に、集計可能性基準を満たす。より厳密には、投票システムのコンパイルまたは集計の複雑さは、個々の選挙区の投票集計の難しさを測定するものであり、すべての票を要約するために必要な最小ビット数に等しい。 [ 1 ]投票方式は、ビット数が候補者数の多項式関数として増加する場合に、集計可能であると呼ばれる。
多くの場合、グループで決定を下す必要がありますが、すべての投票者を一箇所に集めることはできません。このような状況では、その場にいる投票者の票を集計し、残りの票が集まった際に勝者を決定できるようにする必要があります。投票ルールのコンパイル複雑度は、この集計に必要な最小ビット数です。
コンパイルの複雑さが低いことの重要な利点は、投票結果の検証が容易になることです。コンパイルの複雑さが低いと、各投票所の結果を個別に集計することができ、各政党の代表者が各投票所で投票用紙を数えることで簡単に検証できます。その後、どの有権者も、1000の投票所の結果を合計することで最終結果を検証できます。この検証可能性は、国民が結果を信頼し受け入れるために重要です。[ 1 ]各投票区から公開された情報は、独立した選挙監査人が統計的手法を用いて選挙不正の証拠を特定するために使用できます。
コンパイルの複雑さは、スタッケルベルグ投票ゲームにおける後方帰納法の勝者を計算する際にもアルゴリズム的に有用である。[ 2 ]
rを投票ルールとする。これは、 n 人の投票者の選好を表すn個の順位付けされた投票用紙のリストを入力として受け取り、結果を返す関数である。投票が既知であるk < n人の投票者がいる。コンパイル関数fは、 k個の順位付けされた投票用紙のリストを入力として受け取り、任意の数u := n - kの追加順位付けされた投票用紙が与えられたときに、投票用紙全体のセットに対する r の出力を正確に計算できるような出力を返す関数である。
ルール r のコンパイル複雑度は、最も効率的なコンパイル関数fの出力における最悪の場合のビット数です。[ 1 ]この数は通常、 n (投票者の数)、k (既知の投票数)、c (候補者の数)の関数です。ただし、通常は未知の投票数が非常に多い場合を対象とするため、ここでは簡略化のためにcのみに焦点を当てます。
順位付け投票ルールにおける可能な投票用紙の数はこれは複雑さの上限を示しています。しかし、ほとんどのルールはコンパイルの複雑さがはるかに小さいです。[ 1 ]
多数決やボルダのような順位投票システムでは、各候補者の合計得点（例えば、多数決で候補者が最初に登場した回数）を記録することで、任意の投票セットを要約できます。勝者は、各投票区の得点を合計することで見つけることができ、上限は同様の議論は、スコア投票や承認投票にも当てはまります。[ 1 ]
投票者プロファイルの加重多数決グラフは、ノードが候補者であり、投票者の過半数がyよりもxを好む場合に限りxからyへの有向エッジが存在する有向グラフです。このエッジの重みは、yよりもxを好む投票者の数です。多くのルールは多数決グラフのみに基づいており、そのようなルールの同値類の数は、可能な加重多数決グラフの数以下です。この数はT( k , c )で表され、 k人の投票者から得られるc個の頂点上の加重トーナメントの数です。したがって、コンパイルの複雑さは最大でlog(T( k , c ))です。log(T( k , c ))の上限はなぜなら、各候補者ペア x,y について、y よりも x を好む有権者の数を保持すれば十分であり、この数は 0 からkの間だからである。[ 1 ] [ 2 ]
2ラウンド投票（条件付き投票）のコンパイル複雑度はなお、これはボルダ投票のコンパイル複雑度よりも高いが、2ラウンド投票の通信複雑度はボルダ投票よりも低い。 [ 3 ]
単一譲渡投票のコンパイル複雑度は合計不可能な式となる。[ 1 ]
バックリン投票の場合、コンパイルの複雑さは[ 2 ]密接に関連する最高中央値投票ルールの場合、投票用紙の複雑さには以下が含まれます可能な評価は。
カリアとラングは、順位付け投票または承認投票のいずれかを用いた、複数の勝者による投票ルールのコンパイル複雑性を研究している。例えば、次のとおりである。
