Метод Шульце - Schulze method

Часть Политика серии
Избирательные системы
Цветной ящик для голосования. Svg Политический портал

В Метод Шульце (/ˈʃʊлтsə/) является избирательная система разработан в 1997 году Маркусом Шульце, который выбирает единственный победитель используя голоса, выражающие предпочтения. Этот метод также можно использовать для создания отсортированного списка победителей. Метод Шульце также известен как Шварц Последовательное падение (SSD), клоностойкое последовательное падение по Шварцу (CSSD), метод beatpath, победитель beatpath, Путь голосования, и победитель пути.

Метод Шульце - это Метод Кондорсе, что означает, что если есть кандидат, который большинством голосов предпочтительнее любого другого кандидата при парных сравнениях, то этот кандидат будет победителем при применении метода Шульце.

Результат метода Шульце (определенный ниже) дает упорядочение кандидатов. Следовательно, если доступно несколько позиций, метод можно использовать для этой цели без изменений, позволяя k лучшие кандидаты выигрывают k доступные места. Кроме того, для пропорциональное отображение выборы вариант с возможностью передачи одного голоса было предложено.

Метод Шульце используется несколькими организациями, в том числе Викимедиа, Debian, Ubuntu, Gentoo, Пиратская вечеринка политические партии и многие другие.

Описание метода

Бюллетень

Preferential ballot.svg

Входные данные для метода Шульце такие же, как и для других в рейтинге Избирательные системы с одним победителем: каждый избиратель должен предоставить упорядоченный список предпочтений кандидатов, связи разрешается (строгий слабый приказ ).[1]

Один типичный способ избирателям указать свои предпочтения на бюллетень составляет. В каждом бюллетене перечислены все кандидаты, и каждый избиратель ранжирует этот список в порядке предпочтения, используя числа: избиратель ставит «1» рядом с наиболее предпочтительным кандидатом (кандидатами), «2» рядом со вторым по предпочтению кандидатом и т. Д. . Каждый избиратель может по желанию:

  • отдавать одинаковое предпочтение более чем одному кандидату. Это свидетельствует о том, что избиратель безразличен к этим кандидатам.
  • используйте непоследовательные числа для выражения предпочтений. Это не влияет на результат выборов, поскольку имеет значение только порядок, в котором кандидаты ранжируются избирателем, а не абсолютное количество предпочтений.
  • держать кандидатов без рейтинга. Когда избиратель ранжирует не всех кандидатов, это интерпретируется так, как будто этот избиратель (i) строго предпочитает все ранжированные всем кандидатам без рейтинга и (ii) безразличен ко всем кандидатам без рейтинга.

Вычисление

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

А дорожка от кандидата кандидату это последовательность кандидатов со следующими свойствами:

  1. и .
  2. Для всех .

Другими словами, при попарном сравнении каждый кандидат на пути побьет следующего кандидата.

В прочность пути от кандидата кандидату - наименьшее количество проголосовавших в последовательности сравнений:

Для всех .

Для пары кандидатов и которые связаны хотя бы одним путем, сила сильнейшего пути это максимальная сила пути (ей), соединяющего их. Если нет пути от кандидата кандидату вообще тогда .

Кандидат является лучше чем кандидат если и только если .

Кандидат это потенциальный победитель если и только если для каждого другого кандидата .

Можно доказать, что и вместе подразумевают .[1]:§4.1 Следовательно, гарантируется (1), что приведенное выше определение "лучше"действительно определяет переходное отношение и (2) что всегда есть хотя бы один кандидат с участием для каждого другого кандидата .

пример

В следующем примере 45 избирателей оценивают 5 кандидатов.

Сначала необходимо вычислить парные предпочтения. Например, при сравнении А и B попарно есть 5+5+3+7=20 избиратели, которые предпочитают А к B, и 8+2+7+8=25 избиратели, которые предпочитают B к А. Так и . Полный набор парных предпочтений:

Направленный граф помечены парными предпочтениями d [*, *]
Матрица парных предпочтений
20263022
25163318
19291724
15122814
23272131

Ячейки для d [X, Y] имеют светло-зеленый фон, если d [X, Y]> d [Y, X], в противном случае фон светло-красный. Там нет бесспорного победителя лишь глядя на попарных различиях здесь.

