Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Smith criterion
Summary
The Smith criterion (sometimes generalized Condorcet criterion, but this can have other meanings) is a voting systems criterion defined such that it's satisfied when a voting system always elects a candidate that is in the Smith set, which is the smallest non-empty subset of the candidates such that every candidate in the subset is majority-preferred over every candidate not in the subset. (A candidate X is said to be majority-preferred over another candidate Y if, in a one-on-one competition between X & Y, the number of voters who prefer X over Y exceeds the number of voters who prefer Y over X.) The Smith set is named for mathematician John H Smith, whose version of the Condorcet criterion is actually stronger than that defined above for social welfare functions. Benjamin Ward was probably the first to write about this set, which he called the "majority set".
The Smith set is also called the top cycle. The term top cycle may be somewhat misleading, however, since the Smith set can contain candidates that do not cycle. For examples, when there is a Condorcet winner it doesn't cycle with any alternatives, and when the Smith set consists only of two alternatives that tie pairwise, the two do not cycle with any alternatives.
The Smith set can be calculated with the Floyd–Warshall algorithm in time Θ(n3) or Kosaraju's algorithm in time Θ(n2).
When there is a Condorcet winner—a candidate that is majority-preferred over all other candidates—the Smith set consists of only that candidate. Here is an example 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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.