View source for Smith set

{{Short description|Set preferred to any other by a majority}}
{{Electoral systems sidebar|expanded=Paradox}}
The '''Smith''' '''set''',{{notetag|Many authors reserve the term "Schwartz set" for the strict Smith set described below.}} sometimes called the '''top-cycle''' generalizes the idea of a [[Condorcet winner]] to cases where [[Condorcet paradox|no such winner exists]]. It does so by allowing cycles of candidates to be treated jointly, as if they were a single Condorcet winner.<ref>{{cite web|last=Soh|first=Leen-Kiat|title=Voting: Preference Aggregating & Social Choice [CSCE475/875 class handout]|date=2017-10-04|url=http://cse.unl.edu/~lksoh/Classes/CSCE475_875_Fall17/handouts/10VotingSocialChoice.pdf}}</ref> Voting systems that always elect a candidate from the Smith set pass the '''Smith criterion'''. The Smith set and Smith criterion are both named for mathematician [[John H. Smith (mathematician)|John H. Smith]]. 

The Smith set provides one standard of optimal choice for an election outcome. An alternative, stricter criterion is given by the [[Landau set]].

== Definition ==
The Smith set is formally defined as the smallest set such that every candidate inside the set ''S'' pairwise defeats every candidate outside ''S''.

Alternatively, it can be defined as the set of all candidates with a (non-strict) [[beatpath]] to any candidate who defeats them.

A set of candidates each of whose members pairwise defeats every candidate outside the set is known as a ''dominating set''. Thus the Smith set is also called the '''smallest dominating set'''.

=== Strict top-cycle (Schwartz set) ===
The Schwartz set is equivalent to the Smith set, except it ignores tied votes. Formally, the Schwartz set is the set such that any candidate inside the set has a ''strict'' [[beatpath]] to any candidate who defeats them.

The Smith set can be constructed from the Schwartz set by repeatedly adding two types of candidates until no more such candidates exist outside the set:

* candidates that are pairwise-tied with candidates in the set,
* candidates that defeat a candidate in the set.

Note that candidates of the second type can only exist after candidates of the first type have been added.


==Properties==

* The Smith set always exists and is non-empty. It is also well-defined (see next section).
* 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 criterion|Condorcet winner]], if one exists, is the sole member of the Smith set. If [[Condorcet method#Related terms|weak Condorcet winners]] exist they are in the Smith set.
* The Smith set is always a subset of the smallest [[Mutual majority criterion|mutual majority]]-preferred set of candidates.<ref name="Brandt">{{cite journal | last=Brandt | first=Felix | title=Some Remarks on Dodgson's Voting Rule | journal=Mathematical Logic Quarterly | publisher=Wiley | volume=55 | issue=4 | date=2009-07-17 | issn=0942-5616 | doi=10.1002/malq.200810017 | pages=460–463}}</ref>

===Properties of dominating sets===
'''''Theorem:''''' Dominating sets are ''nested''; that is, of any two dominating sets in an election, one is a subset of the other.

'''''Proof:''''' Suppose on the contrary that there exist two dominating sets, ''D'' and ''E'', neither of which is a subset of the other. Then there must exist candidates {{nowrap|''d'' ∈ ''D'',}} {{nowrap|''e'' ∈ ''E''}} such that {{nowrap|''d'' ∉ ''E''}} and {{nowrap|''e'' ∉ ''D''.}} But by hypothesis ''d'' defeats every candidate not in ''D'' (including ''e'') while ''e'' defeats every candidate not in ''E'' (including ''d''), a contradiction. ∎

'''''Corollary:''''' It follows that the Smith set is the smallest non-empty dominating set, and that it is well defined.

'''''Theorem:''''' If ''D'' is a dominating set, then there is some threshold θ<sub>''D''</sub> such that the elements of ''D'' are precisely the candidates whose [[Copeland's method|Copeland scores]] are at least θ<sub>''D''</sub>. (A candidate's Copeland score is the number of other candidates whom he or she defeats plus half the number of other candidates with whom he or she is tied.)

'''''Proof:''''' Choose ''d'' as an element of ''D'' with minimum Copeland score, and identify this score with θ<sub>''D''</sub>. Now suppose that some candidate {{nowrap|''e'' ∉ ''D''}} has a Copeland score not less than θ<sub>''D''</sub>. Then since ''d'' belongs to ''D'' and ''e'' doesn't, it follows that ''d'' defeats ''e''; and in order for ''e''{{'}}s Copeland score to be at least equal to ''d''{{'}}s, there must be some third candidate ''f'' against whom ''e'' gets a better score than does ''d''. If {{nowrap|''f'' ∈ ''D'',}} then we have an element of ''D'' who does not defeat ''e'', and if {{nowrap|''f'' ∉ ''D''}} then we have a candidate outside of ''D'' whom ''d'' does not defeat, leading to a contradiction either way. ∎

==The Smith criterion==
The Smith criterion is a [[Voting system criteria|voting system criterion]] that formalizes a stronger idea of [[majority rule]] than the [[Condorcet winner criterion|Condorcet criterion]]. A [[voting system]] satisfies the Smith criterion if it always picks a candidate from the Smith set.

Though less common, the term '''Smith-efficient''' has also been used for methods that elect from the Smith set.<ref name="y421">{{citation | last=Boudet | first=Samuel | title=Bipartisan/Range Voting in Two Rounds Reaches a Promising Balance between Efficiency and Strategy-Resistance | publisher=MDPI AG | date=2023-09-06 | doi=10.20944/preprints202309.0388.v1 | doi-access=free | page=}}</ref>

Here is an example of an electorate in which there is no Condorcet winner: There are four candidates: A, B, C and D. 40% of the voters rank D>A>B>C. 35% of the voters rank B>C>A>D. 25% of the voters rank C>A>B>D. The Smith set is {A,B,C}. All three candidates in the Smith set are majority-preferred over D (since 60% rank each of them over D). The Smith set is not {A,B,C,D} because the definition calls for the ''smallest'' subset that meets the other conditions. The Smith set is not {B,C} because B is not majority-preferred over A; 65% rank A over B. (Etc.)
{| class="wikitable"
!{{diagonal split header|pro|con}}
!A
!B
!C
!D
|-
!A
|—
|65
|40
|60
|-
!B
|35
|—
|75
|60
|-
!C
|60
|25
|—
|60
|-
!D
|40
|40
|40
|—
|-
!max opp
|60
|65
|75
|60
|-
!minimax
|60
|
|
|60
|}
In this example, under minimax, A and D tie; under Smith//Minimax, A wins.

In the example above, the three candidates in the Smith set are in a "rock/paper/scissors" ''majority cycle'': A is ranked over B by a 65% majority, B is ranked over C by a 75% majority, and C is ranked over A by a 60% majority.

=== Other criteria ===
Any election method that complies with the Smith criterion also complies with the [[Condorcet criterion|Condorcet winner criterion]], since if there is a Condorcet winner, then it is the only candidate in the Smith set. Smith methods also comply with the [[Condorcet loser criterion]], because a Condorcet loser will never fall in the Smith set. It also implies the [[mutual majority criterion]], since the Smith set is a subset of the MMC set.<ref name="Brandt" /> Conversely, any method that fails any of those three majoritarian criteria (Mutual majority, Condorcet loser or Condorcet winner) will also fail the Smith criterion.

=== Complying methods ===
The Smith criterion is satisfied by [[ranked pairs]], [[Schulze method|Schulze's method]], [[Nanson's method]], and several other methods. Moreover, any voting method can be modified to satisfy the Smith criterion, by finding the Smith set and eliminating any candidates outside of it. 

For example, the voting method Smith//Minimax applies Minimax to the candidates in the Smith set. Another example is the [[Tideman alternative method|Tideman alternative]] method, which alternates between eliminating candidates outside of the Smith set, and eliminating the candidate who was the plurality loser (similar to [[Instant-runoff voting|instant-runoff]]), until a Condorcet winner is found. A different approach is to elect the member of the Smith set that is highest in the voting method's order of finish. 

Methods failing the Condorcet criterion also fail the Smith criterion. However, some Condorcet methods (such as [[Minimax Condorcet|Minimax]]) can fail the Smith criterion.

==Relation to other tournament sets==
{{Main|Tournament solution}}
The Smith set contains the [[Copeland set]] and [[Landau set]] as subsets.

It also contains the Banks set and the [[Bipartisan set]]. A number of other subsets of the Smith set have been defined as well.<ref name="BrandtTS">{{cite journal | last1=Brandt | first1=Felix | last2=Brill | first2=Markus | last3=Harrenstein | first3=Paul | title=Extending tournament solutions | journal=Social Choice and Welfare | publisher=Springer Science and Business Media LLC | volume=51 | issue=2 | date=2018-01-16 | issn=0176-1714 | doi=10.1007/s00355-018-1112-x | url=https://cdn.aaai.org/ojs/8792/8792-13-12320-1-2-20201228.pdf |quote=For many tournament solutions, generalizations or extensions to weak tournaments have been proposed in the literature}}</ref>

==Computing the Smith set==
The Smith set can be calculated with the [[Floyd–Warshall algorithm]] in time '''[[Big O notation|Θ]]'''(''n''<sup>3</sup>) or [[Kosaraju's algorithm]] in time '''Θ'''(''n''<sup>2</sup>).

=== Detailed algorithm ===
The algorithm can be presented in detail through an example. Suppose that the results matrix is as follows:
{| class="wikitable"
! {{diagonal split header|1st|2nd}}
!A
!B
!C
!D
!E
!F
!G
| rowspan="8" |
!score
|-
!A
|–
|1
|1
|1
|1
|1
|0
|5
|-
!B
|0
|–
|0
|0
|1
|0
|0
|1
|-
!C
|0
|1
|–
|0
|1
|{{sfrac|1|2}}
|1
|3{{sfrac|1|2}}
|-
!D
|0
|1
|1
|–
|1
|1
|1
|5
|-
!E
|0
|0
|0
|0
|–
|0
|0
|0
|-
!F
|0
|1
|{{sfrac|1|2}}
|0
|1
|–
|0
|2{{sfrac|1|2}}
|-
!G
|1
|1
|0
|0
|1
|1
|–
|4
|}
Here an entry in the main table is 1 if the first candidate was preferred to the second by more voters than preferred the second to the first; 0 if the opposite relation holds; and {{sfrac|1|2}} if there is a tie. The final column gives the Copeland score of the first candidate.

The algorithm to compute the Smith set is agglomerative: it starts with the Copeland set, which is guaranteed to be a subset of it but will often be smaller, and adds items until no more are needed. The first step is to sort the candidates according to score:
{| class="wikitable"
! {{diagonal split header|1st|2nd}}
!A
!D
!G
!C
!F
!B
!E
| rowspan="8" |
!score
|-
!A
|–
|1
|0
|1
|1
|1
|1
|5
|-
!D
|0
|–
|1
|1
|1
|1
|1
|5
|-
!G
|1
|0
|–
|0
|1
|1
|1
|4
|-
!C
|0
|0
|1
|–
|{{sfrac|1|2}}
|1
|1
|3{{sfrac|1|2}}
|-
!F
|0
|0
|0
|{{sfrac|1|2}}
|–
|1
|1
|2{{sfrac|1|2}}
|-
!B
|0
|0
|0
|0
|0
|–
|1
|1
|-
!E
|0
|0
|0
|0
|0
|0
|–
|0
|}
We look at the highest score (5) and consider the candidates (Copeland winners) whose score is at least this high, i.e. {A,D}. These certainly belong to the Smith set, and any candidates whom they do not defeat will need to be added. To find undefeated candidates we look at the cells in the table below the top-left 2×2 square containing {A,D} (this square is shown with a broken border): the cells in question are shaded yellow in the table. We need to find the lowest (positionally) non-zero entry among these cells, which is the cell in the G row. All candidates as far down as this row, and any lower rows with the same score, need to be added to the set, which expands to {A,D,G}.

Now we look at any new cells which need to be considered, which are those below the top-left square containing {A,D,G}, but excluding those in the first two columns which we have already accounted for. The cells which need attention are shaded pale blue. As before we locate the positionally lowest non-zero entry among the new cells, adding all rows down to it, and all rows with the same score as it, to the expanded set, which now comprises {A,D,G,C}.

We repeat the operation for the new cells below the four members which are known to belong to the Smith set. These are shaded pink, and allow us to find any candidates not defeated by any of {A,D,G,C}. Again there is just one, F, whom we add to the set.

The cells which come into consideration are shaded pale green, and since all their entries are zero we do not need to add any new candidates to the set, which is therefore fixed as {A,D,G,C,F}. And by noticing that all the entries in the black box are zero, we have confirmation that all the candidates above it defeat all the candidates within it.

The following C function illustrates the algorithm by returning the cardinality of the Smith set for a given doubled results matrix ''r'' and array ''s'' of doubled Copeland scores. There are ''n'' candidates; ''r<sub>i&nbsp;j</sub>'' is 2 if more voters prefer ''i'' to ''j'' than prefer ''j'' to ''i'', 1 if the numbers are equal, and 0 if more voters prefer ''j'' to ''i'' than prefer ''i'' to ''j''&nbsp;; ''s<sub>i</sub>'' is the sum over ''j'' of the ''r<sub>i&nbsp;j&nbsp;</sub>''. The candidates are assumed to be sorted in decreasing order of Copeland score.<syntaxhighlight lang="c">
int smithset(int ** r, int * s, int n) {
  int row, col, lhs, rhs;
  for (rhs = 1, lhs = 0; lhs < rhs; lhs = rhs, rhs = row + 1) {
    for (; rhs < n && s[rhs] == s[rhs - 1]; rhs++); /* this line optional */
    for (col = rhs, row = n; col == rhs && row >= rhs; row--)
      for (col = lhs; col < rhs && r[row - 1][col] == 0; col++);
  }
  return lhs;
}
</syntaxhighlight>

==See also==

* [[Condorcet criterion]]
* [[Condorcet method]]
* [[Landau set]]
* [[Preorder]]
* [[Partial order]]
* [[Maximal and minimal elements]] - the Smith set can be defined as the maximal elements of a particular partial order.

==Notes==
<references group="note" />
==References==
<references />

== Further reading ==
* {{cite journal |author=Ward, Benjamin |year=1961 |title=Majority Rule and Allocation |journal=Journal of Conflict Resolution |volume=5 |issue=4 |pages=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.
* {{cite journal |author=Smith, J.H. |year=1973 |title=Aggregation of Preferences with Variable Electorates |journal=Econometrica |publisher=The Econometric Society |volume=41 |issue=6 |pages=1027–1041 |doi=10.2307/1914033 |jstor=1914033 |authorlink=John H. Smith (mathematician)}} 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.
* {{cite journal |author=Fishburn, Peter C. |year=1977 |title=Condorcet Social Choice Functions |journal=SIAM Journal on Applied Mathematics |volume=33 |issue=3 |pages=469–489 |doi=10.1137/0133030}} Narrows Smith's generalized Condorcet Criterion to the smallest dominating set and calls it Smith's Condorcet Principle.
* {{cite book |last=Schwartz |first=Thomas |title=The Logic of Collective Choice |publisher=Columbia University Press |year=1986 |location=New York}} Discusses the Smith set (named GETCHA) and the Schwartz set (named GOTCHA) as possible standards for optimal collective choice.
* {{cite journal |author=Schwartz, Thomas |year=1970 |title=On the Possibility of Rational Policy Evaluation |journal=Theory and Decision |volume=1 |pages=89–106 |doi=10.1007/BF00132454 |s2cid=154326683}}  Introduces the notion of the Schwartz set at the end of the paper as a possible alternative to maximization, in the presence of cyclic preferences, as a standard of rational choice.
* {{cite journal |author=Schwartz, Thomas |year=1972 |title=Rationality and the Myth of the Maximum |journal=Noûs |publisher=Noûs, Vol. 6, No. 2 |volume=6 |issue=2 |pages=97–117 |doi=10.2307/2216143 |jstor=2216143}}  Gives an axiomatic characterization and justification of the Schwartz set as a possible standard for optimal, rational collective choice.
* {{cite journal |author=Deb, Rajat |year=1977 |title=On Schwart's Rule |journal=Journal of Economic Theory |volume=16 |pages=103–110 |doi=10.1016/0022-0531(77)90125-9}}  Proves that the Schwartz set is the set of undominated elements of the transitive closure of the pairwise preference relation.
* Green-Armytage, James. [http://www.votingmatters.org.uk/ISSUE29/I29P1.pdf Four Condorcet-Hare Hybrid Methods for Single-Winner Elections].
* Somdeb Lahiri (nd), "Group and multi-criteria decision making". Outlines some properties of choice sets.

[[Category:Electoral system criteria]]