シュルツ方式

シュルツ方式（しゅるつほうしき、）は、1997年にマルクス・シュルツが開発した、選好を表す投票を用いて単一の当選者を選ぶ選挙方法である。英語ではシュルツ方式はSchwartz Sequential Dropping（SSD）、Cloneproof Schwartz Sequential Dropping（CSSD）、Beatpath Method、Beatpath Winner、Path Voting、Path Winnerとしても知られている。

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

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

現在シュルツ方式は最も広く使われるコンドルセ方式である。シュルツ方式はウィキメディア財団やDebian、Ubuntu、Gentoo、Software in the Public Interest、Free Software Foundation Europe、海賊党など多くの団体で用いられている（一覧）。

 シュルツ方式に関する解説 
 投票用紙 
140px|left|thumb
シュルツ方式に対する投票形式は、他の選好投票における単議席単票制と同じである。各々の投票者は、候補者たちに対して選好の順序（同順位も認める）を付けなければならない。

典型的には、投票者は以下の通りに投票用紙に選好を明記する。投票用紙には全ての候補者が一覧になっており、投票者は番号を用いて選好順にこの一覧に番号を振る。最も好ましい候補者には「1」を、次に好ましい候補者に「2」を、以下も順に番号を付ける。投票者には次のことも許されている。
 複数の候補者に同じ番号を付けること。このことは、これらの候補者間に差異を付けられないことを意味する。
 選好を示すのに連続しない番号を用いること。番号の絶対値は重要ではなく、選好の順序のみが選挙の結果に影響するためである。
 何名かの候補者に順位付けしないままでいること。候補者に順位を付けないことで、投票者は以下の意見を表明したと解釈される。(i) 順位付けしていない候補者たちより、順位付けした候補者たちの方を選好する。(ii) 順位付けしていない候補者間に差異は付けない。

 シュルツ方式 
W候補者よりV候補者を選好する投票者の数を d[V,W] で表す。

