Schulze Method - Beat-path Condorcet-consistent rank aggregation

Overview

The Schulze method is Condorcet-consistent (elects Condorcet winner if one exists), clone-independent, and runs in O(m³) time (Floyd-Warshall). It is widely used in real elections (Debian, Wikimedia). The beat-path strength p[i,k] measures the strongest indirect evidence that A_i should beat A_k.

Output

rank position, higher is better

Data

Crisp, complete rank

Size

2+ alternatives, 3-12 criteria works best

Used for

Rank aggregation, social choice, preference fusion

How it works

1. 1

   Collect K expert rankings R_k.

   $$\mathcal{R}=\{R_1,\dots ,R_K\}$$

   Schulze 2011, p.273 Sec.2

2. 2

   Pairwise preference matrix d[a,b] = #{k: a ≻_k b}.

   $$d[a,b]=\sum _{k=1}^{K}1[a{\succ }_{k}b]$$

   Schulze 2011, p.273 Eq.(1)

3. 3

   Strongest path p[a,b] via widest-path Floyd-Warshall.

   $$p[a,b]=\underset{\text{paths}a\to b}{\max }\underset{(u,v)\in \text{path}}{\min }d[u,v]$$

   Schulze 2011, p.274 Eq.(2)

4. 4

   Schulze winner: a beats b iff p[a,b] > p[b,a]; derive ranking.

   $$a{\succ }_{S}b⟺p[a,b]>p[b,a]$$

   Schulze 2011, p.275 Theorem 1

Fits when / Look elsewhere when

Assumptions to verify

• Input is a rank matrix (1=best, m=worst per voter)
• Each voter ranks all alternatives

Edge cases and pitfalls

• Condorcet cycles can still produce equal p[i,k] and p[k,i] for some pairs - these are true ties in the Schulze ordering.

How to cite