Metoda Schulze - Schulze method

Metoda Schulze ( / ʃ ʊ l t s ə / ) este un sistem electoral dezvoltat în 1997 de către Markus Schulze , care selectează un singur câștigător , folosind note care exprimă preferințe . Metoda poate fi utilizată și pentru a crea o listă sortată de câștigători. Metoda Schulze este , de asemenea , cunoscut sub numele de Schwartz Sequential cădere ( SSD ), cloneproof Schwartz cădere secvențială ( CSSD ), metoda beatpath , câștigător beatpath , vot cale și câștigător cale .

Metoda Schulze este o metodă Condorcet , ceea ce înseamnă că, dacă există un candidat care este preferat de o majoritate față de orice alt candidat în comparații perechi, atunci acest candidat va fi câștigătorul atunci când se aplică metoda Schulze.

Rezultatul metodei Schulze (definit mai jos) oferă o ordonare a candidaților. Prin urmare, dacă sunt disponibile mai multe posturi, metoda poate fi utilizată în acest scop fără modificări, permițând celor k candidați de top să câștige cele k locuri disponibile. Mai mult, pentru alegerile cu reprezentare proporțională , a fost propusă o singură variantă de vot transferabil .

Metoda Schulze este utilizată de mai multe organizații, inclusiv Wikimedia , Debian , Ubuntu , Gentoo , partidele politice ale partidului pirat și multe altele .

Descrierea metodei

Vot

Preferential ballot.svg

Contribuția pentru metoda Schulze este aceeași ca și pentru alte sisteme electorale clasate cu un singur câștigător: fiecare alegător trebuie să furnizeze o listă ordonată de preferințe pentru candidații unde sunt permise legături ( o ordine strict slabă ).

O modalitate tipică pentru alegători de a-și specifica preferințele în cadrul unui scrutin este următoarea. Fiecare scrutin listează toți candidații și fiecare alegător clasează această listă în ordinea preferințelor folosind cifre: alegătorul plasează un „1” lângă cel mai preferat (i) candidat (e), un „2” lângă al doilea cel mai preferat și așa mai departe . Fiecare alegător poate opțional:

  • acordați aceeași preferință mai multor candidați. Acest lucru indică faptul că acest alegător este indiferent între acești candidați.
  • folosiți numere non-consecutive pentru a exprima preferințele. Acest lucru nu are niciun impact asupra rezultatului alegerilor, deoarece contează doar ordinea în care candidații sunt clasați în funcție de alegători și nu numărul absolut al preferințelor.
  • mențineți candidații nereclasați. Atunci când un alegător nu clasează toți candidații, atunci acest lucru este interpretat ca și cum acest alegător (i) preferă cu strictețe pe toți candidații neclasați și (ii) este indiferent între toți candidații nereclasați.

Calcul

Să fie numărul de alegători care preferă candidatul în locul candidatului .

O cale de la candidat la candidat este o secvență de candidați cu următoarele proprietăți:

  1. și .
  2. Pentru toți .

Cu alte cuvinte, într-o comparație în perechi, fiecare candidat din cale îl va învinge pe următorul candidat.

Puterea unei căi de la candidat la candidat este cel mai mic număr de alegători din secvența de comparații:

Pentru toți .

Pentru o pereche de candidați și care sunt conectați prin cel puțin o cale, forța celei mai puternice căi este puterea maximă a căii (căilor) care le conectează. Dacă nu există deloc o cale de la candidat la candidat , atunci .

Candidatul este mai bun decât candidatul dacă și numai dacă .

Candidatul este un potențial câștigător dacă și numai dacă pentru fiecare alt candidat .

Se poate dovedi că și împreună implică . Prin urmare, este garantat (1) că definiția de mai sus de „ mai bine “ definește într - adevăr o relație tranzitivă și (2) că există întotdeauna cel puțin un candidat cu pentru fiecare alt candidat .

Exemplu

În exemplul următor 45 de alegători clasează 5 candidați.

Preferințele perechi trebuie calculate mai întâi. De exemplu, atunci când se compară A și B Pairwise, există 5 + 5 + 3 + 7 = 20 alegători care preferă A la B și 8 + 2 + 7 + 8 = 25 alegători care preferă B la A . Deci și . Setul complet de preferințe perechi este:

Grafic direcționat etichetat cu preferințe pereche d [*, *]
Matrice de preferințe pereche
20 26 30 22
25 16 33 18
19 29 17 24
15 12 28 14
23 27 21 31

Celulele pentru d [X, Y] au un fundal verde deschis dacă d [X, Y]> d [Y, X], altfel fundalul este roșu deschis. Nu există niciun câștigător de necontestat, uitându-se doar la diferențele perechi de aici.

