Метод Шульце

Метод Шульце — система голосования, разработанная в 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) является слабейшая парная победа одного кандидата над другим в этой последовательности.

Другими словами:

• Предположим, что 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) со следующими пятью свойствами:

1. C(1) принимается равным X.
2. C(n) принимается равным Y.
3. Для всех i от 1 до (n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
4. Для всех i от 1 до (n-1): d[C(i),C(i+1)] ≥ p.
5. По крайней мере для одного 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[*,A]	d[*,B]	d[*,C]
d[A,*]	—	70	33
d[B,*]	27	—	60
d[C,*]	64	35	—

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

Пример 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[*,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.

Применение

Пример электронного избирательного листа для выборов кураторов Фонда Викимедиа

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

• Wikimedia
• Википедия на французском языке
• Debian
• Software in the Public Interest
• Gentoo Foundation
• Sender Policy Framework
• Mathematical Knowledge Management Interest Group (MKM-IG)
• Kingman Hall
• TopCoder
• GNU Privacy Guard

Альтернативное голосование

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

Ссылки

• Markus Schulze, Tiebreakers, Subcycle Rules, август 1998 г.
• Markus Schulze, Maybe Schulze is decisive, август 1998 г.