Метод Шульце — система голосования, разработанная в 1997 году Маркусом Шульце. Сам Шульце называет её «методом разъезженного пути» (англ. Beatpath method). Она позволяет определить победителя с использованием бюллетеней для голосования, в которых голосующие указывают свои предпочтения относительно кандидатур. Также этот метод можно использовать и для получения отсортированного по предпочтительности списка победителей.
Этот метод удовлетворяет критерию Кондорсе: если один из кандидатов является предпочтительным при попарном сравнении с каждым из других кандидатов, он объявляется победителем.
По методу Шульце, каждый бюллетень содержит полный список кандидатов, и каждый избиратель ранжирует их в порядке своего предпочтения. В самом распространённом формате используются числа по возрастанию, когда избиратель ставит «1» напротив имени самого желательного кандидата, «2» — напротив второго по предпочтительности, и так далее. Избиратели могут ставить одинаковые числа нескольким кандидатурам, либо вообще не заполнять это поле для части кандидатур (в таком случае считается, что избиратель поставил такие кандидатуры одинаково ниже всех, для которых он указал число).
Существуют различные эвристики, реализующие решение по этому методу. Основными являются эвристика пути (англ. path heuristic) и эвристика множества Шварца (англ. Schwartz set heuristic).
Содержание |
Основная идея эвристики пути — концепция косвенных побед, так называемых путей.
Если при парном сравнении кандидат 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) является слабейшая парная победа одного кандидата над другим в этой последовательности.
Другими словами:
Силой сильнейшего пути p[A,B] от кандидатуры A к кандидатуре B называется максимальное из значений силы всех возможных путей от кандидатуры A до кандидатуры B. Если пути от кандидатуры A к кандидатуре B не существует, то p[A,B] принимается равной нулю.
Кандидат A побеждает кандидата B косвенно если выполняется любое из двух следующих условий:
Косвенные победы удовлетворяют условию транзитивности. Это означает, что: если кандидат A косвенно побеждает кандидата B, а кандидат B косвенно побеждает кандидата C, то кандидат A также побеждает кандидата C косвенно. Таким образом, дополнительной процедуры для определения косвенных побед не требуется.
В эвристике пути используется следующая процедура построения графа путей предпочтения и определение силы путей:
Путём силы p от кандидата X до кандидата Y называется последовательность кандидатур C(1),…,C(n) со следующими пятью свойствами:
Кандидатура A является возможным победителем тогда и только тогда, когда p[A,Z] ≥ p[Z,A] для каждой другой кандидатуры Z.
| d[*,A] | d[*,B] | d[*,C] | |
|---|---|---|---|
| d[A,*] | — | 70 | 33 |
| d[B,*] | 27 | — | 60 |
| d[C,*] | 64 | 35 | — |
Жирным выделены значения d[X,Y]>d[Y,X]. Как видно из таблицы, в этом примере каждому кандидату предпочитается другой кандидат, однако сила предпочтения различается. Предпочтение, отдаваемое кандидату А перед кандидатом В, больше предпочтения, отдаваемого кандидату C перед кандидатом А, который и будет признан победителем.
Рассмотрим выборы, на которых 45 избирателей голосуют за пять кандидатов, A, B, C, D, E. Голоса распределились следующим образом:
| d[*,A] | d[*,B] | d[*,C] | d[*,D] | d[*,E] | |
|---|---|---|---|---|---|
| d[A,*] | 20 | 26 | 30 | 22 | |
| d[B,*] | 25 | 16 | 33 | 18 | |
| d[C,*] | 19 | 29 | 17 | 24 | |
| d[D,*] | 15 | 12 | 28 | 14 | |
| d[E,*] | 23 | 27 | 21 | 31 |
Сила пути — это сила его слабейшего звена (критическое звено). Пути, каждый переход в которых удовлетворяет d[X,Y]>d[Y,X] можно построить, пользуясь следующими кусочками последовательностей: AC, AD, BA, BD, CB, CE, DC, EA, EB, ED.
Следующая таблица показывает сильнейшие пути от кандидата X к кандидату Y. Критическое звено сильнейшего пути подчёркнуто.
| … к A | … к B | … к C | … к D | … к E | |
|---|---|---|---|---|---|
| от A … | A-(30)-D-(28)-C-(29)-B | A-(30)-D-(28)-C | A-(30)-D | A-(30)-D-(28)-C-(24)-E | |
| от B … | B-(25)-A | B-(33)-D-(28)-C | B-(33)-D | B-(33)-D-(28)-C-(24)-E | |
| от C … | C-(29)-B-(25)-A | C-(29)-B | C-(29)-B-(33)-D | C-(24)-E | |
| от D … | D-(28)-C-(29)-B-(25)-A | D-(28)-C-(29)-B | D-(28)-C | D-(28)-C-(24)-E | |
| от E … | E-(31)-D-(28)-C-(29)-B-(25)-A | E-(31)-D-(28)-C-(29)-B | E-(31)-D-(28)-C | E-(31)-D |
| p[*,A] | p[*,B] | p[*,C] | p[*,D] | p[*,E] | |
|---|---|---|---|---|---|
| p[A,*] | 28 | 28 | 30 | 24 | |
| p[B,*] | 25 | 28 | 33 | 24 | |
| p[C,*] | 25 | 29 | 29 | 24 | |
| p[D,*] | 25 | 28 | 28 | 24 | |
| p[E,*] | 25 | 28 | 28 | 31 |
По методу Шульце будет провозглашён победителем кандидат 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.
Метод Шульце пока не применяется в общественных выборах, но он становится всё более популярным в частных организациях. По сей день он применяется в следующих выборах:
Метод Шульце представляет собой развитие идеи альтернативного голосования, которое применяется при выборах в различные органы власти Австралии, Новой Зеландии, Папуа — Новой Гвинеи, Фиджи, Ирландии, США, а также в ряде политических партий, неправительственных организаций и т. д.
Метод Шульце.
