Smith crowd
 |
This item has been on the quality assurance side of the portal mathematics entered. This is done in order to bring the quality of the mathematics articles to an acceptable level .
Please help fix the shortcomings in this article and please join the discussion ! ( Enter article ) |
When elected, the Smith set is the smallest non-empty set of candidates, each of which would defeat any candidate outside the set in a purely pairwise comparison. The Smith crowd sets a standard for the optimal choice of an election result. Voting systems in which one candidate from the Smith crowd always wins, meet the Smith criterion and are considered "Smith efficient".
A group of candidates whose members defeat each member outside the group in pairs is called a dominant group . The Smith crowd is the smallest possible dominant group.
The Smith set is named after John H. Smith, it is also known as the Top Cycle or Generalized Top Choice Assumption (GETCHA).
properties
- The Smith set always exists and is uniquely determined. There is only a smallest dominant set because dominant sets are nested and not empty and the set of candidates is finite.
- The Smith crowd can have more than one candidate, either due to pairwise ties or due to cycles as in Condorcet's Paradox .
- The Condorcet winner , if any, is the only member of the Smith crowd. If there are weak Condorcet winners, they're all in the Smith crowd.
- The Smith set is always a subset of the set given by the majority criterion for solid coalitions if its requirements are met.
Algorithms
The Smith set can be calculated in time O using the Floyd-Warshall algorithm . It can also be calculated in time O with a version of the Kosaraju algorithm or the Tarjan algorithm .
You can also find them by creating a pairwise comparison matrix of candidates who paired according to their number of wins minus pairwise defeats (a ranking of the Copeland method ) are ordered, and then for the least square of the cells studied far left, which so it can be covered that all cells to the right of these cells show victories in pairs. All candidates named to the left of these cells are in the Smith set
Example with the Copeland ranking:
| A. | B. | C. | D. | E. | F. | G | |
|---|---|---|---|---|---|---|---|
| A. | --- | victory | loss | victory | victory | victory | victory |
| B. | loss | --- | victory | victory | victory | victory | victory |
| C. | victory | loss | --- | loss | victory | victory | victory |
| D. | loss | loss | victory | --- | draw | victory | victory |
| E. | loss | loss | loss | draw | --- | victory | victory |
| F. | loss | loss | loss | loss | loss | --- | victory |
| G | loss | loss | loss | loss | loss | loss | --- |
A loses to C, so all candidates from A to C (A, B, and C) are confirmed to be in the Smith set. There is a comparison where a candidate who has already been confirmed as a member of the Smith set loses or is undecided against someone who has not yet been confirmed as a member of the Smith set: C loses to D; So this confirms that D belongs to the Smith set. There is another such comparison: D is undecided against E, so E is added to the Smith set. Since all candidates from A to E beat all other, as yet unconfirmed candidates, the Smith set only consists of candidates A to E.
See also
credentials
- Ward, Benjamin: Majority Rule and Allocation . In: Journal of Conflict Resolution . 5, No. 4, 1961, pp. 379-389. doi : 10.1177 / 002200276100500405 . In an analysis of serial decision making based on majority rule, describes the Smith set and the Schwartz set.
- Smith, JH: Aggregation of Preferences with Variable Electorates . In: Econometrica . 41, No. 6, 1973, pp. 1027-1041. doi : 10.2307 / 1914033 . 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.
- Fishburn, Peter C .: Condorcet Social Choice Functions . In: SIAM Journal on Applied Mathematics . 33, No. 3, 1977, pp. 469-489. doi : 10.1137 / 0133030 . Narrows Smith's generalized Condorcet Criterion to the smallest dominating set and calls it Smith's Condorcet Principle.
- Schwartz, Thomas (1986). The Logic of Collective Choice. New York: Columbia University Press. Discusses the Smith set (named GETCHA) and the Schwartz set (named GOTCHA) as possible standards for optimal collective choice.