Acum trebuie identificate cele mai puternice căi. Pentru a ajuta la vizualizarea celor mai puternice căi, setul de preferințe perechi este descris în diagrama din dreapta sub forma unui grafic direcționat . O săgeată de la nod care reprezintă un candidat X la cel care reprezintă un candidat Y este etichetată cu d [X, Y]. Pentru a evita aglomerația diagramei, o săgeată a fost trasă numai de la X la Y când d [X, Y]> d [Y, X] (adică celulele de masă cu fundal verde deschis), omițând pe cea din direcția opusă ( celule de masă cu fundal roșu deschis).

Un exemplu de calcul a puterii celei mai puternice a căii este p [B, D] = 33: cea mai puternică cale de la B la D este calea directă (B, D) care are puterea 33. Dar când se calculează p [A, C], mai puternic cale de la a la C , nu este calea directă (a, C) de putere 26, mai degrabă cea mai puternică calea este calea indirectă (a, D, C) , care are o putere min (30, 28) = 28. Concentrația de o cale este forța celei mai slabe verigi a acesteia.

Pentru fiecare pereche de candidați X și Y, tabelul următor arată cea mai puternică cale de la candidatul X la candidatul Y în roșu, cu cea mai slabă legătură subliniată .

Cele mai puternice căi
La
Din
A B C D E
A N / A
Schulze method example1 AB.svg
A- (30) -D- (28) -C- (29) -B
Schulze method example1 AC.svg
A- (30) -D- (28) -C
Schulze method example1 AD.svg
A- (30) -D
Schulze method example1 AE.svg
A- (30) -D- (28) -C- (24) -E
A
B
Schulze method example1 BA.svg
B- (25) -A
N / A
Schulze method example1 BC.svg
B- (33) -D- (28) -C
Schulze method example1 BD.svg
B- (33) -D
Schulze method example1 BE.svg
B- (33) -D- (28) -C- (24) -E
B
C
Schulze method example1 CA.svg
C- (29) -B- (25) -A
Schulze method example1 CB.svg
C- (29) -B
N / A
Schulze method example1 CD.svg
C- (29) -B- (33) -D
Schulze method example1 CE.svg
C- (24) -E
C
D
Schulze method example1 DA.svg
D- (28) -C- (29) -B- (25) -A
Schulze method example1 DB.svg
D- (28) -C- (29) -B
Schulze method example1 DC.svg
D- (28) -C
N / A
Schulze method example1 DE.svg
D- (28) -C- (24) -E
D
E
Schulze method example1 EA.svg
E- (31) -D- (28) -C- (29) -B- (25) -A
Schulze method example1 EB.svg
E- (31) -D- (28) -C- (29) -B
Schulze method example1 EC.svg
E- (31) -D- (28) -C
Schulze method example1 ED.svg
E- (31) -D
N / A E
A B C D E
Din
La
Punctele tari ale celor mai puternice căi
28 28 30 24
25 28 33 24
25 29 29 24
25 28 28 24
25 28 28 31

Acum rezultatul metodei Schulze poate fi determinat. De exemplu, atunci când se compară A și B , din moment ce , pentru metoda de candidat Schulze A este mai bună decât candidat B . Un alt exemplu este că , deci candidatul E este mai bun decât candidatul D. Continuând în acest fel, rezultatul este că clasamentul Schulze este și E câștigă. Cu alte cuvinte, E câștigă pentru că pentru fiecare alt candidat X.

Implementare

Singurul pas dificil în implementarea metodei Schulze este calcularea celor mai puternice puncte forte. Cu toate acestea, aceasta este o problemă binecunoscută în teoria graficelor numită uneori cea mai largă problemă de cale . O modalitate simplă de a calcula punctele forte, prin urmare, este o variantă a algoritmului Floyd – Warshall . Următorul pseudocod ilustrează algoritmul.

# Input: d[i,j], the number of voters who prefer candidate i to candidate j.
# Output: p[i,j], the strength of the strongest path from candidate i to candidate 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]))

Acest algoritm este eficient și are timp de funcționare O ( C 3 ) unde C este numărul de candidați.

Legături și implementări alternative

Atunci când le permiteți utilizatorilor să aibă legături în preferințele lor, rezultatul metodei Schulze depinde în mod natural de modul în care aceste legături sunt interpretate în definirea d [*, *]. Două alegeri naturale sunt că d [A, B] reprezintă fie numărul alegătorilor care preferă strict A în fața lui B (A> B), fie marja (votanții cu A> B) minus (alegătorii cu B> A). Dar, indiferent de modul în care sunt definite d- urile, clasamentul Schulze nu are cicluri și, presupunând că d-urile sunt unice, nu are legături.

