シュルツ方式

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

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

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

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

1. シュルツ方式に関する解説
---------------

1.1. 投票用紙
---------

シュルツ方式に対する投票形式は、他の選好投票における単議席単票制と同じである。各々の投票者は、候補者たちに対して選好の順序を付けなければならない。典型的には、投票者は以下の通りに投票用紙に選好を明記する。投票用紙には全ての候補者が一覧になっており、投票者は番号を用いて選好順にこの一覧に番号を振る。最も好ましい候補者には「1」を、次に好ましい候補者に「2」を、以下も順に番号を付ける。投票者には次のことも許されている。

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

1.2. シュルツ方式
-----------

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

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

C = X かつ C = Y
任意の i = 1, …, n-1 に対して、d[C,C] > d[C,C]
任意の i = 1, …, n-1 に対して、d[C,C] ≥ 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] であることが証明できる§4.1}}。これは、上記の「より良い」という関係が推移関係であることを意味し、他の全ての候補者Eに対して p[D,E] ≥ p[E,D] を満たす候補者Dが少なくとも一人はいることが保証される。

2. 例
----

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

5 ACBED
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] > d[Y,X] ならば、d[Y,X] の値は選挙の結果に影響を与えないため、図には d[X,Y] の値のみ記す。

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

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

これでシュルツ方式による結果を確定できる。例えば 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] であるがゆえに当選した。

3. 実装
-----

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

Input: d[i,j]
Output: p[i,j]for i from 1 to C for j from 1 to C if  then if  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  then for k from 1 to C if  then p[j,k] := max  )<WtXmlEndTag />

このアルゴリズムは優れていて、候補者数を//C//とするとOの時間計算量で解が求まる。

4. 同順位と別の実装
-----------

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

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

シュルツ方式の勝者を選出する別のやや手間のかかる方法は次のとおりである。

全ての候補者と、候補者間のあり得る全ての線の完全な有向グラフを描く。
[a]シュワルツ集合に含まれない候補者を全て除外し、[b]最弱のリンクを除外する。これらを繰り返す。
最後まで除外されなかった候補者が勝者である。

5. 基準を満たした例と満たしていない例
--------------------

5.1. 満たした基準
-----------

シュルツ方式は下記の基準を満たしている。

無制限領域
非賦課
非独裁制
パレート基準
単一強健基準
多数派基準
多数派敗北基準
コンドルセ基準
コンドルセ敗北基準
シュワルツ基準
スミス基準
スミスの優位選択の独立
相互多数派基準
クローンの独立
逆行調和
単一付加
単一付加投票
分解性基準
多項式時間
当選票がd[X,Y]に使えるなら、ウッドールの過半数基準
得票差がd[X,Y]に使えるなら、相称的完成

5.2. 満たしていない基準
--------------

シュルツ方式はコンドルセ基準を満たしているので、自動的に下記の基準は満たしていない。

参加
一貫性
妥協する強み
葬る強み
後日無害同様にシュルツ方式は独裁制ではなく満場一致の投票で一致しているので、アローの不可能性定理はこの方式が基準を満たしていないことを暗示している。

無関係な選択肢の独立

5.3. 比較表
--------

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

シュルツ方式と順位づけられた組み合わせの主な違いは、この例で見ることができる。

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

6. シュルツ方式の歴史
------------

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

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

7. シュルツ方式の利用
------------

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

Annodex協会
[1]
BoardGameGeek
Cassandra
[2]
海洋学単科大学
ヨーク大学コンピューター学部門協会
[3]
Debian
[4]
[5]
[6]
EuroBillTracker
欧州民主教育会議
[7]
FFmpeg
[8]
[9]
Free Software Foundation Europe 
Gentoo Foundation
GNU Privacy Guard 
[10]
[11]
Haskell
[12]
KDE e.V.
キングマン会館
ナイト財団
Kumoricon
システムアドミニストレーター連盟
[13]
Lumiera/Cinelerra
[14]
Metalab
Music Television
Neo
netznetz
Noisebridge
[15]
OpenStack
[16]
オーストラリア海賊党
オーストリア海賊党
ブラジル海賊党
ドイツ海賊党
ニュージーランド海賊党
スウェーデン海賊党
スイス海賊党
[17]
[18]
[19]
Sender Policy Framework 
Software in the Public Interest 
Squeak
自由な文化のための学生
Sugar Labs
TopCoder
[20]
[21]
ウィキメディア財団
フランス語、ヘブライ語、ハンガリー語、ロシア語のウィキペディア

8. 脚注
-----

9. 外部リンク
--------

9.1. 一般
-------

マルクス・シュルツによる[22]

9.2. チュートリアル
------------

クリストフ・ギーゼルによる[23]
ヨハネス・グラブマイアーによる[24]
ベルンハルト・ネーベルによる[25]
シュトゥットガルト大学による[26]

9.3. 擁護者
--------

ロブ・レグランドによる[27]
ロブ・ローリングによる[28]
ケヴィン・ヴェンスケによる[29]
ヨヘン・フォスによる[30]
[31]

9.4. 本
------

クリストフ・ベルガース：[32], SIAM, ISBN 0-89871-695-0
サウル・シュタールとポール・E・ジョンソン：[33], Sudbury: Jones and Bartlett Publishers, ISBN 0-7637-3401-2
ニコラウス・タイドマン：[34], Burlington: Ashgate, ISBN 0-7546-4717-X

9.5. ソフトウェア
-----------

ブラッド・ビーティーによる[35]
ブレイク・クレトニーによる[36]
マシュー・ゴールドスタインによる[37]
エリック・ゴアによる[38]
ベンジャミン・マコ・ヒルによる[39]と[40] [41] [42]
アドリアン・ラングによる[43]
ロブ・ランフィアーによる[44]
ロブ・レグランドによる[45]
エヴァン・マーティンによる[46]
アンドリュー・マイヤーズによる[47]
ブライアン・オルソンによる[48]
ジェフリー・オニールによる[49]
[50]
公共ソフトウェア集団による[51]
[52]

9.6. 法制化事業
----------

[53] [54] [55] [56]