Schulze-módszer

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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:

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]

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

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]

Fájl:Commons-logo.svg
A Wikimédia Commons tartalmaz Schulze-módszer témájú médiaállományokat.