Metoda Schulze - Schulze method
Parte a seriei Politics |
Sisteme electorale |
---|
Portalul politicii |
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
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:
- și .
- 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:
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ă .
La
Din
|
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 |
Din
La
|
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ă:
- desenați un grafic complet direcționat cu toți candidații și toate marginile posibile între candidați
- 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).
- 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.
- 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.
- Dacă există un candidat fără roșu pe linia lor, acesta câștigă.
- Î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.
- Tăiați fiecare parte a mesei în afara cutiei.
- 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.
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.
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.
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:
- Domeniu nelimitat
- Neimpoziție ( aka suveranitate cetățeană )
- Nedictatura
- Criteriul Pareto
- Criteriul monotoniei
- Criteriul majorității
- Criteriul pierderii majorității
- Criteriul Condorcet
- Criteriul pierderii Condorcet
- Criteriul Schwartz
- Criteriul Smith
- Independența alternativelor dominate de Smith
- Criteriul majorității reciproce
- Independența clonelor
- Simetrie inversă
- Mono-anexă
- Mono-add-plump
- Criteriul de rezolvabilitate
- Timp de rulare polinomial
- prudenţă
- Seturi MinMax
- Criteriul pluralității lui Woodall dacă voturile câștigătoare sunt folosite pentru d [X, Y]
- Completare simetrică dacă se utilizează marje pentru d [X, Y]
Criterii nereușite
Deoarece metoda Schulze îndeplinește criteriul Condorcet, nu reușește automat următoarele criterii:
- Participare
- Coerență
- Invulnerabilitatea la compromisuri
- Invulnerabilitatea la îngropare
- Mai târziu, fără rău
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ă
- Criteriul lui Peyton Young Independența locală a alternativelor irelevante .
Tabel comparativ
Tabelul următor compară metoda Schulze cu alte metode preferențiale de alegere cu un singur câștigător:
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
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:
- AEGEE - Forumul European al Studenților
- Asociația Annodex
- Guvern studențesc asociat la Universitatea Northwestern
- Guvern studențesc asociat la Universitatea din Freiburg
- Guvern studențesc asociat la Departamentul de științe informatice al Universității din Kaiserslautern
- Berufsverband der Kinder- und Jugendärzte (BVKJ)
- BoardGameGeek
- Club der Ehemaligen der Deutschen SchülerAkademien e. V.
- Agenția colectivă
- Highpointers județene
- Debian
- EuroBillTracker
- Comunitatea Europeană a Educației Democratice (EUDEC)
- FFmpeg
- Mișcarea Cinci Stele din Campobasso , Fondi , Monte Compatri , Montemurlo , Pescara și San Cesareo
- Societatea flamandă a studenților ingineri Leuven
- Geek gratuit
- Free Hardware Foundation din Italia
- Fundația Gentoo
- GlitzerKollektiv
- GNU Privacy Guard (GnuPG)
- Organizația studenților absolvenți la Universitatea de Stat din New York: Informatică (GSOCS)
- Haskell
- Casa Hillegass Parker
- Internet Corporation pentru nume și numere atribuite (ICANN)
- Generator Ithaca
- Kanawha Valley Scrabble Club
- KDE eV
- Sala Kingman
- Fundația Cavaler
- Kubuntu
- Kumoricon
- Liga administratorilor de sistem profesioniști (LOPSA)
- LiquidFeedback
- Madisonium
- Metalab
- Music Television (MTV)
- Neo
- Noi liberali
- Noisebridge
- OpenEmbedded
- OpenStack
- OpenSwitch
- Pirate Party Australia
- Partidul Piraților din Austria
- Partidul Piraților din Belgia
- Partidul Piraților din Brazilia
- Partidul Piraților din Germania
- Petrecerea Piraților din Islanda
- Partidul Piraților din Italia
- Partidul Piraților din Olanda
- Partidul Piraților din Noua Zeelandă
- Partidul Piraților din Suedia
- Partidul Piraților din Elveția
- Partidul Piraților din Statele Unite
- RLLMUK
- Chiţăit
- Studenți pentru cultura liberă
- Sugar Labs
- SustainableUnion
- Sverok
- TestPAC
- TopCoder
- Ubuntu
- Premiile Vidya Gaem
- Volt Europa
- Wikipedia în franceză , ebraică , maghiară , rusă și persană .
Note
linkuri externe
- Metoda de vot Schulze de Markus Schulze
- Calcule Condorcet de Johannes Grabmeier
- Spieltheorie (în germană) de Bernhard Nebel
- Accurate Democracy de Rob Loring
- Christoph Börgers (2009), Matematica alegerii sociale: vot, compensare și divizare , SIAM, ISBN 0-89871-695-0
- Nicolaus Tideman (2006), Decizii colective și vot: potențialul pentru alegerea publică , Burlington: Ashgate, ISBN 0-7546-4717-X
- pre-instrumente de la Public Software Group
- Arizonanii pentru Condorcet votul clasat
- Aplicația Condorcet PHP pentru linia de comandă și biblioteca PHP , care acceptă mai multe metode Condorcet, inclusiv Schulze.
- Implementare în Java
- Implementare în Ruby
- Implementare în Python 2
- Implementare în Python 3