Smith set

Wikipedia has an article on:

Smith set

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+1 is at least as large as the number of votes that have z_i+1 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.

An election method that always elects a candidate in the Smith Set is said to satisfy the Smith criterion.

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.

Properties

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

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.

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 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.

References

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

Properties

References

See also