シュルツ方式

**シュルツ方式**（しゅるつほうしき、）は、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、海賊党など多くの団体で用いられている（一覧）。

## シュルツ方式に関する解説
### 投票用紙

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

典型的には、投票者は以下の通りに投票用紙に選好を明記する。投票用紙には全ての候補者が一覧になっており、投票者は番号を用いて選好順にこの一覧に番号を振る。最も好ましい候補者には「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)] &gt; 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] &gt; p[E,D] であれば、D候補者はE候補者より**良い**とみなす。

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

p[X,Y] &gt; p[Y,X] かつ p[Y,Z] &gt; p[Z,Y] ならば、p[X,Z] &gt; 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 となる。ペアに関する選好の全体像は以下のようになる。

右の図式は、最強の道を視覚的に把握しやすくしたもので、X から Y への矢印に d[X,Y] の値を付した有向グラフである。d[X,Y] &gt; 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 を比較すると、28 = p[A,B] &gt; p[B,A] = 25 であるので、シュルツ方式ではA候補者はB候補者より**良い**。別の例では、31 = p[E,D] &gt; p[D,E] = 24 であるので、E候補者はD候補者より**良い**。同様にして全ての候補者を比較すると、E &gt; A &gt; C &gt; B &gt; D となり、E が当選との結果を得る。言い方を変えれば、E は他の全てのX候補者に対して p[E,X] &gt; p[X,E] であるがゆえに当選した。

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


```python
# 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(''C''<sup>3</sup>)の時間計算量で解が求まる。（これにはd[*,*]を求める時間計算量を含んでおらず、最も簡単な方法で実装するなら、投票者の数を*V*とするとO(*VC*2)の時間計算量が必要である。）

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

シュルツ順位での同順位は、滅多にないとはいえ、可能性がない訳ではない。シュルツの元の論文は、無作為に選んだ投票者に従って同順位を解消する(必要に応じて繰り返す)ことを提案した。

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

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

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

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

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

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

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

## シュルツ方式の歴史
シュルツ方式は1997年にマルクス・シュルツにより開発された。初めて公のメーリングリストで1997年-1998年と2000年に討論された。その後シュルツ方式はSoftware in the Public Interest（2003年）、Debian（2003年）、Gentoo（2005年）、TopCoder（2005年）、ウィキメディア（2008年）、KDE（2008年）、Free Software Foundation Europe（2008年）、スウェーデン海賊党（2009年）、ドイツ海賊党（2010年）などで用いられている。フランス語版ウィキペディアではシュルツ方式は2005年に多数決で賛成された二つの候補者が多数いる場合の方式の一つであり、数回用いられている。

2011年、シュルツは学術誌*Social Choice and Welfare*でこの方式を発表した。

## シュルツ方式の利用

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

* Annodex協会
* Blitzed 
* BoardGameGeek
* Cassandra 
* Codex Alpe Adria 
* 海洋学単科大学
* ヨーク大学コンピューター学部門協会（HackSoc） 
* County Highpointers 
* Debian 
* Demokratische Bildung Berlin 
* Digital Freedom in Education and Youth 
* EnMasse Forums
* EuroBillTracker
* 欧州民主教育会議（EUDEC）
* Fair Trade Northwest 
* FFmpeg 
* Flemish Student Society of Leuven 
* Free Hardware Foundation of Italy 
* Free Software Foundation Europe (FSFE) 
* Gentoo Foundation 
* GNU Privacy Guard (GnuPG) 
* Gothenburg Hacker Space (GHS) 
* Graduate Student Organization at the State University of New York: Computer Science (GSOCS) 
* Haskell 
* Kanawha Valley Scrabble Club 
* KDE e.V. 
* キングマン会館
* ナイト財団
* Kumoricon
*システムアドミニストレーター連盟（LOPSA）
* Libre-Entreprise 
* Lumiera/Cinelerra
* Mathematical Knowledge Management Interest Group (MKM-IG) 
* Metalab
* Music Television（MTV） 
* Neo 
* netznetz
* Noisebridge
* North Shore Cyclists (NSC) 
* OpenStack 
* Park Alumni Society (PAS) 
* オーストラリア海賊党
* オーストリア海賊党
* ブラジル海賊党
* ドイツ海賊党
* ニュージーランド海賊党
* スウェーデン海賊党 
* スイス海賊党
* Pitcher Plant of the Month
* Pittsburgh Ultimate 
* RPMrepo 
* Sender Policy Framework (SPF) 
* Software in the Public Interest (SPI) 
* Squeak 
* 自由な文化のための学生
* Sugar Labs 
* TopCoder
* University of British Columbia Math Club 
* WikIAC 
* ウィキメディア財団 
* フランス語、ヘブライ語、ハンガリー語、ロシア語のウィキペディア

## 脚注

## 外部リンク

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

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

### 擁護者

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

### 本

* クリストフ・ベルガース（2009年）：**[https://books.google.co.jp/books?id=dccBaphP1G4C&pg=PA37&redir_esc=y&hl=ja 社会選択の数学：投票、代償、分配]**, SIAM, ISBN 0-89871-695-0
* サウル・シュタールとポール・E・ジョンソン（2006年）：**[https://books.google.co.jp/books?id=CMLL9sVGLb8C&pg=PA119&redir_esc=y&hl=ja 現代数学の理解]**, Sudbury:  Jones and Bartlett Publishers, ISBN 0-7637-3401-2
* ニコラウス・タイドマン（2006年）：**[https://books.google.co.jp/books?id=RN5q_LuByUoC&pg=PA228&redir_esc=y&hl=ja 集団の決定と投票：公共の選択のための可能性]**, Burlington: Ashgate, ISBN 0-7546-4717-X

### ソフトウェア

* ブラッド・ビーティーによるPython Vote Core
* ブレイク・クレトニーによるVoting Software Project
* マシュー・ゴールドスタインによるCondorcet with Dual Dropping Perl Scripts
* エリック・ゴアによるCondorcet Voting Calculator
* ベンジャミン・マコ・ヒルによるSelectricityとRubyVote https://web.mit.edu/newsoffice/2008/voting-tt0312.html http://labcast.media.mit.edu/?p=56
* アドリアン・ラングによる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 https://ballotpedia.org/wiki/index.php?title=Arizona_Competitive_Elections_Reform_Act_%282008%29 https://www.azcentral.com/members/Blog/PoliticalInsider/22368 https://www.ballot-access.org/2008/04/29/arizona-high-school-student-files-paperwork-for-initiatives-for-irv-and-easier-ballot-access/