Метод Шульце

Часть серии " Политика"
Избирательные системы
Множественность / мажоритарность Множество Мажоритарной Единый голос без права передачи Ограниченное голосование Множественность в целом (голосование за блок) Общий билет Многократное голосование Два раунда Исчерпывающее голосование Рейтинговые / преференциальные системы Мгновенный сток (альтернативное голосование) Условное голосование Метод Кумбса Методы Кондорсе ( методы Коупленда , Доджсона , Кемени – Янга , Минимакс , Нансона , ранжированные пары , Шульце , Альтернативный Смит ) Позиционное голосование ( счет Борда , метод Науру / Даудалла , Евровидение ) Баклин голосование Первичная избирательная система Оклахомы Преференциальное блокирующее голосование Кардинальные / ступенчатые системы Оценка голосования Утверждающее голосование ( единые первичные ) Комбинированное одобрительное голосование Обычное суждение Голосование одобрения удовлетворенности Решение большинства ЗВЕЗДНОЕ голосование
Пропорциональное отображение Партийный список ( открытые списки , закрытые списки , локальные списки ) Самые высокие средние ( д'Ондта , Сент-Lague , Хантингтон-Hill ) Наибольший остаток ( Hare , Droop , Imperiali , Hagenbach-Bischoff ) Пропорциональные формы рейтингового голосования Единственный передаваемый голос ( Грегори , Райт ) CPO-STV Schulze STV Пропорциональные формы одобрительного голосования Пропорциональное одобрительное голосование Последовательное пропорциональное одобрительное голосование Бипропорциональное распределение Голосование справедливым большинством Взвешенное голосование Прямое представительство Интерактивное представление Жидкая демократия
Смешанные системы Смешанный пропорциональный Дополнительная система участников Параллельное голосование (смешанное мажоритарное) Скорпион Бонус за большинство Альтернативное голосование Плюс Двухчленный пропорциональный Пропорционально между городом и деревней
Другие системы и родственная теория Кумулятивное голосование Биномиальное голосование Голосование по доверенности Делегированное голосование Случайный выбор ( жеребьевка , случайное голосование ) Сравнение избирательных систем Теория социального выбора Теорема Эрроу Теорема Гиббарда – Саттертуэйта. Теория общественного выбора
Политический портал
v т е

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

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

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

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

Описание метода [ править ]

Бюллетень [ править ]

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

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

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

Вычисление [ править ]

Пусть будет количество избирателей, которые предпочли кандидата кандидату .${\ displaystyle d [V, W]}$${\ displaystyle V}$${\ displaystyle W}$

Путь от кандидата к кандидату является последовательностью кандидатов со следующими свойствами:${\ displaystyle X}$${\ displaystyle Y}$${\ Displaystyle С (1), \ cdots, С (п)}$

1. ${\ Displaystyle C (1) = X}$и .${\ Displaystyle C (п) = Y}$
2. Для всех .${\ Displaystyle я = 1, \ cdots, (п-1): d [С (я), С (я + 1)]> d [С (я + 1), С (я)]}$

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

Сила на пути от кандидата к кандидату наименьшее число избирателей в последовательности сравнения:${\ displaystyle p}$${\ displaystyle X}$${\ displaystyle Y}$

Для всех .${\ Displaystyle я = 1, \ cdots, (п-1): d [С (я), С (я + 1)] \ geq p}$

Для пары кандидатов и которые соединены , по меньшей мере , одного пути, то сила самого сильного пути максимальной сила пути (ов) , соединяющие их. Если вообще нет пути от кандидата к кандидату , тогда .${\ displaystyle A}$${\ displaystyle B}$ ${\ displaystyle p [A, B]}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle p [A, B] = 0}$

Кандидат является лучше , чем кандидат , если и только если .${\ displaystyle D}$${\ displaystyle E}$${\ displaystyle p [D, E]> p [E, D]}$

Кандидат является потенциальным победителем тогда и только тогда, когда для всех остальных кандидатов .${\ displaystyle D}$${\ displaystyle p [D, E] \ geq p [E, D]}$${\ displaystyle E}$

Можно доказать, что и вместе подразумеваем . ^{[1] : §4.1} Следовательно, гарантируется (1), что приведенное выше определение « лучше » действительно определяет транзитивное отношение и (2) что всегда есть по крайней мере один кандидат с для каждого другого кандидата .${\ displaystyle p [X, Y]> p [Y, X]}$${\ displaystyle p [Y, Z]> p [Z, Y]}$${\ displaystyle p [X, Z]> p [Z, X]}$${\ displaystyle D}$${\ displaystyle p [D, E] \ geq p [E, D]}$${\ displaystyle E}$

