Schulze-módszer

Választási rendszerek
Többségi rendszerek
Relatív többségi szabály Relatív többségi szavazás, blokkszavazás, pártlistás blokkszavazás Többfordulós Kétfordulós szavazás Egyenkénti kieséses szavazás Preferenciális Azonnali többfordulós szavazás (IRV), feltételes szavazat, pótszavazat Condorcet-módszer Schulze-módszer Rangsorolt párok módszere Pozíciós szavazás Bucklin-módszer Preferenciális blokkszavazás Kardinális Elfogadó szavazás Pontozásos szavazás
Arányos rendszerek
Egyéni Egyetlen átruházható szavazat Arányos elfogadó szavazás Pártlistás Legmagasabb átlag alapú módszerek: D’Hondt, Sainte-Laguë, Hungtington-Hill Legnagyobb maradék alapú módszerek: Hare, Droop, Imperiali, Hagenbach-Bischoff Egyéb Biproporcionális mandátumelosztás
Félarányos és vegyes rendszerek
Nem vegyes félarányos Egyetlen nem-átruházható szavazat Korlátozott blokkszavazás Nem kompenzációs vegyes Árokrendszer Többségi bónusz Kompenzációs vegyes Vegyes arányos rendszer Kétszavazatos töredékszavazat-visszaszámláló Egyszavazatos módszerek Magyar országgyűlési (2010−) Magyar országgyűlési (1989−2010)
Egyéb
Pártlisták Nyílt lista, Zárt lista, Helyi lista Választási rendszerek összehasonlítása Választási rendszerek országonként
Sablon:Választási rendszerek m v sz

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

Teljesülő tulajdonságok

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

• Korlátozatlan tartomány, minden szavazónak megengedett az összes preferenciasorrend
• Minden összesített preferenciasorrend előfordulhat (Arrow lehetetlenségi tétele)
• Diktátormentesség
• Pareto hatékony^[1]
• Monoton^[1]
• Többségi kritérium
• Többségi vesztes kritérium
• Condorcet kritérium
• Condorcet vesztes kritérium
• Schwartz-kritérium
• Smith-kritérium^[1]
• A Smith-dominált alternatívák függetlensége^[1]
• Kölcsönösségi többségi kritérium
• A klónok függetlensége^[1]
• Fordított szimmetria^[1]
• Mono-append^[2]
• Mono-add-plump^[2]
• Visszakövethetőségi kritérium^[1]
• Polinomiális bonyolultság^[1]
• prudence^[1]:§4.9"
• MinMax halmazok^[1]
• Woodall sokféleségi kritérium a szigorú megelőzés esetén
• Szimmetria-komplemencia^[2] a gyenge megelőzés esetén

Nem teljesülő tulajdonságok

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

• Részvételi kritérium^[1]:§3.4
• Konzisztencia
• Védettség az összebeszélés ellen
• Védettség a süllyesztés ellen
• Visszahatásmentesség

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

• Az irreleváns alternatívák függetlensége

A Schulze-módszer nem teljesíti a

• Peyton Young-kritériumot

Első lépé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

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

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

Első példa

21 szavazó, 4 jelölt:

8 ACDB

2 BADC

4 CDBA

4 DBAC

3 DCBA

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 legerősebb utak:

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

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

• 5 ${\displaystyle ACBED}$
• 5 ${\displaystyle ADECB}$
• 8 ${\displaystyle BEDAC}$
• 3 ${\displaystyle CABED}$
• 7 ${\displaystyle CAEBD}$
• 2 ${\displaystyle CBADE}$
• 7 ${\displaystyle DCEBA}$
• 8 ${\displaystyle EBADC}$

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

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

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

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 ${\displaystyle p[P,Q]}$-t, és csökkentik ${\displaystyle p[Q,P]}$-t. Jelöljön E a következőkben egy tetszőleges jelöltet a többi közül! Ekkor ${\displaystyle p[P,E]}$ és ${\displaystyle p[E,Q]}$ nő, és ${\displaystyle p[E,P]}$ vagy ${\displaystyle 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ó

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 C³ , 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 C² szorozva a szavazók számával.

Holtversenyek és alternatív implementációk

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

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

További információk

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

• Proposed Statutory Rules for the Schulze Single-Winner Election Method by Markus Schulze
• A New Monotonic, Clone-Independent, Reversal Symmetric, and Condorcet-Consistent Single-Winner Election Method by Markus Schulze