シュルツ方式

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

シュルツ方式(しゅるつほうしき、: Schulze method)は、1997年にマルクス・シュルツが開発した、選好を表す投票を用いて単一の当選者を選ぶ選挙方法である。英語ではシュルツ方式はSchwartz Sequential DroppingSSD)、Cloneproof Schwartz Sequential DroppingCSSD)、Beatpath MethodBeatpath WinnerPath VotingPath Winnerとしても知られている。

シュルツ方式はコンドルセ方式である。すなわち、他のいずれの候補者と一対比較してもより好まれるような候補者がいたならば、その候補者はシュルツ方式が適用される場合に当選者となる。

現在シュルツ方式は最も広く使われるコンドルセ方式である(一覧)。シュルツ方式はウィキメディア財団DebianGentooSoftware in the Public Interestなどいくつかの団体で用いられている。

(下記に定義する)シュルツ方式の出力は、候補者の順序を与える。従って議席が複数ある場合も、上位k人の候補者がkの議席を得られるようにすることで、この方式は修正することなく用いることができる。更に比例代表選挙のために、単独移譲投票バージョンが提案されている。

シュルツ方式に関する解説[編集]

投票用紙[編集]

Preferential ballot.svg

シュルツ方式に対する投票形式は、他の選好投票における単議席単票制と同じである。各々の投票者は、候補者たちに対して選好の順序(同順位も認める)を付けなければならない。

典型的には、投票者は以下の通りに投票用紙に選好を明記する。投票用紙には全ての候補者が一覧になっており、投票者は番号を用いて選好順にこの一覧に番号を振る。最も好ましい候補者には「1」を、次に好ましい候補者に「2」を、以下も順に番号を付ける。投票者には次のことも許されている。

  • 複数の候補者に同じ番号を付けること。このことは、これらの候補者間に差異を付けられないことを意味する。
  • 選好を示すのに連続しない番号を用いること。番号の絶対値は重要ではなく、選好の順序のみが選挙の結果に影響するためである。
  • 何名かの候補者に順位付けしないままでいること。候補者に順位を付けないことで、投票者は以下の意見を表明したと解釈される。(i) 順位付けしていない候補者たちより、順位付けした候補者たちの方を選好する。(ii) 順位付けしていない候補者間に差異は付けない。

シュルツ方式[編集]

W候補者よりV候補者を選好する投票者の数を d[V,W] で表す。

X候補者からY候補者への強さ p のとは、候補者 C(1), …, C(n) のであって、以下の条件を全て満たすものである。

  1. C(1) = X かつ C(n) = Y
  2. 任意の i = 1, …, n-1 に対して、d[C(i),C(i+1)] > d[C(i+1),C(i)]
  3. 任意の i = 1, …, n-1 に対して、d[C(i),C(i+1)] ≥ p

さらに、A候補者からB候補者への道の強さの最大値を p[A,B] で表す。そのような道がなければ、p[A,B] = 0 と定義する。

p[D,E] > p[E,D] であれば、D候補者はE候補者より良いとみなす。

D候補者が他の全てのE候補者に対して p[D,E] ≥ p[E,D] であれば、D候補者は当選の可能性がある

p[X,Y] > p[Y,X] かつ p[Y,Z] > p[Z,Y] ならば、p[X,Z] > p[Z,X] であることが証明できる[1]:§4.1。これは、上記の「より良い」という関係推移関係であることを意味し、他の全ての候補者Eに対して p[D,E] ≥ p[E,D] を満たす候補者Dが少なくとも一人はいることが保証される。

[編集]

45人の投票者が5人の候補者 A, B, C, D, E を順位付けする下記の例を考えてみよう。

  • 5 ACBED(5人の投票者がA > C > B > E > Dと選好することを表す。)
  • 5 ADECB
  • 8 BEDAC
  • 3 CABED
  • 7 CAEBD
  • 2 CBADE
  • 7 DCEBA
  • 8 EBADC

