Метод Шульце

Метод Шульце — система голосования, разработанная в 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^[1]
• Википедия на французском языке^[2]
• Debian^[3]
• Software in the Public Interest^[4]
• Gentoo Foundation^[5]
• Sender Policy Framework^[6]
• Mathematical Knowledge Management Interest Group (MKM-IG)^[7]
• Kingman Hall^[8]
• TopCoder^[9]
• GNU Privacy Guard^[10]

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

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

Примечания

1. ↑ Board election to use preference voting, Mai 2008 (англ.)
2. ↑ Prise de décision, Dezember 2005 (фр.)
3. ↑ Verfassung für das Debian-Projekt, Anhang A6
4. ↑ Process for adding new board members, Januar 2003 (англ.)
5. ↑ См:
   • Gentoo Foundation Charter
   • Aron Griffis, 2005 Gentoo Trustees Election Results, May 2005
   • Lars Weiler, Gentoo Weekly Newsletter 23 May 2005
   • Daniel Drake, Gentoo metastructure reform poll is open, June 2005
   • Grant Goodyear, Results now more official, September 2006
   • 2007 Gentoo Council Election Results, September 2007
   • 2008 Gentoo Council Election Results, June 2008
   • 2008 Gentoo Council Election Results, November 2008
   • 2009 Gentoo Council Election Results, June 2009
   • 2009 Gentoo Council Election Results, December 2009
   • 2010 Gentoo Council Election Results, June 2010
6. ↑ Council Election Procedures
7. ↑ The MKM-IG использует метод Кондорсе с двумя отбрасываниями. Это значит, что вычисляются результаты по методу Шульце и ранжированным парам и победителем становится кандидат с наивысшим рейтингом в той из ранжировок, которая имеет лучшие результаты Кемени. См:
   • MKM-IG Charter
   • Michael Kohlhase, MKM-IG Trustees Election Details & Ballot, November 2004
   • Andrew A. Adams, MKM-IG Trustees Election 2005, December 2005
   • Lionel Elie Mamane, Elections 2007: Ballot, August 2007
8. ↑ Kingman adopts Condorcet voting, April 2005 (англ.)
9. ↑ См:
   • 2006 TopCoder Open Logo Design Contest, November 2005
   • 2006 TopCoder Collegiate Challenge Logo Design Contest, June 2006
   • 2007 TopCoder High School Tournament Logo, September 2006
   • 2007 TopCoder Arena Skin Contest, November 2006
   • 2007 TopCoder Open Logo Contest, January 2007
   • 2007 TopCoder Open Web Design Contest, January 2007
   • 2007 TopCoder Collegiate Challenge T-Shirt Design Contest, September 2007
   • 2008 TopCoder Open Logo Design Contest, September 2007
   • 2008 TopCoder Open Web Site Design Contest, October 2007
   • 2008 TopCoder Open T-Shirt Design Contest, March 2008
10. ↑ GnuPG Logo Vote, November 2006 (англ.)

Ссылки

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