В системах голосования , то набор Смита , названный в честь Джона Х. Смита , но также известный как верхний цикл , или как обобщенным Top-Choice Успенская (стучи), является наименьшим непустое множество кандидатов в конкретных выборах , так что каждый член побеждает каждого кандидата вне набора на парных выборах. Набор Смита обеспечивает единый стандарт оптимального выбора результатов выборов. Системы голосования, которые всегда выбирают кандидата из набора Смита, соответствуют критерию Смита и считаются «эффективными по Смиту».
Набор кандидатов, каждый из членов которого попарно побеждает каждого кандидата вне набора, известен как доминирующий набор .
Свойства наборов Смита [ править ]
- Множество Смита всегда существует и четко определено (см. Следующий раздел).
- Набор Смита может иметь более одного кандидата либо из-за парных связей, либо из-за циклов, например, в парадоксе Кондорсе .
- Победитель Кондорсе , если таковой существует, является единственным членом набора Смита. Если существуют слабые победители Кондорсе, то они входят в набор Смита.
- Набор Смита всегда является подмножеством предпочтительного для взаимного большинства набора кандидатов, если таковой существует. [1]
Свойства доминирующих множеств [ править ]
Теорема: доминирующие множества вложены ; то есть из любых двух доминирующих групп на выборах одна является подмножеством другой.
Доказательство. Предположим противное, что существуют два доминирующих множества, D и E , ни одно из которых не является подмножеством другого. Тогда должны существовать кандидатов d ∈ D , е ∈ E такоечто d ∉ E и электронной ∉ D . Но по гипотезе d побеждает каждого кандидата не в D (включая e ), в то время как e побеждает всех кандидатов не в E (включая d ), что является противоречием. ∎
Следствие: Отсюда следует, что множество Смита является наименьшим непустым доминирующим множеством и что оно хорошо определено.
Теорема: Если D является доминирующим множеством, то есть некоторый порог θ D такихчто элементы D являются именно кандидатами, Copeland оценки , по крайней мереθ D . (Оценка кандидата по Коупленду - это количество других кандидатов, которых он или она побеждает, плюс половина количества других кандидатов, с которыми он или она связаны.)
Доказательство: Выберите D как элемент D с минимальной Copeland балла, и идентифицировать этот счет сthetas ; D . Теперь предположимчто некоторые кандидат е ∉ D имеет Copeland забить не менее thetas ; D . Тогда, поскольку d принадлежит D, а e нет, отсюда следует, что d побеждает e ; и для тогочтобы е « s Copeland оценка, по крайней мереравными d » s, должен быть какойто третий кандидат е против которого е получает лучший результатчем делает д . Еслиf ∈ D , то у нас есть элемент D, который не побеждает e , и если f ∉ D, то у нас есть кандидат вне D, которого d не побеждает, что в любом случае приводит к противоречию. ∎
Сравнение наборов Шварца [ править ]
Набор Шварца , известный как обобщенная аксиома оптимального выбора или GOCHA, тесно связан с множеством Смита и всегда является его подмножеством . Множество Смита больше тогда и только тогда, когда кандидат в наборе Шварца попарно связан с кандидатом, которого нет в множестве Шварца.
Набор Смита может быть построен из набора Шварца путем многократного добавления двух типов кандидатов до тех пор, пока такие кандидаты не перестанут существовать вне набора:
- кандидаты, имеющие попарные связи с кандидатами в наборе,
- кандидаты, которые побеждают кандидата в наборе.
Обратите внимание, что кандидаты второго типа могут существовать только после добавления кандидатов первого типа.
Алгоритмы [ править ]
Набор Смита можно вычислить в квадратичном времени, начиная с оценки Коупленда. Предположим, что матрица результатов имеет следующий вид:
2-й 1-й | А | B | C | D | E | F | грамм | счет | |
|---|---|---|---|---|---|---|---|---|---|
| А | - | 1 | 1 | 1 | 1 | 1 | 0 | 5 | |
| B | 0 | - | 0 | 0 | 1 | 0 | 0 | 1 | |
| C | 0 | 1 | - | 0 | 1 | 1/2 | 1 | 31/2 | |
| D | 0 | 1 | 1 | - | 1 | 1 | 1 | 5 | |
| E | 0 | 0 | 0 | 0 | - | 0 | 0 | 0 | |
| F | 0 | 1 | 1/2 | 0 | 1 | - | 0 | 21/2 | |
| грамм | 1 | 1 | 0 | 0 | 1 | 1 | - | 4 |
Здесь запись в основной таблице равна 1, если первый кандидат предпочел второму большее количество избирателей, чем второй кандидат первому; 0, если верно обратное соотношение; и1/2если есть галстук. В последнем столбце приводится оценка Коупленда первого кандидата.
Алгоритм вычисления набора Смита является агломеративным: он начинается с набора Коупленда, который гарантированно является его подмножеством, но часто будет меньше, и добавляет элементы до тех пор, пока они больше не понадобятся. Первый шаг - отсортировать кандидатов по баллам:
2-й 1-й | А | D | грамм | C | F | B | E | счет | |
|---|---|---|---|---|---|---|---|---|---|
| А | - | 1 | 0 | 1 | 1 | 1 | 1 | 5 | |
| D | 0 | - | 1 | 1 | 1 | 1 | 1 | 5 | |
| грамм | 1 | 0 | - | 0 | 1 | 1 | 1 | 4 | |
| C | 0 | 0 | 1 | - | 1/2 | 1 | 1 | 31/2 | |
| F | 0 | 0 | 0 | 1/2 | - | 1 | 1 | 21/2 | |
| B | 0 | 0 | 0 | 0 | 0 | - | 1 | 1 | |
| E | 0 | 0 | 0 | 0 | 0 | 0 | - | 0 |
Мы смотрим на наивысший балл - 5 - и рассматриваем кандидатов (победителей Коупленда), чей балл по крайней мере такой высокий, т.е. {A, D}. Они, безусловно, принадлежат к группе Смита, и необходимо будет добавить всех кандидатов, которых они не победят. Чтобы найти их, мы смотрим на ячейки в таблице под левым верхним квадратом, содержащим их: в таблице эти ячейки заштрихованы желтым цветом. Нам нужно найти самую низкую (позиционно) ненулевую запись среди этих ячеек, которая является ячейкой в строке G. Все кандидаты до этой строки и любые более низкие строки с одинаковым количеством баллов должны быть добавлены в набор, который расширяется до {A, D, G}.
Теперь мы смотрим на любые новые ячейки, которые необходимо учитывать, а именно на ячейки под левым верхним квадратом, содержащие {A, D, G}, но исключая те, которые находятся в первых двух столбцах, которые мы уже учли. Ячейки, требующие внимания, окрашены в бледно-голубой цвет. Как и раньше, мы размещаем позиционно самую низкую ненулевую запись среди новых ячеек, добавляя все строки до нее и все строки с той же оценкой, что и она, в расширенный набор, который теперь включает {A, D, G, C} .
Мы повторяем операцию для новых ячеек под четырьмя элементами, которые, как известно, принадлежат множеству Смита. Они окрашены в розовый цвет и позволяют нам находить кандидатов, не побежденных ни одним из {A, D, G, C}. Опять же, есть только один, F, которого мы добавляем в набор.
Ячейки, которые принимаются во внимание, имеют бледно-зеленый цвет, и, поскольку все их записи равны нулю, нам не нужно добавлять никаких новых кандидатов в набор, который, следовательно, фиксируется как {A, D, G, C, F}. Заметив, что все записи в черном ящике равны нулю, мы получаем подтверждение того, что все кандидаты выше него побеждают всех кандидатов в нем.
Следующая функция C иллюстрирует алгоритм, возвращая мощность множества Смита для данной удвоенной матрицы результатов r и массива s удвоенных оценок Коупленда. Есть n кандидатов; г I J = 2 , если больше избирателей предпочитают I в J , чем предпочитают J к I , 1 , если числа равны, и 0 , если больше избирателей предпочитают J к I , чем предпочесть I к J ; s i - сумма по j значений r i j . Предполагается, что кандидаты будут отсортированы в порядке убывания баллов Коупленда.
интервал smithset (интервал ** r, интервал * s, интервал n) {int row, col, lhs, rhs; для (rhs = 1, lhs = 0; lhs <rhs; lhs = rhs, rhs = row + 1) {для (; rhs <n && s [rhs] == s [rhs-1]; rhs ++); / * эта строка необязательна * / for (col = rhs, row = n; col == rhs && row> = rhs; row--) for (col = lhs; col <rhs && r [row-1] [col] == 0; col ++); } return lhs; }Другие алгоритмы, которые могут быть применены к той же проблеме: алгоритм Флойда – Уоршалла ; версия алгоритм косарайи и алгоритма Tarján в . Нет быстрее квадратичного.
Метод Смита [ править ]
Набор Смита можно рассматривать как определение метода ранжированного голосования, в котором ...
Все члены набора Смита - победители. Обычно сочетается с другим методом. [2]
Ярким примером сочетания метода Смита является Smith / IRV (см. Мгновенное голосование во втором туре ).
См. Также [ править ]
Ссылки [ править ]
Дальнейшее чтение [ править ]
- Уорд, Бенджамин (1961). «Правило большинства и распределение». Журнал разрешения конфликтов . 5 (4): 379–389. DOI : 10.1177 / 002200276100500405 . При анализе последовательного принятия решений на основе правила большинства описываются множества Смита и Шварца.
- Смит, JH (1973). «Агрегирование предпочтений с переменным электоратом». Econometrica . Эконометрическое общество. 41 (6): 1027–1041. DOI : 10.2307 / 1914033 . JSTOR 1914033 . Вводит версию обобщенного критерия Кондорсе, который выполняется, когда парные выборы основаны на выборе простого большинства, и для любого доминирующего набора любой кандидат в наборе коллективно предпочтительнее любого кандидата, не входящего в набор. Но Смит не обсуждает идею наименьшего доминирующего множества.
- Фишберн, Питер С. (1977). «Функции социального выбора Кондорсе». Журнал СИАМ по прикладной математике . 33 (3): 469–489. DOI : 10.1137 / 0133030 . Обобщенный критерий Кондорсе Смита сводит к наименьшему доминирующему множеству и называет его принципом Кондорсе Смита.
- Шварц, Томас (1986). Логика коллективного выбора . Нью-Йорк: издательство Колумбийского университета. Обсуждает набор Смита (названный GETCHA) и набор Шварца (названный GOTCHA) как возможные стандарты для оптимального коллективного выбора.
- Сомдеб Лахири (nd), «Групповое и многокритериальное принятие решений». Описывает некоторые свойства наборов выбора.
Внешние ссылки [ править ]
- Примеры алгоритмов для вычисления множества Смита