初めにペアに関する選好を計算する。例えば A と B を比較すると、B より A を好む投票者が 5+5+3+7 = 20 人いて、A より B を好む投票者が 8+2+7+8 = 25 人いる。よって d[A,B] = 20, d[B,A] = 25 となる。ペアに関する選好の全体像は以下のようになる。

d[*, *] の値を辺に付した有向グラフ
ペアに関する選好の表
d[*,A] d[*,B] d[*,C] d[*,D] d[*,E]
d[A,*] 20 26 30 22
d[B,*] 25 16 33 18
d[C,*] 19 29 17 24
d[D,*] 15 12 28 14
d[E,*] 23 27 21 31

右の図式は、最強の道を視覚的に把握しやすくしたもので、X から Y への矢印に d[X,Y] の値を付した有向グラフである。d[X,Y] > d[Y,X] ならば、d[Y,X] の値は選挙の結果に影響を与えないため、図には d[X,Y] の値のみ記す。

道の強さが辺の強さの最小値であることを思い出そう。例えば、B から D への最強の道は、強さ 33 の直接の道 (B,D) であり、よって p[B,D] = 33 である。比較のため、p[A,C] も見てみよう。直接の道 (A,C) の強さは 26 であるが、より強い道 (A,D,C) がある。その強さは d[A,D] = 30, d[D,C] = 28 の最小値 28 であり、ゆえに p[A,C] = 28 である。

下記の表では、最強の道を赤で示し、辺の強さの最小値に下線を引いている。

最強の道
... Aに ... Bに ... Cに ... Dに ... Eに
Aから ...
Schulze method example1 AB.svg
A-(30)-D-(28)-C-(29)-B
Schulze method example1 AC.svg
A-(30)-D-(28)-C
Schulze method example1 AD.svg
A-(30)-D
Schulze method example1 AE.svg
A-(30)-D-(28)-C-(24)-E
Aから ...
Bから ...
Schulze method example1 BA.svg
B-(25)-A
Schulze method example1 BC.svg
B-(33)-D-(28)-C
Schulze method example1 BD.svg
B-(33)-D
Schulze method example1 BE.svg
B-(33)-D-(28)-C-(24)-E
Bから ...
Cから ...
Schulze method example1 CA.svg
C-(29)-B-(25)-A
Schulze method example1 CB.svg
C-(29)-B
Schulze method example1 CD.svg
C-(29)-B-(33)-D
Schulze method example1 CE.svg
C-(24)-E
Cから ...
Dから ...
Schulze method example1 DA.svg
D-(28)-C-(29)-B-(25)-A
Schulze method example1 DB.svg
D-(28)-C-(29)-B
Schulze method example1 DC.svg
D-(28)-C
Schulze method example1 DE.svg
D-(28)-C-(24)-E
Dから ...
Eから ...
Schulze method example1 EA.svg
E-(31)-D-(28)-C-(29)-B-(25)-A
Schulze method example1 EB.svg
E-(31)-D-(28)-C-(29)-B
Schulze method example1 EC.svg
E-(31)-D-(28)-C
Schulze method example1 ED.svg
E-(31)-D
Eから ...
... Aに ... Bに ... Cに ... Dに ... Eに
最強の道の強さ
p[*,A] p[*,B] p[*,C] p[*,D] p[*,E]
p[A,*] 28 28 30 24
p[B,*] 25 28 33 24
p[C,*] 25 29 29 24
p[D,*] 25 28 28 24
p[E,*] 25 28 28 31

これでシュルツ方式による結果を確定できる。例えば A と B を比較すると、28 = p[A,B] > p[B,A] = 25 であるので、シュルツ方式ではA候補者はB候補者より良い。別の例では、31 = p[E,D] > p[D,E] = 24 であるので、E候補者はD候補者より良い。同様にして全ての候補者を比較すると、E > A > C > B > D となり、E が当選との結果を得る。言い方を変えれば、E は他の全てのX候補者に対して p[E,X] > p[X,E] であるがゆえに当選した。

