シュルツェ法

シュルツ法( / ˈ ʃ ʊ l t s ə / ) は、ビートパス法とも呼ばれ、マルクス・シュルツが開発した、単一勝者の 順位付け投票ルールです。シュルツ法はコンドルセ補完法であり、多数派が好む候補者が存在する場合はその候補者を選出します。言い換えると、ほとんどの人がA をBより上位にランク付けした場合、A はBに勝ちます(可能な場合は常に)。シュルツ法は、間接的な勝利を使用して循環的な同点を解消します。アリスがボブに勝ち、ボブがチャーリーに勝った場合、アリスは (間接的に) チャーリーに勝つという考え方です。このような間接的な勝利は「ビートパス」と呼ばれます。

比例代表制には、シュルツェ STVと呼ばれる単記移譲式投票(STV) の変種も存在します。シュルツェ方式は、Debian、Ubuntu、Gentoo、海賊党政党など、多くの組織で使用されています。また、スコア投票を採用する前は、ウィキメディアでも使用されていました。

シュルツェ法では、同等の評価が認められる順位付け投票を使用します。シュルツェ法には、2 つの一般的な (同等の) 説明があります。

シュルツの方法の背後にある考え方は、アリスがボブに勝ち、ボブがチャーリーに勝った場合、アリスは「間接的に」チャーリーに勝つというものです。これらの連鎖した「ビート」のシーケンスは「ビートパス」と呼ばれます。

すべてのビートパスには特定の強度が割り当てられています。アリスからボブへのシングルステップのビートパスの強度は、アリスをボブより上位にランク付けする投票者の数に相当します。複数のビートで構成されるより長いビートパスの場合、ビートパスの強度は最も弱いリンク (つまり、勝利票数が最も少ないビート) と同じになります。

アリスのボブへの最強のビートパスが、ボブのアリスへの最強のビートパスすべてよりも強い場合、アリスはボブに対して「ビートパス勝利」したと言います。勝者は、他のすべての候補者に対してビートパス勝利した候補者です。

Markus Schulzeは、このビートパス勝利の定義が推移的であることを証明した。言い換えれば、アリスがボブに対してビートパス勝利を持ち、ボブがチャーリーに対してビートパス勝利を持つ場合、アリスはチャーリーに対してビートパス勝利を持つ。^{[1] ：§4.1}結果として、Schulze法はコンドルセ法であり、多数決ルールを任意の投票セットに完全に拡張します。

シュルツの勝者は、敗北ドロップ法を使用して反復的に構築することもできます。

1. すべての候補者をノードとして有向グラフを描き、エッジに勝者を支持する投票数のラベルを付けます。
2. 複数の候補者が残っている場合:
   • 候補者が同票かどうかを確認します（同票の場合は、無作為投票で同票を決定してください）。
   • 多数派が好むセット以外のすべての候補を排除します。
   • 結びついている部分に最も近いエッジを削除します。

勝者は手続きの最後に残った唯一の候補者です。

次の例では、45 人の有権者が 5 人の候補者をランク付けします。

まず、ペアワイズ選好を計算する必要があります。たとえば、AとB をペアワイズで比較すると、BよりAを好む投票者は5+5+3+7=20 人、AよりB を好む投票者は8+2+7+8=25 人います。したがって、およびです。ペアワイズ選好の完全なセットは次のようになります。 ${\displaystyle d[A,B]=20}$${\displaystyle d[B,A]=25}$

d[X, Y] のセルには、d[X, Y] > d[Y, X] の場合、明るい緑色の背景が表示されます。それ以外の場合は、背景は明るい赤色になります。ここでは、ペアワイズの違いだけを見ても、議論の余地のない勝者はいません。

次に、最も強いパスを特定する必要があります。最も強いパスを視覚化するために、ペアワイズ プリファレンスのセットが有向グラフの形式で右側の図に示されています。候補 X を表すノードから候補 Y を表すノードへの矢印には、d[X, Y] というラベルが付けられています。図が乱雑にならないように、d[X, Y] > d[Y, X] の場合のみ (つまり、明るい緑の背景の表のセル)、X から Y への矢印が描かれ、反対方向の矢印 (明るい赤の背景の表のセル) は省略されています。

最も強いパスの強度を計算する一例は、p[B, D] = 33 です。B から D への最も強いパスは、強度 33 の直接パス (B, D) です。ただし、p[A, C] を計算する場合、A から C への最も強いパスは強度 26 の直接パス (A, C) ではなく、強度 min(30, 28) = 28 の間接パス (A, D, C) です。パスの強度は、その最も弱いリンクの強度です。

次の表では、候補 X と候補 Y の各ペアについて、候補 X から候補 Y への最も強いパスが赤で示され、最も弱いリンクが下線で示されています。