X候補者からY候補者への強さ p の道とは、候補者 C(1), …, C(n) の列であって、以下の条件を全て満たすものである。
 C(1) = X かつ C(n) = Y
 任意の i = 1, …, n-1 に対して、d[C(i),C(i+1)] > d[C(i+1),C(i)]
 任意の 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] であることが証明できる。これは、上記の「より良い」という関係が推移関係であることを意味し、他の全ての候補者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[*,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から ...  border|none|150px A-(30)-D-(28)-C-(29)-B  border|none|150px A-(30)-D-(28)-C  border|none|150px A-(30)-D  border|none|150px A-(30)-D-(28)-C-(24)-E Aから ...  Bから ... border|none|150px B-(25)-A   border|none|150px B-(33)-D-(28)-C  border|none|150px B-(33)-D  border|none|150px B-(33)-D-(28)-C-(24)-E Bから ...  Cから ... border|none|150px C-(29)-B-(25)-A  border|none|150px C-(29)-B   border|none|150px C-(29)-B-(33)-D  border|none|150px C-(24)-E Cから ...  Dから ... border|none|150px D-(28)-C-(29)-B-(25)-A  border|none|150px D-(28)-C-(29)-B  border|none|150px D-(28)-C   border|none|150px D-(28)-C-(24)-E Dから ...  Eから ... border|none|150px E-(31)-D-(28)-C-(29)-B-(25)-A  border|none|150px E-(31)-D-(28)-C-(29)-B  border|none|150px E-(31)-D-(28)-C  border|none|150px 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と呼ばれている。従って強さを計算する単純な一つの方法はワーシャル・フロイド法の変形である。下記の擬似コードはアルゴリズムを表している。

# Input: d[i,j]（j候補者よりi候補者を好む投票者の数）
# Output: p[i,j]（i候補者からj候補者への最強の道の強さ）

for i from 1 to C
   for j from 1 to C
      if (i <> j) then
         if (d[i,j] > d[j,i]) then
            p[i,j] := d[i,j]
         else
            p[i,j] := 0

for i from 1 to C
   for j from 1 to C
      if (i <> j) then
         for k from 1 to C
            if (i <> k and j <> k) then
               p[j,k] := max ( p[j,k], min ( p[j,i], p[i,k] ) )

このアルゴリズムは優れていて、候補者数をCとするとO(C3)の時間計算量で解が求まる。（これにはd[*,*]を求める時間計算量を含んでおらず、最も簡単な方法で実装するなら、投票者の数をVとするとO(VC2)の時間計算量が必要である。）

 同順位と別の実装 
選好にあたって同順位を許す場合、d[*,*]の定義においてこの同順位をどう解釈するかによって、シュルツ方式の出力はおのずと異なってくる。d[A,B]を、厳密にBよりAを好む（A>B）投票者数を表すものとするか、（A>Bの投票者）引く（B>Aの投票者）の票差を表すのものとするかの二つの考えがある。しかし、たとえdがどう定義されても、シュルツ順位に循環は生じず、d値は一意であり同値はないと仮定できるだろう。

シュルツ順位での同順位は、滅多にない投票者数が候補者数よりじゅうぶん大きい場合、合理的確率的な仮定においてとはいえ、可能性がない訳ではない。シュルツの元の論文は、無作為に選んだ投票者に従って同順位を解消する(必要に応じて繰り返す)ことを提案した。

シュルツ方式の勝者を選出する別のやや手間のかかる方法は次のとおりである。
 全ての候補者と、候補者間のあり得る全ての線(エッジ)の完全な有向グラフを描く。
 [a]シュワルツ集合に含まれない候補者（たとえば他の候補者につながらない候補者）を全て除外し、[b]最弱のリンクを除外する。これらを繰り返す。
 最後まで除外されなかった候補者が勝者である。

 基準を満たした例と満たしていない例 
 満たした基準 
シュルツ方式は下記の基準を満たしている。
 無制限領域
 非賦課（別名：市民主権）
 非独裁制
 パレート基準
 単一強健基準
 多数派基準
 多数派敗北基準
 コンドルセ基準
 コンドルセ敗北基準
 シュワルツ基準
 スミス基準
 スミスの優位選択の独立
 相互多数派基準
 クローンの独立
 逆行調和
 単一付加Douglas R. Woodall, 選好選挙規則の所有, Voting Matters, issue 3, pages 8-15, December 1994
 単一付加投票
 分解性基準
 多項式時間
 当選票がd[X,Y]に使えるなら、ウッドールの過半数基準
 得票差がd[X,Y]に使えるなら、相称的完成

 満たしていない基準 
シュルツ方式はコンドルセ基準を満たしているので、自動的に下記の基準は満たしていない。
 参加
 一貫性
 妥協する強み
 葬る強み
 後日無害

同様にシュルツ方式は独裁制ではなく満場一致の投票で一致しているので、アローの不可能性定理はこの方式が基準を満たしていないことを暗示している。
 無関係な選択肢の独立

 比較表 
下記の表は、シュルツ方式と他の選好投票の単議席単票制を比較したものである。

 単一強健 コンドルセ 多数派 コンドルセ敗者 多数派敗者 相互多数派 スミス ISDA クローン独立 逆行対称 多項式時間 参加、一貫性] Schulze                        順位づけられた組み合わせ                        ケメニー・ヤング                          ナンソン                           ボールドウィン                            Instant-runoff voting                             ボルダ                              バックリン                              クームズ                              ミニマックス                               小選挙区制                                反小選挙区制                                コンティジェント投票                               スリランカコンティジェント投票                                 補足投票                                 ドッジソン                                

シュルツ方式と順位づけられた組み合わせの主な違いは（両方とも上記の表では同じ可否をチェックしている）、この例で見ることができる。

