ドジソンの方法

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

ドジソンの方法は、ルイス・キャロルとしてよく知られている、著者、数学者、論理学者のチャールズ・ドジソンによって提案された選挙制度です。この方法は、コンドルセの勝者が見つかるまで候補を交換することによって、コンドルセの方法を拡張することです。勝者は、最小数のスワップを必要とする候補者です。Dodgsonは、1876年の著作「2つ以上の問題に投票する方法」でこの投票スキームを提案しました。整数kと選挙が与えられた場合、候補者がk回未満のスワップ でコンドルセ勝者になることができるかどうかを判断することはNP完全です。

説明

Dodgsonの方法では、各有権者は自分の好みに応じて(最良から最悪まで)すべての候補者の順序付きリストを提出します。勝者は、コンドルセの勝者になる前に、各投票で(すべての候補に追加された)最小数のペアワイズスワップを実行する必要がある候補と定義されます特に、すでにコンドルセの勝者がいる場合、彼らは選挙に勝ちます。

要するに、コンドルセの勝者がいるように、入力からケンドールタウの距離が最小の投票プロファイルを見つける必要があります。次に、コンドルセットの勝者が勝利者として宣言されます。候補者の勝者またはDodgsonスコア(その候補者を勝者にするために必要なスワップの数)を計算することは、正確なカバーから3セット(X3C)削減することにより、 NP困難な問題です[1] 。[2]

参考文献

  1. ^ バルトルディ、J。; Tovey、CA; マサチューセッツ州トリック(1989年4月)。「誰が選挙に勝ったかを判断するのが難しい投票スキーム」。社会的選択と福祉6(2):157–165。土井10.1007 / BF00303169この記事はNP困難を直接証明するだけですが、候補とkスワップのリストが与えられると、その候補が多項式時間でコンドルセ勝者であるかどうかを判断できるため、決定問題がNPにあることは明らかです。
  2. ^ ギャリー、マイケルR。; ジョンソン、デビッドS.(1979)。コンピューターと難易度WH Freeman Co.、サンフランシスコ。