Метод Шульце

Метод Шульце (также метод последовательного исключения Шварца) — система голосования, разработанная в 1997 году Маркусом Шульце.

Сам Шульце называет её «методом разъезженного пути» (). Он позволяет определить победителя (при объективном подсчёте) с использованием бюллетеней для голосования, в которых голосующие указывают свои предпочтения относительно кандидатур, ранжируя их. Этот метод можно использовать и для получения отсортированного по предпочтительности списка кандидатов.

Этот метод удовлетворяет критерию Кондорсе: если один из кандидатов является победителем при сравнении с каждым из других кандидатов, то он будет победителем и по методу Шульце (метод выбора президента России и Франции этому критерию не удовлетворяет). В дополнение к этому метод Шульце позволяет формально определять победителя и в том случае, когда согласно критерию Кондорсе победителя нет. Победитель по методу Шульце всегда принадлежит .

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

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

Эвристика пути 

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

Если при парном сравнении кандидат C(1) побеждает C(2), кандидат C(2) побеждает C(3), кандидат C(3) побеждает C(4), …, и C(n − 1) побеждает C(n), то мы можем говорить, что существует путь от кандидата C(1) к кандидату C(n). Чем больше голосующих предпочитают первого кандидата второму кандидату, тем сильнее победа первого над вторым. Силой пути C(1), …, C(n) является слабейшая парная победа одного кандидата над другим в этой последовательности.

Другими словами:
 Предположим, что d[V, W] — число голосующих, которые строго предпочитают кандидатуру V кандидатуре W.
 Путь — это последовательность кандидатур C(1), …, C(n), где d[C(i), C(i + 1)] > d[C(i + 1), C(i)] для всех i = 1, …, n − 1.
 Сила пути C(1), …, C(n) — это минимум d[C(i), C(i + 1)] для всех i = 1, …, n − 1, где C(i) — позиция номер i с начала пути; d[A, B] — количество человек, поставивших кандидата A выше на одну или несколько позиций, чем кандидата B, при этом, если определён рассматриваемый путь, то имена кандидатов могут заменяться их позициями в данном пути.

Силой сильнейшего пути p[A, B] от кандидатуры A к кандидатуре B называется максимум значений силы всех возможных путей от кандидатуры A до кандидатуры B. Если пути от кандидатуры A к кандидатуре B не существует, то p[A, B] принимается равной нулю.

Кандидат A побеждает кандидата B косвенно, если выполняется любое из двух следующих условий:
 Сила сильнейшего пути от кандидата A к кандидату B сильнее, чем сила сильнейшего пути от кандидата B к кандидату A.
 Существует путь от кандидата A к кандидату B, а пути от кандидата B к кандидату A не существует.

Косвенные победы удовлетворяют условию транзитивности. Это означает, что если кандидат A косвенно побеждает кандидата B, а кандидат B косвенно побеждает кандидата C, то кандидат A также побеждает кандидата C косвенно.

Процедура 
В эвристике пути используется следующая процедура построения графа путей предпочтения и определение силы путей:

Путём силы p от кандидата X до кандидата Y называется последовательность кандидатур C(1), …, C(n) со следующими пятью свойствами:
 C(1) принимается равным X.
 C(n) принимается равным Y.
 Для всех i от 1 до n − 1: d[C(i), C(i + 1)] > d[C(i + 1), C(i)].
 Для всех i от 1 до n − 1: d[C(i), C(i + 1)] ⩾ p.
 По крайней мере для одного i из диапазона от 1 до n − 1: d[C(i), C(i + 1)] = p, где p — сила пути от кандидата X до кандидата Y, то есть p[X, Y].

Кандидатура A является возможным победителем тогда и только тогда, когда p[A, Z] ⩾ p[Z, A] для каждой другой кандидатуры Z.

Примеры

Пример 1 

Жирным выделены значения d[X, Y] > d[Y, X]. Как видно из таблицы, в этом примере каждому кандидату предпочитается другой кандидат — имеет место парадокс Кондорсе. Однако сила предпочтения различается. Предпочтение, отдаваемое кандидату A перед кандидатом B, больше предпочтения, отдаваемого кандидату C перед кандидатом A.

Кандидат A лучше кандидата B, который лучше кандидата С, который лучше кандидата A… Здесь нарушается транзитивность и нет победителя по критерию Кондорсе. Однако, для установления победителя в подобных случаях можно одну за другой отбрасывать самые слабые из сильных путей, в данном случае начав с d[C, A] = 64, в результате чего победителем будет признан кандидат А.

Пример 2 
Рассмотрим выборы, на которых 45 избирателей голосуют за пять кандидатов: A, B, C, D, E. Голоса распределились следующим образом:

 5 ACBED (то есть 5 избирателей поставили A выше C, C выше B, B выше E, а E выше D),
 5 ADECB,
 8 BEDAC,
 3 CABED,
 7 CAEBD,
 2 CBADE,
 7 DCEBA,
 8 EBADC.

