Метод Шульце

Метод Шульце (также метод последовательного исключения Шварца) — система голосования, разработанная в 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, *]  —7033
d[B, *] 27 —60
d[C, *] 6437—

Жирным выделены значения 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, *] 20263022
d[B, *] 25163318
d[C, *] 19291724
d[D, *] 15122814
d[E, *] 23272131

Сила пути — это сила его слабейшего звена (критическое звено). Пути, каждый переход в которых удовлетворяет 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, *] 28283024
p[B, *] 25283324
p[C, *] 25292924
p[D, *] 25282824
p[E, *] 25282831

По методу Шульце будет провозглашён победителем кандидат 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. Архивная копия от 26 апреля 2005 на Wayback Machine, January 2005.
  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.
  11. Appendix 1 of the constitution. Архивная копия от 18 июля 2011 на Wayback Machine
  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, September 2011.
  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, 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.
  29. Knight Foundation awards $5000 to best created-on-the-spot projects Архивная копия от 20 июля 2011 на Wayback Machine, June 2009.
  31. Article 8.3 of the bylaws.
  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.
  39. 2009 Director Elections.
  40. NSC Jersey election Архивная копия от 26 марта 2009 на Wayback Machine, NSC Jersey vote, September 2007.
  41. Online Voting Policy.
  43. Voting Procedures (недоступная ссылка). Parkscholars.org. Дата обращения: 8 мая 2010. Архивировано 13 апреля 2013 года.
  44. National Congress 2011 Results, 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 для внутрипартийных голосований. В 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.
  53. Piratenversammlung der Piratenpartei Schweiz, September 2010.
  54. Article IV, section 4 of the constitution. Архивная копия от 9 ноября 2012 на Wayback Machine
  55. 2006 Community for Pittsburgh Ultimate Board Election, September 2006.
  56. Committee Elections, April 2012.
  57. LogoVoting Архивная копия от 13 июня 2010 на Wayback Machine, December 2007.
  59. Process for adding new board members, January 2003.
  60. Squeak Oversight Board Election 2010, March 2010.
  62. Election status update, September 2009.
  63. Minutes of the 2010 Annual Sverok Meeting, November 2010.
  64. Article VI, section 6 of the bylaws. Архивная копия от 30 января 2012 на Wayback Machine
  66. Ubuntu IRC Council Position, May 2012.
  67. this mail.
  69. Choix dans les votes.
  70. here (May 2009), here (August 2009), and here (December 2009).
  71. here and here.

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.