候補者の組み合わせXのミニマックススコアが候補者B ∈ Xに対する候補者A ∉ Xの最強の組み合わさった当選の強さと仮定する。この時シュルツ方式は（順位づけられた組み合わせではない）、当選者が常に最小のミニマックススコアで組み合わされた候補者であることを保障する。そこである意味でシュルツ方式は当選者を決定する際に覆さなければならない最強の組み合わさった当選を最小化する。

 シュルツ方式の歴史 
シュルツ方式は1997年にマルクス・シュルツにより開発された。初めて公のメーリングリストで1997年-1998年と下記を参照のこと。
 Markus Schulze, Condorect sub-cycle rule, October 1997（このメッセージではシュルツ方式は順位づけられた組み合わせ方式と同一のものと誤解されている。）
 Mike Ossipoff, Party List P.S., July 1998
 Markus Schulze, Tiebreakers, Subcycle Rules, August 1998
 Markus Schulze, Maybe Schulze is decisive,  August 1998
 Norman Petry, Schulze Method - Simpler Definition, September 1998
 Markus Schulze, Schulze Method, November 19982000年に下記を参照のこと。
 Anthony Towns, Disambiguation of 4.1.5, November 2000
 Norman Petry, Constitutional voting, definition of cumulative preference, December 2000討論された。その後シュルツ方式はSoftware in the Public Interest（2003年）Process for adding new board members, January 2003、Debian（2003年）下記を参照のこと。
 Constitutional Amendment: Condorcet/Clone Proof SSD Voting Method, June 2003
 Constitution for the Debian Project, appendix A6
 Debian Voting Information、Gentoo（2005年）下記を参照のこと。
 Gentoo Foundation Charter
 Aron Griffis, 2005 Gentoo Trustees Election Results, May 2005
 Lars Weiler, Gentoo Weekly Newsletter 23 May 2005
 Daniel Drake, Gentoo metastructure reform poll is open, June 2005
 Grant Goodyear, Results now more official, September 2006
 2007 Gentoo Council Election Results, September 2007
 2008 Gentoo Council Election Results, June 2008
 2008 Gentoo Council Election Results, November 2008
 2009 Gentoo Council Election Results, June 2009
 2009 Gentoo Council Election Results, December 2009
 2010 Gentoo Council Election Results, June 2010、TopCoder（2005年）下記を参照のこと。
 2006 TopCoder Open Logo Design Contest, November 2005
 2006 TopCoder Collegiate Challenge Logo Design Contest, June 2006
 2007 TopCoder High School Tournament Logo, September 2006
 2007 TopCoder Arena Skin Contest, November 2006
 2007 TopCoder Open Logo Contest, January 2007
 2007 TopCoder Open Web Design Contest, January 2007
 2007 TopCoder Collegiate Challenge T-Shirt Design Contest, September 2007
 2008 TopCoder Open Logo Design Contest, September 2007
 2008 TopCoder Open Web Site Design Contest, October 2007
 2008 TopCoder Open T-Shirt Design Contest, March 2008、ウィキメディア（2008年）下記を参照のこと。
 Jesse Plamondon-Willard, Board election to use preference voting, May 2008
 Mark Ryan, 2008 Wikimedia Board Election results, June 2008
 2008 Board Elections, June 2008
 2009 Board Elections, August 2009、KDE（2008年）section 3.4.1 of the Rules of Procedures for Online Voting、Free Software Foundation Europe（2008年）下記を参照のこと。
 article 6 section 3 of the constitution
 Fellowship vote for General Assembly seats, March 2009
 And the winner of the election for FSFE's Fellowship GA seat is ..., June 2009、スウェーデン海賊党（2009年）下記を参照のこと。
 Inför primärvalen, October 2009
 Dags att kandidera till riksdagen, October 2009
 Råresultat primärvalet, January 2010、ドイツ海賊党（2010年）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)などで用いられている。フランス語版ウィキペディアではシュルツ方式は2005年に多数決で賛成された二つの候補者が多数いる場合の方式の一つでありChoix dans les votes、数回用いられている :fr:Spécial:Pages liées/Méthode Schulze。

