Smith set

Wikipedia has an article on:

Smith set

Wikipedia has an article on:

Schwartz set

According to English Wikipedia in May 2023^[1]:

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 a particular election such that each member defeats every candidate outside the set in a pairwise election. The Smith set provides one standard of optimal choice for an election outcome. Voting systems that always elect a candidate from the Smith set pass the Smith criterion and are said to be 'Smith-efficient' or to satisfy the Smith criterion.
A set of candidates each of whose members pairwise defeats every candidate outside the set is known as a dominating set.
The Smith set can be seen as defining a voting method (Smith's method) which is most often encountered when extended by an IRV tie-break as Smith/IRV or as Tideman's Alternative, or by minimax as Smith/minimax.

Condorcet cycles

See also: Condorcet cycle and Condorcet paradox

The "Smith set" can be considered the Condorcet top tier of candidates. It is he smallest group of candidates such that more voters prefer any candidate in the group over anyone not in the group (when looking at pairwise matchups). Voting methods which always select the winner from the Smith set are called Smith-efficient, pass the Smith criterion, and are all Condorcet methods, since the Condorcet winner will always be the only candidate in the Smith set when they exist, thus they will be the only candidate eligible to win and so must be picked.

The Schwartz set is always a subset of the Smith set. The Schwartz set is equal to the Smith set except when there is a candidate in the Schwartz set that has a pairwise tie with a candidate outside of the Schwartz set. See Schwartz set to learn more.

Smith loser set

The Smith loser set (which could probably analagously be called the Condorcet bottom tier or bottom cycle) is the smallest group of candidates such that fewer voters prefer any candidate in the group than any candidate not in the group. it can be equivalent to the Smith set; for example:

1 A

1 B

Both the Smith set and Smith loser set are (A, B). When there is a Condorcet loser, they are the only candidate in the Smith loser set. Note that the Smith loser set is distinct from the set of all candidates not in the Smith set. For example:

49 A>B
3 B>A
48 C>B

The Smith loser set is C, while the set of all candidates not in the Smith set is (A, C).

Note that this is not an academic concept, but written here for knowledge's sake.

Properties

The Smith Set is always a subset of the mutual majority-preferred set of candidates, when one exists.

There is always a Smith set ranking of the candidates which reveals which groups of candidate pairwise beat each other. It reduces to the Condorcet ranking when one exists.

If the Smith set contains more than one candidate, this is due to majority cycles such as in Condorcet's paradox, or to pairwise ties.

The Smith set always contains the weak Condorcet winners if they exist.

The Schwartz set is always a subset of the Smith set. The Schwartz set is equal to the Smith set except when there is a candidate in the Schwartz set that has a pairwise tie with a candidate outside of the Schwartz set.

The Uncovered set and the Banks set are also subsets of the Smith set. The Banks set is defined as the alternatives that can win given the Robert's Rules sequential pairwise voting method for at least one agenda order of candidates, assuming the voters are strategically sophisticated and know each other's preferences. (An assumption more likely to hold when the voters are a professional legislature.)

Some examples of the Smith set and Schwartz set are provided, some with 3 candidates or with 12 candidates.

The Smith set is the maximal cycle equivalence class of the beat-or-tie order.

Algorithms

The Smith set can be calculated using versions of either Kosaraju's algorithm or the Floyd-Warshall algorithm. Examples of both algorithms applied to calculating the Smith set and the Schwartz set are available here.

A simpler but less efficient way to find the Smith set is to use any Smith-efficient Condorcet method to find at least one member of the Smith set, and then to repeatedly add into the Smith set any candidates that pairwise beat or tie the candidates already in the Smith set. For this purpose, Copeland's method or https://electowiki.org/wiki/Category:Sequential_comparison_Condorcet_methods sequential comparison Condorcet methods such as BTR-IRV are likely best, since with Copeland, candidates in the Smith set always have a Copeland score at least 2 points higher than all other candidates, so for example, if some candidate with a Copeland score of 14 is added into the Smith set, then all candidates with a Copeland score of 13 or more can also automatically be added into the Smith set, whereas with sequential comparison Condorcet methods, they require fewer pairwise comparisons than any other methods to find a member of the Smith set. Example using the Copeland ranking:

Losses and ties are bolded
	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 loses to C, so A through C (A, B, and C) are confirmed to be in the Smith set. C loses to D, so D is confirmed to be in the Smith set. D ties with E, so E is added into the Smith set. All of A through E beat all candidates not yet confirmed to be in the Smith set, so the Smith set is A through E.

Any Condorcet method that produces a Smith set ranking of the candidates in general can be used to find the Smith set by seeing if anyone pairwise beats or ties the candidates in the Smith set (1st place candidates), and if so, adding all candidates at those candidates' ranks or above in the voting method to the Smith set, and repeating. For example, if the 3rd place candidate in Schulze pairwise ties a 1st place candidate, then all candidates from 1st to 3rd place are in the Smith set, and then if a 6th place candidate pairwise beats one of the newly added candidates, all candidates from 1st to 6th are in the Smith set, etc.

Another way is to count the number of pairwise victories each candidate has, and then starting with the candidate(s) with the joint-most victories (who are confirmed to be in the Smith set), ignoring any victories they have against each other, check if they all have at least (number of candidates not confirmed to be in the Smith set) pairwise victories. If they do, they are the only members of the Smith set, but if they don't, then the candidates with the next-joint-highest victories are also in the Smith set. Repeat this procedure until the Smith set is found.

Notes

Most strategic voting in Smith-efficient Condorcet methods revolves around either shrinking the Smith set using compromising strategy (Favorite Betrayal), or burial to expand the Smith set. Both strategies involve either creating or closing Condorcet cycles by helping certain candidates get more or fewer pairwise victories.

It is worth noting for the sake of proving that many defeat-dropping Condorcet methods are Smith-efficient and pass ISDA that members of the Smith set can't be in a Condorcet cycle with candidates not in the Smith set. This is because by definition, no candidate not in the Smith set can pairwise defeat anyone in the Smith set, therefore they can't be involved in any such cycle. In addition, eliminating all but one Smith candidate makes the remaining one a Condorcet winner.

The Smith set can be somewhat of an equilibrium point in many voting methods, because a majority/plurality of voters are incentivized to go with a candidate in the set rather than a candidate not in the set by definition. For example:

17 A>B>C
17 B>C>A
17 C>A>B
49 D

Though there is a Condorcet cycle among A, B, and C, 51 voters prefer any of them to D, and therefore, even in voting methods which may otherwise have incentives for bullet voting, voters may prefer to help elect one of A, B, or C, rather than risk electing D.

The Smith set can usually be visualized by imagining voters supporting their 1st choice, and moving to support anyone they prefer over the candidate with the most 1st choices. This creates a series of head-to-head runoffs where the candidates in the Smith set "block" non-Smith candidates, but can cycle with each other. In this context, the head-to-head matchups essentially can be thought of as what the numbers look like as different groups of voters move around to take different sides.

The Smith Set found using an algorithmized version of Asset Voting.

Alternative Definitions

(Note: Most of this section is overly complicated.)

There are two definitions of the Smith set. One is general and holds for any voting method; the other can be used only when the votes permit a comparison of any pair of candidates. Thus, the Robert's Rules single elimination pairwise voting method (which is used for voting on motions and amendments) requires the more general definition because it doesn't elicit enough information to allow all pairs of alternatives to be compared. Most voting methods that use a single round of voting—even methods like Plurality Rule and Approval—are compatible with both definitions.

[Actually, Plurality and Approval always choose from the Smith set, when the definition referred to here as the simple definition is used. In that way, Plurality and Approval pass the Smith Criterion as it is often defined. But not when the Smith Criterion is defined as I define it two paragraphs below on this page]

(However, the definitions should be used cautiously when the voting method does not allow a vote to contain the voter's order of preference, because the pairwise comparisons will undercount voters and thus be misleading.)

The "Sincere Smith set", (also mentioned below on this page) is the basis for a definition of the Smith Criterion that is applicable to all voting systems, including Plurality and Approval.

Definition of sincere Smith set:

X is socially preferred to Y if more voters prefer X to Y than prefer Y to X. The sincere Smith set is the smallest set of candidates such that every candidate in the set is socially preferred to every candidate outside the set.

Smith Criterion:

If everyone votes sincerely, the winner should come from the sincere Smith set.

Note that this definition is applicable to Plurality and Approval (which don't pass), and is also applicable to Sequential Pairwise (which passes).

If the Smith Criterion were defined in terms of the voted Smith set, Plurality and Approval would pass.

The less general (but simpler) definition: The Smith set is the smallest non-empty subset of candidates such that, for each candidate x in the subset and each candidate y not in the subset, the number of votes that have x better than y exceeds the number of votes that have y better than x.

The general definition: The Smith set is the subset of candidates {x such that, for all y not equal to x, there exists an arrangement of k candidates z₁,z₂,...,z_k where z₁ = x and z_k = y and for all i from 1 to k-1 the number of votes that have z_i better than z_i₊₁ is at least as large as the number of votes that have z_i₊₁ better than z_i.} In other words, x is in the Smith set if and only if, for all y not equal to x there exists a "beats-or-ties path" from x to y.

Example:

35% rank A > B > C.

20% rank B > A > C.

45% rank C > B > A.

The Smith set is {B} with either definition. Using the less general definition: B is voted over A by a (65%) majority and B is voted over C by a (55%) majority, and the only smaller subset of the candidates is empty. Using the general definition: B is in the subset: When z_k=A, we can pick k=2; the number of votes that rank z₁(B) over z₂(A) is 65% and exceeds the number that rank z₂ over z₁. When z_k=C, pick k=2; the number of votes that rank B over C (55%) exceeds the number that rank C over B. A is not in the subset: When y=B, so that z_k=B, there does not exist a candidate z_k-1 such that the number of votes that rank z_k-1 over B exceeds the number of votes that rank B over z_k-1. C is not in the subset, by the same reasoning.

The Smith set represents one approach to identifying a subset of candidates from which an election method should choose a winner. The idea is to choose the "best compromise." (In the example above, B is the first or second choice of every voter.) The most widely used voting method, the sequential pairwise elimination method used when voting on motions and amendments under Robert's Rules of Order, always chooses an alternative in the Smith set.

Also of note is the sincere Smith set: the smallest non-empty set of candidates such that every candidate in the set is sincerely preferred by a majority of the voters over every candidate not in the set. (That isn't correct. It's only necessary that each candidate in the set be preferred to each candidate outside the set by more voters than vice-versa. It needn't be a majority Maybe some voters are indifferent between some candidate-pairs] Since the definition depends on voters' preferences, it does not matter what voting method is used, assuming voters' preferences do not depend on the voting method. However, that assumption is naive, because candidates who want to win choose positions on issues that they hope will help them win, and winning positions depend in part on the voting method, and candidates' positions affect voters' preferences. For example, Plurality Rule, Top Two Runoff, Instant Runoff and many other methods can cause candidates to avoid centrist positions due to the risk of being sandwiched between a candidate "on the left" and a candidate "on the right" whereas voting methods that satisfy the Smith criterion can cause candidates to take more centrist positions. In this important sense, the sincere Smith set (and the voted Smith set) depend on the voting method. However, this is beyond the scope of this article. (Unfortunately, many comparisons of voting methods naively oversimplify their analysis by assuming candidates' positions and voters' preferences are constant, and neglect the possibility that the most important criteria for comparing voting methods may involve the effects that voting methods have on candidates' positions.)

The Smith set can differ from the sincere Smith set because votes may misrepresent voters' preferences. (Voters sometimes have an incentive to strategically misrepresent their preferences, as the Gibbard-Satterthwaite "manipulability" theorem shows. Also, some voting methods such as "vote for one, plurality rule" and Approval Voting simply do not allow voters to accurately represent their preferences when there are more than two candidates.) When people say it is desirable that voting methods satisfy the Smith criterion, what they usually mean is that a candidate in the sincere Smith set should be elected. (Similarly, when people say it is desirable that voting methods satisfy the Condorcet criterion they mean it is desirable to elect the sincere Condorcet winner—which is defined according to voters' preferences rather than votes—when it exists.)

Satisfaction of the Smith criterion does not imply the winner is in the sincere Smith set. Therefore, satisfaction of additional criteria (for example, Truncation Resistance and Minimal Defense criterion) can help to elect a candidate in the sincere Smith set.

Two other names for the Smith set are the Top Cycle and the GETCHA set.

The Smith set and the sincere Smith set always exist, regardless of the voting method. When a Condorcet winner exists, the Smith set contains only that candidate. This means every voting method that satisfies the Smith criterion also satisfies the Condorcet criterion. Similarly, when a sincere Condorcet winner exists, the sincere Smith set contains only that candidate.

Below are two concepts offered for archival's sake, though they are not used in modern discussion.

Smith winner

The Smith winner is the "beats-all-winner" who would beat every other candidate in the two-choice head-to-head election got by erasing every other candidate from all votes. The Smith winner is a generalization of the pairwise champion (aka Condorcet winner) to encompass rated voting methods. A Smith method always elects a Smith winner if one exists.

In common usage, "Smith winner" usually refers to any member of the Smith set.

Smith method

A Smith method elects the "beats-all-winner" who would beat every other candidate in the two-choice head-to-head election got by erasing every other candidate from all votes. Smith method is a generalization of Condorcet method to encompass rated voting methods. A Smith method always elects a Smith winner if one exists.

"Smith method" could also simply mean a method that always elects from the Smith set.

Both of these two terms are related to Self-referential Smith-efficient Condorcet methods.

References

Smith, J. H.(1973). "Aggregation of preferences with variable electorate". Econometrica 41: 1027-1041.