Schulze-módszer

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ékonyMarkus 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. Monoton Többségi kritérium Többségi vesztes kritérium Condorcet kritérium Condorcet vesztes kritérium Schwartz-kritérium Smith-kritérium A Smith-dominált alternatívák függetlensége Kölcsönösségi többségi kritérium A klónok függetlensége Fordított szimmetria Mono-appendDouglas R. Woodall, Properties of Preferential Election Rules, Voting Matters, issue 3, pages 8-15, December 1994 Mono-add-plump Visszakövethetőségi kritérium Polinomiális bonyolultság prudence MinMax halmazok Woodall sokféleségi kritérium a szigorú megelőzés esetén Szimmetria-komplemencia 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 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

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:

border|none|300px

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.

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

thumb|300px|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 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 A szavazás manipulálásának egy módja az esélyesek szétválasztása.http://rangevoting.org/IncentToExagg.html 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.http://scorevoting.net/DH3.html 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 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 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ű.

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.

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

Rajzoljunk fel egy teljes irányított gráfot az összes jelölttel 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 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* 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.) Mike Ossipoff, Party List P.S., July 1998 Markus Schulze, Tiebreakers, Subcycle Rules, August 1998 Markus Schulze, Maybe Schulze is decisive, August 1998 Norman Petry, Schulze Method - Simpler Definition, September 1998 Markus Schulze, Schulze Method, November 1998 és 2000-ben. Anthony Towns, Disambiguation of 4.1.5, November 2000 Norman Petry, Constitutional voting, definition of cumulative preference, December 2000 Ezután sok közösségben bevezették, például a Software in the Public Interest (2003),Process for adding new board members, January 2003 Debian (2003), Constitutional Amendment: Condorcet/Clone Proof SSD Voting Method, June 2003 Constitution for the Debian Project, appendix A6

Schulze-módszer

Źródło i licencja