2011年、シュルツは学術誌Social Choice and Welfareでこの方式を発表した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.。

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

 Annodex協会Election of the Annodex Association committee for 2007, February 2007
 Blitzed Condorcet method for admin voting, January 2005
 BoardGameGeek下記を参照のこと。
 Important notice for Golden Geek voters, September 2007
 Golden Geek Awards 2008 - Nominations Open, August 2008
 Golden Geek Awards 2009 - Nominations Open, August 2009
 Golden Geek Awards 2010 - Nominations Open, September 2010
 Cassandra Project Logo, October 2009
 Codex Alpe Adria 
 海洋学単科大学
 ヨーク大学コンピューター学部門協会（HackSoc） Report on HackSoc Elections, December 2008
 County Highpointers Adam Helman, Family Affair Voting Scheme - Schulze Method
 Debian 
 Demokratische Bildung Berlin appendix 1 of the constitution
 Digital Freedom in Education and Youth Logo Competition, May 2009
 EnMasse Forums
 EuroBillTracker下記を参照のこと。
 Candidate cities for EBTM05, December 2004
 Meeting location preferences, December 2004
 Date for EBTM07 Berlin, January 2007
 Vote the date of the Summer EBTM08 in Ljubljana, January 2008
 New Logo for EBT, August 2009
 欧州民主教育会議（EUDEC）
 Fair Trade Northwest article XI section 2 of the bylaws
 FFmpeg Democratic election of the server admins, July 2010
 Flemish Student Society of Leuven article 51 of the statutory rules
 Free Hardware Foundation of Italy See:
 Eletto il nuovo Consiglio nella Free Hardware Foundation, June 2008
 Poll Results, June 2008
 Free Software Foundation Europe (FSFE) 
 Gentoo Foundation 
 GNU Privacy Guard (GnuPG) GnuPG Logo Vote, November 2006
 Gothenburg Hacker Space (GHS) §14 of the bylaws
 Graduate Student Organization at the State University of New York: Computer Science (GSOCS) 
 Haskell Haskell Logo Competition, March 2009
 Kanawha Valley Scrabble Club A club by any other name ..., April 2009
 KDE e.V. 
 キングマン会館下記を参照のこと。
 Ka-Ping Yee, Condorcet elections, March 2005
 Ka-Ping Yee, Kingman adopts Condorcet voting, April 2005
 ナイト財団Knight Foundation awards $5000 to best created-on-the-spot projects, June 2009
 Kumoricon下記を参照のこと。
 Mascot 2007 contest, July 2006
 Mascot 2008 and cover 2007 contests, May 2007
 Mascot 2009 and program cover 2008 contests, April 2008
 Mascot 2010 and program cover 2009 contests, May 2009
 Mascot 2011 and book cover 2010 contests, May 2010
