Schulze STV

Voting systems
Part of the Politics series
Plurality/Majoritarian Simple majoritarianism Limited voting Single non-transferable vote Plurality First-past-the-post Two-round Exhaustive ballot Preferential/ranked/ordinal systems Borda count Bucklin voting Condorcet methods (Copeland's, Dodgson's, Kemeny-Young, Minimax, Nanson's, Ranked pairs, Schulze) Coombs' method Instant-runoff (alternative vote) Contingent vote Oklahoma primary electoral system Cardinal/graded/rated systems Approval voting Proportional approval voting Sequential proportional approval voting Satisfaction approval voting Majority judgment Range voting
Proportional Representation Party-list (Open lists, Closed lists, Local lists) Highest averages (D'Hondt, Sainte-Laguë) Largest remainder (Hare, Droop, Imperiali, Hagenbach-Bischoff) Single transferable vote (CPO-STV, Gregory, Schulze STV, Wright)
Mixed-Member Mixed-member proportional Majority bonus system Additional member system Scorporo, Av+ Parallel voting Majoritarian representation Plurality-at-large Preferential block voting General ticket
Other Proxy voting Delegable voting Delegated voting Random selection Sortition Random ballot Social choice theory Arrow's theorem Gibbard–Satterthwaite theorem Voting system criteria Public choice theory (separate but related) Multiple Ballot Voting Cumulative voting
Politics portal

Schulze STV is a draft ranked voting system designed to achieve proportional representation.^[1]^[2] It is a single transferable vote (STV) voting system. 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.^[3] 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

Procedure

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 (A₁,A₂,...,A_S) and (A₂,...,A_S,B).

The ballots are then assigned to one of the candidates in (A₁,A₂,...,A_S). However, a ballot may only be assigned to A_i if the voter prefers A_i to B. This means that ballots which prefer B to all the candidates in (A₁,A₂,...,A_S) will remain unassigned. The ballots are assigned in order to maximise the smallest number of ballots held by any candidate in (A₁,A₂,...,A_S).

The number of votes in favour of the proposal that (A₁,A₂,...,A_S) beats (A₂,...,A_S,B) is equal to the smallest number of ballots held by any candidate in (A₁,A₂,...,A_S).

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 (A₁,A₂,...,A_S) beats (A₂,...,A_S,B), i.e. the number of votes in favour of the proposal that (A₂,...,A_S,B) beats (A₁,A₂,...,A_S).

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
Andrea (Y) Brad (P) Carter (Y)	Andrea (Y) Carter (Y) Brad (P)	Andrea (Y) Carter (Y) Brad (P)	Carter (Y) Andrea (Y) Brad (P)	Brad (P)

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.

Result

The elected candidates are Andrea (Y) and Brad (P).

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
Andrea (Y) Brad (P) Carter (Y)	Andrea (Y) Carter (Y) Brad (P)	Carter (Y) Andrea (Y) Brad (P)	Carter (Y) Andrea (Y) Brad (P)	Brad (P)

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-STV, 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 first past the post system and instant-runoff voting (IRV), if the number of seats to be filled is sufficiently large. Schulze STV has additional resistance to forms of tactical voting which are specific to single transferable voting methods.

All forms of STV that reduce to IRV in single winner elections fail the monotonicity criterion. 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. This isn't the case for Schulze STV. When some voters rank candidate $b$ higher without changing the order in which they rank the other candidates relatively to each other, then the strength of the vote management of the candidates $a_1,\ldots,a_M$ against candidate $b$ can't increase. I. e. the strength of any vote management and the strength of beatpaths is monotonic in $b$ and the monotonicity follows from that of the underlying Schulze method.

As Schulze STV reduces to the Schulze method in single winner elections, it fails the participation criterion, the later-no-harm criterion and the later-no-help criterion, whereas traditional forms of STV (that reduce to IRV in single winner elections) fulfill later-no-help and later-no-harm.

STV methods which make use of Meek's or Warren'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.^[1]

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.

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, 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.

Use of Schulze STV

Schulze STV is not currently used in parliamentary elections. Organizations which currently use Schulze STV are:

Mathematics Society of the University of Waterloo ^[4]

References

1 2 Markus Schulze, Free Riding and Vote Management under Proportional Representation by Single Transferable Vote
↑ Markus Schulze, Implementing the Schulze STV Method
↑ Markus Schulze, Free Riding, Voting matters, issue 18, pages 2–8, June 2004
↑ §1.5.6 of the Election Procedure

External links

Personalisierung der Verhältniswahl durch Varianten der Single Transferable Vote (German) by Martin Wilke
Python implementation
A voting web application that uses Schulze STV

Voting systems

Part of the Politics and Election series

Single-winner voting system	Approval voting Borda count Bucklin voting Contingent vote Coombs' method Copeland's method Exhaustive ballot First-past-the-post voting Instant-runoff voting Kemeny–Young method Simple majoritarianism Minimax Condorcet Nanson's method Plurality Positional voting system Range voting Ranked pairs Schulze method Two-round system

Proportional representation	Mixed-member Party-list Single transferable vote Schulze STV CPO-STV Highest averages method Sainte-Laguë D'Hondt Largest remainder method Alternative vote Plus Closed list Open list Overhang seat Underhang seat

Semi-proportional representation	Parallel voting Single non-transferable vote Cumulative voting Limited voting Proportional approval voting Sequential proportional approval voting Satisfaction approval voting

Usage	Table of voting systems by country

Voting system criterion	Condorcet criterion Condorcet loser criterion Consistency criterion Independence of clones Independence of irrelevant alternatives Independence of Smith-dominated alternatives Later-no-harm criterion Majority criterion Majority loser criterion Monotonicity criterion Mutual majority criterion Pareto efficiency Participation criterion Plurality criterion Resolvability criterion Reversal symmetry Smith criterion

Voting system quotas	Droop quota Hagenbach-Bischoff quota Hare quota Imperiali quota

Other	Ballot Vote counting system Election threshold First-preference votes Spoilt vote Sortition

Portal — Project

This article is issued from Wikipedia - version of the Friday, July 31, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.