シュルツ方式
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/07/11 08:57 UTC 版)
同順位と別の実装
選好にあたって同順位を許す場合、d[*,*]の定義においてこの同順位をどう解釈するかによって、シュルツ方式の出力はおのずと異なってくる。d[A,B]を、厳密にBよりAを好む(A>B)投票者数を表すものとするか、(A>Bの投票者)引く(B>Aの投票者)の票差を表すのものとするかの二つの考えがある。しかし、たとえdがどう定義されても、シュルツ順位に循環は生じず、d値は一意であり同値はないと仮定できるだろう[1]。
シュルツ順位での同順位は、滅多にない[2]とはいえ、可能性がない訳ではない。シュルツの元の論文[1]は、無作為に選んだ投票者に従って同順位を解消する(必要に応じて繰り返す)ことを提案した。
シュルツ方式の勝者を選出する別のやや手間のかかる方法は次のとおりである。
- 全ての候補者と、候補者間のあり得る全ての線(エッジ)の完全な有向グラフを描く。
- [a]シュワルツ集合に含まれない候補者(たとえば他の候補者につながらない候補者)を全て除外し、[b]最弱のリンクを除外する。これらを繰り返す。
- 最後まで除外されなかった候補者が勝者である。
基準を満たした例と満たしていない例
満たした基準
シュルツ方式は下記の基準を満たしている。
- 無制限領域
- 非賦課(別名:市民主権)
- 非独裁制
- パレート基準[1]:§4.3
- 単一強健基準[1]:§4.5
- 多数派基準
- 多数派敗北基準
- コンドルセ基準
- コンドルセ敗北基準
- シュワルツ基準
- スミス基準[1]:§4.7
- スミスの優位選択の独立[1]:§4.7
- 相互多数派基準
- クローンの独立[1]:§4.6
- 逆行調和[1]:§4.4
- 単一付加[3]
- 単一付加投票[3]
- 分解性基準[1]:§4.2
- 多項式時間[1]:§2.3"
- 当選票がd[X,Y]に使えるなら、ウッドールの過半数基準
- 得票差がd[X,Y]に使えるなら、相称的完成[3]
満たしていない基準
シュルツ方式はコンドルセ基準を満たしているので、自動的に下記の基準は満たしていない。
同様にシュルツ方式は独裁制ではなく満場一致の投票で一致しているので、アローの不可能性定理はこの方式が基準を満たしていないことを暗示している。
- 無関係な選択肢の独立
比較表
下記の表は、シュルツ方式と他の選好投票の単議席単票制を比較したものである。
単一強健 | コンドルセ | 多数派 | コンドルセ敗者 | 多数派敗者 | 相互多数派 | スミス | ISDA | クローン独立 | 逆行対称 | 多項式時間 | 参加、一貫性] | |
Schulze | Yes | Yes | Yes | Yes | Yes | Yes | Yes | Yes | Yes | Yes | Yes | No |
---|---|---|---|---|---|---|---|---|---|---|---|---|
順位づけられた組み合わせ | Yes | Yes | Yes | Yes | Yes | Yes | Yes | Yes | Yes | Yes | Yes | No |
ケメニー・ヤング | Yes | Yes | Yes | Yes | Yes | Yes | Yes | Yes | No | Yes | No | No |
ナンソン | No | Yes | Yes | Yes | Yes | Yes | Yes | No | No | Yes | Yes | No |
ボールドウィン | No | Yes | Yes | Yes | Yes | Yes | Yes | No | No | No | Yes | No |
Instant-runoff voting | No | No | Yes | Yes | Yes | Yes | No | No | Yes | No | Yes | No |
ボルダ | Yes | No | No | Yes | Yes | No | No | No | No | Yes | Yes | Yes |
バックリン | Yes | No | Yes | No | Yes | Yes | No | No | No | No | Yes | No |
クームズ | No | No | Yes | Yes | Yes | Yes | No | No | No | No | Yes | No |
ミニマックス | Yes | Yes | Yes | No | No | No | No | No | No | No | Yes | No |
小選挙区制 | Yes | No | Yes | No | No | No | No | No | No | No | Yes | Yes |
反小選挙区制 | Yes | No | No | No | Yes | No | No | No | No | No | Yes | Yes |
コンティジェント投票 | No | No | Yes | Yes | Yes | No | No | No | No | No | Yes | No |
スリランカコンティジェント投票 | No | No | Yes | No | No | No | No | No | No | No | Yes | No |
補足投票 | No | No | Yes | No | No | No | No | No | No | No | Yes | No |
ドッジソン | No | Yes | Yes | No | No | No | No | No | No | No | No | No |
シュルツ方式と順位づけられた組み合わせの主な違いは(両方とも上記の表では同じ可否をチェックしている)、この例で見ることができる。
候補者の組み合わせXのミニマックススコアが候補者B ∈ Xに対する候補者A ∉ Xの最強の組み合わさった当選の強さと仮定する。この時シュルツ方式は(順位づけられた組み合わせではない)、当選者が常に最小のミニマックススコアで組み合わされた候補者であることを保障する[1]:§4.8。そこである意味でシュルツ方式は当選者を決定する際に覆さなければならない最強の組み合わさった当選を最小化する。
シュルツ方式の歴史
シュルツ方式は1997年にマルクス・シュルツにより開発された。初めて公のメーリングリストで1997年-1998年と[4]2000年に[5]討論された。その後シュルツ方式はSoftware in the Public Interest(2003年)[6]、Debian(2003年)[7]、Gentoo(2005年)[8]、TopCoder(2005年)[9]、ウィキメディア(2008年)[10]、KDE(2008年)[11]、Free Software Foundation Europe(2008年)[12]、スウェーデン海賊党(2009年)[13]、ドイツ海賊党(2010年)[14]などで用いられている。フランス語版ウィキペディアではシュルツ方式は2005年に多数決で賛成された二つの候補者が多数いる場合の方式の一つであり[15]、数回用いられている[16]。
2011年、シュルツは学術誌Social Choice and Welfareでこの方式を発表した[1]。
- シュルツ方式のページへのリンク