WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

Метод Шульце (также метод последовательного исключения Шварца) — система голосования, разработанная в 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]. Как видно из таблицы, в этом примере каждому кандидату предпочитается другой кандидат — имеет место парадокс Кондорсе. Однако сила предпочтения различается. Предпочтение, отдаваемое кандидату А перед кандидатом В, больше предпочтения, отдаваемого кандидату 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,*] 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
  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 Архивная копия от 26 июля 2011 на Wayback Machine
  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 Архивная копия от 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
  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. ↑ <span lang=" (нем.)" xml:lang=" (нем.)">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 Архивная копия от 26 марта 2009 на Wayback Machine, NSC Jersey vote, September 2007
  41. ↑ Online Voting Policy
  42. ↑ Смотри:
  43. ↑ Voting Procedures (недоступная ссылка). Parkscholars.org. Проверено 8 мая 2010. Архивировано 13 апреля 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 Архивная копия от 13 июня 2010 на Wayback Machine, 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. ↑ Смотри например here (May 2009), here (August 2009), and here (December 2009).
  71. ↑ Смотри here and here.
  72. ↑ Смотри:

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .



Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии