Schulze method

The Schulze method ( ), also known as the beatpath method, is a single winner ranked-choice voting rule developed by Markus Schulze. The Schulze method is a Condorcet completion method, which means it will elect a majority-preferred candidate if one exists. In other words, if most people rank A above B, A will defeat B (whenever this is possible). Schulze's method breaks cyclic ties by using indirect victories. The idea is that if Alice beats Bob, and Bob beats Charlie, then Alice (indirectly) beats Charlie; this kind of indirect win is called a "beatpath". The Schulze method is used by several organizations including Debian, Ubuntu, Gentoo, Pirate Party political parties and many others. It was also used by Wikimedia prior to their adoption of score voting.

The Schulze method ( ), also known as the beatpath method, is a single winner ranked-choice voting rule developed by Markus Schulze. The Schulze method is a Condorcet completion method, which means it will elect a majority-preferred candidate if one exists. In other words, if most people rank A above B, A will defeat B (whenever this is possible). Schulze's method breaks cyclic ties by using indirect victories. The idea is that if Alice beats Bob, and Bob beats Charlie, then Alice (indirectly) beats Charlie; this kind of indirect win is called a "beatpath". The Schulze method is used by several organizations including Debian, Ubuntu, Gentoo, Pirate Party political parties and many others. It was also used by Wikimedia prior to their adoption of score voting. The pairwise preferences have to be computed first. For example, when comparing and pairwise, there are voters who prefer to , and voters who prefer to . So d[A, B] = 20 and d[B, A] = 25 . The full set of pairwise preferences is: labeled with pairwise preferences d[*, *] ]] The cells for d[X, Y] have a light green background if d[X, Y] > d[Y, X], otherwise the background is light red. There is no undisputed winner by only looking at the pairwise differences here. Now the strongest paths have to be identified. To help visualize the strongest paths, the set of pairwise preferences is depicted in the diagram on the right in the form of a directed graph. An arrow from the node representing a candidate X to the one representing a candidate Y is labelled with d[X, Y]. To avoid cluttering the diagram, an arrow has only been drawn from X to Y when d[X, Y] > d[Y, X] (i.e. the table cells with light green background), omitting the one in the opposite direction (the table cells with light red background). One example of computing the strongest path strength is p[B, D] = 33: the strongest path from B to D is the direct path (B, D) which has strength 33. But when computing p[A, C], the strongest path from A to C is not the direct path (A, C) of strength 26, rather the strongest path is the indirect path (A, D, C) which has strength min(30, 28) = 28. The strength of a path is the strength of its weakest link. For each pair of candidates X and Y, the following table shows the strongest path from candidate X to candidate Y in red, with the weakest link underlined. Now the output of the Schulze method can be determined. For example, when comparing and , since (28 =) p[A,B] > p[B,A] (= 25) , for the Schulze method candidate is better than candidate . Another example is that (31 =) p[E,D] > p[D,E] (= 24) , so candidate E is better than candidate D. Continuing in this way, the result is that the Schulze ranking is E > A > C > B > D , and wins. In other words, wins since p[E,X] \ge p[X,E] for every other candidate X. Computation of the strongest path strengths is the widest path problem. It is a variation of the all-pairs shortest path problem and it can be solved via a variant of the Floyd–Warshall algorithm. The following pseudocode illustrates the algorithm. Input: d[i,j], the number of voters who prefer candidate i to candidate j. Output: p[i,j], the strength of the strongest path from candidate i to candidate j. for i from 1 to C for j from 1 to C if i ≠ j then p[i,j] := d[i,j] - d[j,i] for k from 1 to C for i from 1 to C if i ≠ k then for j from 1 to C if j ≠ k and j ≠ i then p[i,j] := max (p[i,j], min (p[i,k], p[k,j])) This algorithm is efficient and has running time O(C 3 ) where C is the number of candidates. The Schulze Method by Hubert Bray Spieltheorie by Bernhard Nebel Accurate Democracy by Rob Loring Christoph Börgers (2009), Mathematics of Social Choice: Voting, Compensation, and Division, SIAM, Nicolaus Tideman (2006), Collective Decisions and Voting: The Potential for Public Choice, Burlington: Ashgate, preftools by the Public Software Group Arizonans for Condorcet Ranked Voting Condorcet PHP Command line application and PHP library, supporting multiple Condorcet methods, including Schulze. Implementation in Java Implementation in Ruby Implementation in Python 2 Implementation in Python 3

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375500385 under CC BY-SA 4.0; modifications have been made.