Schulze-módszer

A Wikipédiából, a szabad enciklopédiából

A Schulze-módszer egy egy hely betöltésére kiírt szavazási rendszer. A módszer más neveken is ismert, mint Schwartz szekvenciális csöpögtetés (SSD), Cloneproof Schwartz szekvenciális csöpögtetés, és még számos más néven. Több szervezet is használja, például a Wikipédia, a Debian, a Gentoo fejlesztőközössége, a Svéd Kalózpárt és a Német Kalózpárt. Többségi, többségi vesztes, kölcsönös többségi, Condorcet, Condorcet vesztes, Smith tulajdonságú, monoton, klónfüggetlen, visszafejthető, és fordítottan szimmetrikus.

Tulajdonságai[szerkesztés | forrásszöveg szerkesztése]

Teljesülő tulajdonságok[szerkesztés | forrásszöveg szerkesztése]

A Schulze-módszer megfelel ezeknek a tulajdonságoknak:

Nem teljesülő tulajdonságok[szerkesztés | forrásszöveg szerkesztése]

Mivel a Schulze-módszer Condorcet tulajdonságú, ezért nem teljesíti a következőket:

A diktátormentesség miatt, és mert az egyöntetű szavazás esetén a végeredmény megegyezik az egyöntetű szavazatok eredményével, ezért Arrow tételéből következően

A Schulze-módszer nem teljesíti a

Első lépés[szerkesztés | forrásszöveg szerkesztése]

Minden szavazólap tartalmazza a jelöltek teljes listáját. A szavazók sorrendet állítansak fel a jelöltek között szimpátiájuk alapján. A legjobb kapja az 1-es, a második legjobb a 2-es számot, és így tovább.

A szavazónak lehetősége van:

  • több jelöltnek is ugyanazt a preferenciát adni
Nem állít fel sorrendet közöttük.
  • preferenciákat kihagyni
Ez nem befolyásolja a szavazás eredményét, mert csak a sorrend a fontos.
  • jelölteket kihagyni
A kihagyott jelöltekről felteszik, hogy a szavazó a többi jelölt mögé sorolja, és nem állít fel közöttük sorrendet.

Második lépés[szerkesztés | forrásszöveg szerkesztése]

Minden jelöltpárra kiszámítják, hogy hányan helyezik az egyiket szigorúan a másik elé. Ha V és W jelöltek, akkor rájuk ez a szám d[V,W].

Harmadik lépés[szerkesztés | forrásszöveg szerkesztése]

Definíciók:

Ha X és Y jelöltek, akkor egy z erősségű X-től Y-ig vezető út jelöltek egy C(1),...,C(n) sorozata, ahol:

  • C(1) megegyezikX-szel
  • C(n) megegyezik Y-nal
  • d[C(i),C(i+1)] > d[C(i+1),C(i)] minden i = 1,...,(n-1)-re
  • [C(i),C(i+1)] ≥ z minden i = 1,...,(n-1)-re.

p[A,B] a legerősebb A-ból B-be vezető út ereje.

Ha nincs az A és a B jelöltek között út, akkor p[A,B] : = 0.

A D jelölt jobb, mint E, ha p[D,E] > p[E,D].

D Schulze-győztes, ha p[D,E] ≥ p[E,D] minden más E-be helyettesíthető jelöltre.

Belátható, hogy a jobb tulajdonság tranzitív, ezért biztosan van győztes.

Példák[szerkesztés | forrásszöveg szerkesztése]

Első példa[szerkesztés | forrásszöveg szerkesztése]

21 szavazó, 4 jelölt:

8 ACDB
2 BADC
4 CDBA
4 DBAC
3 DCBA
d[*,A] d[*,B] d[*,C] d[*,D]
d[A,*] 8 14 10
d[B,*] 13 6 2
d[C,*] 7 15 12
d[D,*] 11 19 9
A páronkénti legyőzte mátrix a következő:

A páronkénti legyőzte gráf:

Schulze method example7.svg

