stringtranslate.com

метод Шульце

Метод Шульце ( / ˈ ʃ ʊ l t s ə / ), также известный как метод beatpath , представляет собой правило голосования с ранжированным выбором одного победителя, разработанное Маркусом Шульце. Метод Шульце представляет собой метод завершения Кондорсе , что означает, что он выберет кандидата, которого предпочитает большинство, если таковой существует. Другими словами, если большинство людей оценивают A выше B , A победит B (когда это возможно). Метод Шульце разрывает циклические связи , используя косвенные победы. Идея состоит в том, что если Алиса побеждает Боба, а Боб побеждает Чарли, то Алиса (косвенно) побеждает Чарли; этот вид косвенной победы называется beatpath .

Для пропорционального представительства также существует вариант единого передаваемого голоса (STV), известный как STV Шульце . Метод Шульце используется несколькими организациями, включая Debian , Ubuntu , Gentoo , политические партии Pirate Party и многие другие. Он также использовался Wikimedia до принятия ими голосования по баллам .

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

Образец бюллетеня, предлагающий избирателям упорядочить кандидатов по предпочтениям

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

объяснение Beatpath

Идея метода Шульце заключается в том, что если Алиса побеждает Боба, а Боб побеждает Чарли, то Алиса «косвенно» побеждает Чарли. Эти связанные последовательности «битов» называются «битпутями».

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

Мы говорим, что у Алисы есть "beatpath-win" над Бобом, если ее сильнейший beatpath к Бобу сильнее, чем все сильнейшие beatpath Боба к Алисе. Победителем становится кандидат, у которого beatpath-win над всеми остальными кандидатами.

Маркус Шульце доказал, что это определение выигрыша по принципу «beatpath-win» является транзитивным : другими словами, если у Алисы выигрыш по принципу «beatpath-win» над Бобом, а у Боба выигрыш по принципу «beatpath-win» над Чарли, то у Алисы выигрыш по принципу «beatpath-win» над Чарли. [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.для i от 1 до C для j от 1 до C если i ≠ j, то если d[i,j] > d[j,i], то р[i,j] := d[i,j] еще р[i,j] := 0для i от 1 до C для j от 1 до C если i ≠ j, то для k от 1 до C если i ≠ k и j ≠ k, то p[j,k] := макс (p[j,k], мин (p[j,i], p[i,k]))

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

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

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

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

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

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

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

Первое падение (проигрыш A команде E с разницей в 1 голос) не способствует сокращению числа Шварцев.

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

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

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

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

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

Несоответствие критериям

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

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

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

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



Отличие от ранжированных пар

Ранжированные пары — это еще один метод Кондорсе , который очень похож на правило Шульце и обычно дает тот же результат. Однако есть небольшие различия. Главное отличие между методом beatpath и ранжированными парами заключается в том, что Шульце сохраняет поведение, близкое к минимаксу . Допустим, что минимаксная оценка набора X кандидатов — это сила сильнейшей попарной победы кандидата A ∉ X против кандидата B ∈ X. Тогда метод Шульце, но не ранжированные пары, гарантирует, что победителем всегда будет кандидат из набора с минимальной минимаксной оценкой. [2] : §4.8  Это тот смысл, в котором метод Шульце минимизирует наибольшее большинство, которое должно быть отменено при определении победителя.

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

История

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

Использование

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

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

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

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

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

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

Организации

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

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

Примечания

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

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

На Викискладе есть медиафайлы по теме «Метод Шульце».