シュルツ方式

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] > 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に ...

最強の道

	... Aに	... Bに	... Cに	... Dに	... Eに
Aから ...		A-(30)-D-(28)-C-(29)-B	A-(30)-D-(28)-C	A-(30)-D	A-(30)-D-(28)-C-(24)-E	Aから ...
Bから ...	B-(25)-A		B-(33)-D-(28)-C	B-(33)-D	B-(33)-D-(28)-C-(24)-E	Bから ...
Cから ...	C-(29)-B-(25)-A	C-(29)-B		C-(29)-B-(33)-D	C-(24)-E	Cから ...
Dから ...	D-(28)-C-(29)-B-(25)-A	D-(28)-C-(29)-B	D-(28)-C		D-(28)-C-(24)-E	Dから ...
Eから ...	E-(31)-D-(28)-C-(29)-B-(25)-A	E-(31)-D-(28)-C-(29)-B	E-(31)-D-(28)-C	E-(31)-D		Eから ...
	... Aに	... Bに	... Cに	... Dに	... Eに

閉じる

これでシュルツ方式による結果を確定できる。例えば 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(C³)の時間計算量で解が求まる。（これにはd[*,*]を求める時間計算量を含んでおらず、最も簡単な方法で実装するなら、投票者の数をVとするとO(VC²)の時間計算量が必要である。）

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

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

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

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

シュルツ方式は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]。

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