Egy út ereje a leggyengébb láncszemének erejével egyezik meg. Az alábbi táblázat minden jelöltpárra megadja a legerősebb utat. A leggyengébb láncszemek aláhúzással vannak megjelölve.

... A-ba ... B-be ... C-be ... D-be
A-ból ...
Schulze method example7 AB.svg
A-(14)-C-(15)-B
Schulze method example7 AC.svg
A-(14)-C
Schulze method example7 AD.svg
A-(14)-C-(12)-D
B-ből ...
Schulze method example7 BA.svg
B-(13)-A
Schulze method example7 BC.svg
B-(13)-A-(14)-C
Schulze method example7 BD.svg
B-(13)-A-(14)-C-(12)-D
C-ből ...
Schulze method example7 CA.svg
C-(15)-B-(13)-A
Schulze method example7 CB.svg
C-(15)-B
Schulze method example7 CD.svg
C-(12)-D
D-ből ...
Schulze method example7 DA.svg
D-(19)-B-(13)-A
Schulze method example7 DB.svg
D-(19)-B
Schulze method example7 DC.svg
D-(19)-B-(13)-A-(14)-C
A legerősebb utak:
p[*,A] p[*,B] p[*,C] p[*,D]
p[A,*] 14 14 12
p[B,*] 13 13 12
p[C,*] 13 15 12
p[D,*] 13 19 13
A legerősebb utak ereje:


A D jelölt Schulze-győztes, mert p[D,X] ≥ p[X,D] minden más X jelöltre.

  • 14 = p[A,B] > p[B,A] = 13, az A jelölt jobb, mint a B jelölt.
  • 14 = p[A,C] > p[C,A] = 13, az A jelölt jobb, mint a C jelölt.
  • 15 = p[C,B] > p[B,C] = 13, a C jelölt jobb, mint a B jelölt.
  • 13 = p[D,A] > p[A,D] = 12, a D jelölt jobb, mint az A jelölt.
  • 19 = p[D,B] > p[B,D] = 12, a D jelölt jobb, mint a B jelölt.
  • 13 = p[D,C] > p[C,D] = 12, a D jelölt jobb, mint a C jelölt.

Ezért a Schulze-rangsor is D > A > C > B.

Második példa[szerkesztés | forrásszöveg szerkesztése]

45 szavazó dönt 5 jelöltről:

  • 5 ACBED
  • 5 ADECB
  • 8 BEDAC
  • 3 CABED
  • 7 CAEBD
  • 2 CBADE
  • 7 DCEBA
  • 8 EBADC

Először a páronkénti preferenciákat számítják ki. Például A és B közül 5+5+3+7=20 részesítette előnyben A-t, és 8+2+7+8=25 B-t.

Irányított gráf a d[*, *] preferenciákkal címkézve
A páronkénti preferenciák mátrixa
d[*,A] d[*,B] d[*,C] d[*,D] d[*,E]
d[A,*] 20 26 30 22
d[B,*] 25 16 33 18
d[C,*] 19 29 17 24
d[D,*] 15 12 28 14
d[E,*] 23 27 21 31

A d[X, Y] értékek közül világoszöldek a győztesek, vagyis azok, amelyekre d[X, Y] > d[Y, X], a többiek háttere rózsaszín. A végső győztes még nem látszik a páronkénti adatok alapján.

A második lépésben meghatározzuk a legerősebb utakat. A gráf csak azokat az éleket tartalmazza, amelyekre d[X, Y] > d[Y, X], vagyis a győztes éleket. Az ellenkező irányú és előjelű vesztes éleket mellőztük.

Például a B és D közötti legerősebb út ereje p[B, D] = 33, mivel a kettő közötti él a legerősebb út, és ereje 33. De A és C esetén már nem a közvetlen él a legerősebb, hiszen (A, D, C) ereje 28 szemben az AC él 26-ával szemben. Az út ereje megegyezik leggyengébb élének erejével.

