набор Смита

Набор Смита или Шварца , ^{[примечание 1]} Иногда называемый верхним циклом , это концепция теории избирательных систем , которая обобщает победителя Кондорсе на случаи, когда такого победителя не существует . Это достигается за счет того, что циклы кандидатов рассматриваются совместно, как если бы они были одним победителем Кондорсе.

Названный в честь Джона Х. Смита , набор Смита представляет собой наименьший непустой набор кандидатов на конкретных выборах, такой, что каждый член побеждает каждого кандидата за пределами набора на парных выборах. Набор Смита обеспечивает один стандарт оптимального выбора для исхода выборов. Системы голосования, которые всегда выбирают кандидата из множества Смита, соответствуют критерию Смита .

Определение

Набор Смита формально определяется как наименьший набор, такой, что каждый кандидат внутри набора попарно непобедим каждым кандидатом вне S. S

В качестве альтернативы его можно определить как набор всех кандидатов с (нестрогим) маршрутом до любого кандидата, который их победит.

Набор кандидатов, каждый из членов которого попарно побеждает каждого кандидата вне набора, называется доминирующим набором . Таким образом, множество Смита также называют наименьшим доминирующим множеством .

Строгий топ-цикл (множество Шварца)

Набор Шварца эквивалентен набору Смита, за исключением того, что он игнорирует равное количество голосов. Формально набор Шварца — это набор, в котором любой кандидат внутри набора имеет строгий путь к любому кандидату, который его победит.

Набор Смита можно составить из набора Шварца путем многократного добавления двух типов кандидатов до тех пор, пока такие кандидаты не перестанут существовать вне набора:

кандидаты, которые попарно связаны с кандидатами в наборе,
кандидаты, которые побеждают кандидата в наборе.

Обратите внимание, что кандидаты второго типа могут существовать только после добавления кандидатов первого типа.

Характеристики

Множество Смита всегда существует и непусто. Он также четко определен (см. следующий раздел).
Множество Смита может иметь более одного кандидата либо из-за парных связей, либо из-за циклов, как, например, в парадоксе Кондорсе .
Победитель Кондорсе , если таковой существует, является единственным членом множества Смита. Если существуют слабые победители Кондорсе, они входят в набор Смита.
Набор Смита всегда является подмножеством взаимным большинством , если таковой существует. набора кандидатов, предпочитаемого ^[1]

Свойства доминирующих множеств

Теорема: Доминирующие множества вложены ; то есть из любых двух доминирующих групп на выборах одна является подгруппой другой.

Доказательство: предположим, что существуют два доминирующих множества, 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 не побеждает, что в любом случае приводит к противоречию. ∎

Критерий Смита

Критерию Смита удовлетворяет любой метод голосования, при котором победитель всегда принадлежит множеству Смита. Любой метод, удовлетворяющий критерию Смита, должен также удовлетворять критерию Кондорсе ; следовательно, любой метод (такой как IRV ), который не является согласованным по Кондорсе, также должен не соответствовать критерию Смита. Минимакс — наиболее известный метод Кондорсе, не удовлетворяющий критерию Смита; эта неудача привела к разработке ранговых пар и метода Шульце , двух методов, которые сильно похожи на минимакс при выборе из набора Смита.

Связь с другими турнирными наборами

Множество Смита содержит множество Коупленда в качестве подмножества .

Он также содержит набор Бэнкса и двухпартийный набор .

Вычисление множества Смита

Изложенные выше логические свойства доминирующих множеств можно использовать для построения эффективного алгоритма вычисления множества Смита. Мы видели, что доминирующие множества вложены по шкале Коупленда. Отсюда следует, что, регулируя порог Коупленда, можно работать с вложенными наборами в порядке возрастания размера, пока не будет достигнут доминирующий набор; и это множество обязательно является множеством Смита. Дарлингтон описывает этот метод. ^[2]

Проверка того, является ли набор доминирующим на каждом этапе, может привести к повторению некоторых вычислений, но этого довольно легко избежать, что приведет к созданию алгоритма, коэффициент работы которого квадратичен по числу кандидатов.

Подробный алгоритм

Подробно алгоритм можно представить на примере. Предположим, что матрица результатов имеет следующий вид:

2-й 1-й	А	Б	С	Д	И	Ф	Г	счет
А	–	1	1	1	1	1	0	5
Б	0	–	0	0	1	0	0	1
С	0	1	–	0	1	⁠ 1 / 2 ⁠	1	3 ⁠ 1 / 2 ⁠
Д	0	1	1	–	1	1	1	5
И	0	0	0	0	–	0	0	0
Ф	0	1	⁠ 1 / 2 ⁠	0	1	–	0	2 ⁠ 1 / 2 ⁠
Г	1	1	0	0	1	1	–	4