Теперь нужно определить самые сильные пути. Чтобы помочь визуализировать самые сильные пути, набор парных предпочтений изображен на диаграмме справа в виде ориентированный граф. Стрелка от узла, представляющего кандидата X, к узлу, представляющему кандидата Y, помечена d [X, Y]. Чтобы не загромождать диаграмму, стрелка нарисована от X к Y только тогда, когда d [X, Y]> d [Y, X] (т. Е. Ячейки таблицы со светло-зеленым фоном), а стрелка в противоположном направлении ( ячейки таблицы со светло-красным фоном).

Одним из примеров вычисления наибольшей силы пути является p [B, D] = 33: самый сильный путь от B к D - это прямой путь (B, D), который имеет силу 33. Но при вычислении p [A, C] Самый сильный путь от A до C - это не прямой путь (A, C) с силой 26, скорее, самый сильный путь - это непрямой путь (A, D, C), который имеет силу min (30, 28) = 28. прочность пути - это сила его самого слабого звена.

Для каждой пары кандидатов X и Y в следующей таблице показан самый сильный путь от кандидата X к кандидату Y красным цветом с самым слабым звеном. подчеркнутый.

Сильнейшие пути
Чтобы
От
АBCDE
АНет данных
Пример метода Шульце1 AB.svg
А- (30) -D-(28)-C- (29) -B
Пример метода Шульце1 AC.svg
А- (30) -D-(28)-C
Метод Шульце example1 AD.svg
А-(30)-D
Пример метода Шульце1 AE.svg
A- (30) -D- (28) -C-(24)-E		А
B
Метод Шульце example1 BA.svg
B-(25)-А		Нет данных
Пример метода Шульце1 BC.svg
B- (33) -D-(28)-C
Пример метода Шульце1 BD.svg
B-(33)-D
Метод Шульце example1 BE.svg
В- (33) -D- (28) -C-(24)-E		B
C
Пример метода Шульце1 CA.svg
C- (29) -B-(25)-А
Пример метода Шульце1 CB.svg
C-(29)-B		Нет данных
Пример метода Шульце1 CD.svg
C-(29)-B- (33) -D
Пример метода Шульце1 CE.svg
C-(24)-E		C
D
Пример метода Шульце1 DA.svg
D- (28) -C- (29) -B-(25)-А
Пример метода Шульце1 DB.svg
D-(28)-C- (29) -B
Пример метода Шульце1 DC.svg
D-(28)-C		Нет данных
Метод Шульце example1 DE.svg
D- (28) -C-(24)-E		D
E
Пример метода Шульце1 EA.svg
E- (31) -D- (28) -C- (29) -B-(25)-А
Пример метода Шульце1 EB.svg
E- (31) -D-(28)-C- (29) -B
Метод Шульце example1 EC.svg
E- (31) -D-(28)-C
Пример метода Шульце1 ED.svg
E-(31)-D		Нет данныхE
АBCDE
От
Чтобы
Сильные стороны сильнейших путей
28283024
25283324
25292924
25282824
25282831

Теперь можно определить результат метода Шульце. Например, при сравнении А и B, поскольку , для кандидата метода Шульце А является лучше чем кандидат B. Другой пример: , поэтому кандидат E лучше чем кандидат D. Продолжая таким образом, в результате рейтинг Шульце , и E побеждает. Другими словами, E побеждает с для всех остальных кандидатов X.

Реализация

Единственный трудный шаг в реализации метода Шульце - это вычисление сильнейших путей. Однако это хорошо известная проблема в теории графов, которую иногда называют проблема самого широкого пути. Таким образом, один простой способ вычислить сильные стороны - это вариант Алгоритм Флойда-Уоршолла. Следующее псевдокод иллюстрирует алгоритм.

 1 # Введите: d [i, j], количество избирателей, которые предпочли кандидата i кандидату j. 2 # Вывод: p [i, j], сила самого сильного пути от кандидата i к кандидату j. 3  4 для i от 1 до C 5     для j от 1 до C 6         если (i ≠ j), то 7             если (d [i, j]> d [j, i]), то 8                 p [i, j]: = d [i, j] 9             еще10                 p [i, j]: = 011 12 для i от 1 до C13     для j от 1 до C14         если (i ≠ j), то15             для k от 1 до C16                 если (i ≠ k и j ≠ k), то17                     p [j, k]: = max (p [j, k], min (p [j, i], p [i, k]))

