Smith set

In voting systems, the Smith set, named after John H. Smith, but also known as the top cycle, or as Generalized Top-Choice Assumption (GETCHA), is the smallest non-empty set of candidates in an election such that more voters prefer any candidate in the set over any candidate not in the set in head-to-head matchups. The Smith set is one way to determine who the best candidates in an election are.  Voting systems that always elect a candidate from the Smith set pass the Smith criterion and are said to be "Smith-efficient".

A set of candidates where every candidate in the set pairwise beats every candidate not in the set is known as a dominating set.

 Properties 

 The Smith set always exists.  There is only one smallest dominating set since dominating sets are nested and non-empty and there is a limited number of candidates.
 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 only member of the Smith set. If weak Condorcet winners exist then they are in the Smith set.
 The Smith set only contains candidates who are also in the mutual majority-preferred set of candidates, if one exists.

 Algorithms 
The Smith set can be calculated with the Floyd–Warshall algorithm in time Θ.  It can also be calculated using a version of Kosaraju's algorithm or Tarjan's algorithm in time Θ.

It can also be found by ordering the candidates by their number of pairwise victories minus pairwise defeats (a Copeland method ranking), and then looking for the smallest group of candidates, starting from the top, who pairwise beat all candidates not already in the group.

Example using the Copeland ranking:
ABCDEFGA ---WinLoseWinWinWinWinBLose ---WinWinWinWinWinCWinLose ---LoseWinWinWinDLoseLoseWin ---TieWinWinELoseLoseLoseTie ---WinWinFLoseLoseLoseLoseLose ---WinGLoseLoseLoseLoseLoseLose ---
A pairwise loses to C, so it is certain that all candidates from A through C (A, B, and C) are in the Smith set. However, there is one matchup where a candidate who is known to be in the Smith set loses or ties someone who may or may not be in the Smith set: C loses to D; so D is confirmed to be in the Smith set. Another such matchup can now be seen: D ties with E. So E is added into the Smith set. Because all of A through E beat all candidates other than each other, the Smith set is A through E.

 Related pages 

 Condorcet criterion
 Condorcet method
 Landau set
 Preorder
 Partial order

 References 

   In an analysis of serial decision making based on majority rule, describes the Smith set and the Schwartz set.
   Introduces a version of a generalized Condorcet Criterion that is satisfied when pairwise elections are based on simple majority choice, and for any dominating set, any candidate in the set is collectively preferred to any candidate not in the set.  But Smith does not discuss the idea of a smallest dominating set.
   Narrows Smith's generalized Condorcet Criterion to the smallest dominating set and calls it Smith's Condorcet Principle.
   Discusses the Smith set (named GETCHA) and the Schwartz set (named GOTCHA) as possible standards for optimal collective choice.

 Other websites 

 Example algorithms to calculate the Smith set 

Category:Voting systems