Критерий Смита (иногда обобщенный критерий Кондорса , но это может иметь другие значения) является голосование системы критерия определяется таким образом, что он удовлетворен , когда система голосования всегда выбирает кандидат , который находится в наборе Смита , который является самым маленьким непустым подмножеством кандидаты, так что каждый кандидат в подмножестве имеет большинство предпочтений по сравнению с каждым кандидатом не в подмножестве. (Кандидат X считается более предпочтительным по сравнению с другим кандидатом Y, если в соревновании один на один между X и Y количество избирателей, которые предпочитают X, а не Y, превышает количество избирателей, которые предпочитают Y, а не X. ) [1] Набор Смита назван в честь математика Джона Смита., чья версия критерия Кондорсе [1] на самом деле сильнее, чем определенная выше для функций общественного благосостояния. Бенджамин Уорд [2], вероятно, был первым, кто написал об этом наборе, который он назвал «набором большинства».
Множество Смит может быть вычислено с помощью Флойд-Воршалл алгоритма во время thetas ; ( п 3 ) или алгоритме косарайи в время thetas ; ( п 2 ).
Когда есть победитель Кондорсе - кандидат, пользующийся преимуществом большинства по сравнению со всеми другими кандидатами, - набор Смита состоит только из этого кандидата. Вот пример, в котором нет победителя Кондорсе: есть четыре кандидата: A, B, C и D. 40% избирателей имеют рейтинг D> A> B> C. 35% избирателей имеют рейтинг B> C> A> D. 25% избирателей имеют рейтинг C> A> B> D. Набор Смита - {A, B, C}. Все три кандидата в наборе Смита имеют большинство предпочтений по сравнению с D (поскольку 60% ставят каждый из них выше D). Множество Смита не является {A, B, C, D}, потому что определение требует наименьшего подмножества, которое удовлетворяет другим условиям. Множество Смита не является {B, C}, потому что B не предпочтительнее A; 65% имеют рейтинг A выше B. (и т. Д.)
за \ против | А | B | C | D |
---|---|---|---|---|
А | - | 65 | 40 | 60 |
B | 35 год | - | 75 | 60 |
C | 60 | 25 | - | 60 |
D | 40 | 40 | 40 | - |
Макс ОПП | 60 | 65 | 75 | 60 |
минимакс | 60 | 60 |
В этом примере при минимаксе A и D совпадают; под Smith / Minimax побеждает A.
Набор Смита также называют верхним циклом . [2] В приведенном выше примере три кандидата в наборе Смита находятся в цикле большинства «камень / ножницы / бумага» : A имеет рейтинг выше B с большинством в 65%, B имеет рейтинг выше C с большинством в 75%, и C имеет более высокий рейтинг, чем A, большинством в 60%. Однако термин «верхний цикл» может вводить в заблуждение, поскольку набор Смита может содержать кандидатов, которые не циклически повторяются. Например, когда есть победитель Кондорсе, он не зацикливается ни с какими альтернативами [3], а когда набор Смита состоит только из двух альтернатив, которые связываются попарно, они не проходят цикл с любыми альтернативами.
Прочие критерии
Любой метод выборов, соответствующий критерию Смита, также соответствует критерию Кондорсе , поскольку если есть победитель Кондорсе, то он является единственным кандидатом в наборе Смита. Очевидно, это означает, что невыполнение критерия Кондорсе автоматически означает несоблюдение и критерия Смита. Кроме того, такие наборы соответствуют критерию проигравшего по Кондорсе . Это примечательно, потому что даже некоторые методы Кондорсе этого не делают (Минимакс). Это также подразумевает критерий взаимного большинства , поскольку множество Смита является подмножеством множества MMC. [4]
Наборы Смита и Шварца иногда путают в литературе. Миллер (1977, с. 775) перечисляет GOCHA как альтернативное название для набора Смита, но на самом деле оно относится к набору Шварца. Множество Шварца на самом деле является подмножеством множества Смита (и равно ему, если нет попарных связей между членами множества Смита).
Соответствующие методы
Критерий Смита удовлетворяет ранговые пары , метод Шульца , метод Nanson в , метод Роберты Правила для голосования по движениям и изменениям, а также ряд других методов.
Методы, не отвечающие критерию Кондорсе, также не соответствуют критерию Смита. Некоторые методы Кондорсе, такие как Minimax , также не соответствуют критерию Смита.
Методы голосования, которые не соответствуют критерию Смита, могут быть изменены для его удовлетворения (обычно за счет других критериев). Один из подходов - применить метод голосования только к набору Смита. (Другими словами, начните с удаления из голосов кандидатов, не входящих в набор Смита.) Например, метод голосования Смит / Минимакс - это применение Minimax к кандидатам в наборе Смита. Другой подход состоит в том, чтобы выбрать того члена группы Смита, который является наивысшим в порядке завершения метода голосования.
Примеры
Минимакс
Критерий Смита подразумевает критерий взаимного большинства, поэтому несоответствие Minimax критерию взаимного большинства также является невыполнением критерия Смита. Обратите внимание, что множество S = {A, B, C} в примере - это множество Смита, а D - победитель минимакса.
Смотрите также
Рекомендации
- ^ «Четыре гибридных метода Кондорсе-Хара для выборов с одним победителем» .
Множество Смита - это наименьшее множество, в котором любой кандидат выиграет гонку один на один против любого кандидата, не участвующего. Таким образом, принцип Смита, который требует, чтобы правила голосования выбирали победивших кандидатов из множества Смита, является расширением принципа Кондорсе. это применимо ко всем результатам выборов.
- ^ http://cse.unl.edu/~lksoh/Classes/CSCE475_875_Fall17/handouts/10VotingSocialChoice.pdf
- ^ CW никому не проигрывает попарно, поэтому они не могут быть в цикле.
- ^ http://dss.in.tum.de/files/brandt-research/dodgson.pdf