Этот алгоритм эффективный и имеет Продолжительность O (C3) где C количество кандидатов.

Связи и альтернативные реализации

Когда пользователям разрешается иметь связи в своих предпочтениях, результат метода Шульце, естественно, зависит от того, как эти связи интерпретируются при определении d [*, *]. Два естественных варианта: d [A, B] представляет либо количество избирателей, которые строго предпочитают A вместо B (A> B), либо прибыль из (избирателей с A> B) минус (избирателей с B> A). Но как бы то ни было ds определены, рейтинг Шульце не имеет циклов, и в предположении ds уникальны, не имеет связей.[1]

Хотя связи в рейтинге Шульце маловероятны,[2][нужна цитата ] они возможны. Оригинальная статья Шульце[1] предложил разорвать связи в соответствии с избирателем, выбранным случайным образом, и при необходимости повторить.

Альтернативный способ описать победителя метода Шульце - следующая процедура:[нужна цитата ]

  1. нарисовать полный ориентированный граф со всеми кандидатами и всеми возможными ребрами между кандидатами
  2. итеративно [a] удалить всех кандидатов, не входящих в Набор Шварца (т.е. любой кандидат Икс который не может достичь всех, кто достигает Икс) и [b] удаляют ребро графа с наименьшим значением (если по полям, то с наименьшим полем; если по голосам, то с наименьшим количеством голосов).
  3. победителем становится последний не удаленный кандидат.

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

  1. Составьте таблицу результатов, называемую «матрицей парных предпочтений», например, использованную выше в примере. Если вы используете поля, а не исходные итоги голосования, вычтите их из транспонирования. Тогда каждое положительное число является парным выигрышем для кандидата в этой строке (отмечено зеленым), ничьи равны нулю, а проигрыши отрицательны (отмечены красным). Распределите кандидатов по тому, как долго они продержатся в отсечении.
  2. Если на линии есть кандидат, у которого нет красного цвета, они побеждают.
  3. В противном случае нарисуйте квадратную рамку вокруг набора Шварца в верхнем левом углу. Вы можете описать его как минимальный «круг победителей», состоящий из кандидатов, которые не проигрывают никому вне круга. Обратите внимание, что справа от поля нет красного цвета, что означает, что это круг победителя, и обратите внимание, что внутри поля нет возможности переупорядочить, чтобы получить меньший круг победителя.
  4. Отрежьте все части стола, которых нет в коробке.
  5. Если по-прежнему нет кандидата, на линии которого нет красного цвета, необходимо что-то сделать; каждый кандидат проиграл какую-то гонку, и проигравший, который мы терпим лучшие, получил наибольшее количество голосов. Итак, возьмите красную ячейку с наибольшим номером (если вы идете по полям, наименее отрицательным), сделайте ее зеленой или любого другого цвета, кроме красного, и вернитесь к шагу 2.

Вот таблица полей, сделанная из приведенного выше примера. Обратите внимание на изменение порядка, используемое для демонстрационных целей.

Таблица исходных результатов
EАCBD
E1-3917
А-17-515
C3-713-11
B-95-1321
D-17-1511-21

Первое падение (проигрыш А против Е на 1 голос) не помогает уменьшить набор Шварца.

Первая капля
EАCBD
E1-3917
А-17-515
C3-713-11
B-95-1321
D-17-1511-21

Итак, мы переходим сразу ко второму падению (поражение E от C на 3 голоса), и он показывает нам победителя, E, с его чистой строкой.

Вторая капля, финал
EАCBD
E1-3917
А-17-515
C3-713-11
B-95-1321
D-17-1511-21

Этот метод также можно использовать для расчета результата, если вы составите таблицу таким образом, чтобы можно было удобно и надежно изменить порядок кандидатов как в строке, так и в столбце (всегда используйте один и тот же порядок для обоих).

Соответствующие и неудовлетворительные критерии

Удовлетворенные критерии

Метод Шульце удовлетворяет следующим критериям:

