Метод Шульце

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

Метод Шульце (также метод последовательного исключения Шварца) — система голосования, разработанная в 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 37 —

Жирным выделены значения 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[*, 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.

Применение

[править | править код]

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

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

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

[править | править код]

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

Примечания

[править | править код]
  1. ↑ Election of the Annodex Association committee for 2007 Архивная копия от 3 марта 2016 на Wayback Machine, February 2007.
  2. ↑ Condorcet method for admin voting. Архивная копия от 26 апреля 2005 на Wayback Machine, January 2005.
  3. ↑ * Important notice for Golden Geek voters Архивная копия от 14 октября 2007 на Wayback Machine, September 2007.
  4. ↑ Project Logo Архивная копия от 3 октября 2015 на Wayback Machine, 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 Архивная копия от 6 февраля 2012 на Wayback Machine.
  10. ↑ :
  11. ↑ Appendix 1 of the constitution. Архивная копия от 18 июля 2011 на Wayback Machine
  12. ↑ * Candidate cities for EBTM05, December 2004.
  13. ↑ Guidance Document. Eudec.org (15 ноября 2009). Дата обращения: 8 мая 2010. Архивировано 2 февраля 2013 года.
  14. ↑ Article XI, section 2 of the bylaws Архивная копия от 26 июля 2011 на Wayback Machine
  15. ↑ Democratic election of the server admins. Архивная копия от 2 октября 2015 на Wayback Machine, July 2010.
  16. ↑ Article 51 of the statutory rules.
  17. ↑ Voters Guide Архивная копия от 17 августа 2012 на Wayback Machine, September 2011.
  18. ↑ * Eletto il nuovo Consiglio nella Free Hardware Foundation Архивная копия от 25 декабря 2008 на Wayback Machine, June 2008.
  19. ↑ * article 6 section 3 of the constitution Архивная копия от 6 января 2009 на Wayback Machine.
  20. ↑ * Gentoo Foundation Charter Архивная копия от 15 марта 2015 на Wayback Machine
  21. ↑ GnuPG Logo Vote. Архивная копия от 16 декабря 2006 на Wayback Machine, November 2006.
  22. ↑ § 14 of the bylaws. Архивная копия от 29 апреля 2010 на Wayback Machine
  23. ↑ User Voting Instructions. Gso.cs.binghamton.edu. Дата обращения: 8 мая 2010. Архивировано из оригинала 2 февраля 2013 года.
  24. ↑ Haskell Logo Competition Архивная копия от 28 марта 2009 на Wayback Machine, March 2009.
  25. ↑ Article VI, section 10 of the bylaws (недоступная ссылка), November 2012.
  26. ↑ A club by any other name … Архивная копия от 22 февраля 2012 на Wayback Machine, April 2009.
  27. ↑ section 3.4.1 of the Rules of Procedures for Online Voting Архивная копия от 21 января 2013 на Wayback Machine.
  28. ↑
  29. ↑ Knight Foundation awards $5000 to best created-on-the-spot projects Архивная копия от 20 июля 2011 на Wayback Machine, June 2009.
  30. ↑ * Mascot 2007 contest Архивная копия от 31 января 2013 на Wayback Machine, July 2006.
  31. ↑ Article 8.3 of the bylaws Архивная копия от 22 июля 2012 на Wayback Machine.
  32. ↑ * Choix de date pour la réunion Libre-entreprise durant le Salon Solution Linux 2006 Архивная копия от 13 июня 2010 на Wayback Machine, January 2006.
  33. ↑ Concepts. Home page of LiquidFeedback. Interactive Democracy. Дата обращения: 26 декабря 2012. Архивировано 2 февраля 2013 года.
  34. ↑ Lumiera Logo Contest Архивная копия от 25 декабря 2009 на Wayback Machine, January 2009.
  35. ↑ The MKM-IG uses Condorcet with dual dropping Архивная копия от 25 ноября 2011 на Wayback Machine:
  36. ↑ Wahlmodus (нем.). Metalab.at. Дата обращения: 8 мая 2010. Архивировано 18 июля 2011 года.
  37. ↑ Benjamin Mako Hill, Voting Machinery for the Masses Архивная копия от 22 июля 2012 на Wayback Machine, July 2008.
  38. ↑ * Wahlen zum Neo-2-Freeze: Formalitäten Архивная копия от 27 июля 2011 на Wayback Machine, February 2010.
  39. ↑ 2009 Director Elections Архивная копия от 17 июля 2012 на Wayback Machine.
  40. ↑ NSC Jersey election Архивная копия от 26 марта 2009 на Wayback Machine, NSC Jersey vote Архивная копия от 3 марта 2016 на Wayback Machine, September 2007.
  41. ↑ Online Voting Policy Архивная копия от 2 декабря 2016 на Wayback Machine.
  42. ↑ * 2010 OpenStack Community Election Архивная копия от 9 октября 2012 на Wayback Machine, November 2010.
  43. ↑ Voting Procedures. Parkscholars.org. Дата обращения: 8 мая 2010. Архивировано из оригинала 13 апреля 2013 года.
  44. ↑ National Congress 2011 Results Архивная копия от 20 апреля 2013 на Wayback Machine, November 2011.
  45. ↑ § 6(10) of the bylaws. Архивная копия от 11 мая 2012 на Wayback Machine
  46. ↑ Ik word Piraat! (недоступная ссылка), August 2012.
  47. ↑ § 11.2.E of the statutory rules. Архивная копия от 23 марта 2013 на Wayback Machine
  48. ↑ 11 из 16 региональных организаций и федеральная организация Пиратской партии Германии используют LiquidFeedback Архивная копия от 28 января 2013 на Wayback Machine для внутрипартийных голосований. В 2010—2011 годах Пиратские партии Neukölln (link Архивная копия от 6 октября 2014 на Wayback Machine), Mitte (link Архивная копия от 5 июля 2013 на Wayback Machine), Steglitz-Zehlendorf (link Архивная копия от 9 июня 2017 на Wayback Machine), Lichtenberg (link), и Tempelhof-Schöneberg (link Архивная копия от 6 ноября 2013 на Wayback Machine) приняли метод Шульце для внутрипартийных выборов. Также Пиратская партия Берлина (в 2011 году) (link Архивная копия от 17 мая 2013 на Wayback Machine) и Пиратская партия Регенсбурга (в 2012 году) (link Архивная копия от 23 апреля 2012 на Wayback Machine) одобрила этот метод для внутрипартийных выборов.
  49. ↑ Rules adopted on 18 December 2011 (недоступная ссылка).
  50. ↑ Vote Result for Name Definition (недоступная ссылка).
  51. ↑ 23 January 2011 meeting minutes Архивная копия от 10 февраля 2013 на Wayback Machine.
  52. ↑ * Inför primärvalen Архивировано 24 декабря 2012 года., October 2009.
  53. ↑ Piratenversammlung der Piratenpartei Schweiz Архивная копия от 21 сентября 2010 на Wayback Machine, September 2010.
  54. ↑ Article IV, section 4 of the constitution. Архивная копия от 9 ноября 2012 на Wayback Machine
  55. ↑ 2006 Community for Pittsburgh Ultimate Board Election Архивная копия от 3 марта 2016 на Wayback Machine, September 2006.
  56. ↑ Committee Elections Архивная копия от 8 июля 2022 на Wayback Machine, April 2012.
  57. ↑ LogoVoting Архивная копия от 13 июня 2010 на Wayback Machine, December 2007.
  58. ↑ * SPF Council Election Procedures. Архивная копия от 16 июля 2011 на Wayback Machine
  59. ↑ Process for adding new board members, January 2003.
  60. ↑ Squeak Oversight Board Election 2010 Архивная копия от 29 марта 2012 на Wayback Machine, March 2010.
  61. ↑ * Bylaws of the Students for Free Culture Архивная копия от 18 марта 2013 на Wayback Machine, article V, section 1.1.1.
  62. ↑ Election status update Архивная копия от 14 июля 2012 на Wayback Machine, September 2009.
  63. ↑ Minutes of the 2010 Annual Sverok Meeting Архивная копия от 28 марта 2012 на Wayback Machine, November 2010.
  64. ↑ Article VI, section 6 of the bylaws. Архивная копия от 30 января 2012 на Wayback Machine
  65. ↑ * 2006 TopCoder Open Logo Design Contest Архивная копия от 9 августа 2011 на Wayback Machine, November 2005.
  66. ↑ Ubuntu IRC Council Position Архивная копия от 14 февраля 2013 на Wayback Machine, May 2012.
  67. ↑ this mail Архивная копия от 17 апреля 2017 на Wayback Machine.
  68. ↑
  69. ↑ Choix dans les votes.
  70. ↑ here Архивная копия от 21 апреля 2022 на Wayback Machine (May 2009), here Архивная копия от 21 апреля 2022 на Wayback Machine (August 2009), and here Архивная копия от 19 апреля 2022 на Wayback Machine (December 2009).
  71. ↑ here and here.
  72. ↑ * Result of 2007 Arbitration Committee Elections.Архивированная копия. Дата обращения: 17 января 2022. Архивировано 11 мая 2009 года.

Ссылки

[править | править код]
Источник — https://ru.wikipedia.org/w/index.php?title=Метод_Шульце&oldid=140729322