Метод Шульце

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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


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

Существуют различные эвристики, позволяющие определять победителя голосования по таким исходным данным. На сегодняшний день наиболее употребительной является эвристика пути (англ. path 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
Schulze method example1.svg
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 …
Schulze method example1 AB.svg
A-(30)-D-(28)-C-(29)-B
Schulze method example1 AC.svg
A-(30)-D-(28)-C
Schulze method example1 AD.svg
A-(30)-D
Schulze method example1 AE.svg
A-(30)-D-(28)-C-(24)-E
от B …
Schulze method example1 BA.svg
B-(25)-A
Schulze method example1 BC.svg
B-(33)-D-(28)-C
Schulze method example1 BD.svg
B-(33)-D
Schulze method example1 BE.svg
B-(33)-D-(28)-C-(24)-E
от C …
Schulze method example1 CA.svg
C-(29)-B-(25)-A
Schulze method example1 CB.svg
C-(29)-B
Schulze method example1 CD.svg
C-(29)-B-(33)-D
Schulze method example1 CE.svg
C-(24)-E
от D …
Schulze method example1 DA.svg
D-(28)-C-(29)-B-(25)-A
Schulze method example1 DB.svg
D-(28)-C-(29)-B
Schulze method example1 DC.svg
D-(28)-C
Schulze method example1 DE.svg
D-(28)-C-(24)-E
от E …
Schulze method example1 EA.svg
E-(31)-D-(28)-C-(29)-B-(25)-A
Schulze method example1 EB.svg
E-(31)-D-(28)-C-(29)-B
Schulze method example1 EC.svg
E-(31)-D-(28)-C
Schulze method example1 ED.svg
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.

Применение[править | править исходный текст]

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

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

Альтернативное голосование[править | править исходный текст]

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

Примечания[править | править исходный текст]

  1. Election of the Annodex Association committee for 2007, February 2007
  2. Condorcet method for admin voting, January 2005
  3. Смотри:
  4. Project Logo, October 2009
  5. Codex Alpe Adria Competitions. 0xaa.org (24 января 2010). Проверено 8 мая 2010. Архивировано из первоисточника 2 февраля 2013.
  6. Civics Meeting Minutes, March 2012
  7. Fellowship Guidelines (PDF)(недоступная ссылка — история). Проверено 1 июня 2011. Архивировано из первоисточника 28 сентября 2011.
  8. Report on HackSoc Elections, December 2008
  9. Adam Helman, Family Affair Voting Scheme - Schulze Method
  10. Смотри:
  11. appendix 1 of the constitution
  12. Смотри:
  13. Guidance Document. Eudec.org (15 ноября 2009). Проверено 8 мая 2010. Архивировано из первоисточника 2 февраля 2013.
  14. article XI section 2 of the bylaws
  15. Democratic election of the server admins, July 2010
  16. article 51 of the statutory rules
  17. Voters Guide, September 2011
  18. Смотри:
  19. Смотри:
  20. Смотри:
  21. GnuPG Logo Vote, November 2006
  22. §14 of the bylaws
  23. User Voting Instructions. Gso.cs.binghamton.edu. Проверено 8 мая 2010. Архивировано из первоисточника 2 февраля 2013.
  24. Haskell Logo Competition, March 2009
  25. article VI section 10 of the bylaws, November 2012
  26. A club by any other name ..., April 2009
  27. section 3.4.1 of the Rules of Procedures for Online Voting
  28. Смотри:
  29. Knight Foundation awards $5000 to best created-on-the-spot projects, June 2009
  30. Смотри:
  31. article 8.3 of the bylaws
  32. Смотри:
  33. Concepts. Home page of LiquidFeedback. Interactive Democracy. Проверено 26 декабря 2012. Архивировано из первоисточника 2 февраля 2013.
  34. Lumiera Logo Contest, January 2009
  35. The MKM-IG uses Condorcet with dual dropping. Смотри:
  36. Wahlmodus(нем.)). Metalab.at. Проверено 8 мая 2010.
  37. Benjamin Mako Hill, Voting Machinery for the Masses, July 2008
  38. Смотри:
  39. 2009 Director Elections
  40. NSC Jersey election, NSC Jersey vote, September 2007
  41. Online Voting Policy
  42. Смотри:
  43. Voting Procedures. Parkscholars.org. Проверено 8 мая 2010. Архивировано из первоисточника 14 апреля 2013.
  44. National Congress 2011 Results, November 2011
  45. §6(10) of the bylaws
  46. Ik word Piraat!, August 2012
  47. §11.2.E of the statutory rules
  48. 11 из 16 региональных организаций и федеральная организация Пиратской партии Германии используют LiquidFeedback для внутрипартийных голосований. В 2010/2011, Пиратские партии Neukölln (link), Mitte (link), Steglitz-Zehlendorf (link), Lichtenberg (link), и Tempelhof-Schöneberg (link) приняли метод Шульце для внутрипартийных выборов. Также Пиратская партия Берлина (в 2011) (link) и Пиратская партия Регенсбурга (в 2012) (link) одобрила этот метод для внутрипартийных выборов.
  49. Rules adopted on 18 December 2011
  50. Vote Result for Name Definition
  51. 23 January 2011 meeting minutes
  52. Смотри:
  53. Piratenversammlung der Piratenpartei Schweiz, September 2010
  54. Article IV Section 4 of the constitution
  55. 2006 Community for Pittsburgh Ultimate Board Election, September 2006
  56. Committee Elections, April 2012
  57. LogoVoting, December 2007
  58. Смотри:
  59. Process for adding new board members, January 2003
  60. Squeak Oversight Board Election 2010, March 2010
  61. Смотри:
  62. Election status update, September 2009
  63. Minutes of the 2010 Annual Sverok Meeting, November 2010
  64. article VI section 6 of the bylaws
  65. Смотри:
  66. Ubuntu IRC Council Position, May 2012
  67. Смотри this mail.
  68. Смотри:
  69. Choix dans les votes
  70. fr:Spécial:Pages liées/Méthode Schulze
  71. Смотри например here (May 2009), here (August 2009), and here (December 2009).
  72. Смотри here and here.
  73. Смотри:

Ссылки[править | править исходный текст]