Smith criterion
Encyclopedia
The Smith criterion is a voting systems criterion defined such that its satisfaction by a voting system
occurs when the system always picks the winner from the Smith set
, the smallest set of candidates such that every member of the set is pairwise preferred to every candidate not in the set. One candidate is pairwise preferred over another candidate if, in a one-on-one competition, more voters prefer the first candidate than prefer the other candidate. The Smith set is named for mathematician John H Smith, whose version of the Condorcet criterion is actually stronger than that defined above for social welfare functions. Benjamin Ward was probably the first to write about this set, which he called the "majority set".
The Smith set can be calculated with the Floyd-Warshall algorithm
in time Θ
(n3) or Kosaraju's algorithm
in time Θ(n2).
, since if there is a Condorcet winner, then that winner is the only member of the Smith set. Obviously, this means that failing the Condorcet criterion automatically implies the non-compliance with the Smith criterion as well. Additionally, such sets comply with the Condorcet loser criterion
. This is notable, because even some Condorcet methods do not (Minimax). It also implies the mutual majority criterion
, since the Smith set is a subset of the MMC set.
The Smith set and Schwartz set
are sometimes confused in the literature. Miller (1977, p. 775) lists GOCHA 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 ties between members of the Smith set).
, Nanson's method
, and Ranked Pairs
comply with the Smith Criterion. Compliance with the Smith criterion can be "forced" by explicitly applying a voting system to the Smith set. For example, Smith/Minimax is the application of Minimax
to only the candidates inside the Smith set.
Methods failing the Condorcet criterion never comply with the Smith criterion, and many Condorcet methods also fail the Smith criterion.
Voting system
A voting system or electoral system is a method by which voters make a choice between options, often in an election or on a policy referendum....
occurs when the system always picks the winner from the Smith set
Smith set
In voting systems, the Smith set, named after John H. Smith, is the smallest non-empty set of candidates in a particular election such that each member beats every other candidate outside the set in a pairwise election. The Smith set provides one standard of optimal choice for an election outcome...
, the smallest set of candidates such that every member of the set is pairwise preferred to every candidate not in the set. One candidate is pairwise preferred over another candidate if, in a one-on-one competition, more voters prefer the first candidate than prefer the other candidate. The Smith set is named for mathematician John H Smith, whose version of the Condorcet criterion is actually stronger than that defined above for social welfare functions. Benjamin Ward was probably the first to write about this set, which he called the "majority set".
The Smith set can be calculated with the Floyd-Warshall algorithm
Floyd-Warshall algorithm
In computer science, the Floyd–Warshall algorithm is a graph analysis algorithm for finding shortest paths in a weighted graph and also for finding transitive closure of a relation R...
in time Θ
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n3) or Kosaraju's algorithm
Kosaraju's algorithm
In computer science, the Kosaraju-Sharir algorithm is an algorithm to find the strongly connected components of a directed graph. Aho, Hopcroft and Ullman credit it to an unpublished paper from 1978 by S. Rao Kosaraju and Micha Sharir...
in time Θ(n2).
Other criteria
Any election method that complies with the Smith criterion also complies with the Condorcet criterionCondorcet criterion
The Condorcet candidate or Condorcet winner of an election is the candidate who, when compared with every other candidate, is preferred by more voters. Informally, the Condorcet winner is the person who would win a two-candidate election against each of the other candidates...
, since if there is a Condorcet winner, then that winner is the only member of the Smith set. Obviously, this means that failing the Condorcet criterion automatically implies the non-compliance with the Smith criterion as well. Additionally, such sets comply with the Condorcet loser criterion
Condorcet loser criterion
In single-winner voting system theory, the Condorcet loser criterion is a measure for differentiating voting systems. It implies the majority loser criterion....
. This is notable, because even some Condorcet methods do not (Minimax). It also implies the mutual majority criterion
Mutual majority criterion
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...
, since the Smith set is a subset of the MMC set.
The Smith set and Schwartz set
Schwartz set
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...
are sometimes confused in the literature. Miller (1977, p. 775) lists GOCHA 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 ties between members of the Smith set).
Complying methods
SchulzeSchulze 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...
, Nanson's method
Nanson's method
The Borda count can be combined with an Instant Runoff procedure to create hybrid election methods that are called Nanson method and Baldwin method.- Nanson method :The Nanson method is based on the original work of the mathematician Edward J...
, and Ranked Pairs
Ranked Pairs
Ranked pairs or the Tideman method is a voting system developed in 1987 by Nicolaus Tideman that selects a single winner using votes that express preferences. RP can also be used to create a sorted list of winners....
comply with the Smith Criterion. Compliance with the Smith criterion can be "forced" by explicitly applying a voting system to the Smith set. For example, Smith/Minimax is the application of Minimax
Minimax Condorcet
In voting systems, the Minimax method is one of several Condorcet methods used for tabulating votes and determining a winner when using preferential voting in a single-winner election...
to only the candidates inside the Smith set.
Methods failing the Condorcet criterion never comply with the Smith criterion, and many Condorcet methods also fail the Smith criterion.