これで、Schulze 法の出力を決定できます。たとえば、AとB を比較する場合、 であるため、Schulze 法では候補A が候補Bよりも優れています。別の例として、 であるため、候補 E は候補 D よりも優れています。このように続けると、結果は Schulze ランキングとなり、E が勝ちます。言い換えると、他のすべての候補 X に対して E が勝ちます。${\displaystyle (28=)p[A,B]>p[B,A](=25)}$${\displaystyle (31=)p[E,D]>p[D,E](=24)}$${\displaystyle E>A>C>B>D}$${\displaystyle p[E,X]\geq p[X,E]}$

Schulze 法を実装する上で難しい唯一のステップは、最も強いパスの強度を計算することです。ただし、これはグラフ理論ではよく知られた問題であり、最も広いパス問題と呼ばれることもあります。したがって、強度を計算する簡単な方法の 1 つは、 Floyd-Warshall アルゴリズムの変形です。次の疑似コードは、このアルゴリズムを示しています。

# 入力: d[i,j]、候補者iを候補者jより好む有権者の数。
# 出力: p[i,j]、候補iから候補jへの最も強いパスの強度。

i は 1 から C まで
    jは1からCまで
        i ≠ j ならば
            d[i,j] > d[j,i]ならば
                p[i,j] := d[i,j]
            それ以外
                p[i,j] := 0

i は 1 から C まで
    jは1からCまで
        i ≠ j ならば
            kは1からCまで
                i ≠ k かつ j ≠ k ならば
                    p[j,k] := 最大値 (p[j,k]、最小値 (p[j,i]、p[i,k]))

このアルゴリズムは効率的で、実行時間は O( C ³ )です。ここで、Cは候補の数です。

ユーザーの好みが同点であることを許容する場合、シュルツ法の結果は当然のことながら、d[*,*]の定義でこれらの同点がどのように解釈されるかによって決まります。自然な選択肢としては、d[A, B]が、AをBより厳密に好む投票者の数（A>B）を表すか、（A >Bの投票者）から（B>Aの投票者）を引いた差を表すかの2つがあります。しかし、 dがどのように定義されても、シュルツのランキングには循環がなく、dが一意であると仮定すると同点はありません。^[2]

シュルツのランキングで同点が出る可能性は低いが、可能性はある。シュルツの元の論文では、同点の場合は無作為な投票で決定することを推奨していた。^[2]

Schulze 法の勝者を示す別の方法があります。この方法は、ここで説明した他の方法と同等ですが、計算ではなく、人間が手順を実行するときに 視覚的に明らかになる手順の重要性に合わせてプレゼンテーションが最適化されています。

1. 上記の例で使用されているような、「ペアワイズ プリファレンスのマトリックス」と呼ばれる結果表を作成します。次に、すべての正の数字は、その行の候補者のペアワイズ勝利 (緑色でマーク)、同点はゼロ、敗北は負 (赤色でマーク) です。候補者を、脱落までの期間順に並べます。
2. ライン上に赤がない候補者がいる場合、その候補者が勝ちます。
3. それ以外の場合は、左上隅のシュワルツ集合の周りに四角いボックスを描きます。これは、円の外側の誰にも負けない候補者の最小限の「勝者のサークル」として説明できます。ボックスの右側に赤がないことに注目してください。これは勝者のサークルであることを意味します。また、ボックス内では、より小さな勝者のサークルを生成する並べ替えが不可能であることに注意してください。
4. 箱の外側のテーブルの部分をすべて切り取ります。
5. それでも、赤が付いていない候補者がいない場合は、何か妥協する必要があります。すべての候補者はどこかの選挙で負けており、私たちが最も許容できる敗北は、敗者が最も多くの票を獲得した敗北です。したがって、最も高い数字 (差で判断する場合、最もマイナスが少ない) の赤いセルを取り、それを緑 (または赤以外の色) にして、手順 2 に戻ります。

これは上記の例から作成されたマージン テーブルです。デモンストレーションの目的で使用されている順序の変更に注意してください。

最初のドロップ（A が E に 1 票差で敗北）は、シュワルツ セットの縮小には役立ちません。

したがって、2 番目のドロップ (E が 3 票差で C に負ける) に直接進み、明確な行を持つ勝者 E が表示されます。

この方法は、行と列の両方で候補の順序を便利かつ確実に並べ替えることができ、常に両方で同じ順序が使用されるように表を作り直す場合に、結果の計算にも使用できます。

シュルツェ法は次の基準を満たします。

シュルツェ法はコンドルセ基準を満たしているため、次の基準には自動的に適合しません。

• 参加^{[2] : §3.4}
• 一貫性
• 埋葬に対する無敵性
• 後で害はない

