stringtranslate.com

метод Шульце

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

Результат метода Шульце дает упорядочение кандидатов. Следовательно, если доступно несколько должностей, этот метод можно использовать для этой цели без изменений, позволяя k кандидатам с самым высоким рейтингом выиграть k доступных мест. Кроме того, для выборов по пропорциональному представительству был предложен вариант единого передаваемого голоса (STV), известный как Schulze STV . Метод Шульце используется несколькими организациями, включая Wikimedia , Debian , Ubuntu , Gentoo , политические партии Пиратской партии и многие другие.

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

бюллетень

Образец бюллетеня, в котором избирателям предлагается расположить кандидатов по предпочтениям.

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

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

Вычисление

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

Путь от кандидата к кандидату представляет собой последовательность кандидатов со следующими свойствами:

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

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

Сила пути от кандидата к кандидату — это наименьшее количество избирателей в последовательности сравнений:

Для всех .

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

Кандидат лучше кандидата тогда и только тогда, когда .

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

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

Пример

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

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

Ориентированный граф , помеченный парными предпочтениями d[*, *]

Ячейки для 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 красным цветом, а самое слабое звено подчеркнуто.

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

Выполнение

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

# Входные данные: d[i,j], количество избирателей, которые предпочитают кандидата i кандидату j.# Выход: p[i,j], сила самого сильного пути от кандидата i к кандидату j.для меня от 1 до C для j от 1 до C если я ≠ j, то если d[i,j] > d[j,i], то p[i,j] := d[i,j] еще p[i,j] := 0для меня от 1 до C для j от 1 до C если я ≠ j, то для k от 1 до C если я ≠ k и j ≠ k, то p[j,k] := max (p[j,k], min (p[j,i], p[i,k]))

Этот алгоритм эффективен и имеет время работы O( C 3 ), где C — количество кандидатов.

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

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

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

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

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

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

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

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

Первое падение (поражение А от Е с перевесом в 1 голос) не способствует сокращению множества Шварца.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

История

Метод Шульце был разработан Маркусом Шульце в 1997 году. Впервые он обсуждался в публичных списках рассылки в 1997–1998 годах [5] и в 2000 году [6].

В 2011 году Шульце опубликовал метод в академическом журнале Social Choice and Welfare . [1]

Применение

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

Правительство

Метод Шульце используется городом Силла на всех референдумах. [7] [8] Он также используется городами Турин и Сан-Дона-ди-Пьяве , а также лондонским районом Саутварк посредством использования платформы WeGovNow, которая, в свою очередь, использует инструмент принятия решений LiquidFeedback . [ нужна цитата ]

Политические партии

Шульце был принят Пиратской партией Швеции (2009 г.) [9] и Пиратской партией Германии (2010 г.). [10] Недавно сформированное отделение Демократических социалистов Америки в Бойсе, штат Айдахо , в феврале выбрало этот метод для своих первых внеочередных выборов, состоявшихся в марте 2018 года. [11]

Студенческое самоуправление и ассоциации

Организации

Он используется Институтом инженеров по электротехнике и электронике , Ассоциацией вычислительной техники и USENIX посредством использования ими инструмента принятия решений HotCRP.

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

