критерий Смита
Критерий Смита (иногда обобщенный критерий Кондорсе ) — критерий системы голосования , который формализует концепцию правила большинства. Система голосования удовлетворяет критерию Смита, если она всегда выбирает кандидата из множества Смита , что обобщает идею «победителя Кондорсе» на случаи, когда могут быть циклы или ничьи , допуская несколько кандидатов, которых вместе можно рассматривать как «Победители Кондорсе». Метод Смита всегда выбирает кандидата из множества Смита.
Критерий Смита также называют верхнего цикла (Кондорсе) критерием , но это может немного вводить в заблуждение: множество Смита иногда состоит из вырожденного цикла, в котором есть только один кандидат, который «циклизируется» сам с собой (победитель Кондорсе), или пара связали кандидатов, которые «циклизуются» друг с другом. [1]
Альтернативный, более строгий критерий дает множество Ландау .
Определение
[ редактировать ]Множество Смита можно вычислить с помощью алгоритма Флойда–Уоршалла за время Θ ( n 3 ) или алгоритм Косараджу за время Θ ( n 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. (и т. д.)
| за\против | А | Б | С | Д |
|---|---|---|---|---|
| А | — | 65 | 40 | 60 |
| Б | 35 | — | 75 | 60 |
| С | 60 | 25 | — | 60 |
| Д | 40 | 40 | 40 | — |
| максимум | 60 | 65 | 75 | 60 |
| минимакс | 60 | 60 |
В этом примере в минимаксе A и D связаны; при Смите//Минимаксе побеждает А.
В приведенном выше примере три кандидата из набора Смита находятся в мажоритарном цикле «камень/ножницы/бумага» : A имеет рейтинг выше B с большинством в 65%, B имеет рейтинг выше C с большинством в 75%, а C 60% голосов поставили его выше А.
Другие критерии
[ редактировать ]Любой метод выборов, соответствующий критерию Смита, также соответствует критерию победителя Кондорсе , поскольку если есть победитель Кондорсе, то он является единственным кандидатом в наборе Смита. Методы Смита также соответствуют критерию проигравшего Кондорсе , поскольку проигравший Кондорсе никогда не попадает в множество Смита. Это также подразумевает критерий взаимного большинства , поскольку множество Смита является подмножеством множества MMC. [2]
множество Смита и множество Шварца В литературе иногда путают . Миллер (1977, стр. 775) указывает альтернативное название набора Смита, но на самом деле оно относится к множеству Шварца. Множество Шварца на самом деле является подмножеством множества Смита (и равно ему, если между членами множества Смита нет попарных связей).
Соответствующие методы
[ редактировать ]Критерию Смита удовлетворяют ранжированные пары , метод Шульце , метод Нансона и ряд других методов. [ нужна ссылка ] Более того, любой метод голосования можно модифицировать, чтобы он удовлетворял критерию Смита, найдя множество Смита и исключив всех кандидатов за его пределами. Например, метод голосования Smith//Minimax применяет Minimax к кандидатам из набора Смита. Другой подход заключается в выборе члена множества Смита, который находится на самом высоком месте в порядке завершения метода голосования.
Методы, не отвечающие критерию Кондорсе, также не соответствуют критерию Смита. Однако некоторые методы Кондорсе (например, Minimax ) могут не соответствовать критерию Смита.
Примеры
[ редактировать ]Минимакс
[ редактировать ]Критерий Смита подразумевает критерий взаимного большинства, поэтому неспособность Minimax удовлетворить критерию взаимного большинства также является неспособностью удовлетворить критерий Смита. Обратите внимание, что набор S = {A, B, C} в этом примере является набором Смита, а D — победителем минимакса.