ドジソン法

ドジソン法は、ルイス・キャロルとして知られる数学者チャールズ・ドジソンの提案に基づく選挙制度である。この方法では、多数派が好む勝者を探し、そのような勝者が見つからない場合は、投票用紙の編集回数を最小限に抑えてコンドルセ勝者に変えることができる候補者を探す。この場合、投票用紙の編集により、有権者の投票用紙上の2人の隣り合う候補者が入れ替わる。^[1]

ドジソン法では、各投票者は、自分の好み（最良から最悪まで）に従って、すべての候補者の順序付きリストを提出します。勝者は、コンドルセ勝者になる前に、各投票で（すべての候補者に追加して）最小数のペアワイズスワップを実行する必要がある候補者として定義されます。

つまり、入力からケンドールタウ距離が最小となる投票プロファイルを見つけ、コンドルセ勝者を選出する必要があります。そうすると、コンドルセ勝者が勝者と宣言されます。候補者の勝者やドジソンスコア（その候補者を勝者にするために必要なスワップの数）を計算することは、3セットによる完全カバー（X3C）からの還元によりNP困難問題になります^[2]。^[3]

整数kと選挙が与えられた場合、候補者がk未満のスワップでコンドルセ勝者になれるかどうかを判断することはNP 完全です。