Примечания

  1. ^ abcdefghijklmnopq Маркус Шульце, «Новый монотонный, независимый от клонов, обратно-симметричный и соответствующий Кондорсе метод выборов с одним победителем», Social Choice and Welfare, том 36, номер 2, страницы 267–303, 2011. Предварительная версия в разделе «Голосование » Matters , 17:9-19, 2003.
  2. ^ При разумных вероятностных предположениях, когда число избирателей намного превышает количество кандидатов.
  3. ^ abc Дуглас Р. Вудалл, Свойства правил преференциальных выборов, Вопросы голосования , выпуск 3, страницы 8–15, декабрь 1994 г.
  4. ^ Тайдман, Т. Николаус, «Независимость клонов как критерий правил голосования», Social Choice and Welfare, том 4, № 3 (1987), стр. 185–206.
  5. ^ См.:
    • Маркус Шульце, правило подцикла Condorect, октябрь 1997 г.
    • Майк Осипофф, Партийный список PS, июль 1998 г.
    • Маркус Шульце, тай-брейки, правила подцикла, август 1998 г.
    • Маркус Шульце, «Может быть, Шульце имеет решающее значение», август 1998 г.
    • Норман Петри, Метод Шульце - более простое определение, сентябрь 1998 г.
    • Маркус Шульце, Метод Шульце, ноябрь 1998 г.
  6. ^ См.:
    • Энтони Таунс, Разрешение неоднозначности 4.1.5, ноябрь 2000 г.
    • Норман Петри, конституционное голосование, определение кумулятивного предпочтения, декабрь 2000 г.
  7. ^ Hortanoticias, Redaccion (23 февраля 2016 г.). «Все 2000 участников умерли в первом популярном конкурсе Силья, который решил носить очки с тауринами». Hortanoticias.com (на испанском языке) . Проверено 24 сентября 2022 г.
  8. ^ Силла, ~ Эль Кресоль де (26 мая 2016 г.). «Un all d'aprofundiment democracy a Silla». Эль Кресоль де Силья (на каталонском языке) . Проверено 24 сентября 2022 г.
  9. ^ аб См.:
    • Информация первоначальная, октябрь 2009 г.
    • Дагс атт кандидера до риксдагена, октябрь 2009 г.
    • Первые результаты, январь 2010 г.
  10. ^ ab 11 из 16 региональных секций и федеральная секция Пиратской партии Германии используют LiquidFeedback для отмены обязательности внутренних опросов общественного мнения. В 2010/2011 году пиратские партии Нойкёльна (ссылка), Митте (ссылка), Штеглиц-Целендорфа (ссылка), Лихтенберга (ссылка) и Темпельхоф-Шёнеберга (ссылка) приняли метод Шульце на своих праймериз. Кроме того, Пиратская партия Берлина (в 2011 году) (ссылка) и Пиратская партия Регенсбурга (в 2012 году) (ссылка) приняли этот метод на своих праймериз.
  11. ^ Чумич, Андрей. «Специальные выборы DSA» . Проверено 25 февраля 2018 г.
  12. ^ Кампобассо. Comunali, scattano le primarie a 5 Stelle, февраль 2014 г.
  13. ^ Макаро, Мирко (3 марта 2015 г.). «Fondi, il punto sui candidati a sindaco. Certezze, novità e colpi di scena». h24 notizie - независимый портал новостей из провинции (на итальянском языке) . Проверено 24 сентября 2022 г.
  14. статья 25(5) устава, октябрь 2013 г.
  15. ^ "MoVimento 5 Stelle - Монтемурло: 2 ° Step Comunarie di Montemurlo" . Ноябрь 2013 г. Архивировано из оригинала 2 апреля 2015 г. Проверено 24 сентября 2022 г.
  16. статья 12 устава, январь 2015 г.
  17. Ridefinizione della lista di San Cesareo con Metodo Schulze, февраль 2014 г.
  18. ^ «Результаты Национального конгресса 2011 года - Пиратская партия Австралии» . Pirateparty.org.au . Проверено 24 сентября 2022 г.
  19. ^ §6(10) устава
  20. ^ Статья III.3.4 Уставных правил (французский, нидерландский)
  21. ^ Пиратар (23 октября 2013 г.). «Шульце афердин». Пиратар (на исландском языке) . Проверено 24 сентября 2022 г.
  22. Правила приняты 18 декабря 2011 г.
  23. ^ Понтье, Маттейс (11 января 2015 г.). «Verslagledenraadpleging 4 января». Piratenpartij Noord Holland (на голландском языке) . Проверено 24 сентября 2022 г.
  24. ^ Панкерл, Флориан (18 сентября 2010 г.). «Piratenversammlung der Piratenpartei Schweiz 2010 – Samstag» (на немецком языке) . Проверено 24 сентября 2022 г.
  25. ^ статья IV раздел 3 устава, июль 2012 г.
  26. ^ §10 III устава, июнь 2013 г.
  27. ^ «Некоторые соображения по поводу того, к какой группе Volt Europe присоединится в Европейском парламенте» .
  28. ^ Хайду, Текла (24 сентября 2017 г.). «Метод Шульце – Агора 101». The AEGEEan — Интернет-журнал AEGEE — AEGEE-Europe . Проверено 24 сентября 2022 г.
  29. ^ Подробности голосования, январь 2021 г.
  30. Référendum sur la reforme du thurnage, июнь 2021 г.
  31. ^ статья 57 уставных правил.
  32. ^ «Инструкции по голосованию пользователей» . Gso.cs.binghamton.edu. Архивировано из оригинала 9 сентября 2013 г. Проверено 8 мая 2010 г.
  33. ^ «Постановление Дома Хиллегасс-Паркер § 5. Выборы» . Веб-сайт Hillegass-Parker House . Проверено 4 октября 2015 г.
  34. ^ См.:
    • Ка-Пинг Йи, выборы в Кондорсе, март 2005 г.
    • Ка-Пинг Йи, Кингман поддерживает голосование Кондорсе, апрель 2005 г.
  35. статья 9.4.5.h устава, ноябрь 2017 г.
  36. ^ Аджит, Ван Атта победили на выборах ASG, апрель 2013 г.
  37. ^ §6 и §7 устава, май 2014 г.
  38. ^ §6 (6) устава
  39. ^ Выборы комитета Ассоциации Annodex на 2007 г., февраль 2007 г.
  40. ^ §9a устава, октябрь 2013 г.
  41. ^ См.:
    • Премия Golden Geek Awards 2013 — открытие номинаций, январь 2014 г.
    • Премия Golden Geek Awards 2014 — открытие номинаций, январь 2015 г.
    • Премия Golden Geek Awards 2015 – открытие номинаций, март 2016 г.
    • Премия Golden Geek Awards 2016 — открытие номинаций, январь 2017 г.
    • Премия Golden Geek Awards 2017 – открытие номинаций, февраль 2018 г.
    • Премия Golden Geek Awards 2018 – открытие номинаций, март 2019 г.
  42. ^ статья 7(e)(iii)(2) устава, май 2021 г.
  43. ^ Адам Хелман, Схема голосования по семейным делам - метод Шульце
  44. ^ Руководящий и технический комитет, ноябрь 2021 г.
  45. ^ См.:
    • Поправка к Конституции: метод голосования SSD по Кондорсе/клонированию, июнь 2003 г.
    • Конституция проекта Debian, приложение A6
    • Информация о голосовании по Debian
  46. ^ «Руководящий документ». Eudec.org. 15 ноября 2009 г. Проверено 8 мая 2010 г.
  47. Демократические выборы администраторов сервера. Архивировано 2 октября 2015 г. в Wayback Machine , июль 2010 г.
  48. Руководство для избирателей, сентябрь 2011 г.
  49. ^ Проект: Выборы
  50. ^ «Результаты выборов CIVS: голосование за логотип GnuPG» . 03.10.2013. Архивировано из оригинала 3 октября 2013 г. Проверено 24 сентября 2022 г.
  51. ^ Конкурс логотипов Haskell, март 2009 г.
  52. Статья 6, раздел 2 Конституции, февраль 2021 г.
  53. ^ раздел 9.4.7.3 Рабочих процедур Совета по адресам Организации поддержки адресов (архивировано из источника от 6 июня 2023 г.)
  54. ^ «Клуб под любым другим названием...» Клуб скрэббл-клуба долины Канава . 2 апреля 2009 г. Проверено 24 сентября 2022 г.
  55. ^ раздел 3.4.1 Правил процедуры онлайн-голосования.
  56. ^ Фонд Knight Foundation награждает 5000 долларов лучшим проектам, созданным на месте, июнь 2009 г.
  57. ^ Сообщество Kubernetes, Kubernetes, 24 сентября 2022 г. , получено 24 сентября 2022 г.
  58. ^ "Куморикон - Конкурс талисманов" . Куморикон . Проверено 24 сентября 2022 г.
  59. ^ статья 8.3 устава.
  60. ^ Принципы LiquidFeedback. Берлин: Интерактивная демократия e. В. 2014. ISBN. 978-3-00-044795-2.
  61. ^ «Постановления Мэдисониума - приняты» . Гугл документы .
  62. ^ «Вальмодус» (на немецком языке). Metalab.at . Проверено 8 мая 2010 г.
  63. ^ Дэвид Чендлер, Голосование за нечто большее, чем просто «или-или», MIT Tech Talk, том 52, номер 19, страница 2, 12 марта 2008 г.
  64. ^ См.:
    • Wahlen zum Neo-2-Freeze: Formalitäten. Архивировано 27 июля 2011 г. в Wayback Machine , февраль 2010 г.
    • Hinweise zur Stimmabgabe, март 2010 г.
    • Эргебниссе, март 2010 г.
  65. ^ «Выборы директора 2009 г.» . Noisebridge.net .
  66. ^ «Политика онлайн-голосования». openembedded.org .
  67. ^ Руководство по выборам Руководящего комитета ONNX
  68. ^ «Выборы OpenStack — Управление OpenStack» . www.governance.openstack.org . Проверено 24 сентября 2022 г.
  69. Марк, Этвуд (25 мая 2016 г.). «[Партнеры] текст Устава проекта OpenSwitch от 03 мая 2016 г.» . Проверено 24 сентября 2022 г.
  70. ^ «Выборы комитета 2012» . рлмук . Проверено 24 сентября 2022 г.
  71. ^ Выборы в наблюдательный совет Squeak 2010 г., март 2010 г.
  72. ^ См.:
    • Устав студентов за свободную культуру. Архивировано 18 марта 2013 г. в Wayback Machine , статья V, раздел 1.1.1.
    • Студенческий совет свободной культуры избран с использованием электричества, февраль 2008 г.
  73. ^ «[IAEP] Обновление статуса выборов» . lists.sugarlabs.org . Проверено 24 сентября 2022 г.
  74. ^ Протокол ежегодного собрания Сверок 2018 г., ноябрь 2018 г.
  75. ^ "Студенческий конкурс TopCoder 2007" . сообщество.topcoder.com . Проверено 24 сентября 2022 г.
  76. Белл, Алан (17 мая 2012 г.). «Позиция Совета IRC Ubuntu» . Проверено 24 сентября 2022 г.
  77. ^ "/v/GAs - Результаты попарного голосования" . vidyagaemawards.com .
  78. ^ См.:
    • Выборы в совет директоров 2008 г., июнь 2008 г.
    • Выборы в совет директоров 2009 г., август 2009 г.
    • Выборы в совет директоров 2011 г., июнь 2011 г.
  79. ^ "Википедия:Prise de décision/Choix dans les voices", Википедия (на французском языке), 22 августа 2019 г. , получено 24 сентября 2022 г.
  80. ^ "Страницы, написанные по методу Шульце" . fr.wikipedia.org (на французском языке) . Проверено 24 сентября 2022 г.
  81. ^ "ויקיפדיה:פרלמנט/הכרעה" [Википедия: Парламент/Принятие решений]. he.wikipedia.org (на иврите).
  82. ^ См., например, здесь [1] (май 2009 г.), здесь [2] (август 2009 г.) и здесь [3] (декабрь 2009 г.).
  83. ^ См. здесь и здесь.
  84. ^ Девятнадцатые выборы арбитров, второй тур [Результаты выборов Арбитражного комитета]. kalan.cc (на русском языке). Архивировано из оригинала 22 февраля 2015 г.
  85. ^ Смотрите здесь

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