Schulze-módszer

egy hely betöltésére kiírt szavazási rendszer

A Schulze-módszer 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

Teljesülő tulajdonságok szerkesztés

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

Nem teljesülő tulajdonságok szerkesztés

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

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

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

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

Első példa szerkesztés

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:

 

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 ...
 
A-(14)-C-(15)-B
 
A-(14)-C
 
A-(14)-C-(12)-D
B-ből ...
 
B-(13)-A
 
B-(13)-A-(14)-C
 
B-(13)-A-(14)-C-(12)-D
C-ből ...
 
C-(15)-B-(13)-A
 
C-(15)-B
 
C-(12)-D
D-ből ...
 
D-(19)-B-(13)-A
 
D-(19)-B
 
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

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

  • 5  
  • 5  
  • 8  
  • 3  
  • 7  
  • 2  
  • 7  
  • 8  

Először a páronkénti preferenciákat számítják ki. Például   és   közül   részesítette előnyben  -t, és    -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 ...
 
A-(30)-D-(28)-C-(29)-B
 
A-(30)-D-(28)-C
 
A-(30)-D
 
A-(30)-D-(28)-C-(24)-E
A-ból ...
B-ből ...
 
B-(25)-A
 
B-(33)-D-(28)-C
 
B-(33)-D
 
B-(33)-D-(28)-C-(24)-E
B-ből ...
C-ből ...
 
C-(29)-B-(25)-A
 
C-(29)-B
 
C-(29)-B-(33)-D
 
C-(24)-E
C-ből ...
D-ből ...
 
D-(28)-C-(29)-B-(25)-A
 
D-(28)-C-(29)-B
 
D-(28)-C
 
D-(28)-C-(24)-E
D-ből ...
E-ből ...
 
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-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

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  -t, és csökkentik  -t. Jelöljön E a következőkben egy tetszőleges jelöltet a többi közül! Ekkor   és   nő, és   vagy   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

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:

# Input: d[i,j], hány szavazó részesíti előnyben i-t j-vel szemben.
# Output: p[i,j], a legerősebb ij út ereje.

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

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

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

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]

Jegyzetek szerkesztés

  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 Archiválva 2013. január 4-i dátummal az Archive.is-en, 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. * Markus Schulze, Condorect sub-cycle rule, October 1997 (In this message, the Schulze method is mistakenly believed to be identical to the ranked pairs method.)
  6. Process for adding new board members, January 2003
  7. See:
  8. * 2006 TopCoder Open Logo Design Contest, November 2005
  9. See:
  10. section 3.4.1 of the Rules of Procedures for Online Voting
  11. See:
  12. See:
  13. * http://wiki.piratenpartei.de/BE:Neuk%C3%B6lln/Gebietsversammlungen/2010.3/Protokoll
  14. Choix dans les votes
  15. fr:Spécial:Pages liées/Méthode Schulze

További információk szerkesztés

A Wikimédia Commons tartalmaz Schulze-módszer témájú médiaállományokat.