Smith criterion

Last updated

The Smith criterion (sometimes the generalized Condorcet criterion) is a voting system criterion that formalizes the concept of a majority rule. A voting system satisfies the Smith criterion if it always elects a candidate from the Smith set, which generalizes the idea of a "Condorcet winner" to cases where there may be cycles or ties, by allowing for several who together can be thought of as being "Condorcet winners." A Smith method will always elect a candidate from the Smith set.

Contents

The Smith criterion is also called the top cycle criterion, but this is slightly misleading, as the Smith set can include "degenerate" cycles--the Smith set can include a single candidate "cycling" with themselves (a Condorcet winner), or a pair of exactly-tied candidates who "cycle" with each other. [1]

An alternative, stricter criterion is given by the Landau set.

Determination

The Smith set can be calculated with the Floyd–Warshall algorithm in time Θ (n3) or Kosaraju's algorithm in time Θ(n2).

Example

When there is a Condorcet winner—a candidate that is majority-preferred over all other candidates—the Smith set consists of only that candidate. Here is an example in which there is no Condorcet winner: There are four candidates: A, B, C and D. 40% of the voters rank D>A>B>C. 35% of the voters rank B>C>A>D. 25% of the voters rank C>A>B>D. The Smith set is {A,B,C}. All three candidates in the Smith set are majority-preferred over D (since 60% rank each of them over D). The Smith set is not {A,B,C,D} because the definition calls for the smallest subset that meets the other conditions. The Smith set is not {B,C} because B is not majority-preferred over A; 65% rank A over B. (Etc.)

pro\conABCD
A654060
B357560
C602560
D404040
max opp60657560
minimax6060

In this example, under minimax, A and D tie; under Smith//Minimax, A wins.

In the example above, the three candidates in the Smith set are in a "rock/paper/scissors" majority cycle: A is ranked over B by a 65% majority, B is ranked over C by a 75% majority, and C is ranked over A by a 60% majority.

Other criteria

Any election method that complies with the Smith criterion also complies with the Condorcet winner criterion, since if there is a Condorcet winner, then it is the only candidate in the Smith set. Smith methods also comply with the Condorcet loser criterion, because a Condorcet loser will never fall in the Smith set. It also implies the mutual majority criterion, since the Smith set is a subset of the MMC set. [2]

The Smith set and Schwartz set are sometimes confused in the literature. Miller (1977, p. 775) lists as an alternate name for the Smith set, but it actually refers to the Schwartz set. The Schwartz set is actually a subset of the Smith set (and equal to it if there are no pairwise ties between members of the Smith set).

Complying methods

The Smith criterion is satisfied by Ranked Pairs, Schulze's method, Nanson's method, and several other methods[ citation needed ]. Moreover, any voting method can be modified to satisfy the Smith criterion, by finding the Smith set and then eliminating any candidates who are not in the Smith set. For example, the voting method Smith//Minimax applies Minimax to the candidates in the Smith set. Another approach is to elect the member of the Smith set that is highest in the voting method's order of finish.

Methods failing the Condorcet criterion also fail the Smith criterion. However, some Condorcet methods (such as Minimax) can fail the Smith criterion.

Examples

Minimax

Mutual majority criterion#Minimax

The Smith criterion implies the mutual majority criterion, so Minimax's failure to satisfy the Mutual majority criterion is also a failure to satisfy the Smith criterion. Observe that the set S = {A, B, C} in the example is the Smith set and D is the Minimax winner.

See also

Related Research Articles

<span class="mw-page-title-main">Condorcet method</span> Pairwise-comparison electoral system

A Condorcet method is an election method that elects the candidate who wins a majority of the vote in every head-to-head election against each of the other candidates, that is, a candidate preferred by more voters than any others, whenever there is such a candidate. A candidate with this property, the pairwise champion or beats-all winner, is formally called the Condorcet winner. The head-to-head elections need not be done separately; a voter's choice within any given pair can be determined from the ranking.

<span class="mw-page-title-main">Copeland's method</span> Single-winner ranked vote system

Copeland's method, also called Llull's method or Ranked-Robin, is a ranked-choice voting system based on scoring pairwise wins and losses.

The Smith set, also known as the top cycle, is a concept from the theory of electoral systems that generalizes the Condorcet winner to cases where no such winner exists, by allowing cycles of candidates to be treated jointly as if they were a single Condorcet winner. Named after John H. Smith, the Smith set consists the smallest non-empty set of candidates in a particular election, such that each member defeats every candidate outside the set in a pairwise election. The Smith set provides one standard of optimal choice for an election outcome. Voting systems that always elect a candidate from the Smith set pass the Smith criterion.

In voting systems, the Schwartz set is the union of all Schwartz set components. A Schwartz set component is any non-empty set S of candidates such that

  1. Every candidate inside the set S is pairwise unbeaten by every candidate outside S; and
  2. No non-empty proper subset of S fulfills the first property.

Ranked pairs or the Tideman method is an electoral system developed in 1987 by Nicolaus Tideman that selects a single winner using votes that express preferences. The ranked-pairs procedure can also be used to create a sorted list of winners.

The Schulze method is an electoral 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. The Schulze method is also known as Schwartz Sequential dropping (SSD), cloneproof Schwartz sequential dropping (CSSD), the beatpath method, beatpath winner, path voting, and path winner. The Schulze method is a Condorcet method, which means that if there is a candidate who is preferred by a majority over every other candidate in pairwise comparisons, then this candidate will be the winner when the Schulze method is applied.