Пример [ править ]

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

${\displaystyle {\begin{array}{|c|c|}{\text{number of voters}}&{\text{order of preference}}\\\hline 5&ACBED\\5&ADECB\\8&BEDAC\\3&CABED\\7&CAEBD\\2&CBADE\\7&DCEBA\\8&EBADC\end{array}}}$

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

Матрица парных предпочтений

	${\displaystyle d[*,A]}$	${\displaystyle d[*,B]}$	${\displaystyle d[*,C]}$	${\displaystyle d[*,D]}$	${\displaystyle d[*,E]}$
${\displaystyle d[A,*]}$		20	26 год	30	22
${\displaystyle d[B,*]}$	25		16	33	18
${\displaystyle d[C,*]}$	19	29		17	24
${\displaystyle d[D,*]}$	15	12	28 год		14
${\displaystyle d[E,*]}$	23	27	21 год	31 год

Ячейки для 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] сильный путь от а до с не прямой путь (а, с) прочности 26, а самый сильный путь косвенный путь (а, D, C) , который имеет прочность мин (30, 28) = 28. сила из путь - это сила его самого слабого звена.

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

Сильные стороны сильнейших путей

	${\displaystyle p[*,A]}$	${\displaystyle p[*,B]}$	${\displaystyle p[*,C]}$	${\displaystyle p[*,D]}$	${\displaystyle p[*,E]}$
${\displaystyle p[A,*]}$		28 год	28 год	30	24
${\displaystyle p[B,*]}$	25		28 год	33	24
${\displaystyle p[C,*]}$	25	29		29	24
${\displaystyle p[D,*]}$	25	28 год	28 год		24
${\displaystyle p[E,*]}$	25	28 год	28 год	31 год

Теперь можно определить выход метода Шульце. Например, при сравнении A и B , так как для кандидата метода Schulze это лучше , чем кандидата B . Другой пример: кандидат E лучше, чем кандидат D. Продолжая таким образом, результат таков, что рейтинг Шульце равен , а E побеждает. Другими словами, E побеждает, поскольку для всех остальных кандидатов X.${\displaystyle (28=)p[A,B]>p[B,A](=25)}$${\displaystyle (31=)p[E,D]>p[D,E](=24)}$${\displaystyle E>A>C>B>D}$${\displaystyle p[E,X]\geq p[X,E]}$

Реализация [ править ]

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

# Введите: d [i, j], количество избирателей, которые предпочли кандидата i кандидату j.# Вывод: p [i, j], сила самого сильного пути от кандидата i к кандидату j.для i от 1 до C для j от 1 до C если (i ≠ j), то если (d [i, j]> d [j, i]), то p [i, j]: = d [i, j] еще p [i, j]: = 0для i от 1 до C для j от 1 до C если (i ≠ j), то для k от 1 до C если (i ≠ 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 s, у ранжирования Шульце нет циклов, и если предположить, что d s уникальны, у него нет связей. ^[1]

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

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

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

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

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

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

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

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

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

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

Соответствующие критерии [ править ]

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

Неудачные критерии [ править ]

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

• Участие ^{[1] : §3.4}
• Последовательность
• Неуязвимость к компромиссу
• Неуязвимость к захоронению
• Позже без вреда

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

• Независимость от нерелевантных альтернатив

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

• Критерий Пейтона Янга Локальная независимость от несущественных альтернатив .

Таблица сравнения [ править ]

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

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

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

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

История [ править ]

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

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

Пользователи [ править ]

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

Заметки [ править ]

Внешние ссылки [ править ]

Викискладе есть медиафайлы, связанные с методом Шульце .

• Метод голосования по Шульце, Маркус Шульце
• Вычисления Кондорсе , Иоганнес Грабмайер
• Spieltheorie (на немецком языке ) от Bernhard Nebel
• Точная демократия Роба Лоринга
• Кристоф Бёргерс (2009), Математика социального выбора: голосование, компенсация и разделение , SIAM, ISBN 0-89871-695-0 
• Николаус Тидеман (2006), Коллективные решения и голосование: потенциал общественного выбора , Берлингтон: Ashgate, ISBN 0-7546-4717-X 
• preftools от Public Software Group
• Жители Аризоны за рейтинговое голосование по Кондорсе
• Condorcet PHP Приложение командной строки и библиотека PHP , поддерживающая несколько методов Кондорсе, включая Schulze.
• Реализация на Java
• Реализация на Ruby
• Реализация на Python 2
• Реализация на Python 3