Smith set
Encyclopedia
In voting system
s, the Smith set, named after John H. Smith, is the smallest non-empty set of candidates in a particular election such that each member beats every other 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".
A set of candidates where every member of the set pair-wise beats every member outside of the set is also known as a dominating set.
is closely related to and is always a subset
of the Smith set. The Smith set is larger if and only if a candidate in the Schwartz set has a pair-wise tie with a candidate that is not in the Schwartz set.
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:
Note that candidates of the second type can only exist after candidates of the first type have be added.
R on a set A can generate a natural partial order on the R-cycle
equivalence classes of set A, so that xRy implies [x] ≥ [y].
When R is the Beats-or-Ties binary relation on the set of candidates defined by x Beats-or-Ties y if and only if x pair-wise beats or ties y, then the resulting partial order is the beat-or-tie order which is a total order
. The Smith set is the maximal element
of the beat-or-tie order.
in time Θ
(n3). It can also be calculated using a version of Kosaraju's algorithm
in time Θ
(n2).
Voting system
A voting system or electoral system is a method by which voters make a choice between options, often in an election or on a policy referendum....
s, the Smith set, named after John H. Smith, is the smallest non-empty set of candidates in a particular election such that each member beats every other 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
Smith criterion
The Smith criterion is a voting systems criterion defined such that its satisfaction by a voting system occurs when the system always picks the winner from the Smith set, the smallest set of candidates such that every member of the set is pairwise preferred to every candidate not in the set...
and are said to be "Smith-efficient".
A set of candidates where every member of the set pair-wise beats every member outside of the set is also known as a dominating set.
Properties
- The Smith set always exists and is well-defined. There is only one smallest dominating set since dominating sets are nested, non-empty, and the set of candidates is finite.
- The Smith set can have more than one candidate, either because of pair-wise ties or because of cycles, such as in Condorcet's paradox.
- The Condorcet winnerCondorcet criterionThe Condorcet candidate or Condorcet winner of an election is the candidate who, when compared with every other candidate, is preferred by more voters. Informally, the Condorcet winner is the person who would win a two-candidate election against each of the other candidates...
, if one exists, is the sole member of the Smith set. If weak Condorcet winners exist, they are in the Smith set.
Schwartz set comparison
The Schwartz setSchwartz set
In voting systems, the Schwartz set is the union of all Schwartz set components. A Schwartz set component is any non-empty set S of candidates such that...
is closely related to and is always a subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of the Smith set. The Smith set is larger if and only if a candidate in the Schwartz set has a pair-wise tie with a candidate that is not in the Schwartz set.
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 have pair-wise ties with candidates in the set,
- candidates that beat a candidate in the set.
Note that candidates of the second type can only exist after candidates of the first type have be added.
Alternative formulation
Any binary relationBinary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
R on a set A can generate a natural partial order on the R-cycle
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
equivalence classes of set A, so that xRy implies [x] ≥ [y].
When R is the Beats-or-Ties binary relation on the set of candidates defined by x Beats-or-Ties y if and only if x pair-wise beats or ties y, then the resulting partial order is the beat-or-tie order which is a total order
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
. The Smith set is the maximal element
Maximal element
In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually...
of the beat-or-tie order.
Algorithms
The Smith set can be calculated with the Floyd-Warshall algorithmFloyd-Warshall algorithm
In computer science, the Floyd–Warshall algorithm is a graph analysis algorithm for finding shortest paths in a weighted graph and also for finding transitive closure of a relation R...
in time Θ
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n3). It can also be calculated using a version of Kosaraju's algorithm
Kosaraju's algorithm
In computer science, the Kosaraju-Sharir algorithm is an algorithm to find the strongly connected components of a directed graph. Aho, Hopcroft and Ullman credit it to an unpublished paper from 1978 by S. Rao Kosaraju and Micha Sharir...
in time Θ
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n2).