Smith set
From Free net encyclopedia
In voting systems, the Smith set is the smallest set of candidates in a particular election such that each member beats every other candidate outside the set in a pairwise election. Ideally, this set consists of only one candidate, the Condorcet winner. Conversely, an occurrence of Condorcet's paradox implies that the set has more than one member. See also Schwartz set. This concept was devised by the mathematician J. H. Smith in 1973 (JH Smith, Aggregation of preferences with variable electorate, Econometrica, vol. 41, pp. 1027--1041, 1973).
Voting methods that always elect a candidate from the Smith set pass the "Smith criterion," and are said to be "Smith-efficient." Some argue that Smith-efficient methods have the best claim to providing majority rule in multi-candidate elections.
It is clear that a Smith set exists by observing that we can construct a directed graph where the vertices are the candidates and there is an edge from A to B if A is pairwise preferred to B. Such a graph equals its own transitive closure, since the preference relation is transitive, and its strongly connected components are cliques of members which all beat one another. If we contract each of these cliques to a single vertex representing a set of candidates, we have a directed acyclic graph, which necessarily has a vertex with zero in-degree, and the set of candidates this vertex corresponds to is the Smith set.