Введение
Критерий голосования, требующий некоего правила большинства. Критерий Смита (иногда обобщенный критерий Кондорсе) — это критерий системы голосования, формализующий понятие правила большинства. Система голосования удовлетворяет критерию Смита, если она всегда выбирает кандидата из множества Смита, которое обобщает идею "победителя Кондорсе" для случаев, когда могут возникать циклы или ничьи, допуская несколько кандидатов, которые вместе могут рассматриваться как "победители Кондорсе". Метод Смита всегда выбирает кандидата из множества Смита. Критерий Смита также называют критерием верхнего (кондорсеевского) цикла, однако это может быть несколько вводящим в заблуждение: множество Смита иногда состоит из вырожденного цикла, содержащего только одного кандидата, "циклически" противостоящего самому себе (победитель Кондорсе), или пары кандидатов, находящихся в ничьей и "циклически" противостоящих друг другу. Альтернативный, более строгий критерий задается множеством Ландау.
The Smith criterion (sometimes the generalized Condorcet criterion) is a voting system criterion that formalizes the concept of a majority rule. A voting system satisfies the Smith criterion if it always elects a candidate from the Smith set, which generalizes the idea of a "Condorcet winner" to cases where there may be cycles or ties, by allowing for several who together can be thought of as being "Condorcet winners." A Smith method will always elect a candidate from the Smith set. The Smith criterion is also called the top (Condorcet) cycle criterion, but this can be slightly misleading: the Smith set sometimes consists of a degenerate cycle with only one candidate who "cycles" with themselves (a Condorcet winner), or a pair of tied candidates who "cycle" with each other. An alternative, stricter criterion is given by the Landau set.
Определение
Множество Смита можно вычислить с помощью алгоритма Флойда — Уоршелла за время Θ(n³) или алгоритма Косараджу за время Θ(n²).
Другие критерии
Любой метод голосования, удовлетворяющий критерию Смита, также удовлетворяет критерию победителя Кондорсе, поскольку, если существует победитель Кондорсе, то он является единственным кандидатом в множестве Смита. Методы Смита также удовлетворяют критерию проигравшего Кондорсе, потому что проигравший Кондорсе никогда не попадает в множество Смита. Это также подразумевает критерий взаимного большинства, так как множество Смита является подмножеством множества MMC. В литературе иногда путают множество Смита и множество Шварца. Миллер (1977, с. 775) указывает как альтернативное название для множества Смита, но на самом деле речь идет о множестве Шварца. Множество Шварца на самом деле является подмножеством множества Смита (и равно ему, если между членами множества Смита нет ничьих в парных сравнениях).
Соответствующие методы
Критерий Смита удовлетворяют методы ранжированных пар, метод Шульце, метод Нэнсона и несколько других методов. Более того, любой метод голосования можно модифицировать для удовлетворения критерию Смита, определяя множество Смита и исключая всех кандидатов, не входящих в него. Например, метод голосования Smith//Minimax применяет метод Minimax к кандидатам, входящим в множество Смита. Другой подход заключается в избрании члена множества Смита, который занимает наивысшее место в порядке предпочтений, определяемом методом голосования. Методы, не удовлетворяющие критерию Кондорсе, также не удовлетворяют критерию Смита. Однако некоторые методы Кондорсе (например, Minimax) могут не удовлетворять критерию Смита.