Сила пути — это сила его слабейшего звена (критическое звено). Пути, каждый переход в которых удовлетворяет d[X, Y] > d[Y, X] можно построить, пользуясь следующими кусочками последовательностей AC, AD, BA, BD, CB, CE, DC, EA, EB, ED.

Следующая таблица показывает сильнейшие пути от кандидата X к кандидату Y. Критическое звено сильнейшего пути подчёркнуто.

По методу Шульце будет провозглашён победителем кандидат E, так как p[E, X] ⩾ p[X, E] для любого другого кандидата X.

Так как 25 = p[E, A] > p[A, E] = 24, кандидат E лучше, чем кандидат A.

Так как 28 = p[E, B] > p[B, E] = 24, кандидат E лучше, чем кандидат B.

Так как 28 = p[E, C] > p[C, E] = 24, кандидат E лучше, чем кандидат C.

Так как 31 = p[E, D] > p[D, E] = 24, кандидат E лучше, чем кандидат D.

Так как 28 = p[A, B] > p[B, A] = 25, кандидат A лучше, чем кандидат B.

Так как 28 = p[A, C] > p[C, A] = 25, кандидат A лучше, чем кандидат C.

Так как 30 = p[A, D] > p[D, A] = 25, кандидат A лучше, чем кандидат D.

Так как 29 = p[C, B] > p[B, C] = 28, кандидат C лучше, чем кандидат B.

Так как 29 = p[C, D] > p[D, C] = 28, кандидат C лучше, чем кандидат D.

Так как 33 = p[B, D] > p[D, B] = 28, кандидат B лучше, чем кандидат D.

Таким образом, метод Шульце приводит к следующему порядку кандидатов: E > A > C > B > D.

Применение 
Метод Шульце пока не применяется на общеполитических выборах, но он становится всё более популярным в частных организациях. На сегодняшний день он применяется на выборах в следующих частных организациях и партиях:

 Annodex Association
 Blitzed
 BoardGameGeek
 Cassandra
 Codex Alpe Adria
 Collective Agency
 College of Marine Science
 Computer Science Departmental Society for York University (HackSoc)
 County Highpointers
 Debian
 Demokratische Bildung Berlin
 EuroBillTracker
 European Democratic Education Conference (EUDEC)
 Fair Trade Northwest
 FFmpeg
 Flemish Student Society of Leuven
 Free Geek
 Free Hardware Foundation of Italy
 Free Software Foundation Europe (FSFE)
 Gentoo Foundation
 GNU Privacy Guard (GnuPG)
 Gothenburg Hacker Space (GHS)
 Graduate Student Organization at the State University of New York: Computer Science (GSOCS)
 Haskell
 Ithaca Generator
 Kanawha Valley Scrabble Club
 KDE e.V.
 Kingman Hall
  
 Kumoricon
 League of Professional System Administrators (LOPSA)
 Libre-Entreprise
 LiquidFeedback
 Lumiera/Cinelerra
 Mathematical Knowledge Management Interest Group (MKM-IG)
 Metalab
 Music Television (MTV)
 
 Noisebridge
 North Shore Cyclists (NSC)
 OpenEmbedded
 OpenStack
 Park Alumni Society (PAS)
 Пиратская партия Австралии
 Пиратская партия Австрии
 Пиратская партия Бельгии
 Пиратская партия Бразилии
 Пиратская партия Франции
 Пиратская партия Германии
 Пиратская партия Италии
 Пиратская партия Мексики
 Пиратская партия Новой Зеландии
 Пиратская партия Швеции
 Пиратская партия Швейцарии
 Пиратская партия США
 Pitcher Plant of the Month
 Pittsburgh Ultimate
 RLLMUK
 RPMrepo
 Sender Policy Framework (SPF)
 Software in the Public Interest (SPI)
 Squeak
 Students for Free Culture<ref>* Bylaws of the Students for Free Culture , article V, section 1.1.1.
 Culture Student Board Elected Using Selectricity. , February 2008.</ref>
 Sugar Labs
 Sverok
 TestPAC
 TopCoder
 Ubuntu
 University of British Columbia Math Club
 Фонд Викимедиа
 Википедия на французском, иврите, венгерском и русском.

Альтернативное голосование 
Метод Шульце представляет собой развитие идеи альтернативного голосования, которое применяется при выборах в различные органы власти Австралии, Новой Зеландии, Папуа — Новой Гвинеи, Фиджи, Ирландии, США, а также в ряде политических партий, неправительственных организаций и т. д.

Примечания

Ссылки 
 Markus Schulze, Tiebreakers, Subcycle Rules, август 1998 г.
 Markus Schulze, Maybe Schulze is decisive, август 1998 г.

Системы выборов