Перегляд вихідного коду сторінки Метод Шульце

'''Метод Шульце'''&nbsp;— [[виборча система]], розроблена в 1997&nbsp;р. Маркусом Шульце, яка дозволяє обрати єдиного переможця через використання [[Виборчий бюлетень|бюлетенів]] для голосування із можливістю ранжувати кандидатури відповідно до вподобань виборців.<ref>{{Cite news|url=http://www.springerlink.com/content/y5451n4908227162/?p=78c7a3edd3f64751ac9c2afc8aa6fad2&pi=0|title=A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method|last=Schulze|first=Markus|date=2010-07-11|pages=267–303|language=en|work=Social Choice and Welfare|volume=36|doi=10.1007/s00355-010-0475-4|issn=0176-1714|issue=2|accessdate=2018-09-19|archive-date=4 січня 2013|archive-url=https://archive.today/20130104215739/http://www.springerlink.com/content/y5451n4908227162/?p=78c7a3edd3f64751ac9c2afc8aa6fad2&pi=0}}</ref> Зазвичай розподіл преференцій виборців відбувається у формі від найбільш бажаного до найменш бажаного кандидата на думку конкретного виборця. Метод Шульца корелюється з '''методом Кондорсе''', останній з яких&nbsp;— це будь-який спосіб обрання кандидата, який би переміг один-на-один будь-якого іншого кандидата. «Метод Шульца»&nbsp;— це матиметатична конкретна модель, яка дозволяє застосувати ідею метода Кондорсе на практиці. Метод Шульца вигідний тим, що дозволяє побороти традицію виборців обирати «менше зло» на виборах, так як дозволяє проголосувати за всіх виборців завдяки системі ранжування і враховує всі голоси. Кожен голос враховується і через математичні розрахунки впливає на загальні результати голосування.

'''Метод Шульце'''&nbsp;— використовується деякими організаціями, серед яких [[Debian]], [[Ubuntu]], Gentoo, [[Software in the Public Interest]], Піратськими партіями Австралії, Австрії, Бельгії, Бразилії, Франції, Німеччини, Ісландії, Італії, Мекски, Нідерландів, Нової Зеландії, Швеції, Швейцарії, США та багатьма іншими.

== Опис методу Шульце ==

=== Виборчий бюлетень ===
Так званий «вхід» для методу Шульце є таким самим, як і для інших методів обрання одного переможця серед багатьох кандидатів шляхом чесних виборів. Кожен виборець має надати упорядкований список переваг про кандидатів. [[Нічия|Нічиї]] є дозволеними та можливими.

Одним типовим способом для виборців є можливість вказати свої переваги на голосування і він виглядає наступним чином: Кожен виборчий бюлетень містить список всіх кандидатів, і кожен виборець входить в цей список в порядку переваги з використанням номерів: виборець ставить «1» поруч з найкращим кандидатом(-ами), «2» поруч з другим кандидатом, якому надають найбільшу перевагу, і так далі. Кожен виборець має можливість:

* надавати однакову перевагу у вигляді цифри більш, ніж одному кандидату. Це вказує на те, що цей виборець є незалежним між цими кандидатами. Тобто, виборцеві байдуже, який з цих кандидатів стане переможцем;
* не використовувати порядкові номери, щоб висловити свої переваги до того чи іншого кандидата. Це не має ніякого впливу на результат виборів, так як це відображає тільки порядок, в якому кандидати ранжуються(оцінюються) з питань виборців, а не абсолютне число переваг;
* не оцінювати кандидатів. Коли виборець не виставляє бали всім кандидатам, то це інтерпретується як факт, що цей виборець (І) є строго кращим, ніж весь ранг всіх неоцінених кандидатів, і (ІІ) є незалежним серед усіх неоцінених кандидатів.

=== Обрахунки ===
Нехай <math>d[V,W]</math>&nbsp;— це число виборців, хто вважає кращим кандидата <math>V</math> за кандидата <math>W</math>.

Шлях від кандидата <math>X</math> до іншого кандидата, тобто <math>Y</math> з рейтингом ''сили'' <math>p</math> є нічим іншим, як [[Послідовність|послідовністю]] усіх кандидатів, що беруть участь у виборах, <math>C(1),\cdots,C(n)</math> з наступними пріоритетами:
# <math>C(1) = X</math> and <math>C(n) = Y</math>.
# Для всіх <math>i = 1,\cdots,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)]</math>.
# Для всіх <math>i = 1,\cdots,(n-1): d[C(i),C(i+1)] \ge p</math>.

Нехай <math>p[A,B]</math>&nbsp;— the ''сила найсильнішого шляху'' від кандидата <math>A</math> до кандидата <math>B</math>&nbsp;— будемо вважати максимальним значенням таким чином, що існує шлях від кандидата <math>A</math> до кандидата <math>B</math> з цією «силою» (''сила'' шляху є нічим іншим, як силою найслабшого зв'язку між кандидатами). Якщо немає жодного шляху від кандидата <math>A</math> до кандидата <math>B</math> взагалі, тоді вважається, що <math>p[A,B] = 0</math>.

Кандидат <math>D</math> є ''кращим'', ніж кандидат <math>E</math> лише в тому випадку, якщо <math>p[D,E] > p[E,D]</math>.

Кандидат <math>D</math> є ''потенційним переможцем'' лише в тому випадку, якщо <math>p[D,E] \ge p[E,D]</math> за кожного іншого кандидата <math>E</math>.

Це може бути доведено так: <math>p[X,Y] > p[Y,X]</math> та <math>p[Y,Z] > p[Z,Y]</math> в сукупності означає, що <math>p[X,Z] > p[Z,X]</math>.<ref name=schulze2011/>{{rp|§4.1}}. Таким чином, гарантується:
* наведене вище визначення дійсно «краще» визначає [[транзитивне відношення|Транзитивне відношення]];
* завжди є принаймні один кандидат <math>D</math> з пріоритетом <math>p[D,E] \ge p[E,D]</math> у порівнянні з іншими кандидатами <math>E</math><math>i</math>.

== Приклад ==
У наступному прикладі, поданому нижче, 45 виборців оцінюють 5-ох кандидатів. Утворюється матриця з кількості голосів та порядку пріоритетів:
: <math>\begin{array}{|c|c|}
\text{number of voters} & \text{order of preference} \\
\hline
5 & ACBED \\
5 & ADECB \\
8 & BEDAC \\
3 & CABED \\
7 & CAEBD \\
2 & CBADE \\
7 & DCEBA \\
8 & EBADC
\end{array}
</math>

Попарні пріоритети (переваги) повинні бути обчислені в першу чергу. Наприклад, при порівнянні {{mvar|A}} та {{mvar|B}} попарно, то можна побачити, що є {{math|1=5+5+3+7=20}} виборців, які надають перевагу {{mvar|A}} у порівнянні з аналогічним показником для {{mvar|B}}, і {{math|1=8+2+7+8=25}} виборців, які надають перевагу {{mvar|B}} в порівнянні з {{mvar|A}}. Отже, <math>d[A, B] = 20</math> and <math>d[B, A] = 25</math>. Повний набір парних переваг має вигляд:

[[Файл:Schulze method example1.svg|thumb|300px|right|[[Орієнтований граф]], помічений попарними перевагами d[*, *] ]]

{| class="wikitable" style="text-align:center"
|+ Матриця попарних переваг
|-
! !! <math>d[*,A]</math> !! <math>d[*,B]</math> !! <math>d[*,C]</math> !! <math>d[*,D]</math> !! <math>d[*,E]</math>
|-
! <math>d[A,*]</math>
| || style="background:#fdd;"|20 || style="background:#dfd;"|26 || style="background:#dfd;"|30 || style="background:#fdd;"|22
|-
! <math>d[B,*]</math>
| style="background:#dfd;"|25 || || style="background:#fdd;"|16 || style="background:#dfd;"|33 || style="background:#fdd;"|18
|-
! <math>d[C,*]</math>
| style="background:#fdd;"|19 || style="background:#dfd;"|29 || || style="background:#fdd;"|17 || style="background:#dfd;"|24
|-
! <math>d[D,*]</math>
| style="background:#fdd;"|15 || style="background:#fdd;"|12 || style="background:#dfd;"|28 || || style="background:#fdd;"|14
|-
! <math>d[E,*]</math>
| style="background:#dfd;"|23 || style="background:#dfd;"|27 || style="background:#fdd;"|21 || style="background:#dfd;"|31 ||
|}

Клітини d[X, Y] мають світло-зелений фон (як можна помітити), якщо d[X, Y] > d[Y, X]. У всіх інших випадках фон клітинки є світло-червоним. Тут немає одноголосного переможця, якщо дивитись лише на попарні відмінності переваг.

Тепер слід ідентифікувати так звані найсильніші шляхи. Для того щоб візуалізувати найсильніші шляхи та зробити останні більш-менш прийнятними для сприйняття, попарні переваги зображено на малюнку справа у вигляді [[Орієнтований граф|орієнтованого графу]]. Стрілці від вузла, що представляє кандидата X до іншої, який представляє кандидата Y надають мітку d[X, Y]. Для того, щоб не захаращувати діаграму, стрілку малюють з X до Y лише у випадку, коли d[X, Y] > d[Y, X] (тобто елементи таблиці з світло-зеленим фоном), опускаючи іншу стрілку в протилежному напрямку (елементи таблиці зі світло-червоним тлом).

Одним із прикладів обчислення найбільш сильного шляху p[B, D] = 33: найсильніший шлях від B до D є прямим шляхом (B, D), що має силу 33. Але під час обчислення вже іншого найсильнішого шляху, наприклад, p[A, C], то тут найсильніший шлях від A до C не має прямої дороги (A, C) з силою 26, тим паче, швидше за все найсильніший шлях є непрямим (A, D, C), що має силу між мінімальними елементами сусідніх вершин графу min(30, 28) = 28. ''Сила'' шляху є силою його найслабшого зв'язку.
Для кожної пари кандидатів X і Y, наступна таблиця показує сильний шлях від кандидата X до кандидата Y зафарбуванням вершини червоним кольором, з найслабшою ланкою, що є підкресленою. Примітка: рядки&nbsp;— звідки, стовпці&nbsp;— куди рухаємось.

{{clear}}
{| class="wikitable" style="text-align:center"
|+ Найсильніші шляхи
|-
! !! A !! B !! C !! D !! E
!
|-
! A
| {{n/a}} || [[Файл:Schulze method example1 AB.svg|border|none|150px]] A-(30)-D-<u>(28)</u>-C-(29)-B || [[Файл:Schulze method example1 AC.svg|border|none|150px]] A-(30)-D-<u>(28)</u>-C || [[Файл:Schulze method example1 AD.svg|border|none|150px]] A-<u>(30)</u>-D || [[Файл:Schulze method example1 AE.svg|border|none|150px]] A-(30)-D-(28)-C-<u>(24)</u>-E
! A
|-
! B
| [[Файл:Schulze method example1 BA.svg|border|none|150px]] B-<u>(25)</u>-A || {{n/a}} || [[Файл:Schulze method example1 BC.svg|border|none|150px]] B-(33)-D-<u>(28)</u>-C || [[Файл:Schulze method example1 BD.svg|border|none|150px]] B-<u>(33)</u>-D || [[Файл:Schulze method example1 BE.svg|border|none|150px]] B-(33)-D-(28)-C-<u>(24)</u>-E
! B
|-
! C
| [[Файл:Schulze method example1 CA.svg|border|none|150px]] C-(29)-B-<u>(25)</u>-A || [[Файл:Schulze method example1 CB.svg|border|none|150px]] C-<u>(29)</u>-B || {{n/a}} || [[Файл:Schulze method example1 CD.svg|border|none|150px]] C-<u>(29)</u>-B-(33)-D || [[Файл:Schulze method example1 CE.svg|border|none|150px]] C-<u>(24)</u>-E
! C
|-
! D
| [[Файл:Schulze method example1 DA.svg|border|none|150px]] D-(28)-C-(29)-B-<u>(25)</u>-A || [[Файл:Schulze method example1 DB.svg|border|none|150px]] D-<u>(28)</u>-C-(29)-B || [[Файл:Schulze method example1 DC.svg|border|none|150px]] D-<u>(28)</u>-C || {{n/a}} || [[Файл:Schulze method example1 DE.svg|border|none|150px]] D-(28)-C-<u>(24)</u>-E
! D
|-
! E
| [[Файл:Schulze method example1 EA.svg|border|none|150px]] E-(31)-D-(28)-C-(29)-B-<u>(25)</u>-A || [[Файл:Schulze method example1 EB.svg|border|none|150px]] E-(31)-D-<u>(28)</u>-C-(29)-B || [[Файл:Schulze method example1 EC.svg|border|none|150px]] E-(31)-D-<u>(28)</u>-C || [[Файл:Schulze method example1 ED.svg|border|none|150px]] E-<u>(31)</u>-D || {{n/a}}
! E
|-
!
! A !! B !! C !! D !! E
|}

{| class="wikitable" style="text-align:center"
|+Сили найсильніших шляхів
|-
! !! <math>p[*,A]</math> !! <math>p[*,B]</math> !! <math>p[*,C]</math> !! <math>p[*,D]</math> !! <math>p[*,E]</math>
|-
! <math>p[A,*]</math>
| || style="background:#dfd;"|28 || style="background:#dfd;"|28 || style="background:#dfd;"|30 || style="background:#fdd;"|24
|-
! <math>p[B,*]</math>
| style="background:#fdd;"|25 || || style="background:#fdd;"|28 || style="background:#dfd;"|33 || style="background:#fdd;"|24
|-
! <math>p[C,*]</math>
| style="background:#fdd;"|25 || style="background:#dfd;"|29 || || style="background:#dfd;"|29 || style="background:#fdd;"|24
|-
! <math>p[D,*]</math>
| style="background:#fdd;"|25 || style="background:#fdd;"|28 || style="background:#fdd;"|28 || || style="background:#fdd;"|24
|-
! <math>p[E,*]</math>
| style="background:#dfd;"|25 || style="background:#dfd;"|28 || style="background:#dfd;"|28 || style="background:#dfd;"|31 ||
|}

Тепер вихідний результат методу Шульце може бути точно визначеним. Наприклад, під час порівняння {{mvar|A}} та {{mvar|B}}, бо <math>(28 =) p[A,B] > p[B,A] (= 25)</math>, за методом Шульце кандидат {{mvar|A}} є ''кращий'', ніж кандидат {{mvar|B}}. Ще одним прикладом є те, що <math>(31 =) p[E,D] > p[D,E] (= 24)</math>, а саме тому кандидат E є ''кращий'', ніж кандидат D. Продовжуючи таким же шляхом, отримаємо результат, що показує рейтинг за методом Шульце: <math>E > A > C > B > D</math>, а це означає, що {{mvar|E}} є переможцем. Іншими словами, кандидат {{mvar|E}} виграв вибори, так як <math>p[E,X] \ge p[X,E]</math> у порівнянні з іншими кандидатами X.

== Комп'ютерна реалізація ==

Важкий кроком в реалізації методу Шульце на практиці є обчислення сил найбільш сильних шляхів. Тим не менш, це є добре відомою проблемою в [[Теорія графів|теорії графів]], яку іноді називають [[Задача про найширший шлях|проблемою найширшого шляху]]. Одним і простим способом для обчислення сили є варіант [[Алгоритм Флойда — Воршелла|алгоритм Флойда&nbsp;— Воршелла]]. Наступний [[псевдокод]] ілюструє алгоритм.

<syntaxhighlight line lang="text">
# Input: d[i,j], кількість виборців, які надають перевагу кандидату i відносно кандидата j.
# Output: p[i,j], сила найбільш сильного шляху від кандидата i до кандидата j.

for i from 1 to C
   for j from 1 to C
      if (i ≠ j) then
         if (d[i,j] > d[j,i]) then
            p[i,j] := d[i,j]
         else
            p[i,j] := 0

for i from 1 to C
   for j from 1 to C
      if (i ≠ j) then
         for k from 1 to C
            if (i ≠ k and j ≠ k) then
               p[j,k] := max ( p[j,k], min ( p[j,i], p[i,k] ) )
</syntaxhighlight>

Цей алгоритм є ефективним, і працює за час [[Нотація Ландау|O(''C''<sup>3</sup>)]], де С являє собою число кандидатів.

== Нічиї та альтернативні реалізації ==
Дозволяючи користувачам (виборцям) не обирати одного кандидата, а з можливістю встановлення однакових пріоритетів, результат методу Шульце зрозуміло залежить від того, як ці однакові пріоритети інтерпретуються під час визначення d[*,*]. Двома природними виборами є такі, що d[A, B] зображає або кількість тих виборців, що точно надають перевагу A відносно B (A>B), або ''межу'' (виборці, де A>B) мінусів (виборці, де B>A). Але немає справжнього значення, як ''d''-ті визначаються, встановлення рейтингу за методом Шульце не передбачає жодних циклів і припущення того, що ''d''-ті є унікальними означає, що не нічиєї однозначно не можу бути.

Хоча нічиї в рейтингу Шульце малоймовірні, вони можливі. Шульце запропонував оригінальний документ для вирішення проблеми нічиєї, що має такі особливості:
* обрання виборців випадковим чином;
* ітерації в міру необхідності.

Ще одним способом опису переможця за допомогою метода Шульце, проте значно повільним, є наступна процедура, що складається з таких кроків:
# намалювати повний орієнтований граф з усіма кандидатами та все можливими ребрами між кандидатами;
# ітераційно (І) видалити усіх кандидатів, що не знаходяться в наборі {{iw| Schwartz set|Шварца|en| Schwartz set}} (тобто будь-який кандидат, що не може досягнути усіх інших та (ІІ)&nbsp;— видалити найслабші зв'язки;
# переможцем є кандидат, що залишився після видалення усіх решти (крок 2).

== Див. також ==
* [[Система єдиного перехідного голосу]]

{{Без джерел|дата=липень 2018}}
{{Authority control}}

== Примітки ==
{{reflist|refs=<ref name="schulze2011">Markus Schulze, [http://www.springerlink.com/content/y5451n4908227162/?p=78c7a3edd3f64751ac9c2afc8aa6fad2&pi=0 A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method] {{Webarchive|url=https://archive.today/20130104215739/http://www.springerlink.com/content/y5451n4908227162/?p=78c7a3edd3f64751ac9c2afc8aa6fad2&pi=0 |date=4 січня 2013 }}, Social Choice and Welfare, volume 36, number 2, page 267–303, 2011. Preliminary version in ''Voting Matters'', 17:9-19, 2003.{{ref-en}} Наведено за англійською вікіпедією.</ref>
}}

{{Виборчі системи}}
[[Категорія:Конституційне право]]
[[Категорія:Виборчі системи]]