Критерий Смита - Smith criterion
В Критерий Смита (иногда обобщенный критерий Кондорсе, но это может иметь другое значение) критерий системы голосования определяется таким образом, что удовлетворяется, когда система голосования всегда выбирает кандидата, который находится в Набор Смита, который представляет собой наименьшее непустое подмножество кандидатов, так что каждый кандидат в подмножестве является более предпочтительным по сравнению с каждым кандидатом, не входящим в подмножество. (Кандидат X считается более предпочтительным по сравнению с другим кандидатом Y, если в соревновании один на один между X и Y количество избирателей, которые предпочитают X, а не Y, превышает количество избирателей, которые предпочитают Y, а не X. ) [1]Набор Смита назван в честь математика. Джон Х. Смит, чья версия Критерий Кондорсе[1] на самом деле сильнее, чем определенное выше для функций социального обеспечения. Бенджамин Уорд[2] вероятно, был первым, кто написал об этом наборе, который назвал «набором большинства».
Набор Смита можно рассчитать с помощью Алгоритм Флойда-Уоршолла во время Θ(п3) или же Алгоритм Косараджу во время Θ(п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 как альтернативное название для набора Смита, но на самом деле оно относится к набору Шварца. Множество Шварца на самом деле является подмножеством множества Смита (и равно ему, если между членами множества Смита нет попарных связей).
Соответствующие методы
Критерий Смита удовлетворяет Рейтинговые пары, Метод Шульце, Метод Нансона, метод правил Роберта для голосования по предложениям и поправкам и ряд других методов.
Методы, не соответствующие критерию Кондорсе, также не соответствуют критерию Смита. Некоторые методы Кондорсе, например Минимакс, также не соответствуют критерию Смита.
Методы голосования, которые не соответствуют критерию Смита, могут быть изменены для его соответствия (обычно за счет других критериев). Один из подходов - применить метод голосования только к набору Смита. (Другими словами, начните с удаления из голосов кандидатов, не входящих в набор Смита.) Например, метод голосования Смит / Минимакс - это применение 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