Здесь запись в основной таблице равна 1, если первому кандидату отдали предпочтение второму больше избирателей, чем предпочли второго первому; 0, если выполняется противоположное соотношение; и ⁠ 1/2 ⁠ . при ничьей В последнем столбце указан балл Коупленда первого кандидата.

Алгоритм вычисления набора Смита является агломеративным: он начинается с набора Коупленда, который гарантированно является его подмножеством, но часто будет меньше, и добавляет элементы до тех пор, пока они не исчезнут. Первым шагом является сортировка кандидатов по баллам:

2-й 1-й	А	Д	Г	С	Ф	Б	И	счет
А	–	1	0	1	1	1	1	5
Д	0	–	1	1	1	1	1	5
Г	1	0	–	0	1	1	1	4
С	0	0	1	–	⁠ 1 / 2 ⁠	1	1	3 ⁠ 1 / 2 ⁠
Ф	0	0	0	⁠ 1 / 2 ⁠	–	1	1	2 ⁠ 1 / 2 ⁠
Б	0	0	0	0	0	–	1	1
И	0	0	0	0	0	0	–	0

Мы смотрим на наивысший балл (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, если больше избирателей предпочитают , i чем предпочитают i j 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++); /* this line optional */
    for (col = rhs, row = n; col == rhs && row >= rhs; row--)
      for (col = lhs; col < rhs && r[row - 1][col] == 0; col++);
  }
  return lhs;
}

См. также

Критерий Кондорсе
Метод Кондорсе
набор Ландау
Предварительный заказ
Частичный заказ
Максимальные и минимальные элементы . Множество Смита можно определить как максимальные элементы определенного частичного порядка.

Дальнейшее чтение

Уорд, Бенджамин (1961). «Правило большинства и распределение». Журнал разрешения конфликтов . 5 (4): 379–389. дои : 10.1177/002200276100500405 . S2CID 145231466 . При анализе последовательного принятия решений на основе правила большинства описываются набор Смита и набор Шварца.
Смит, Дж. Х. (1973). «Агрегация предпочтений с переменным электоратом». Эконометрика . 41 (6). Эконометрическое общество: 1027–1041. дои : 10.2307/1914033 . JSTOR 1914033 . Вводит версию обобщенного критерия Кондорсе, который удовлетворяется, когда парные выборы основаны на простом выборе большинства и для любого доминирующего набора любой кандидат в наборе коллективно предпочтительнее любого кандидата, не входящего в набор. Но Смит не обсуждает идею наименьшего доминирующего множества.
Фишберн, Питер К. (1977). «Функции социального выбора Кондорсе». SIAM Journal по прикладной математике . 33 (3): 469–489. дои : 10.1137/0133030 . Сужает обобщенный критерий Кондорсе Смита до наименьшего доминирующего множества и называет его принципом Кондорсе Смита.
Шварц, Томас (1986). Логика коллективного выбора . Нью-Йорк: Издательство Колумбийского университета. Обсуждает набор Смита (названный GETCHA) и набор Шварца (названный GOTCHA) как возможные стандарты оптимального коллективного выбора.
Шварц, Томас (1970). «О возможности рациональной оценки политики». Теория и решение . 1 : 89–106. дои : 10.1007/BF00132454 . S2CID 154326683 . В конце статьи вводится понятие множества Шварца как возможной альтернативы максимизации при наличии циклических предпочтений как стандарта рационального выбора.
Шварц, Томас (1972). «Рациональность и миф о максимуме». Нус . 6 (2). Ноус, Vol. 6, № 2: 97–117. дои : 10.2307/2216143 . JSTOR 2216143 . Дает аксиоматическую характеристику и обоснование множества Шварца как возможного стандарта оптимального, рационального коллективного выбора.
Деб, Раджат (1977). «О правиле Шварта». Журнал экономической теории . 16 : 103–110. дои : 10.1016/0022-0531(77)90125-9 . Доказывает, что множество Шварца является множеством недоминируемых элементов транзитивного замыкания попарного отношения предпочтения.
Сомдеб Лахири (nd), «Групповое и многокритериальное принятие решений». Очерчивает некоторые свойства наборов выбора.

Внешние ссылки

Примеры алгоритмов расчета множества Смита

^ Многие авторы оставляют за собой термин «множество Шварца» для строгого множества Смита, описанного ниже.

^ http://dss.in.tum.de/files/brandt-research/dodgson.pdf ^{[ только URL-адрес PDF ]}
^ Р.Б. Дарлингтон, «Являются ли системы голосования Кондорсе и минимакс лучшими?» (v8, 2021 г.).

[1] Многие авторы оставляют за собой термин «множество Шварца» для строгого множества Смита, описанного ниже.

[2] ttp://dss.in.tum.de/files/brandt-research/dodgson.pdf ^{[ только URL-адрес PDF ]}

[darlington2-3] Р.Б. Дарлингтон, «Являются ли системы голосования Кондорсе и минимакс лучшими?» (v8, 2021 г.).

[примечание 1]

[1]

[2]