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 Θ $(n^{3})$ . It can also be calculated using a version of Kosaraju's algorithm or Tarjan's algorithm in time Θ $(n^{2})$ .

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.

Related pages

Condorcet criterion
Condorcet method
Landau set
Preorder
Partial order

References

Ward, Benjamin (1961). "Majority Rule and Allocation". Journal of Conflict Resolution. 5 (4): 379–389. doi:10.1177/002200276100500405. S2CID 145231466. In an analysis of serial decision making based on majority rule, describes the Smith set and the Schwartz set.
Smith, J.H. (1973). "Aggregation of Preferences with Variable Electorates". Econometrica. 41 (6). The Econometric Society: 1027–1041. doi:10.2307/1914033. JSTOR 1914033. 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.
Fishburn, Peter C. (1977). "Condorcet Social Choice Functions". SIAM Journal on Applied Mathematics. 33 (3): 469–489. doi:10.1137/0133030. Narrows Smith's generalized Condorcet Criterion to the smallest dominating set and calls it Smith's Condorcet Principle.
Schwartz, Thomas (1986). The Logic of Collective Choice. New York: Columbia University Press. ISBN 9780231058964. 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 Archived 2017-06-17 at the Wayback Machine