An electoral system satisfies the Condorcet winner criterion if it always chooses the Condorcet winner when one exists. The candidate who wins a majority of the vote in every head-to-head election against each of the other candidates – that is, a candidate preferred by more voters than any others – is the Condorcet winner, although Condorcet winners do not exist in all cases. It is sometimes simply referred to as the "Condorcet criterion", though it is very different from the "Condorcet loser criterion". Any voting method conforming to the Condorcet winner criterion is known as a Condorcet method. The Condorcet winner is the person who would win a two-candidate election against each of the other candidates in a plurality vote. For a set of candidates, the Condorcet winner is always the same regardless of the voting system in question, and can be discovered by using pairwise counting on voters' ranked preferences.

The participation criterion, sometimes called join consistency, is a voting system criterion that says that a candidate should never lose an election because they have "too many supporters." In other words, adding a ballot that ranks A higher than B should not cause A to lose to B.

The majority criterion is a voting system criterion. The criterion states that "if only one candidate is ranked first by a majority of voters, then that candidate must win."

A voting system is consistent if combining two sets of votes that both elect A over B always results in a combined electorate that ranks A over B. This property is sometimes called participation, join-consistency, or separability.

The mutual majority criterion is a criterion used to compare voting systems. It is also known as the majority criterion for solid coalitions and the generalized majority criterion. The criterion says if there is a subset S of candidates, with more than half of voters strictly preferring any member of S to every candidate outside of S, the winner must come from S. This is similar to but stricter than the majority criterion, where the requirement applies only to the case that S contains a single candidate. This is also stricter than the majority loser criterion, where the requirement applies only to the case that S contains all but one candidate. The mutual majority criterion is the single-winner case of the Droop proportionality criterion.

In single-winner voting system theory, the Condorcet loser criterion (CLC) is a measure for differentiating voting systems. It implies the majority loser criterion but does not imply the Condorcet winner criterion.

In voting systems, the Minimax Condorcet method is a single-winner ranked-choice voting method that always elects the majority (Condorcet) winner. Minimax compares all candidates against each other in a round-robin tournament, then ranks candidates by their worst election result. The candidate with the largest (maximum) margin of victory in their worst (minimum) matchup is declared the winner.

Reversal symmetry is a voting system criterion which requires that if candidate A is the unique winner, and each voter's individual preferences are inverted, then A must not be elected. Methods that satisfy reversal symmetry include Borda count, ranked pairs, Kemeny–Young method, and Schulze method. Methods that fail include Bucklin voting, instant-runoff voting and Condorcet methods that fail the Condorcet loser criterion such as Minimax.

The later-no-harm criterion is a voting system criterion first formulated by Douglas Woodall. Woodall defined the criterion by saying that "[a]dding a later preference to a ballot should not harm any candidate already listed." For example, a ranked voting method in which a voter adding a 3rd preference could reduce the likelihood of their 1st preference being selected, fails later-no-harm.

In voting systems theory, the independence of clones criterion measures an election method's robustness to strategic nomination. Nicolaus Tideman was the first to formulate this criterion, which states that the winner must not change due to the addition of a non-winning candidate who is similar to a candidate already present. To be more precise, a subset of the candidates, called a set of clones, exists if no voter ranks any candidate outside the set between any candidates that are in the set. If a set of clones contains at least two candidates, the criterion requires that deleting one of the clones must not increase or decrease the winning chance of any candidate not in the set of clones.

The majority loser criterion is a criterion to evaluate single-winner voting systems. The criterion states that if a majority of voters prefers every other candidate over a given candidate, then that candidate must not win.

<span class="mw-page-title-main">Ranked voting</span> Family of electoral systems

The term ranked voting, also known as preferential voting or ranked-choice voting, pertains to any voting system where voters indicate a rank to order candidates or options—in a sequence from first, second, third, and onwards—on their ballots. Ranked voting systems vary based on the ballot marking process, how preferences are tabulated and counted, the number of seats available for election, and whether voters are allowed to rank candidates equally.

The later-no-help criterion is a voting system criterion formulated by Douglas Woodall. The criterion is satisfied if, in any election, a voter giving an additional ranking or positive rating to a less-preferred candidate can not cause a more-preferred candidate to win. Voting systems that fail the later-no-help criterion are vulnerable to the tactical voting strategy called mischief voting, which can deny victory to a sincere Condorcet winner.

Comparison of electoral systems is the result of comparative politics for electoral systems. Electoral systems are the rules for conducting elections, a main component of which is the algorithm for determining the winner from the ballots cast. This article discusses methods and results of comparing different electoral systems, both those that elect a unique candidate in a 'single-winner' election and those that elect a group of representatives in a multiwinner election.

References

  1. http://cse.unl.edu/~lksoh/Classes/CSCE475_875_Fall17/handouts/10VotingSocialChoice.pdf [ bare URL PDF ]
  2. http://dss.in.tum.de/files/brandt-research/dodgson.pdf [ bare URL PDF ]
  1. ^ J. H. Smith, "Aggregation of preferences with variable electorate", Econometrica, vol. 41, pp. 1027–1041, 1973.
  2. ^ Benjamin Ward, "Majority Rule and Allocation", The Journal of Conflict Resolution, Vol. 5, No. 4. (1961), pp. 379–389.