Schulze STV

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Schulze STV is a draft ranked voting system designed to achieve proportional representation.[1][2] 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[edit]

Each voter ranks the candidates in order of preference. For example:

  1. Andrea
  2. Carter
  3. Brad

Procedure[edit]

Pairwise Comparisons of results[edit]

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[edit]

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[edit]

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[edit]

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
  1. Andrea (Y)
  2. Brad (P)
  3. Carter (Y)
  1. Andrea (Y)
  2. Carter (Y)
  3. Brad (P)
  1. Andrea (Y)
  2. Carter (Y)
  3. Brad (P)
  1. Carter (Y)
  2. Andrea (Y)
  3. Brad (P)
  1. Brad (P)

Count under traditional STV[edit]

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[edit]

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

Count under Schulze STV[edit]

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[edit]

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[edit]

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[edit]

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
  1. Andrea (Y)
  2. Brad (P)
  3. Carter (Y)
  1. Andrea (Y)
  2. Carter (Y)
  3. Brad (P)
  1. Carter (Y)
  2. Andrea (Y)
  3. Brad (P)
  1. Carter (Y)
  2. Andrea (Y)
  3. Brad (P)
  1. Brad (P)

Count under traditional STV[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

Proportional representation systems are much less susceptible to tactical voting systems than single-winner systems such as the Single Member District Plurality ('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[edit]

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[edit]

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[edit]

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

References[edit]

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

External links[edit]