Неудачные критерии

Поскольку метод Шульце удовлетворяет критерию Кондорсе, он автоматически не соответствует следующим критериям:

Аналогичным образом, поскольку метод Шульце не является диктатурой и соглашается с единогласным голосованием, Теорема Эрроу подразумевает, что не соответствует критерию

Метод Шульце также не работает

Сравнительная таблица

В следующей таблице сравнивается метод Шульце с другими льготный методы выборов с одним победителем:

Сравнение преференциальных избирательных систем
СистемаМонотонныйКондорсеБольшинствоКондорсе неудачникНеудачник большинстваВзаимное большинствоСмитISDALIIAНезависимость клоновОбратная симметрияУчастие, последовательностьПозже без вредаПозже-без помощиПолиномиальное времяРазрешимость
ШульцедадададададададаНетдадаНетНетНетдада
Ранжированные парыдададададададададададаНетНетНетдада
Альтернатива приливного человекаНетдададададададаНетдаНетНетНетНетдада
Кемени – ЯнгдададададададададаНетдаНетНетНетНетда
CopelandдадададададададаНетНетдаНетНетНетдаНет
NansonНетдадададададаНетНетНетдаНетНетНетдада
ЧерныйдададададаНетНетНетНетНетдаНетНетНетдада
Мгновенное голосованиеНетНетдадададаНетНетНетдаНетНетдададада
БордадаНетНетдадаНетНетНетНетНетдадаНетдадада
БолдуинНетдадададададаНетНетНетНетНетНетНетдада
БаклиндаНетдаНетдадаНетНетНетНетНетНетНетдадада
МножестводаНетдаНетНетНетНетНетНетНетНетдадададада
Условное голосованиеНетНетдададаНетНетНетНетНетНетНетдададада
Кумбс[4]НетНетдадададаНетНетНетНетНетНетНетНетдада
MiniMaxдададаНетНетНетНетНетНетНетНетНетНетНетдада
Анти-множественность[4]даНетНетНетдаНетНетНетНетНетНетдаНетНетдада
Шри-ланкийское условное голосованиеНетНетдаНетНетНетНетНетНетНетНетНетдададада
Дополнительное голосованиеНетНетдаНетНетНетНетНетНетНетНетНетдададада
Доджсон[4]НетдадаНетНетНетНетНетНетНетНетНетНетНетНетда

Основное отличие метода Шульце от метода ранжированные пары можно увидеть в этом примере:

Предположим, что оценка MinMax набора Икс кандидатов - сила сильнейшего попарного выигрыша кандидата A ∉ Икс против кандидата B ∈ Икс. Тогда метод Шульце, но не ранжированные пары, гарантирует, что победителем всегда будет кандидат из набора с минимальным значением MinMax.[1]:§4.8 Таким образом, в некотором смысле метод Шульце сводит к минимуму наибольшее большинство, которое необходимо отменить при определении победителя.

С другой стороны, ранговые пары минимизируют наибольшее большинство, которое должно быть отменено, чтобы определить порядок финиша в смысле minlexmax.[5] Другими словами, когда ранговые пары и метод Шульце производят разные порядки финиша, для большинства, по которому два порядка финиша не совпадают, порядок Шульце меняет большее большинство, чем порядок ранговых пар.

История

Метод Шульце был разработан Маркусом Шульце в 1997 году. Впервые он был обсужден в публичных списках рассылки в 1997–1998 годах.[6] и в 2000 г.[7] Впоследствии пользователи метода Шульце включали Debian (2003),[8] Gentoo (2005),[9] Топкодер (2005),[10] Викимедиа (2008),[11] KDE (2008),[12] то Пиратская партия Швеции (2009),[13] и Пиратская партия Германии (2010).[14] Во французской Википедии метод Шульце был одним из двух методов с несколькими кандидатами, одобренных большинством в 2005 году.[15] и его использовали несколько раз.[16] Вновь образованный Бойсе, Айдахо глава Демократические социалисты Америки в феврале выбрали этот метод для своих первых внеочередных выборов, состоявшихся в марте 2018 года.[17]

В 2011 году Шульце опубликовал метод в академическом журнале. Социальный выбор и благосостояние.[1]

Пользователи

