←
コンドルセ方式の順位付け投票
補助的な方式
Dodgson Quick法
ルイス・キャロルの発想です。最小限の入れ替えで全員に勝てるようになる選択肢を選びます。直感的ですが、Schulze法に匹敵する保証は証明されていません。
向いている場面: 規約でこの方式が指定されている場合や、この結果の読み方が投票者にとってわかりやすい場合。
- 考案
- Charles Dodgson(ルイス・キャロル)、1876年。近似法はMcCabe-Dansted、Pritchard、Slinko、2008年
- 提供するバリエーション
- Dodgson Quick
- 計算
- 多項式時間(選択肢n個でn²)。厳密なDodgson法はNP困難
原理
コンドルセ勝者までの距離を測る。
Dodgson法は、投票用紙上の入れ替えを最も少なくしてコンドルセ勝者になれる選択肢を選びます。この厳密な計算はNP困難です(Bartholdi、Tovey、Trick、1989年)。
Dodgson Quick法は、これを簡単に見積もります。負けた対決ごとに、少なくとも票差の半分を逆転させる必要があります。その半分の票差(端数は切り上げ)を合計した値が得点で、最も小さい選択肢が勝ちます。
手順
同じ循環を、入れ替えの数で測る。
この例の投票用紙100枚
- Camille 、次に Adèle 、次に Sophie 投票者40名
- Adèle 、次に Sophie 、次に Camille 投票者35名
- Sophie 、次に Camille 、次に Adèle 投票者25名
- 1 Camille。 Sophieに20票差で負ける。得点10。
- 2 Adèle。 Camilleに30票差で負ける。得点15。
- 3 Sophie。 Adèleに50票差で負ける。得点25。
- Camille Sophieに20票差で負け 10
- Adèle Camilleに30票差で負け 15
- Sophie Adèleに50票差で負け 25
性質
この方式が保証すること。相対多数決との比較。
Dodgson Quick法を扱った公表済みの比較表はありません。方式の設計または一般的な結果から確立できる欄だけを埋めています。
| 基準 | Dodgson Quick | 相対多数決 |
|---|---|---|
| 過半数基準 投票者の過半数が1位にした選択肢が勝ちます。 | はい 注1 | はい |
| 過半数敗者基準 投票者の過半数が最下位にした選択肢は、決して勝ちません。 | 未確立 | いいえ |
| 相互過半数基準 過半数の投票者が、いくつかの選択肢をほかのすべての選択肢より上位に置いた場合、勝者はその中から出ます。 | 未確立 | いいえ |
| コンドルセ勝者 一対一の対決でほかのすべてに勝つ選択肢は、必ず選ばれます。 | はい 注2 | いいえ |
| コンドルセ敗者 一対一の対決でほかのすべてに負ける選択肢は、決して選ばれません。 | 未確立 | いいえ |
| スミス基準 勝者は、グループ外のすべての選択肢に勝つ最小の選択肢グループに含まれます。 | 未確立 | いいえ |
| クローン独立性 ある選択肢によく似た選択肢を加えても、ほかの選択肢どうしの勝敗は変わりません。 | 未確立 | いいえ |
| 単調性 勝者の順位を上げたことで、その勝者が負けることはありません。 | 未確立 | はい |
| 局所独立性 結果で最下位(または1位)になった選択肢を除いても、ほかの選択肢の順位は変わりません。 | 未確立 | いいえ |
| 逆転対称性 すべての投票用紙の順位を逆にすると、元の勝者は勝てなくなります。 | 未確立 | いいえ |
| 参加基準 正直に投票した結果が、棄権した場合より投票者にとって不利になることはありません。 | いいえ 注3 | はい |
| 一貫性 2つの別々のグループでそれぞれ勝つ選択肢は、両者を合わせても勝ちます。 | いいえ 注3 | はい |
| 後順位無害性 選択肢を追加で順位付けしても、それより上位にした選択肢が不利になることはありません。 | いいえ 注3 | はい 注4 |
| 決定可能性 投票者が増えるほど、最終的な同順位は起こりにくくなります。 | 未確立 | はい |
| 高速な計算 選択肢が多くても、多項式時間で結果を計算できます。 | はい | はい |
- ✓ 常に満たす
- ✕ 投票によっては満たさない場合がある
- ? 公表された文献による裏付けがない
- 1 コンドルセ勝者基準から直接導かれます。過半数が1位にした選択肢は、一対一の対決でほかのすべてに勝つからです。
- 2 設計上保証されます。CondorcetPHPは常にコンドルセ勝者を1位にします。
- 3 コンドルセ勝者基準を満たす方式は、この基準を満たせません。一般的に証明されている結果です。
- 4 自明に満たします。相対多数決は第1希望より先を読まないためです。
Condorcet.Voteでは
実装上の選択。
- コンドルセ勝者を1位に。 コンドルセ勝者がいれば、CondorcetPHPは必ず1位にします。
- あえて近似を採用。 厳密なDodgson法は提供していません。計算が現実的な時間で終わらなくなるおそれがあるためです。
- 知っておきたい限界。 得点は負けだけを見ます。そのため、ほかのすべてに負ける選択肢が、1つの対決にしか負けていない選択肢より上位になることがあります。
出典
さらに詳しく知りたい方へ。
| 種類 | 文献 |
|---|---|
| 百科事典 | Dodgson’s method Wikipedia |
| ドキュメント | Voting Methods CondorcetPHP · docs.condorcet.io |
| 論文 | Approximability of Dodgson’s rule John C. McCabe-Dansted, Geoffrey Pritchard, Arkadii Slinko (2008) · Social Choice and Welfare 31(2) |