Schulzeova metoda - Schulze method

Část Seriál o politice
Volební systémy
Pluralita / majorita Množství První příspěvek Jeden nepřenosný hlas Omezené hlasování Plurality-at-large (blokové hlasování) Obecný lístek Vícekolové hlasování Dvoukolové Vyčerpávající hlasování Hodnocené / preferenční systémy Okamžitý odtok (alternativní hlasování) Podmíněné hlasování Coombsova metoda Condorcetovy metody (Copeland, Dodgson, Kemeny – Young, Minimax, Nanson, hodnocené páry, Schulze, Alternativní Smith ) Poziční hlasování (Borda počítat, Nauru / Dowdallova metoda, Soutěž Eurovision Song Contest ) Bucklin hlasování Oklahoma primární volební systém Preferenční blokové hlasování Kardinální / odstupňované systémy Hodnocení hlasování Hlasování o schválení (sjednocený primární ) Kombinované hlasování o schválení Hlasování o schválení spokojenosti Většinový úsudek Hlasování STAR
Poměrné zastoupení Seznam stran (otevřené seznamy, uzavřené seznamy, místní seznamy ) Nejvyšší průměry (D'Hondt, Sainte-Laguë, Huntington – Hill ) Největší zbytek (Zajíc, Vadnout, Imperiali, Hagenbach-Bischoff ) Proporcionální formy okamžité odtokové hlasování Jeden převoditelný hlas (Gregory, Wrighte ) Proporcionální formy Condorcetovy metody CPO-STV Schulze STV Proporcionální formy schvalovací hlasování Proporcionální hlasování o schválení Postupné poměrné hlasování o schválení Biproporcionální rozdělení Hlasování spravedlivou většinou
Smíšené systémy Smíšený člen proporcionální Další členský systém Paralelní hlasování (smíšený-majoritní) Scorporo Majoritní bonus Alternativní hlasování Plus Dvoučlenný proporcionální Venkovské a městské proporcionální
Další systémy a související teorie Kumulativní hlasování Binomické hlasování Hlasování proxy Delegované hlasování Náhodný výběr (třídění, náhodné hlasování ) Srovnání volebních systémů Teorie sociální volby Arrowova věta Gibbard – Satterthwaiteova věta Teorie veřejné volby
Portál politiky

The Schulzeova metoda (/ˈʃʊltsə/) je volební systém vyvinutý v roce 1997 Markusem Schulzem, který vybírá a jediný vítěz pomocí hlasů, které vyjadřují předvolby. Tuto metodu lze také použít k vytvoření seřazeného seznamu vítězů. Schulzeova metoda je také známá jako Schwartzův postupný pokles (SSD), klonové Schwartzovo sekvenční klesání (ČSSD), metoda beatpath, vítěz beatpath, hlasování o cestě, a vítěz cesty.

Schulzeova metoda je a Condorcetova metoda, což znamená, že pokud existuje kandidát, který je preferován většinou před každým dalším kandidátem v párovém srovnání, pak bude tento kandidát vítězem, když bude použita Schulzeho metoda.

Výstup metody Schulze (definovaný níže) dává pořadí kandidátů. Proto, pokud je k dispozici několik pozic, lze metodu pro tento účel použít beze změn, a to tak, že necháte k nejlepší kandidáti vyhrají k volná místa. Dále pro poměrné zastoupení volby, a varianta jednoho převoditelného hlasu bylo navrženo.

Metodu Schulze používá několik organizací včetně Wikimedia, Debian, Ubuntu, Gentoo, Pirátská párty politické strany a mnoho dalších.

Popis metody

Hlasování

Vstup pro metodu Schulze je stejný jako pro ostatní zařadil volební systémy s jedním vítězem: každý volič musí poskytnout objednaný seznam preferencí kandidátů, kde vazby jsou povoleny (přísný slabý řád ).^[1]

Jeden typický způsob, jak mohou voliči specifikovat své preference na a hlasování je následující. Každý hlasovací lístek uvádí všechny kandidáty a každý volič řadí tento seznam v pořadí podle preferencí pomocí čísel: volič umístí „1“ vedle nejvíce preferovaného kandidáta (kandidátů), „2“ vedle druhého nejvýhodnějšího kandidáta atd. . Každý volič může volitelně:

• dát stejnou přednost více než jednomu kandidátovi. To naznačuje, že tento volič je mezi těmito kandidáty lhostejný.
• k vyjádření preferencí používejte po sobě jdoucí čísla. To nemá žádný dopad na výsledek voleb, protože záleží pouze na pořadí, v jakém jsou kandidáti seřazeni voličem, a nikoli na absolutním počtu preferencí.
• uchovat kandidáty bez hodnocení. Pokud volič nezařadí všechny kandidáty, pak se to interpretuje, jako by tento volič (i) striktně upřednostňoval všechny hodnocené před všemi kandidáty bez hodnocení a (ii) je lhostejný mezi všemi kandidáty bez hodnocení.

Výpočet

Nechat ${ displaystyle d [V, W]}$ být počet voličů, kteří preferují kandidáta ${ displaystyle V}$ na kandidáta ${ displaystyle W}$.

A cesta od kandidáta ${ displaystyle X}$ na kandidáta ${ displaystyle Y}$ je sekvence kandidátů ${ displaystyle C (1), cdots, C (n)}$ s následujícími vlastnostmi:

1. ${ displaystyle C (1) = X}$ a ${ displaystyle C (n) = Y}$.
2. Pro všechny ${ displaystyle i = 1, cdots, (n-1): d [C (i), C (i + 1)]> d [C (i + 1), C (i)]}$.

Jinými slovy, v párovém srovnání každý kandidát na cestě porazí následujícího kandidáta.

The síla ${ displaystyle p}$ cesty od kandidáta ${ displaystyle X}$ na kandidáta ${ displaystyle Y}$ je nejmenší počet voličů v pořadí srovnání:

Pro všechny ${ displaystyle i = 1, cdots, (n-1): d [C (i), C (i + 1)] geq p}$.

Pro dvojici kandidátů ${ displaystyle A}$ a ${ displaystyle B}$ které jsou spojeny alespoň jednou cestou, síla nejsilnější cesty ${ displaystyle p [A, B]}$ je maximální síla cest, které je spojují. Pokud od kandidáta neexistuje cesta ${ displaystyle A}$ na kandidáta ${ displaystyle B}$ tedy vůbec ${ displaystyle p [A, B] = 0}$.

Kandidát ${ displaystyle D}$ je lepší než kandidát ${ displaystyle E}$ kdyby a jen kdyby ${ displaystyle p [D, E]> p [E, D]}$.

Kandidát ${ displaystyle D}$ je potenciální vítěz kdyby a jen kdyby ${ displaystyle p [D, E] geq p [E, D]}$ pro každého dalšího kandidáta ${ displaystyle E}$.

To lze dokázat ${ displaystyle p [X, Y]> p [Y, X]}$ a ${ displaystyle p [Y, Z]> p [Z, Y]}$ společně znamenají ${ displaystyle p [X, Z]> p [Z, X]}$.^[1]:§4.1 Proto je zaručeno (1), že výše uvedená definice „lepší"opravdu definuje a tranzitivní vztah a (2) že vždy existuje alespoň jeden kandidát ${ displaystyle D}$ s ${ displaystyle p [D, E] geq p [E, D]}$ pro každého dalšího kandidáta ${ displaystyle E}$.

Příklad

V následujícím příkladu má 45 voličů 5 kandidátů.

${ displaystyle { begin {array} {| c | c |} { text {počet voličů}} & { text {pořadí preferencí}} hline 5 & ACBED 5 & ADECB 8 & BEDAC 3 & CABED 7 & CAEBD 2 & CBADE 7 & DCEBA 8 & EBADC end {pole}}}$

Nejprve je třeba vypočítat párové preference. Například při porovnávání A a B po párech jsou 5+5+3+7=20 voliči, kteří dávají přednost A na B, a 8+2+7+8=25 voliči, kteří dávají přednost B na A. Tak ${ displaystyle d [A, B] = 20}$ a ${ displaystyle d [B, A] = 25}$. Celá sada párových předvoleb je:

Směrovaný graf s párovými preferencemi d [*, *]

Matice párových preferencí

	${ 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

Buňky pro d [X, Y] mají světle zelené pozadí, pokud d [X, Y]> d [Y, X], jinak je pozadí světle červené. Neexistuje žádný nesporný vítěz, když se zde podíváme na párové rozdíly.

Nyní je třeba identifikovat nejsilnější cesty. Abychom pomohli vizualizovat nejsilnější cesty, je sada párových předvoleb zobrazena v diagramu vpravo ve formě řízený graf. Šipka z uzlu představujícího kandidáta X na ten, který představuje kandidáta Y, je označena d [X, Y]. Aby nedocházelo k přeplnění diagramu, byla šipka nakreslena z X do Y pouze tehdy, když d [X, Y]> d [Y, X] (tj. Buňky tabulky se světle zeleným pozadím), přičemž je vynechána ta v opačném směru ( buňky stolu se světle červeným pozadím).

Jedním příkladem výpočtu nejsilnější síly dráhy je p [B, D] = 33: nejsilnější cestou z B do D je přímá cesta (B, D), která má sílu 33. Ale při výpočtu p [A, C] je nejsilnější cesta z A do C není přímá cesta (A, C) síly 26, spíše nejsilnější cesta je nepřímá cesta (A, D, C), která má sílu min (30, 28) = 28. The síla cesty je síla jejího nejslabšího článku.

U každé dvojice kandidátů X a Y ukazuje následující tabulka červeně nejsilnější cestu od kandidáta X ke kandidátovi Y s nejslabším článkem podtrženo.

Nejsilnější cesty

Na Z	A	B	C	D	E
A	N / 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	N / 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	N / A	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	N / A	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	N / A	E
	A	B	C	D	E	Z Na

Silné stránky nejsilnějších cest

	${ 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

Nyní lze určit výstup Schulzeovy metody. Například při porovnávání A a B, od té doby ${ displaystyle (28 =) p [A, B]> p [B, A] (= 25)}$, pro kandidáta na Schulzeho metodu A je lepší než kandidát B. Dalším příkladem je to ${ displaystyle (31 =) p [E, D]> p [D, E] (= 24)}$, takže kandidát E. lepší než kandidát D. Výsledkem je, že Schulzeův žebříček je takový ${ displaystyle E> A> C> B> D}$, a E vyhrává. Jinými slovy, E vyhrává od ${ displaystyle p [E, X] geq p [X, E]}$ za každého dalšího kandidáta X.

Implementace

Jediným obtížným krokem při implementaci Schulzeovy metody je výpočet nejsilnějších silných stránek cesty. Jedná se však o známý problém v teorii grafů, který se někdy nazývá problém s nejširší cestou. Jedním z jednoduchých způsobů, jak vypočítat silné stránky, je tedy varianta Floyd-Warshallův algoritmus. Následující pseudo kód ilustruje algoritmus.

 1 # Vstup: d [i, j], počet voličů, kteří upřednostňují kandidáta i před kandidátem j. 2 # Výstup: p [i, j], síla nejsilnější cesty od kandidáta i ke kandidátovi j. 3  4 pro i od 1 do C. 5     pro j od 1 do C 6         if (i ≠ j) then 7             if (d [i, j]> d [j, i]) then 8                 p [i, j]: = d [i, j] 9             jiný10                 p [i, j]: = 011 12 pro i od 1 do C.13     pro j od 1 do C14         if (i ≠ j) then15             pro k od 1 do C16                 if (i ≠ k a j ≠ k) pak17                     p [j, k]: = max (p [j, k], min (p [j, i], p [i, k]))

Tento algoritmus je účinný a má provozní doba Ó(C³) kde C je počet kandidátů.

Vazby a alternativní implementace

Když uživatelům umožníme mít ve svých preferencích vazby, výsledek Schulzeovy metody přirozeně závisí na tom, jak jsou tyto vazby interpretovány při definování d [*, *]. Dvě přirozené možnosti jsou, že d [A, B] představuje buď počet voličů, kteří striktně upřednostňují A před B (A> B), nebo okraj z (voliči s A> B) minus (voliči s B> A). Ale bez ohledu na to, jak ds jsou definovány, Schulzeho hodnocení nemá žádné cykly a za předpokladu, že djsou jedinečné, nemá žádné vazby.^[1]

Ačkoli vazby v žebříčku Schulze jsou nepravděpodobné,^{[2][Citace je zapotřebí ]} jsou možné. Schulzeho originální papír^[1] navrhl zlomení vazeb v souladu s náhodně vybraným voličem a opakování podle potřeby.

Alternativní způsob, jak popsat vítěze Schulzeovy metody, je následující postup:^{[Citace je zapotřebí ]}

1. nakreslete kompletní směrovaný graf se všemi kandidáty a všemi možnými hranami mezi kandidáty
2. iterativně [a] smazat všechny kandidáty, kteří nejsou v Schwartzova sada (tj. jakýkoli kandidát X který nemůže dosáhnout všech ostatních, kteří dosáhnou X) a [b] smaže okraj grafu s nejmenší hodnotou (pokud je o okraje, nejmenší okraj, je-li o hlasy, nejméně hlasů).
3. vítězem je poslední nevymazaný kandidát.

Existuje další alternativní způsob prokázat vítěz Schulzeovy metody. Tato metoda je ekvivalentní s ostatními zde popsanými, ale prezentace je optimalizována pro význam kroků vizuálně zjevné jak to procházíte, ne pro výpočet.

1. Vytvořte tabulku výsledků nazvanou „matice párových preferencí“, která se používá výše v příkladu. Pokud používáte spíše marže než součty hrubých hlasů, odečtěte to od její transpozice. Pak je každé kladné číslo dvojicí výhry kandidáta v dané řadě (a označené zeleně), remízy jsou nuly a ztráty jsou záporné (označené červeně). Pořadí kandidátů podle toho, jak dlouho vydrží.
2. Pokud je na lince kandidát bez červené barvy, vyhrává.
3. Jinak nakreslete čtvercový rámeček kolem Schwartzovy sady v levém horním rohu. Můžete to popsat jako minimální „okruh vítězů“ kandidátů, kteří neprohrají s nikým mimo kruh. Všimněte si, že napravo od pole není červená, což znamená, že jde o kruh vítěze, a všimněte si, že uvnitř pole není možné přeskupení, které by vytvořilo menší kruh vítěze.
4. Odřízněte všechny části stolu, které nejsou v krabici.
5. Pokud stále není žádný kandidát bez červené barvy, je třeba něco kompromitovat; každý kandidát prohrál nějakou rasu a ztráta, kterou tolerujeme nejlépe, je ta, kde poražený získal nejvíce hlasů. Vezměte tedy červenou buňku s nejvyšším číslem (pokud jde o okraje, nejméně záporné), změňte ji na zelenou - nebo jinou barvu než červenou - a vraťte se zpět ke kroku 2.

Zde je tabulka okrajů vyrobená z výše uvedeného příkladu. Všimněte si změny pořadí použitého pro demonstrační účely.

První pokles (ztráta A na E o 1 hlas) nepomůže zmenšit Schwartzovu sadu.

Dostáváme se tedy přímo k druhému poklesu (ztráta E na C o 3 hlasy), a to nám ukazuje vítěze, E, s jeho jasnou řadou.

Tuto metodu lze také použít k výpočtu výsledku, pokud vytvoříte tabulku takovým způsobem, že můžete pohodlně a spolehlivě přeskupit pořadí kandidátů na řádek i sloupec (vždy použít stejné pořadí na obou).

Spokojená a nesplněná kritéria

Spokojená kritéria

Metoda Schulze splňuje následující kritéria:

Selhala kritéria

Protože metoda Schulze splňuje kritérium Condorcet, automaticky selže následující kritéria:

• Účast^[1]:§3.4
• Konzistence
• Nezranitelnost vůči kompromisu
• Nezranitelnost pohřbívání
• Později neškodit

Podobně, protože Schulzeova metoda není diktaturou a souhlasí s jednomyslným hlasováním, Arrowova věta znamená, že nesplňuje kritérium

• Nezávislost irelevantních alternativ

Metoda Schulze také selže

• Peyton Young kritérium Místní nezávislost na irelevantních alternativách.

Srovnávací tabulka

Následující tabulka porovnává metodu Schulze s jinými přednostní metody voleb pro jednoho vítěze:

Hlavní rozdíl mezi Schulzeho metodou a metodou hodnocené páry metodu lze vidět v tomto příkladu:

Předpokládejme MinMax skóre sady X kandidátů je síla nejsilnější párové výhry kandidáta A ∉ X proti kandidátovi B ∈ X. Metoda Schulze, ale nikoli hodnocené páry, pak zaručuje, že vítěz je vždy kandidátem sady s minimálním skóre MinMax.^[1]:§4.8 V určitém smyslu tedy Schulzeova metoda minimalizuje největší většinu, kterou je třeba při určování vítěze zvrátit.

Na druhou stranu Ranked Pairs minimalizuje největší většinu, která musí být obrácena k určení pořadí cíle, ve smyslu minlexmax.^[5] Jinými slovy, když hodnocené páry a metoda Schulze vytvářejí různé pořadí dokončení, pro většiny, s nimiž tyto dva řády cíle nesouhlasí, pořadí Schulze obrátí větší většinu než pořadí hodnocených párů.

Dějiny

Schulzeho metodu vyvinul Markus Schulze v roce 1997. Poprvé byla diskutována ve veřejných e-mailových konferencích v letech 1997–1998^[6] a v roce 2000.^[7] Následně byli zahrnuti uživatelé metody Schulze Debian (2003),^[8] Gentoo (2005),^[9] Topcoder (2005),^[10] Wikimedia (2008),^[11] KDE (2008),^[12] the Pirátská strana Švédska (2009),^[13] a Pirátská strana Německa (2010).^[14] Ve francouzské Wikipedii byla Schulzeova metoda jednou ze dvou metod s více kandidáty schválených většinou v roce 2005,^[15] a bylo několikrát použito.^[16] Nově vytvořený Boise, Idaho kapitola Demokratičtí socialisté v Americe v únoru zvolila tuto metodu pro své první zvláštní volby konané v březnu 2018.^[17]

V roce 2011 Schulze tuto metodu publikoval v akademickém časopise Sociální volba a sociální péče.^[1]

Uživatelé

vzorek hlasovacího lístku pro Správní rada Wikimedia volby

Město Schulze používá metodu Schulze Silla za všechna referenda. To je používáno Institute of Electrical and Electronics Engineers tím, že Sdružení pro výpočetní techniku, a tím USENIX prostřednictvím používání rozhodovacího nástroje HotCRP. Města Schulze používají metodu Schulze Turín a San Donà di Piave a podle Londýnská čtvrť Southwarku prostřednictvím jejich používání platformy WeGovNow, která zase používá LiquidFeedback rozhodovací nástroj. Mezi organizace, které v současné době používají Schulzeho metodu, patří:

Poznámky

externí odkazy

• Schulzeho metoda hlasování Markus Schulze
• Výpočty Condorcet Johannes Grabmeier
• Spieltheorie (v němčině) podle Bernhard Nebel
• Přesná demokracie Rob Loring
• Christoph Börgers (2009), Matematika sociální volby: hlasování, odškodnění a rozdělení, SIAM, ISBN  0-89871-695-0
• Nicolaus Tideman (2006), Kolektivní rozhodnutí a hlasování: Potenciál pro veřejnou volbu Burlington: Ashgate, ISBN  0-7546-4717-X
• preftools skupinou Public Software Group
• Arizonans pro Condorcet hodnocené hlasování
• Condorcet PHP Aplikace příkazového řádku a PHP knihovna, podporující více metod Condorcet, včetně Schulze.
• Implementace v Javě
• Implementace v Ruby
• Implementace v Pythonu 2
• Implementace v Pythonu 3