Deși legăturile în clasamentul Schulze sunt puțin probabil, ele sunt posibile. Lucrarea originală a lui Schulze propunea ruperea legăturilor în conformitate cu un alegător ales la întâmplare și repetarea la nevoie.

O modalitate alternativă de a descrie câștigătorul metodei Schulze este următoarea procedură:

  1. desenați un grafic complet direcționat cu toți candidații și toate marginile posibile între candidați
  2. iterativ [a] ștergeți toți candidații care nu fac parte din setul Schwartz (adică orice candidat x care nu poate ajunge la toți ceilalți care ajung la x ) și [b] ștergeți marginea graficului cu cea mai mică valoare (dacă este prin margini, cea mai mică marjă; dacă prin voturi, cele mai puține voturi).
  3. câștigătorul este ultimul candidat care nu a fost șters.

Există o altă modalitate alternativă de a demonstra câștigătorul metodei Schulze. Această metodă este echivalentă cu celelalte descrise aici, dar prezentarea este optimizată pentru semnificația faptului că pașii sunt vizibili pe măsură ce un om trece prin ea, nu pentru calcul.

  1. Faceți tabelul de rezultate, numit „matricea preferințelor perechi”, așa cum este folosit mai sus în exemplu. Dacă utilizați marje mai degrabă decât totaluri de vot brute, scădeți-le din transpunere. Apoi, fiecare număr pozitiv este o victorie pereche pentru candidatul din acel rând (și marcat cu verde), egalitățile sunt zero, iar pierderile sunt negative (marcate cu roșu). Ordonează candidații în funcție de durata lor de eliminare.
  2. Dacă există un candidat fără roșu pe linia lor, acesta câștigă.
  3. În caz contrar, desenați o cutie pătrată în jurul setului Schwartz din colțul din stânga sus. Poate fi descris ca „cercul câștigătorului” minim al candidaților care nu pierd în fața nimănui din afara cercului. Rețineți că în partea dreaptă a casetei nu există roșu, ceea ce înseamnă că este cercul câștigătorului și rețineți că în cadrul casetei nu este posibilă o reordonare care ar produce un cerc câștigător mai mic.
  4. Tăiați fiecare parte a mesei în afara cutiei.
  5. Dacă încă nu există niciun candidat fără roșu pe linia lor, trebuie să fie compromis ceva; fiecare candidat a pierdut o cursă, iar pierderea pe care o tolerăm cel mai bine este cea în care cel care a pierdut a obținut cele mai multe voturi. Deci, luați celula roșie cu cel mai mare număr (dacă mergeți după margini, cel mai puțin negativ), faceți-o verde - sau orice altă culoare decât roșu - și reveniți la pasul 2.

Iată un tabel de margini realizat din exemplul de mai sus. Rețineți schimbarea ordinii utilizate în scopuri demonstrative.

Tabelul de rezultate inițiale
E A C B D
E 1 -3 9 17
A -1 7 -5 15
C 3 -7 13 -11
B -9 5 -13 21
D -17 -15 11 -21

Prima scădere (pierderea lui A la E cu 1 vot) nu ajută la micșorarea setului Schwartz.

Prima picătură
E A C B D
E 1 -3 9 17
A -1 7 -5 15
C 3 -7 13 -11
B -9 5 -13 21
D -17 -15 11 -21

Așa că ajungem direct la a doua scădere (pierderea lui E la C cu 3 voturi), iar asta ne arată câștigătorul, E, cu rândul său clar.

A doua picătură, finală
E A C B D
E 1 -3 9 17
A -1 7 -5 15
C 3 -7 13 -11
B -9 5 -13 21
D -17 -15 11 -21

Această metodă poate fi, de asemenea, utilizată pentru a calcula un rezultat, dacă tabelul este refăcut în așa fel încât să se poată rearanja în mod convenabil și sigur ordinea candidaților atât pe rând, cât și pe coloană, cu aceeași ordine folosită pe ambele în orice moment .

Criterii satisfăcute și nereușite

Criterii satisfăcute

Metoda Schulze îndeplinește următoarele criterii:

Criterii nereușite

Deoarece metoda Schulze îndeplinește criteriul Condorcet, nu reușește automat următoarele criterii:

La fel, deoarece metoda Schulze nu este o dictatură și este de acord cu voturile unanime, teorema lui Arrow implică că nu reușește criteriul

De asemenea, metoda Schulze eșuează

Tabel comparativ

Tabelul următor compară metoda Schulze cu alte metode preferențiale de alegere cu un singur câștigător:

Compararea sistemelor electorale preferențiale
Sistem Monoton Condorcet Majoritate Pierderea Condorcet Pierderea majorității Majoritate reciprocă Smith ISDA LIIA Independența clonelor Simetrie inversă Participare , consecvență Mai târziu, fără rău Mai târziu, fără ajutor Timp polinomial Rezolvabilitatea
Schulze da da da da da da da da Nu da da Nu Nu Nu da da
Perechi clasate da da da da da da da da da da da Nu Nu Nu da da
Ciclul divizat da da da da da da da da Nu da da Nu Nu Nu da Nu
Alternativa lui Tideman Nu da da da da da da da Nu da Nu Nu Nu Nu da da
Kemeny – Young da da da da da da da da da Nu da Nu Nu Nu Nu da
Copeland da da da da da da da da Nu Nu da Nu Nu Nu da Nu
Nanson Nu da da da da da da Nu Nu Nu da Nu Nu Nu da da
Negru da da da da da Nu Nu Nu Nu Nu da Nu Nu Nu da da
Votare instantanee Nu Nu da da da da Nu Nu Nu da Nu Nu da da da da
Smith / IRV Nu da da da da da da da Nu da Nu Nu Nu Nu da da
Borda da Nu Nu da da Nu Nu Nu Nu Nu da da Nu da da da
Geller-IRV Nu Nu da da da da Nu Nu Nu Nu Nu Nu Nu Nu da da
Baldwin Nu da da da da da da Nu Nu Nu Nu Nu Nu Nu da da
Bucklin da Nu da Nu da da Nu Nu Nu Nu Nu Nu Nu da da da
Multitudine da Nu da Nu Nu Nu Nu Nu Nu Nu Nu da da da da da
Votare contingentă Nu Nu da da da Nu Nu Nu Nu Nu Nu Nu da da da da
Coombs Nu Nu da da da da Nu Nu Nu Nu Nu Nu Nu Nu da da
MiniMax da da da Nu Nu Nu Nu Nu Nu Nu Nu Nu Nu Nu da da
Anti-pluralitate da Nu Nu Nu da Nu Nu Nu Nu Nu Nu da Nu Nu da da
Votarea contingentului din Sri Lanka Nu Nu da Nu Nu Nu Nu Nu Nu Nu Nu Nu da da da da
Vot suplimentar Nu Nu da Nu Nu Nu Nu Nu Nu Nu Nu Nu da da da da
Dodgson Nu da da Nu Nu Nu Nu Nu Nu Nu Nu Nu Nu Nu Nu da

Principala diferență între metoda Schulze și metoda perechilor clasate poate fi văzută în acest exemplu:

Să presupunem că scorul Minmax unui set X de candidați este puterea de cel mai puternic câștig al unui candidat Pairwise A ∉ X împotriva unui candidat B ∈ X . Apoi metoda Schulze, dar nu Perechile clasate, garantează că câștigătorul este întotdeauna un candidat al setului cu scorul minim MinMax. Deci, într-un anumit sens, metoda Schulze minimizează cea mai mare majoritate care trebuie inversată atunci când se determină câștigătorul.

Pe de altă parte, Perechile clasate minimizează cea mai mare majoritate care trebuie inversată pentru a determina ordinea de finisare, în sensul minlexmax. Cu alte cuvinte, atunci când Perechile clasate și metoda Schulze produc ordine diferite de finisare, pentru majoritățile în care cele două ordine de finisare nu sunt de acord, ordinea Schulze inversează o majoritate mai mare decât ordinea Perechilor clasate.

Istorie

Metoda Schulze a fost dezvoltată de Markus Schulze în 1997. A fost discutată pentru prima dată în listele de discuții publice în 1997-1998 și în 2000. Ulterior, utilizatorii metodei Schulze au inclus Debian (2003), Gentoo (2005), Topcoder (2005), Wikimedia ( 2008), KDE (2008), Partidul Piraților din Suedia (2009) și Partidul Piraților din Germania (2010). În Wikipedia franceză, metoda Schulze a fost una dintre cele două metode cu mai mulți candidați aprobate cu majoritate în 2005 și a fost folosită de mai multe ori. Nou formatul capitol Boise, Idaho, al socialiștilor democrați din America, în februarie, a ales această metodă pentru primele lor alegeri speciale organizate în martie 2018.

În 2011, Schulze a publicat metoda în revista academică Social Choice and Welfare .

Utilizatori

eșantion de vot pentru alegerile Consiliului de administrație al Wikimedia

Metoda Schulze este utilizată de orașul Silla pentru toate referendumurile. Acesta este utilizat de Institutul de ingineri electrici și electronici , de Asociația pentru mașini de calcul și de USENIX prin utilizarea instrumentului de decizie HotCRP. Metoda Schulze este utilizată de orașele Torino și San Donà di Piave și de London Borough of Southwark prin utilizarea platformei WeGovNow, care la rândul său folosește instrumentul de decizie LiquidFeedback . Organizațiile care utilizează în prezent metoda Schulze includ:

Note

linkuri externe