実践[編集]

シュルツ方式を実践するにあたって唯一困難な段階は、最強の道の強さを計算することである。しかしこのことは時にwidest path problemとして知られる表理論における良く知られた問題である。従って強さを計算する単純な一つの方法は、ワーシャル・フロイド法の変形である。下記の擬似コードは、アルゴリズムを表している。

  1. # Input: d[i,j](j候補者よりi候補者を好む投票者の数)
    
  2. # Output: p[i,j](i候補者からj候補者への最強の道の強さ)
    
  3.  
    
  4. for i from 1 to C
    
  5.    for j from 1 to C
    
  6.       if (i <> j) then
    
  7.          if (d[i,j] > d[j,i]) then
    
  8.             p[i,j] := d[i,j]
    
  9.          else
    
  10.             p[i,j] := 0
    
  11.  
    
  12. for i from 1 to C
    
  13.    for j from 1 to C
    
  14.       if (i <> j) then
    
  15.          for k from 1 to C
    
  16.             if (i <> k and j <> k) then
    
  17.                p[j,k] := max ( p[j,k], min ( p[j,i], p[i,k] ) )
    

このアルゴリズムは優れていて、Cが候補者の数であるC3に比例してランニング時間がある。(このことはd[*,*]を計算するランニング時間を数えるものではなく、最も簡単な方法で実践するなら、C2掛ける投票者の数に比例して時間を使うことになる。)

束縛と二者択一の実践[編集]

利用者に選好にあたって束縛があることを認めた場合、シュルツ方式の結果は、定義[*,*]におけるこの束縛をどう解釈するかによっておのずと違ってくる。本来の選択は二つあり、d[A,B]は厳密にBよりAを好む(A>B)投票者を表すか、(A>Bの投票者)引く(B>Aの投票者)のを表すかである。例え如何にdが定義されていても、シュルツ方式の順位付けは、周回するものではなく、dは束縛されない独自のものだと思われる[1]

シュルツ方式の順位付けにおける束縛はありそうもないが[2]、可能性はある。シュルツの最初の論文は[1]、無作為に選んだ投票者に従って束縛をなくし必要に応じて巡回することを提案した。

シュルツ方式による当選者とする二者択一の手間取る方法に下記の手続きがある。

  1. 全候補者の載った完璧な一覧表を作成し、可能な限り特定の候補者が不利にならないようにする。
  2. 反復して[a]シュワルツセットではない候補者を全て削除し(例:他の候補者の得票数に達しない候補者)[b]最弱のリンクを削除する。
  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]

シュルツ方式の利用[編集]

ウィキメディア理事会選挙用の投票用紙見本

シュルツ方式は現在議会選挙では使われていない。しかしスウェーデンの海賊党の代議員予備選挙で用いられている。他の公的機関でも支援を受け始めている。シュルツ方式を現在採用している機関は、次の通りである。