A következő táblázat tartalmazza az összes jelöltpárra a legerősebb utat, aláhúzással jelölve a leggyengébb éleket:

A legerősebb utak
... A-ba ... B-be ... C-be ... D-be ... E-be
A-ból ...
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ól ...
B-ből ...
Schulze method example1 BA.svg
B-(25)-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-ből ...
C-ből ...
Schulze method example1 CA.svg
C-(29)-B-(25)-A
Schulze method example1 CB.svg
C-(29)-B
Schulze method example1 CD.svg
C-(29)-B-(33)-D
Schulze method example1 CE.svg
C-(24)-E
C-ből ...
D-ből ...
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
Schulze method example1 DE.svg
D-(28)-C-(24)-E
D-ből ...
E-ből ...
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
E-ből ...
... A-ba ... B-be ... C-be ... D-be ... E-be
A legerősebb utak ereje
p[*,A] p[*,B] p[*,C] p[*,D] p[*,E]
p[A,*] 28 28 30 24
p[B,*] 25 28 33 24
p[C,*] 25 29 29 24
p[D,*] 25 28 28 24
p[E,*] 25 28 28 31

Most már megadható a végeredmény is. Például összehasonlítva A-t és B-t A jobb, mint B, mert 28 = p[A,B] > p[B,A] = 25. E jobb, mint D, mivel 31 = p[E,D] > p[D,E] = 24. Tovább folytatva E > A > C > B > D a végső erősorrend, és a győztes E. Más szavakkal, p[E,X] ≥ p[X,E] minden más X jelöltre.

Manipulálás[szerkesztés | forrásszöveg szerkesztése]

A szavazás manipulálásának egy módja az esélyesek szétválasztása.[3] Ha a jelöltek között két esélyes van, P és Q, akkor a P-t választók hajlamosak arra, hopgy P-t helyezzék az élre, és Q-t a lista végére. Ezzel az őszinte választáshoz képest megnövelik p[P,Q]-t, és csökkentik p[Q,P]-t. Jelöljön E a következőkben egy tetszőleges jelöltet a többi közül! Ekkor p[P,E] és p[E,Q] nő, és p[E,P] vagy p[Q,E] csökken.

Ez a stratégia megnöveli az így szavazók szavazatának súlyát az őszinte szavazókkal szemben; növeli P esélyét, és csökkenti Q esélyét. Ha a két jelölt támogatottsága nagyjából megegyezik, és mindkét jelölt támogatói ezt a módszert használják, akkor a hatások nagyjából kiegyenlítik egymást.

Mivel a szavazók átrendezik szavazataikat, ezért a végső sorrend nem az őszinte véleményt fogja tükrözni. Ha a végén lesz Condorcet-győztes, akkor semmi sem garantálja azt, hogy ez a jelölt minden más jelöltet legyőzne, ha csak kettejük közül lehetne választani, mivel a páronkénti rangok nem az őszinte véleményt tükrözik.

Ha nem két, hanem több esélyes jelölt van, akkor a manipuláció egy módosított változata továbbra is működik. Itt egy jelöltet sorolnak az élre, és a többi esélyest a sor legvégére. Ez erősíti a szavazat súlyát, de azt eredményezi, hogy egy máskülönben teljesen esélytelen jelölt nyer, akit mindenki a sor végére tenne, ha őszintén szavazna.[4] Ez minden, a Condorcet-módszeren alapuló szavazási rendszert érint. Ez a manipuláció felveti a fogolydilemmát.

Implementáció[szerkesztés | forrásszöveg szerkesztése]