同様に、シュルツ法は独裁制ではなく、順位付け投票システム（評価されていない）であるため、アローの定理によれば、無関係な選択肢の独立性は満たされず、まれにスポイラー効果の影響を受けやすくなる可能性がある。シュルツ法は、ペイトン・ヤングの無関係な選択肢の局所的独立性基準も満たさない。

次の表は、シュルツ方式と他の単独勝者選挙方式を比較したものです。

ランク付けされたペアは、シュルツのルールに非常によく似た別のコンドルセ法であり、通常は同じ結果を生成します。ただし、わずかな違いがあります。ビートパス法とランク付けされたペアの主な違いは、シュルツはミニマックスに近い動作を維持することです。候補者の集合Xのミニマックススコアが、候補者 B ∈ Xに対する候補者 A ∉ Xの最強のペアワイズ勝利の強さであるとします。すると、ランク付けされたペアではなく、シュルツ法では、勝者は常に最小のミニマックススコアを持つ集合の候補者になることが保証されます。^{[2] : §4.8}これは、シュルツ法が勝者を決定するときに逆転しなければならない最大多数を最小化するという意味です。

一方、ランク付けペアは、順位を決定するために逆転しなければならない最大多数を最小化します。^[5]言い換えれば、ランク付けペアとシュルツ法が異なる順位を出した場合には、2つの順位が一致しない多数については、シュルツ法の順序はランク付けペアの順序よりも大きな多数を逆転させます。

^{シュルツ法は1997年にマルクス・シュルツによって開発されました。この方法は1997年から1998年[6]}と2000年に公開メーリングリストで初めて議論されました。 ^[7] 2011年にシュルツは学術誌「Social Choice and Welfare」でこの方法を発表しました。^[2]

シュルツェ方式は、スペインのシッラ市がすべての住民投票に採用している。^{[8] [9] [10] [11]}また、イタリアのトリノ市とサン・ドナ・ディ・ピアーヴェ市、ロンドンのサザーク区でもWeGovNowプラットフォームを通じて採用されており、WeGovNowプラットフォームではLiquidFeedback意思決定ツールが使用されている。^{[12] [13]}

シュルツェ法は、スウェーデン海賊党（2009年）^[14]とドイツ海賊党（2010年）によって採用されました。^[15]アメリカ民主社会主義者のアイダホ州ボイシ支部は2018年2月にこの方式を選択し、3月に行われた初の特別選挙に臨みました。^[16]

• カンポバッソ、^[17] フォンディ、^[18] モンテ・コンパトリ、^[19] モンテムルロ、^[20] ペスカーラ、^{[21] 、}およびサン・チェザーレオ^[22]の五つ星運動
• オーストラリアの海賊党^[23] 、オーストリア^[24] 、ベルギー^[25] 、ブラジル、ドイツ^[15] 、アイスランド[ ^26] 、イタリア^[27] 、オランダ^[28]、 スウェーデン[ ^14] 、スイス^[29]、アメリカ合衆国^[30]
• サステナブルユニオン^[31]
• ボルトヨーロッパ^[32]

• AEGEE – ヨーロッパ学生フォーラム^[33]
• Club der Ehemaligen der Deutschen SchülerAkademien e. V. ^[34]
• パリ高等師範学校の関連学生自治^[35]
• フランダース工学学生協会ルーヴェン^[36]
• ニューヨーク州立大学大学院生組織：コンピュータサイエンス（GSOCS）^[37]
• ヒレガス・パーカー・ハウス^[38]
• キングマンホール^[39]
• KGIミネルバスクール学生協会^[40]
• ノースウェスタン大学学生自治会^[41]
• フライブルク大学学生自治会^[42]
• カイザースラウテルン大学コンピュータサイエンス学部学生自治会^[43]

これは、電気電子技術者協会、計算機協会、USENIX ^[要出典]によってHotCRP 決定ツールを通じて使用されています。^{[専門用語]}

現在、Schulze メソッドを使用している組織は次のとおりです。

ウィキメディア・コモンズには、シュルツェ法に関連するメディアがあります。

• マルクス・シュルツェによるシュルツェ投票法
• ヒューバート・ブレイ著『シュルツメソッド』
• シュピール理論(ドイツ語)ベルンハルト・ネーベル著
• ロブ・ローリング著『正確な民主主義』
• クリストフ・ボルガース（2009）「社会選択の数学：投票、補償、分割」SIAM、ISBN 0-89871-695-0 
• ニコラウス・タイドマン（2006年）「集団決定と投票：公共選択の可能性」バーリントン：アッシュゲート、ISBN 0-7546-4717-X 
• Public Software Group による preftools
• アリゾナ州コンドルセ支持者投票順位
• Condorcet PHP コマンドライン アプリケーションおよびPHP ライブラリ。Schulzeを含む複数の Condorcet メソッドをサポートします。
• Javaでの実装
• Rubyでの実装
• Python 2での実装
• Python 3での実装