総和可能性基準

選挙科学では、投票方法を集計可能とするには、選挙結果を選挙区ごとに集計し、すべての投票を合計して結果を計算することが必要な必要があります。より正式には、投票システムの集計または合計の複雑さは、個々の選挙区の投票集計の難しさの尺度であり、すべての投票を合計するために必要な最小のビット数に等しくなります。 ^[1]ビット数が候補者の数の 多項式関数として増加する場合、投票方法は合計可能であると呼ばれます。

多くの場合、グループが決定を受け入れなければなりませんが、すべての投票を 1 か所に集めることはできません。このような状況では、現在の投票者の投票をまとめて、他の投票が到着したときに勝者を決定できるようにする必要があります。投票ルールのコンパイルの複雑さは、要約に必要な最小のビット数です。

集計の複雑さが低いことの主な利点は、投票結果の検証が容易になることです。集計の複雑さが低いため、各投票所の結果を個別にまとめることができます。これは、各政党の代表者が各投票所で投票用紙を数えることで簡単に検証できます。その後、どの有権者も1000の投票所の結果を合計することで最終結果を確認できます。この検証可能性は、国民が結果を信頼して受け入れるために重要です。^[1]各選挙区から公開された情報は、独立した選挙監査人が統計的手法を使用して選挙詐欺の証拠を特定するために使用できます。

コンパイル複雑度は、スタックベルグ投票ゲームにおける後方帰納的勝者を計算するアルゴリズムとしても有用である。^{[2] [説明が必要]}

r を投票ルールとします。これは、n 人の投票者の好みを表すn 個の ランク付けされた投票のリストを入力として受け取り、結果を返す関数です。投票がわかっているk < n人の投票者がいます。コンパイル関数は、k 個のランク付けされた投票のリストを入力として受け取り、追加のランク付けされた投票の任意の数u  := n - kが与えられた場合に、投票セット全体に対する r の出力を正確に計算できるような出力を返す関数 f です。

ルールrのコンパイル複雑度は、最も効率的なコンパイル関数fの出力における最悪の場合のビット数です。^{[1]この数値は通常、} n（投票者数）、k（既知の投票数）、c （候補者数）の関数です。ただし、通常は未知の投票数が非常に多いケースに注目するため、ここでは単純化のためにcのみに焦点を当てます。

任意の順位付け投票ルールで可能な投票数はであり、これは複雑さの上限を提供します。ただし、ほとんどのルールのコンパイル複雑さははるかに小さくなります。^[1]${\displaystyle \Theta (c!)}$

多数決やボルダのような位置投票システムでは、各候補者の合計得点（例えば、候補者が多数決で最初に登場した回数）を記録することで、任意の投票セットを要約することができます。その後、各選挙区の得点を加算して の境界を与えることで勝者を見つけることができます。同様の議論は、得点投票や承認投票にも当てはまります。^[1]${\displaystyle \Theta (c)}$

投票者プロフィールの加重多数決グラフは、ノードが候補者である有向グラフであり、投票者の過半数がxをyより好む場合に限り、 xからyへの有向辺が存在する。この辺の重みは、xをyより好む投票者の数である。多くのルールは多数決グラフのみに基づいている。そのようなルールの同値類の数は、最大で可能な加重多数決グラフの数である。この数は T( k , c ) で表され、これはk 人の投票者から得られるc頂点上の加重トーナメントの数である。したがって、コンパイルの複雑さは最大で log(T( k , c )) である。log(T( k , c ))の上限はである。これは、各候補者 x,y のペアについて、 x を y より好む投票者の数を保持すれば十分であり、この数は 0 からk の間であるためである。^{[1] [2]}${\displaystyle {\frac {c(c-1)}{2}}}$

2ラウンド投票（条件付き投票）のコンパイル複雑度は である。2ラウンド投票の通信複雑度はボルダ投票よりも低いが、コンパイル複雑度はボルダ投票よりも高いことに注意すること。[ ^3]${\displaystyle \Theta (c^{2})}$

単一の移譲式投票のコンパイル複雑度は であり、合計不可能である。^[1]${\displaystyle \Theta \left(2^{c}c\right)}$

STAR投票も行われている。^[4]${\displaystyle \Theta (c^{2})}$

バックリン投票の場合、コンパイルの複雑さは です。^[2]密接に関連する最高中央値投票ルールの場合、可能な評価を含む投票の複雑さは です。 ${\displaystyle \Theta (c^{2})}$${\displaystyle k}$${\displaystyle \Theta (ck)}$

Karia と Lang は、順位付け投票または承認投票のいずれかを使用した、複数の勝者投票ルールのコンパイルの複雑さを研究しています。例:

• 単一の譲渡不能投票の場合、複雑度は です。${\displaystyle \Theta (c)}$
• ボルダにとって、複雑さは にある。^[5]${\displaystyle \Theta (c\log {kc})}$

• 知識コンパイル: 入力の一部をオフラインでコンパイルし、オンライン入力が到着したときに出力を迅速に計算できるようにします。ここで、コンパイルの目的は、スペースを節約することではなく、時間を節約することです。
• 終了誘導の複雑さ: 投票ルール、既知の投票のセット、および新しい投票者のセットが与えられた場合、投票の結果は既知の投票からすでに決定されていますか? 明らかに、結果がすでに決定されている場合、その結果を保持するだけでよいため、コンパイルの複雑さは小さくなります。
• 可能性のある勝者と必要な勝者の計算: 投票ルール、不完全な投票のセット (候補者のセットの部分的な順序) が与えられた場合、選挙に勝つ可能性のある候補者は誰ですか。また、確実に勝つ候補者はいますか。明らかに、確実な勝者がいる場合、コンパイルの複雑さは非常に小さくなります。この確実な勝者の ID を保持する必要があるだけです。
• 通信の複雑さ: 投票ルールと投票者の集合が与えられた場合、選挙結果を計算するために投票者とセンターの間で転送しなければならない最小のビット数はいくらでしょうか? Conitzer と Sandholm は、いくつかの一般的な投票ルールの通信の複雑さを研究しています。^[3]コンパイルの複雑さは、1 ラウンドの通信の複雑さとして考えることができます。^[1]

• 投票システム
• 空間の複雑さ