Smith set
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The Smith set, sometimes called the top-cycle generalizes the idea of a Condorcet winner to cases where no such winner exists. It does so by allowing cycles of candidates to be treated jointly, as if they were a single Condorcet winner. Voting systems that always elect a candidate from the Smith set pass the Smith criterion. The Smith set and Smith criterion are both named for mathematician John H. Smith. The Smith set provides one standard of optimal choice for an election outcome. An alternative, stricter criterion is given by the Landau set.
The Smith set, sometimes called the top-cycle generalizes the idea of a Condorcet winner to cases where no such winner exists. It does so by allowing cycles of candidates to be treated jointly, as if they were a single Condorcet winner. Voting systems that always elect a candidate from the Smith set pass the Smith criterion. The Smith set and Smith criterion are both named for mathematician John H. Smith. The Smith set provides one standard of optimal choice for an election outcome. An alternative, stricter criterion is given by the Landau set.
Properties
The Smith set always exists and is non-empty. It is also well-defined (see next section). The Smith set can have more than one candidate, either because of pairwise ties or because of cycles, such as in Condorcet's paradox. The Condorcet winner, if one exists, is the sole member of the Smith set. If weak Condorcet winners exist they are in the Smith set. The Smith set is always a subset of the smallest mutual majority-preferred set of candidates.
Properties of dominating sets
Theorem: Dominating sets are nested; that is, of any two dominating sets in an election, one is a subset of the other. Proof: Suppose on the contrary that there exist two dominating sets, D and E, neither of which is a subset of the other. Then there must exist candidates such that and But by hypothesis d defeats every candidate not in D (including e) while e defeats every candidate not in E (including d), a contradiction. ∎ Corollary: It follows that the Smith set is the smallest non-empty dominating set, and that it is well defined. Theorem: If D is a dominating set, then there is some threshold θ D such that the elements of D are precisely the candidates whose Copeland scores are at least θ D . (A candidate's Copeland score is the number of other candidates whom he or she defeats plus half the number of other candidates with whom he or she is tied.) Proof: Choose d as an element of D with minimum Copeland score, and identify this score with θ D . Now suppose that some candidate has a Copeland score not less than θ D . Then since d belongs to D and e doesn't, it follows that d defeats e; and in order for e s Copeland score to be at least equal to d s, there must be some third candidate f against whom e gets a better score than does d. If then we have an element of D who does not defeat e, and if then we have a candidate outside of D whom d does not defeat, leading to a contradiction either way. ∎
The Smith criterion
The Smith criterion is a voting system criterion that formalizes a stronger idea of majority rule than the Condorcet criterion. A voting system satisfies the Smith criterion if it always picks a candidate from the Smith set. Though less common, the term Smith-efficient has also been used for methods that elect from the Smith set. Here is an example of an electorate 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.) 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.
Relation to other tournament sets
The Smith set contains the Copeland set and Landau set as subsets. It also contains the Banks set and the Bipartisan set. A number of other subsets of the Smith set have been defined as well.
Computing the Smith set
The Smith set can be calculated with the Floyd–Warshall algorithm in time Θ(n 3 ) or Kosaraju's algorithm in time Θ(n 2 ). The following C function illustrates the algorithm by returning the cardinality of the Smith set for a given doubled results matrix r and array s of doubled Copeland scores. There are n candidates; r i j is 2 if more voters prefer i to j than prefer j to i, 1 if the numbers are equal, and 0 if more voters prefer j to i than prefer i to j ; s i is the sum over j of the r i j . The candidates are assumed to be sorted in decreasing order of Copeland score. int smithset(int ** r, int * s, int n) { int row, col, lhs, rhs; for (rhs = 1, lhs = 0; lhs = rhs; row--) for (col = lhs; col
See also
Condorcet criterion Condorcet method Landau set Preorder Partial order Maximal and minimal elements - the Smith set can be defined as the maximal elements of a particular partial order.
Notes
References
Text derived from https://en.wikipedia.org/w/index.php?oldid=1372398945 under CC BY-SA 4.0; modifications have been made.