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.
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:
A | B | C | D | E | F | G | |
---|---|---|---|---|---|---|---|
A | --- | Win | Lose | Win | Win | Win | Win |
B | Lose | --- | Win | Win | Win | Win | Win |
C | Win | Lose | --- | Lose | Win | Win | Win |
D | Lose | Lose | Win | --- | Tie | Win | Win |
E | Lose | Lose | Lose | Tie | --- | Win | Win |
F | Lose | Lose | Lose | Lose | Lose | --- | Win |
G | Lose | Lose | Lose | Lose | Lose | Lose | --- |
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.