脚注[編集]

  1. ^ a b c d e f g h i j k l m n Markus Schulze, A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method, Social Choice and Welfare, volume 36, number 2, page 267–303, 2011. Preliminary version in Voting Matters, 17:9-19, 2003.
  2. ^ 投票者の数が候補者の数を上回る場合の合理的で確率論的な仮説の下で
  3. ^ a b c Douglas R. Woodall, 選好選挙規則の所有, Voting Matters, issue 3, pages 8-15, December 1994
  4. ^ 下記を参照のこと。
  5. ^ 下記を参照のこと。
  6. ^ a b Process for adding new board members, January 2003
  7. ^ a b 下記を参照のこと。
  8. ^ a b 下記を参照のこと。
  9. ^ a b 下記を参照のこと。
  10. ^ a b 下記を参照のこと。
  11. ^ a b section 3.4.1 of the Rules of Procedures for Online Voting
  12. ^ a b 下記を参照のこと。
  13. ^ a b 下記を参照のこと。
  14. ^ a b 11 of the 16 regional sections and the federal section of the Pirate Party of Germany are using LiquidFeedback for unbinding internal opinion polls. In 2010/2011, the Pirate Parties of Neukölln (link), Mitte (link), Steglitz-Zehlendorf (link), Lichtenberg (link), and Tempelhof-Schöneberg (link) adopted the Schulze method for its primaries. In 2011, the Pirate Party of Berlin adopted this method for its primaries (link)
  15. ^ a b Choix dans les votes
  16. ^ fr:Spécial:Pages liées/Méthode Schulze
  17. ^ Election of the Annodex Association committee for 2007, February 2007
  18. ^ Condorcet method for admin voting, January 2005
  19. ^ 下記を参照のこと。
  20. ^ Project Logo, October 2009
  21. ^ Codex Alpe Adria Competitions”. 0xaa.org (2010年1月24日). 2010年5月8日閲覧。
  22. ^ Fellowship Guidelines (PDF)”. 2011年6月1日閲覧。
  23. ^ Report on HackSoc Elections, December 2008
  24. ^ Adam Helman, Family Affair Voting Scheme - Schulze Method
  25. ^ appendix 1 of the constitution
  26. ^ Logo Competition, May 2009
  27. ^ 下記を参照のこと。
  28. ^ Guidance Document”. Eudec.org (2009年11月15日). 2010年5月8日閲覧。
  29. ^ article XI section 2 of the bylaws
  30. ^ Democratic election of the server admins, July 2010
  31. ^ article 51 of the statutory rules
  32. ^ See:
  33. ^ GnuPG Logo Vote, November 2006
  34. ^ §14 of the bylaws
  35. ^ User Voting Instructions”. Gso.cs.binghamton.edu. 2010年5月8日閲覧。
  36. ^ Haskell Logo Competition, March 2009
  37. ^ A club by any other name ..., April 2009
  38. ^ 下記を参照のこと。
  39. ^ Knight Foundation awards $5000 to best created-on-the-spot projects, June 2009
  40. ^ 下記を参照のこと。
  41. ^ article 8.3 of the bylaws
  42. ^ 下記を参照のこと。
  43. ^ Lumiera Logo Contest, January 2009
  44. ^ The MKM-IG uses Condorcet with dual dropping. That means: The Schulze ranking and the ranked pairs ranking are calculated and the winner is the top-ranked candidate of that of these two rankings that has the better Kemeny score. See:
  45. ^ Wahlmodus” ((ドイツ語)). Metalab.at. 2010年5月8日閲覧。
  46. ^ Benjamin Mako Hill, Voting Machinery for the Masses, July 2008
  47. ^ 下記を参照のこと。
  48. ^ 下記を参照のこと。
  49. ^ 2009 Director Elections
  50. ^ NSC Jersey election, NSC Jersey vote, September 2007
  51. ^ 2010 OpenStack Community Election, November 2010
  52. ^ Voting Procedures”. Parkscholars.org. 2010年5月8日閲覧。
  53. ^ §6(10) of the bylaws
  54. ^ 23 January 2011 meeting minutes
  55. ^ Piratenversammlung der Piratenpartei Schweiz, September 2010
  56. ^ 2006 Community for Pittsburgh Ultimate Board Election, September 2006
  57. ^ LogoVoting, December 2007
  58. ^ 下記を参照のこと。
  59. ^ Squeak Oversight Board Election 2010, March 2010
  60. ^ 下記を参照のこと。
  61. ^ Election status update, September 2009
  62. ^ See this mail.
  63. ^ See:
  64. ^ See e.g. here (May 2009), here (August 2009), and here (December 2009).
  65. ^ See here and here.
  66. ^ 下記を参照のこと。

外部リンク[編集]

一般[編集]

チュートリアル[編集]

擁護者[編集]

[編集]

ソフトウェア[編集]

法制化事業[編集]