образец бюллетеня для Попечительский совет Викимедиа выборы

Метод Шульце используется в г. Силла на все референдумы. Он используется Институт инженеров по электротехнике и электронике, посредством Ассоциация вычислительной техники, и по USENIX за счет использования инструмента принятия решений HotCRP. Метод Шульце используют города России. Турин и Сан-Дона-ди-Пьяве и по Лондонский боро Саутварк за счет использования платформы WeGovNow, которая, в свою очередь, использует Жидкость инструмент принятия решений. Организации, которые в настоящее время используют метод Шульце, включают:

Заметки

  1. ^ а б c d е ж г час я j k л м п о п q Маркус Шульце, Новый монотонный, независимый от клонов, обратносимметричный и согласованный по Кондорсе метод выборов с одним победителем, Социальный выбор и благосостояние, том 36, номер 2, стр. 267–303, 2011 г. Предварительная версия в Вопросы голосования, 17:9-19, 2003.
  2. ^ При разумных вероятностных предположениях, когда количество избирателей намного превышает количество кандидатов
  3. ^ а б c Дуглас Р. Вудалл, Свойства правил преференциальных выборов, Вопросы голосования, выпуск 3, страницы 8-15, декабрь 1994 г.
  4. ^ а б c Предполагается, что анти-множественность, Кумбс и Доджсон получают усеченные предпочтения, равномерно распределяя возможные рейтинги не включенных в список альтернатив; например, бюллетень A> B = C считается как A> B> C и A> C> B. Если предполагается, что эти методы не получают усеченные предпочтения, тогда позже без вреда и позже-без помощи не применимы.
  5. ^ Тайдман, Т. Николаус, «Независимость клонов как критерий для правил голосования», «Социальный выбор и благосостояние», том 4 №3 (1987), стр 185-206.
  6. ^ Увидеть:
  7. ^ Увидеть:
  8. ^ а б Увидеть:
  9. ^ а б Увидеть:
  10. ^ а б 2007 TopCoder Collegiate Challenge, Сентябрь 2007 г.
  11. ^ Увидеть:
  12. ^ а б раздел 3.4.1 Правила процедуры онлайн-голосования
  13. ^ а б Увидеть:
  14. ^ а б 11 из 16 региональных отделений и федеральное отделение Пиратская партия Германии используют Жидкость для отмены привязки внутренних опросов общественного мнения. В 2010/2011 гг. Пиратские партии Neukölln (ссылка на сайт ), Mitte (ссылка на сайт ), Штеглиц-Целендорф (ссылка на сайт ), Лихтенберг (ссылка на сайт ), и Tempelhof-Schöneberg (ссылка на сайт ) принял метод Шульце для своих праймериз. Кроме того, Пиратская партия Берлин (в 2011) (ссылка на сайт ) и Пиратская партия Регенсбург (в 2012) (ссылка на сайт ) приняли этот метод для своих праймериз.
  15. ^ а б Выбор в пользу голосов
  16. ^ fr: Spécial: Pages liées / Méthode Schulze
  17. ^ Чумич, Андрей. "Специальные выборы DSA". Получено 2018-02-25.
  18. ^ Статья 7.1.3 своего Рабочий формат Агоры, п. 54, июль 2016
  19. ^ Избрание комитета ассоциации Annodex на 2007 год, Февраль 2007 г.
  20. ^ Аджит и Ван Атта победили на выборах в ГАС, Апрель 2013
  21. ^ § 6 и § 7 его устав, Май 2014 г.
  22. ^ §6 (6) устав
  23. ^ §9а устав, Октябрь 2013
  24. ^ Увидеть:
  25. ^ разрешающая способность, Декабрь 2013
  26. ^ Протоколы общественных собраний, Март 2012 г.
  27. ^ Адам Хельман, Схема голосования по семейным делам - метод Шульце
  28. ^ Увидеть:
  29. ^ «Руководящий документ». Eudec.org. 2009-11-15. Получено 2010-05-08.
  30. ^ Демократическое избрание админов сервера В архиве 2015-10-02 на Wayback Machine, Июль 2010 г.
  31. ^ Кампобассо. Comunali, scattano le primarie a 5 Stelle, Февраль 2014 года
  32. ^ Fondi, il punto sui кандидат в синдако. Certezze, novità e colpi di scena, Март 2015 г.
  33. ^ статья 25 (5) устав, Октябрь 2013
  34. ^ 2 ° Step Comunarie di Montemurlo, Ноябрь 2013
  35. ^ статья 12 устав, Январь 2015
  36. ^ Ridefinizione della lista di San Cesareo con Metodo Schulze, Февраль 2014 года
  37. ^ статья 57 уставные правила
  38. ^ Руководство для избирателей, Сентябрь 2011 г.
  39. ^ Увидеть:
  40. ^ § 7 (3) правила голосования, Ноябрь 2015
  41. ^ Голосование за логотип GnuPG, Ноябрь 2006 г.
  42. ^ «Инструкции по голосованию пользователей». Gso.cs.binghamton.edu. Архивировано из оригинал на 2013-02-02. Получено 2010-05-08.
  43. ^ Конкурс логотипов Haskell, Март 2009 г.
  44. ^ "Устав Хиллегасс-Паркер Хаус § 5. Выборы". Веб-сайт Hillegass-Parker House. Получено 4 октября 2015.
  45. ^ раздел 9.4.7.3 Рабочих процедур Совета по адресам Организации поддержки адресов
  46. ^ статья VI раздела 10 устав, Ноябрь 2012 г.
  47. ^ Клуб под любым другим названием ..., Апрель 2009 г.
  48. ^ Увидеть:
  49. ^ Knight Foundation награждает $ 5000 за лучшие проекты, созданные на месте, Июнь 2009 г.
  50. ^ Совет Кубунту 2013, Май 2013
  51. ^ Увидеть:
  52. ^ статья 8.3 устав
  53. ^ Принципы LiquidFeedback. Берлин: Интерактивная демократия e. V. 2014. ISBN  978-3-00-044795-2.
  54. ^ «Устав Madisonium - принят». Гугл документы.
  55. ^ "Вальмодус" (на немецком). Metalab.at. Получено 2010-05-08.
  56. ^ Бенджамин Мако Хилл, Голосование в массы, Июль 2008 г.
  57. ^ Увидеть:
  58. ^ устав, Сентябрь 2014 г.
  59. ^ «Выборы директора 2009». noisebridge.net.
  60. ^ «Политика онлайн-голосования». openembedded.org.
  61. ^ Увидеть:
  62. ^ Избирательный процесс, Июнь 2016
  63. ^ Итоги Национального Конгресса 2011, Ноябрь 2011 г.
  64. ^ §6 (10) устав
  65. ^ Бельгийская пиратская партия объявила лучших кандидатов на европейские выборы, Январь 2014
  66. ^ устав
  67. ^ Правила приняты 18 декабря 2011 г.
  68. ^ Verslag ledenraadpleging 4 января, Январь 2015
  69. ^ «Протокол заседания от 23 января 2011 года». pirateparty.org.nz.
  70. ^ Piratenversammlung der Piratenpartei Schweiz, Сентябрь 2010 г.
  71. ^ статья IV раздел 3 устав, Июль 2012 г.
  72. ^ Выборы в комитет, Апрель 2012 г.
  73. ^ Выборы в Совет по надзору за Squeak 2010, Март 2010 г.
  74. ^ Увидеть:
  75. ^ Обновление статуса выборов, Сентябрь 2009 г.
  76. ^ §10 III его устав, Июнь 2013
  77. ^ Протокол годового собрания Сверок 2010 г., Ноябрь 2010 г.
  78. ^ статья VI раздел 6 устав
  79. ^ Позиция Совета Ubuntu IRC, Май 2012 г.
  80. ^ "/ v / GAs - Результаты попарного голосования". vidyagaemawards.com.
  81. ^ "Паневропейская партия Вольт".
  82. ^ См. Например Вот [1] (Май 2009 г.), здесь [2] (Август 2009 г.), а здесь [3] (Декабрь 2009 г.).
  83. ^ Увидеть Вот и Вот.
  84. ^ "Девятнадцатые выборы арбитров, второй тур" [Результат выборов в Арбитражный комитет]. kalan.cc. Архивировано из оригинал на 22 февраля 2015 г.
  85. ^ Увидеть Вот

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