Schulze STV
Encyclopedia
Schulze STV is a draft preference voting system designed to achieve proportional representation
. It was invented by Markus Schulze who developed the Schulze method
for resolving ties under the Condorcet method
. It is similar to CPO-STV
in that it compares possible winning sets of candidate outcomes pairwise and selects the Condorcet winner. However, unlike CPO-STV, it only compares outcomes that differ by a single candidate. Comparing outcomes that differ by more than one candidate is accomplished by finding the strongest path.
The method is based on Schulze's investigations into vote management and free riding. When a voter prefers a very popular candidate, there is a strategic advantage to the voter if he gives his first choice to a candidate who is unlikely to win (Woodall free riding) or if he doesn't include his preferred candidate in his rankings at all (Hylland free riding). Schulze showed that vote management is merely party coordination of these free rider effects.
Schulze STV is resistant to both types of free riding. However, Hylland free riding is impossible to completely defend against. Schulze creates a criterion called "weak invulnerability to Hylland free riding". A method meets this criterion if it is invulnerable to Hylland free riding, except in cases where the Droop proportionality criterion would have to be violated. Schulze STV meets this criterion.
Assuming that there are S seats to be filled, the two outcomes are considered to be (A1,A2,...,AS) and (A2,...,AS,B).
The ballots are then assigned to one of the candidates in (A1,A2,...,AS). However, a ballot may only be assigned to Ai if the voter prefers Ai to B. This means that ballots which prefer B to all the candidates in (A1,A2,...,AS) will remain unassigned. The ballots are assigned in order to maximise the smallest number of ballots held by any candidate in (A1,A2,...,AS).
The number of votes in favour of the proposal that (A1,A2,...,AS) beats (A2,...,AS,B) is equal to the smallest number of ballots held by any candidate in (A1,A2,...,AS).
To determine the result of the comparison, the reverse comparison must also be performed. This will give the number of votes against the proposal that (A1,A2,...,AS) beats (A2,...,AS,B), i.e. the number of votes in favour of the proposal that (A2,...,AS,B) beats (A1,A2,...,AS).
For example, if there is a path A,B,C and D, and
A beats B is supported by 100 votes,
B beats C is supported by 80 votes,
C beats D is supported by 110 votes,
then the path ABCD will be supported by 80 votes as it is the lowest.
All paths from A to D would be examined and the one with the largest support will be considered the support for the proposal that A beats D. Similarly, the paths from D to A would be examined and the strongest path would be considered the support for the proposal that D beats A.
There are 90 voters and their preferences are
2. Andrea is immediately declared elected and her surplus is distributed
Brad is thus elected.
Under Schulze STV, it is certain that any candidate with more than the Droop quota of first preferences will be elected. This means that Andrea is certain to be elected. This means that there are only 2 possible outcomes.
These two outcomes will be compared.
Support for (Andrea,Carter) beats (Andrea,Brad*)
Brad is test candidate.
12 prefer Andrea (but not Carter) to Brad (assign to Andrea)
0 prefer Carter (but not Andrea) to Brad
51 prefer Both to Brad (assign 19.5 to Andrea and 31.5 to Carter)
27 prefer Brad to Both (These cannot be assigned to any group)
The 51 ballots that prefer Both to Brad were assigned so that both Andrea and Carter have the same number of ballots. This means that the lower of the 2 is maximised.
Both groups have 31.5 ballots in them.
Support for (Andrea,Brad) beats (Andrea,Carter*)
Carter is the test candidate.
38 prefer Andrea (but not Brad) to Carter (assign to Andrea)
27 prefer Brad (but not Andrea) to Carter (assign to Brad)
12 prefer both to Carter (assign 0.5 to Andrea and 11.5 to Brad)
Both groups have 38.5 ballots in them and this maximises the smallest group size.
This means that (Andrea,Brad) beats (Andrea,Carter) by 38.5 votes to 31.5.
Since (Andrea,Brad) beats (Andrea,Carter), (Andrea,Brad) is the Condorcet winner. This means that Andrea (Y) and Brad (P) are the winners. This is the same result as standard PR-STV.
2. Andrea is immediately declared elected and her surplus is distributed
Carter is thus elected.
The elected candidates are Andrea (Y) and Carter (Y). This means that vote management has been successful. The Yellow Party wins both seats instead of just one and the Purple Party wins no seats.
Under Schulze STV, it is certain that any candidate with more than the Droop quota in the first preferences will be elected. This means that Andrea is certain to be elected as she received 38 votes. This means that there are only 2 possible outcomes
These two outcomes will be compared.
Support for (Andrea,Carter) beats (Andrea,Brad*)
Brad is the test candidate.
12 prefer Andrea (but not Carter) to Brad (assign to Andrea)
0 prefer Carter (but not Andrea) to Brad
51 prefer Both to Brad (assign 19.5 to Andrea and 31.5 to Carter)
27 prefer Brad to Both (These cannot be assigned to any group)
Both groups have 31.5 ballots in them.
Support for (Andrea,Brad) beats (Andrea,Carter*)
Carter is the test candidate.
26 prefer Andrea (but not Brad) to Carter (assign to Andrea)
27 prefer Brad (but not Andrea) to Carter (assign to Brad)
12 prefer both to Carter (assign 6.5 to Andrea and 5.5 to Brad)
Both groups have 32.5 ballots in them and this maximises the smallest group size.
This means that (Andrea,Brad) beats (Andrea,Carter) by 32.5 votes to 31.5.
Since (Andrea,Brad) beats (Andrea,Carter), (Andrea,Brad) is the Condorcet winner. This means that Andrea (Y) and Brad (P) are the winners.
Thus, unlike standard PR-STV, Schulze STV resisted the effects of vote management.
, it doesn't suffer from defects caused by sequential exclusions. In addition, the number of pairwise comparisons are greatly reduced, since Schulze STV only has to compare outcomes that differ by one candidate, unlike CPO-STV which must compare all possible pairwise comparisons.
Even when the Yellow Party instructed all of its supporters to top rank Carter, it didn't result in Carter taking the 2nd seat.
('First-Past-the-Post') system and Instant Run-Off Voting. Schulze STV has additional resistance to forms of tactical voting which are specific to single transferable voting methods.
However, all forms of STV are vulnerable to some degree of tactical voting because they lack monotonicity
. This means that it is sometimes possible to benefit a candidate by ranking them lower than one's true order of preference, or to harm a candidate by ranking them higher.
PR-STV methods which make use of Meek's Method are resistant to Woodall Free Riding, but are still vulnerable to Hylland Free Riding. Schulze's method is not vulnerable to Hylland Free Riding, except where necessary in order to meet the Droop proportionality criterion.
A method which doesn't meet the Droop proportionality criterion has the potential to give disproportional results. Thus, Schulze STV can be considered invulnerable to Hylland Free Riding to as great an extent possible, subject to actually being a proportional representation method.
In addition to the voting system criteria passed by all STV methods, Schulze STV satisfies Dummett's
Proportionality for Solid Coalitions
criterion.
However, with respect to calculating an election result, Schulze STV is significantly more complex than standard PR-STV. Even though it is less complex than CPO-STV
, for large scale elections, it would still be necessary for the results to be calculated by computer. Even then, computing the result would be difficult in some cases: Schulze STV does not have polynomial runtime.
Proportional representation
Proportional representation is a concept in voting systems used to elect an assembly or council. PR means that the number of seats won by a party or group of candidates is proportionate to the number of votes received. For example, under a PR voting system if 30% of voters support a particular...
. It was invented by Markus Schulze who developed the Schulze method
Schulze method
The Schulze method is a voting system developed in 1997 by Markus Schulze that selects a single winner using votes that express preferences. The method can also be used to create a sorted list of winners...
for resolving ties under the Condorcet method
Condorcet method
A Condorcet method is any single-winner election method that meets the Condorcet criterion, which means the method always selects the Condorcet winner if such a candidate exists. The Condorcet winner is the candidate who would beat each of the other candidates in a run-off election.In modern...
. It is similar to CPO-STV
CPO-STV
CPO-STV, or the Comparison of Pairs of Outcomes by the Single Transferable Vote, is a preference voting system designed to achieve proportional representation. It is a highly sophisticated variant of the Single Transferable Vote system, designed to overcome some of that system's perceived...
in that it compares possible winning sets of candidate outcomes pairwise and selects the Condorcet winner. However, unlike CPO-STV, it only compares outcomes that differ by a single candidate. Comparing outcomes that differ by more than one candidate is accomplished by finding the strongest path.
The method is based on Schulze's investigations into vote management and free riding. When a voter prefers a very popular candidate, there is a strategic advantage to the voter if he gives his first choice to a candidate who is unlikely to win (Woodall free riding) or if he doesn't include his preferred candidate in his rankings at all (Hylland free riding). Schulze showed that vote management is merely party coordination of these free rider effects.
Schulze STV is resistant to both types of free riding. However, Hylland free riding is impossible to completely defend against. Schulze creates a criterion called "weak invulnerability to Hylland free riding". A method meets this criterion if it is invulnerable to Hylland free riding, except in cases where the Droop proportionality criterion would have to be violated. Schulze STV meets this criterion.
Voting
Each voter ranks the candidates in order of preference. For example:- Andrea
- Carter
- Brad
Pairwise Comparisons of results
Schulze STV performs comparisons on every possible outcome of the election in order to find the set of winners it considers the best. However, it only compares outcomes that differ by one winner directly. Outcomes that differ by more than one winner are compared by finding the strongest path between the two outcomes. The outcome, if one exists, that beats all other outcomes pairwise is declared the winning outcome. Otherwise, a Condorcet completion method is required to break the tie.Finding the pairwise winner when the results differ by only one candidate
When two outcomes are compared one against another a special method is used to give each a score and so determine which of the two is the winner.Assuming that there are S seats to be filled, the two outcomes are considered to be (A1,A2,...,AS) and (A2,...,AS,B).
The ballots are then assigned to one of the candidates in (A1,A2,...,AS). However, a ballot may only be assigned to Ai if the voter prefers Ai to B. This means that ballots which prefer B to all the candidates in (A1,A2,...,AS) will remain unassigned. The ballots are assigned in order to maximise the smallest number of ballots held by any candidate in (A1,A2,...,AS).
The number of votes in favour of the proposal that (A1,A2,...,AS) beats (A2,...,AS,B) is equal to the smallest number of ballots held by any candidate in (A1,A2,...,AS).
To determine the result of the comparison, the reverse comparison must also be performed. This will give the number of votes against the proposal that (A1,A2,...,AS) beats (A2,...,AS,B), i.e. the number of votes in favour of the proposal that (A2,...,AS,B) beats (A1,A2,...,AS).
Finding the pairwise winner when the results differ by more than one candidate
When two results differ by more than one candidate, a path must be determined that leads from one result to the other. The strength of a path is equal to the weakest link along the path.For example, if there is a path A,B,C and D, and
A beats B is supported by 100 votes,
B beats C is supported by 80 votes,
C beats D is supported by 110 votes,
then the path ABCD will be supported by 80 votes as it is the lowest.
All paths from A to D would be examined and the one with the largest support will be considered the support for the proposal that A beats D. Similarly, the paths from D to A would be examined and the strongest path would be considered the support for the proposal that D beats A.
Scenario
Imagine an election in which there are two seats to be filled and three candidates, Andrea and Carter (who represent the Yellow Party) and Brad (who represents the Purple Party). Andrea is a very popular candidate and has her own supporters who aren't Yellow Party supporters. It is assumed that the Yellow Party can influence their own supporters, but not Andrea's supporters.There are 90 voters and their preferences are
| Andrea's Supporters |
Yellow Party Supporters |
Purple Party Supporter |
||
| 12 | 26 | 12 | 13 | 27 |
|
|
|
|
|
Count under traditional STV
1. The initial tallies are:- Andrea (Y): 50
- Carter (Y): 13
- Brad (P): 27
2. Andrea is immediately declared elected and her surplus is distributed
- Andrea (Y): 50 -20 = 30
- Carter (Y): 13 +15 = 28
- Brad (P): 27 +5 = 32
Brad is thus elected.
Count under Schulze STV
There are three possible outcomes (or sets of winners) in the election:- A. Andrea and Carter.
- B. Andrea and Brad.
- C. Carter and Brad.
Under Schulze STV, it is certain that any candidate with more than the Droop quota of first preferences will be elected. This means that Andrea is certain to be elected. This means that there are only 2 possible outcomes.
- A. Andrea and Carter.
- B. Andrea and Brad.
These two outcomes will be compared.
Comparison of A and B
Support for (Andrea,Carter) beats (Andrea,Brad*)
Brad is test candidate.
12 prefer Andrea (but not Carter) to Brad (assign to Andrea)
0 prefer Carter (but not Andrea) to Brad
51 prefer Both to Brad (assign 19.5 to Andrea and 31.5 to Carter)
27 prefer Brad to Both (These cannot be assigned to any group)
The 51 ballots that prefer Both to Brad were assigned so that both Andrea and Carter have the same number of ballots. This means that the lower of the 2 is maximised.
Both groups have 31.5 ballots in them.
Support for (Andrea,Brad) beats (Andrea,Carter*)
Carter is the test candidate.
38 prefer Andrea (but not Brad) to Carter (assign to Andrea)
27 prefer Brad (but not Andrea) to Carter (assign to Brad)
12 prefer both to Carter (assign 0.5 to Andrea and 11.5 to Brad)
Both groups have 38.5 ballots in them and this maximises the smallest group size.
This means that (Andrea,Brad) beats (Andrea,Carter) by 38.5 votes to 31.5.
Result
Since (Andrea,Brad) beats (Andrea,Carter), (Andrea,Brad) is the Condorcet winner. This means that Andrea (Y) and Brad (P) are the winners. This is the same result as standard PR-STV.
Resistance to Vote Management
Vote Management is where a party instructs its voters not to rank a popular party candidate first choice. This means that instead of voting their true preferences, the Yellow Party's leaders instruct their supporters to vote for Carter as their first choice (and then Andrea). This changes the ballots cast.| Andrea's Supporters |
Yellow Party Supporters |
Purple Party Supporter |
||
| 12 | 26 | 12 | 13 | 27 |
|
|
|
|
|
Count under traditional STV
1. The initial tallies are:- Andrea (Y): 38
- Carter (Y): 25
- Brad (P): 27
2. Andrea is immediately declared elected and her surplus is distributed
- Andrea (Y): 38-8 = 30
- Carter (Y): 25+5.5 = 30.5
- Brad (P): 27+2.5 = 29.5
Carter is thus elected.
Result
The elected candidates are Andrea (Y) and Carter (Y). This means that vote management has been successful. The Yellow Party wins both seats instead of just one and the Purple Party wins no seats.
Count under Schulze STV
There are three possible outcomes (or sets of winners) in the election:- A. Andrea and Carter.
- B. Andrea and Brad.
- C. Carter and Brad.
Under Schulze STV, it is certain that any candidate with more than the Droop quota in the first preferences will be elected. This means that Andrea is certain to be elected as she received 38 votes. This means that there are only 2 possible outcomes
- A. Andrea and Carter.
- B. Andrea and Brad.
These two outcomes will be compared.
Comparison of A and B
Support for (Andrea,Carter) beats (Andrea,Brad*)
Brad is the test candidate.
12 prefer Andrea (but not Carter) to Brad (assign to Andrea)
0 prefer Carter (but not Andrea) to Brad
51 prefer Both to Brad (assign 19.5 to Andrea and 31.5 to Carter)
27 prefer Brad to Both (These cannot be assigned to any group)
Both groups have 31.5 ballots in them.
Support for (Andrea,Brad) beats (Andrea,Carter*)
Carter is the test candidate.
26 prefer Andrea (but not Brad) to Carter (assign to Andrea)
27 prefer Brad (but not Andrea) to Carter (assign to Brad)
12 prefer both to Carter (assign 6.5 to Andrea and 5.5 to Brad)
Both groups have 32.5 ballots in them and this maximises the smallest group size.
This means that (Andrea,Brad) beats (Andrea,Carter) by 32.5 votes to 31.5.
Result
Since (Andrea,Brad) beats (Andrea,Carter), (Andrea,Brad) is the Condorcet winner. This means that Andrea (Y) and Brad (P) are the winners.
Thus, unlike standard PR-STV, Schulze STV resisted the effects of vote management.
Schulze STV and traditional STV
The example above shows Schulze STV's resistance to vote management. Since it performs Condorcet pairwise comparisons, like CPO-STVCPO-STV
CPO-STV, or the Comparison of Pairs of Outcomes by the Single Transferable Vote, is a preference voting system designed to achieve proportional representation. It is a highly sophisticated variant of the Single Transferable Vote system, designed to overcome some of that system's perceived...
, it doesn't suffer from defects caused by sequential exclusions. In addition, the number of pairwise comparisons are greatly reduced, since Schulze STV only has to compare outcomes that differ by one candidate, unlike CPO-STV which must compare all possible pairwise comparisons.
Even when the Yellow Party instructed all of its supporters to top rank Carter, it didn't result in Carter taking the 2nd seat.
Potential for tactical voting
Proportional representation systems are much less susceptible to tactical voting systems than single-winner systems such as the Single Member District PluralityPlurality voting system
The plurality voting system is a single-winner voting system often used to elect executive officers or to elect members of a legislative assembly which is based on single-member constituencies...
('First-Past-the-Post') system and Instant Run-Off Voting. Schulze STV has additional resistance to forms of tactical voting which are specific to single transferable voting methods.
However, all forms of STV are vulnerable to some degree of tactical voting because they lack monotonicity
Monotonicity criterion
The monotonicity criterion is a voting system criterion used to analyze both single and multiple winner voting systems. A voting system is monotonic if it satisfies one of the definitions of the monotonicity criterion, given below.Douglas R...
. This means that it is sometimes possible to benefit a candidate by ranking them lower than one's true order of preference, or to harm a candidate by ranking them higher.
PR-STV methods which make use of Meek's Method are resistant to Woodall Free Riding, but are still vulnerable to Hylland Free Riding. Schulze's method is not vulnerable to Hylland Free Riding, except where necessary in order to meet the Droop proportionality criterion.
A method which doesn't meet the Droop proportionality criterion has the potential to give disproportional results. Thus, Schulze STV can be considered invulnerable to Hylland Free Riding to as great an extent possible, subject to actually being a proportional representation method.
In addition to the voting system criteria passed by all STV methods, Schulze STV satisfies Dummett's
Michael Dummett
Sir Michael Anthony Eardley Dummett FBA D.Litt is a British philosopher. He was, until 1992, Wykeham Professor of Logic at the University of Oxford...
Proportionality for Solid Coalitions
Proportionality for Solid Coalitions
Proportionality for Solid Coalitions is an election methods criterion relating to proportional representation systems. This criterion was invented by Michael Dummett.-Tideman:Tideman defines this criterion as...
criterion.
Impact on candidates and factions
The advantage of the resistance to free riding is that parties who do not participate in vote management will not be at a disadvantage. Vote management requires strict control of the number of party candidates and also requires voters to vote in accordance with the party leadership's instructions. This reduces the ability for voters to express their views and to remove disliked party candidates.Practical implications
From the point of view of the voter Schulze is no more complicated than traditional forms of STV. Under both systems the ballot paper is the same and voting occurs by ranking the candidates in order of preference.However, with respect to calculating an election result, Schulze STV is significantly more complex than standard PR-STV. Even though it is less complex than CPO-STV
CPO-STV
CPO-STV, or the Comparison of Pairs of Outcomes by the Single Transferable Vote, is a preference voting system designed to achieve proportional representation. It is a highly sophisticated variant of the Single Transferable Vote system, designed to overcome some of that system's perceived...
, for large scale elections, it would still be necessary for the results to be calculated by computer. Even then, computing the result would be difficult in some cases: Schulze STV does not have polynomial runtime.