A Schulze-módszer implementálásakor csak a legerősebb út erejének kiszámítása a nehéz. Ez egy jól ismert gráfelméleti probléma, mégpedig a legszélesebb út problémája. Ez megoldható a Floyd–Warshall-algoritmus egy változatával, aminek pszeudokódja:

  1. # Input: d[i,j], hány szavazó részesíti előnyben i-t j-vel szemben.
    
  2. # Output: p[i,j], a legerősebb ij út ereje.
    
  3.  
    
  4. for i from 1 to C
    
  5.    for j from 1 to C
    
  6.       if (i ≠ j) then
    
  7.          if (d[i,j] > d[j,i]) then
    
  8.             p[i,j] := d[i,j]
    
  9.          else
    
  10.             p[i,j] := 0
    
  11.  
    
  12. for i from 1 to C
    
  13.    for j from 1 to C
    
  14.       if (i ≠ j) then
    
  15.          for k from 1 to C
    
  16.             if (i ≠ k and j ≠ k) then
    
  17.                p[j,k] := max ( p[j,k], min ( p[j,i], p[i,k] ) )
    

Az algoritmus bonyolultsága C3 , ahol C a jelöltek száma. Ez nem foglalja magába a d[*,*] értékek kiszámítását, amit naivan implementálva a bonyolultság C2 szorozva a szavazók számával.

Holtversenyek és alternatív implementációk[szerkesztés | forrásszöveg szerkesztése]

Ha a szavazók több jelöltnek is adhatják ugyanazt a preferenciát, akkor a végeredmény függhet d[*,*] definíciójától. A két természetes választás előírhat szigorú vagy gyenge preferenciát. Mindazonáltal mindkét esetben a Schulze-rangsorban nem lesznek körök, és ha a d[*,*] számok mind különböznek, akkor holtverseny sem lehet, a sorrend és a győztes egyértelmű.[1]

Habár nem szeretik, hogy több jelöltnek ugyanaz lehet a preferenciája (mivel rendszerint jóval több a szavazó, mint a jelölt), mégis lehetséges ilyen kimenetel. Schulze cikkében azt javasolta, hogy egy véletlenül választott elektor törje meg ezt az egyöntetűséget, és ezt ismételjük, amíg kell.[1]

A módszer több nevét egy alternatív implementáció után kapta:

  1. Rajzoljunk fel egy teljes irányított gráfot az összes jelölttel
  2. Alkalmazzuk felváltva a következő két lépést:
  • Töröljük azokat a jelölteket, amelyekből nem érhető el az összes többi
  • Töröljük el a leggyengébb élt
  1. Az utoljára maradt jelölt a győztes.

Ez az implementáció azonban lassabb.

Története[szerkesztés | forrásszöveg szerkesztése]

Markus Schulze 1997-ben dolgozta ki a módszert. Nyilvános levelezőlistákon vitatták meg 1997–1998-ban[5] és 2000-ben.[6] Ezután sok közösségben bevezették, például a Software in the Public Interest (2003),[7] Debian (2003),[8] Gentoo (2005),[9] TopCoder (2005)[10] Wikimedia (2008),[11] KDE (2008),[12] the Free Software Foundation Europe (2008),[13] a Svéd Kalózpárt (2009),[14] és a Német Kalózpárt (2010).[15] A francia Wikipédiában a két több jelöltes módszer egyikeként már 2005-ben bevezették,[16] és többször használták.[17]

2011-ben Schulze publikálta módszerét a Social Choice and Welfare. szaklapban.[1]

Források[szerkesztés | forrásszöveg szerkesztése]

  1. ^ a b c d e f g h i j k l m n Markus Schulze, A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method, Social Choice and Welfare, volume 36, number 2, page 267–303, 2011. Preliminary version in Voting Matters, 17:9-19, 2003.
  2. ^ a b c Douglas R. Woodall, Properties of Preferential Election Rules, Voting Matters, issue 3, pages 8-15, December 1994
  3. http://rangevoting.org/IncentToExagg.html
  4. http://scorevoting.net/DH3.html
  5. Process for adding new board members, January 2003
  6. See:
  7. See:
  8. section 3.4.1 of the Rules of Procedures for Online Voting
  9. See:
  10. See:
  11. Choix dans les votes
  12. fr:Spécial:Pages liées/Méthode Schulze
Commons
A Wikimédia Commons tartalmaz Schulze-módszer témájú médiaállományokat.