Метод Шульце

Метод Шульце — виборча система, розроблена в 1997 р. Маркусом Шульце, яка дозволяє обрати єдиного переможця через використання бюлетенів для голосування із можливістю ранжувати кандидатури відповідно до вподобань виборців. Зазвичай розподіл преференцій виборців відбувається у формі від найбільш бажаного до найменш бажаного кандидата на думку конкретного виборця. Метод Шульца корелюється з методом Кондорсе, останній з яких — це будь-який спосіб обрання кандидата, який би переміг один-на-один будь-якого іншого кандидата. «Метод Шульца» — це матиметатична конкретна модель, яка дозволяє застосувати ідею метода Кондорсе на практиці. Метод Шульца вигідний тим, що дозволяє побороти традицію виборців обирати «менше зло» на виборах, так як дозволяє проголосувати за всіх виборців завдяки системі ранжування і враховує всі голоси. Кожен голос враховується і через математичні розрахунки впливає на загальні результати голосування.

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

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

Виборчий бюлетень

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

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

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

Обрахунки

Нехай ${\displaystyle d[V,W]}$ — це число виборців, хто вважає кращим кандидата ${\displaystyle V}$ за кандидата ${\displaystyle W}$.

Шлях від кандидата ${\displaystyle X}$ до іншого кандидата, тобто ${\displaystyle Y}$ з рейтингом сили ${\displaystyle p}$ є нічим іншим, як послідовністю усіх кандидатів, що беруть участь у виборах, ${\displaystyle C(1),\cdots ,C(n)}$ з наступними пріоритетами:

1. ${\displaystyle C(1)=X}$ and ${\displaystyle C(n)=Y}$.
2. Для всіх ${\displaystyle i=1,\cdots ,(n-1):d[C(i),C(i+1)]>d[C(i+1),C(i)]}$.
3. Для всіх ${\displaystyle i=1,\cdots ,(n-1):d[C(i),C(i+1)]\geq p}$.

Нехай ${\displaystyle p[A,B]}$ — the сила найсильнішого шляху від кандидата ${\displaystyle A}$ до кандидата ${\displaystyle B}$ — будемо вважати максимальним значенням таким чином, що існує шлях від кандидата ${\displaystyle A}$ до кандидата ${\displaystyle B}$ з цією «силою» (сила шляху є нічим іншим, як силою найслабшого зв'язку між кандидатами). Якщо немає жодного шляху від кандидата ${\displaystyle A}$ до кандидата ${\displaystyle B}$ взагалі, тоді вважається, що ${\displaystyle p[A,B]=0}$.

Кандидат ${\displaystyle D}$ є кращим, ніж кандидат ${\displaystyle E}$ лише в тому випадку, якщо ${\displaystyle p[D,E]>p[E,D]}$.

Кандидат ${\displaystyle D}$ є потенційним переможцем лише в тому випадку, якщо ${\displaystyle p[D,E]\geq p[E,D]}$ за кожного іншого кандидата ${\displaystyle E}$.

Це може бути доведено так: ${\displaystyle p[X,Y]>p[Y,X]}$ та ${\displaystyle p[Y,Z]>p[Z,Y]}$ в сукупності означає, що ${\displaystyle p[X,Z]>p[Z,X]}$.^:§4.1. Таким чином, гарантується:

• наведене вище визначення дійсно «краще» визначає Транзитивне відношення;
• завжди є принаймні один кандидат ${\displaystyle D}$ з пріоритетом ${\displaystyle p[D,E]\geq p[E,D]}$ у порівнянні з іншими кандидатами ${\displaystyle E}$${\displaystyle i}$.

Приклад

У наступному прикладі, поданому нижче, 45 виборців оцінюють 5-ох кандидатів. Утворюється матриця з кількості голосів та порядку пріоритетів:

${\displaystyle {\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}}}$

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

Орієнтований граф, помічений попарними перевагами d[*, *]

Матриця попарних переваг

	${\displaystyle d[*,A]}$	${\displaystyle d[*,B]}$	${\displaystyle d[*,C]}$	${\displaystyle d[*,D]}$	${\displaystyle d[*,E]}$
${\displaystyle d[A,*]}$		20	26	30	22
${\displaystyle d[B,*]}$	25		16	33	18
${\displaystyle d[C,*]}$	19	29		17	24
${\displaystyle d[D,*]}$	15	12	28		14
${\displaystyle d[E,*]}$	23	27	21	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 зафарбуванням вершини червоним кольором, з найслабшою ланкою, що є підкресленою. Примітка: рядки — звідки, стовпці — куди рухаємось.

Найсильніші шляхи

	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	A
B	B-(25)-A	Н/Д	B-(33)-D-(28)-C	B-(33)-D	B-(33)-D-(28)-C-(24)-E	B
C	C-(29)-B-(25)-A	C-(29)-B	Н/Д	C-(29)-B-(33)-D	C-(24)-E	C
D	D-(28)-C-(29)-B-(25)-A	D-(28)-C-(29)-B	D-(28)-C	Н/Д	D-(28)-C-(24)-E	D
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	Н/Д	E
	A	B	C	D	E

Сили найсильніших шляхів

	${\displaystyle p[*,A]}$	${\displaystyle p[*,B]}$	${\displaystyle p[*,C]}$	${\displaystyle p[*,D]}$	${\displaystyle p[*,E]}$
${\displaystyle p[A,*]}$		28	28	30	24
${\displaystyle p[B,*]}$	25		28	33	24
${\displaystyle p[C,*]}$	25	29		29	24
${\displaystyle p[D,*]}$	25	28	28		24
${\displaystyle p[E,*]}$	25	28	28	31

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

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

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

# 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] ) ) 

Цей алгоритм є ефективним, і працює за час O(C³), де С являє собою число кандидатів.

Нічиї та альтернативні реалізації

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

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

• обрання виборців випадковим чином;
• ітерації в міру необхідності.

Ще одним способом опису переможця за допомогою метода Шульце, проте значно повільним, є наступна процедура, що складається з таких кроків:

1. намалювати повний орієнтований граф з усіма кандидатами та все можливими ребрами між кандидатами;
2. ітераційно (І) видалити усіх кандидатів, що не знаходяться в наборі ^[en] (тобто будь-який кандидат, що не може досягнути усіх інших та (ІІ) — видалити найслабші зв'язки;
3. переможцем є кандидат, що залишився після видалення усіх решти (крок 2).

Див. також

• Система єдиного перехідного голосу

Примітки

1. Schulze, Markus (11 липня 2010). A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method. Social Choice and Welfare (англ.). Т. 36, № 2. с. 267—303. doi:10.1007/s00355-010-0475-4. ISSN 0176-1714. Архів оригіналу за 4 січня 2013. Процитовано 19 вересня 2018.
2. Markus Schulze, A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method [Архівовано 4 січня 2013 у Archive.is], Social Choice and Welfare, volume 36, number 2, page 267–303, 2011. Preliminary version in Voting Matters, 17:9-19, 2003.(англ.) Наведено за англійською вікіпедією.