Множество Смита , [примечание 1] иногда называемое верхним циклом , обобщает идею победителя Кондорсе на случаи, когда такого победителя не существует . Это достигается путем разрешения совместного рассмотрения циклов кандидатов, как если бы они были одним победителем Кондорсе. [1] Системы голосования, которые всегда выбирают кандидата из множества Смита, удовлетворяют критерию Смита . Множество Смита и критерий Смита оба названы в честь математика Джона Х. Смита .
Набор Смита обеспечивает один стандарт оптимального выбора для результата выборов. Альтернативный, более строгий критерий дается набором Ландау .
Множество Смита формально определяется как наименьшее множество, такое, что каждый кандидат внутри множества S попарно непобедим каждым кандидатом вне S.
В качестве альтернативы его можно определить как множество всех кандидатов с (нестрогим) путем обхода любого кандидата, который их побеждает.
Набор кандидатов, каждый из членов которого попарно побеждает каждого кандидата вне этого набора, называется доминирующим набором . Таким образом, набор Смита также называется наименьшим доминирующим набором .
Набор Шварца эквивалентен набору Смита, за исключением того, что он игнорирует равные голоса. Формально набор Шварца — это набор, такой что любой кандидат внутри набора имеет строгий путь к любому кандидату, который его побеждает.
Множество Смита можно построить из множества Шварца, многократно добавляя два типа кандидатов до тех пор, пока за пределами множества не останется ни одного такого кандидата:
Обратите внимание, что кандидаты второго типа могут существовать только после добавления кандидатов первого типа.
Теорема: Доминирующие множества являются вложенными ; то есть из любых двух доминирующих множеств в выборах одно является подмножеством другого.
Доказательство: Предположим, что существуют два доминирующих множества, D и E , ни одно из которых не является подмножеством другого. Тогда должны существовать кандидаты d ∈ D , e ∈ E, такие , что d ∉ E и e ∉ D. Но по гипотезе d побеждает каждого кандидата, не входящего в D (включая e ), в то время как e побеждает каждого кандидата, не входящего в E (включая d ), противоречие. ∎
Следствие: Из этого следует, что множество Смита является наименьшим непустым доминирующим множеством и что оно корректно определено.
Теорема: Если D — доминирующее множество, то существует некоторый порог θ D такой, что элементами D являются в точности те кандидаты, чьи баллы по Коупленду составляют по крайней мере θ D . (Баллы по Коупленду кандидата — это число других кандидатов, которых он или она побеждает, плюс половина числа других кандидатов, с которыми он или она имеет одинаковое количество баллов.)
Доказательство: Выберите d как элемент D с минимальным баллом Коупленда и отождествите этот балл с θ D . Теперь предположим, что некоторый кандидат e ∉ D имеет балл Коупленда не меньше θ D . Тогда, поскольку d принадлежит D , а e — нет, следует, что d побеждает e ; и для того, чтобы балл Коупленда e был по крайней мере равен баллу d , должен быть некоторый третий кандидат f , против которого e получает лучший балл, чем d . Если f ∈ D , то у нас есть элемент D , который не побеждает e , а если f ∉ D , то у нас есть кандидат вне D , которого d не побеждает, что приводит к противоречию в любом случае. ∎
Критерий Смита — это критерий системы голосования , который формализует более сильную идею правила большинства , чем критерий Кондорсе . Система голосования удовлетворяет критерию Смита, если она всегда выбирает кандидата из множества Смита.
Хотя и менее распространенный, термин «эффективный по Смиту» также использовался для методов, которые выбирают из множества Смита. [3]
Вот пример электората, в котором нет победителя Кондорсе: Есть четыре кандидата: 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. (И т. д.)
В этом примере при минимаксе A и D имеют равные шансы; при Смите//Минимаксе побеждает A.
В приведенном выше примере три кандидата из набора Смита находятся в цикле большинства «камень/ножницы/бумага» : A имеет преимущество перед B с большинством в 65%, B имеет преимущество перед C с большинством в 75%, а C имеет преимущество перед A с большинством в 60%.
Любой метод выборов, который соответствует критерию Смита, также соответствует критерию победителя Кондорсе , поскольку если есть победитель Кондорсе, то это единственный кандидат в наборе Смита. Методы Смита также соответствуют критерию проигравшего Кондорсе , поскольку проигравший Кондорсе никогда не попадет в набор Смита. Это также подразумевает критерий взаимного большинства , поскольку набор Смита является подмножеством набора MMC. [2] И наоборот, любой метод, который не соответствует любому из этих трех критериев большинства (взаимное большинство, проигравший Кондорсе или победитель Кондорсе), также не соответствует критерию Смита.
Критерию Смита удовлетворяют ранжированные пары , метод Шульце , метод Нансона и несколько других методов. Более того, любой метод голосования можно модифицировать для удовлетворения критерия Смита, найдя множество Смита и исключив всех кандидатов за его пределами.
Например, метод голосования Smith//Minimax применяет Minimax к кандидатам в наборе Smith. Другим примером является метод альтернативы Тайдмана , который чередует исключение кандидатов вне набора Smith и исключение кандидата, который был проигравшим по относительному числу (аналогично мгновенному ходу ), пока не будет найден победитель Кондорсе. Другой подход заключается в выборе члена набора Smith, который находится выше в порядке финиша метода голосования.
Методы, не соответствующие критерию Кондорсе, также не соответствуют критерию Смита. Однако некоторые методы Кондорсе (например, Minimax ) могут не соответствовать критерию Смита.
Множество Смита содержит в качестве подмножеств множество Коупленда и множество Ландау .
Он также содержит множество Бэнкса и двухпартийное множество . Также были определены некоторые другие подмножества множества Смита. [4]
Множество Смита можно вычислить с помощью алгоритма Флойда–Уоршелла за время Θ ( n 3 ) или алгоритма Косараджу за время Θ ( n 2 ).
Алгоритм можно подробно представить на примере. Предположим, что матрица результатов выглядит следующим образом:
Здесь запись в основной таблице равна 1, если первого кандидата предпочло второму больше избирателей, чем предпочли второго первому; 0, если имеет место противоположное соотношение; и 1/2 если есть ничья. Последний столбец дает оценку по шкале Коупленда первого кандидата.
Алгоритм вычисления множества Смита является агломеративным: он начинается с множества Коупленда, которое гарантированно является его подмножеством, но часто будет меньше, и добавляет элементы до тех пор, пока больше не понадобится. Первый шаг — сортировка кандидатов по баллам:
Мы смотрим на наивысший балл (5) и рассматриваем кандидатов (победителей Коупленда), чей балл по крайней мере такой же, т. е. {A, D}. Они, безусловно, принадлежат к набору Смита, и любых кандидатов, которых они не победили, нужно будет добавить. Чтобы найти непобежденных кандидатов, мы смотрим на ячейки в таблице под верхним левым квадратом 2×2, содержащим {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 кандидатов; r i j равно 2, если больше избирателей предпочитают i j , чем предпочитают j i , 1, если числа равны, и 0, если больше избирателей предпочитают j i, чем предпочитают i j ; s i — это сумма по j от r i j . Предполагается , что кандидаты отсортированы в порядке убывания оценки Коупленда.
int smithset ( int ** r , int * s , int n ) { int row , col , lhs , rhs ; for ( rhs = 1 , lhs = 0 ; lhs < rhs ; lhs = rhs , rhs = row + 1 ) { for (; 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 ; } Для многих турнирных решений в литературе были предложены обобщения или расширения для слабых турниров.