システムアドミニストレーター連盟（LOPSA）article 8.3 of the bylaws
 Libre-Entreprise 下記を参照のこと。
 Choix de date pour la réunion Libre-entreprise durant le Salon Solution Linux 2006, January 2006
 Entrée de Libricks dans le réseau Libre-entreprise, February 2008
 Lumiera/CinelerraLumiera Logo Contest, January 2009
 Mathematical Knowledge Management Interest Group (MKM-IG) 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:
 MKM-IG Charter
 Michael Kohlhase, MKM-IG Trustees Election Details & Ballot, November 2004
 Andrew A. Adams, MKM-IG Trustees Election 2005, December 2005
 Lionel Elie Mamane, Elections 2007: Ballot, August 2007
 Metalab
 Music Television（MTV） Benjamin Mako Hill, Voting Machinery for the Masses, July 2008
 Neo 下記を参照のこと。
 Wahlen zum Neo-2-Freeze: Formalitäten, February 2010
 Hinweise zur Stimmabgabe, March 2010
 Ergebnisse, March 2010
 netznetz下記を参照のこと。
 Online-Abstimmung
 Verfassungsentwurf
 Noisebridge2009 Director Elections
 North Shore Cyclists (NSC) NSC Jersey election, NSC Jersey vote, September 2007
 OpenStack 2010 OpenStack Community Election, November 2010
 Park Alumni Society (PAS) 
 オーストラリア海賊党
 オーストリア海賊党§6(10) of the bylaws
 ブラジル海賊党
 ドイツ海賊党
 ニュージーランド海賊党23 January 2011 meeting minutes
 スウェーデン海賊党 
 スイス海賊党Piratenversammlung der Piratenpartei Schweiz, September 2010
 Pitcher Plant of the Month
 Pittsburgh Ultimate 2006 Community for Pittsburgh Ultimate Board Election, September 2006
 RPMrepo LogoVoting, December 2007
 Sender Policy Framework (SPF) 下記を参照のこと。
 SPF Council Election Procedures
 2006 SPF Council Election, January 2006
 2007 SPF Council Election, January 2007
 Software in the Public Interest (SPI) 
 Squeak Squeak Oversight Board Election 2010, March 2010
 自由な文化のための学生下記を参照のこと。
 Bylaws of the Students for Free Culture, article V, section 1.1.1
 Free Culture Student Board Elected Using Selectricity, February 2008
 Sugar Labs Election status update, September 2009
 TopCoder
 University of British Columbia Math Club See this mail.
 WikIAC See:
 Tornei:Carnevale 2007, March 2007
 Tornei:Sigle estate 2008, July 2008
 ウィキメディア財団 
 フランス語、ヘブライ語See e.g. here (May 2009), here (August 2009), and here (December 2009).、ハンガリー語See here and here.、ロシア語下記を参照のこと。
 Result of 2007 Arbitration Committee Elections
 Result of 2008 Arbitration Committee Elections
 Result of 2009 Arbitration Committee Elections
 Result of 2010 Arbitration Committee Electionsのウィキペディア

 脚注 

 外部リンク 

 一般 
 マルクス・シュルツによるシュルツ方式のサイト

 チュートリアル 
クリストフ・ギーゼルによるSchulze-Methode 
ヨハネス・グラブマイアーによるコンドルセ評価
ベルンハルト・ネーベルによるSpieltheorie 
シュトゥットガルト大学によるSchulze-Methode 

 擁護者 

ロブ・レグランドによる順位付けした投票方式に関する記述
ロブ・ローリングによる的確な民主主義
ケヴィン・ヴェンスケによる選挙方法と基準
ヨヘン・フォスによるデビアン投票制度
選挙方法：選挙方法に関する技術的な議論を含むメーリングリスト

 本 

 クリストフ・ベルガース（2009年）：社会選択の数学：投票、代償、分配, SIAM, ISBN 0-89871-695-0
 サウル・シュタールとポール・E・ジョンソン（2006年）：現代数学の理解, Sudbury:  Jones and Bartlett Publishers, ISBN 0-7637-3401-2
 ニコラウス・タイドマン（2006年）：集団の決定と投票：公共の選択のための可能性, Burlington: Ashgate, ISBN 0-7546-4717-X

 ソフトウェア 

 ブラッド・ビーティーによるPython Vote Core
 ブレイク・クレトニーによるVoting Software Project
 マシュー・ゴールドスタインによるCondorcet with Dual Dropping Perl Scripts
 エリック・ゴアによるCondorcet Voting Calculator
 ベンジャミン・マコ・ヒルによるSelectricityとRubyVote  
 アドリアン・ラングによるSchulze voting for DokuWiki
 ロブ・ランフィアーによるElectowidget
 ロブ・レグランドによるOnline ranked-ballot voting calculator
 エヴァン・マーティンによるHaskell Condorcet Module
 アンドリュー・マイヤーズによるCondorcet Internet Voting Service (CIVS)
 ブライアン・オルソンによるBetterPolls.com
 ジェフリー・オニールによるOpenSTV
 LiquidFeedback
 公共ソフトウェア集団によるpreftools
 Voting Excel Template and Add-In

 法制化事業 
 Arizonans for Condorcet Ranked Voting   

Category:選挙方式