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é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
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 gráf:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7c/Schulze_method_example7.svg/300px-Schulze_method_example7.svg.png)
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 ... | ![]() | ![]() | ![]() | |
B-ből ... | ![]() | ![]() | ![]() | |
C-ből ... | ![]() | ![]() | ![]() | |
D-ből ... | ![]() | ![]() | ![]() |
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 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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e0/Schulze_method_example1.svg/300px-Schulze_method_example1.svg.png)
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-ba | ... B-be | ... C-be | ... D-be | ... E-be | ||
---|---|---|---|---|---|---|
A-ból ... | ![]() | ![]() | ![]() | ![]() | A-ból ... | |
B-ből ... | ![]() | ![]() | ![]() | ![]() | B-ből ... | |
C-ből ... | ![]() | ![]() | ![]() | ![]() | C-ből ... | |
D-ből ... | ![]() | ![]() | ![]() | ![]() | D-ből ... | |
E-ből ... | ![]() | ![]() | ![]() | ![]() | E-ből ... | |
... A-ba | ... B-be | ... C-be | ... D-be | ... E-be |
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.[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ó
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ű.[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:
- 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[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
- ↑ 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.
- ↑ a b c Douglas R. Woodall, Properties of Preferential Election Rules, Voting Matters, issue 3, pages 8-15, December 1994
- ↑ http://rangevoting.org/IncentToExagg.html
- ↑ http://scorevoting.net/DH3.html
- ↑ * 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.[halott link], July 1998
- Markus Schulze, Tiebreakers, Subcycle Rules[halott link], August 1998
- Markus Schulze, Maybe Schulze is decisive[halott link], August 1998
- Norman Petry, Schulze Method - Simpler Definition[halott link], September 1998
- Markus Schulze, Schulze Method[halott link], November 1998
- ↑
- Anthony Towns, Disambiguation of 4.1.5, November 2000
- Norman Petry, Constitutional voting, definition of cumulative preference, December 2000
- ↑ Process for adding new board members, January 2003
- ↑
- Constitutional Amendment: Condorcet/Clone Proof SSD Voting Method, June 2003
- Constitution for the Debian Project, appendix A6
- Debian Voting Information
- ↑ See:
- Gentoo Foundation Charter Archiválva 2013. január 18-i dátummal a Wayback Machine-ben
- Aron Griffis, 2005 Gentoo Trustees Election Results Archiválva 2015. október 3-i dátummal a Wayback Machine-ben, May 2005
- Lars Weiler, Gentoo Weekly Newsletter 23 May 2005 Archiválva 2015. október 2-i dátummal a Wayback Machine-ben
- Daniel Drake, Gentoo metastructure reform poll is open Archiválva 2015. október 3-i dátummal a Wayback Machine-ben, June 2005
- Grant Goodyear, Results now more official Archiválva 2015. szeptember 25-i dátummal a Wayback Machine-ben, September 2006
- 2007 Gentoo Council Election Results Archiválva 2010. december 23-i dátummal a Wayback Machine-ben, September 2007
- 2008 Gentoo Council Election Results Archiválva 2010. december 23-i dátummal a Wayback Machine-ben, June 2008
- 2008 Gentoo Council Election Results Archiválva 2010. december 23-i dátummal a Wayback Machine-ben, November 2008
- 2009 Gentoo Council Election Results Archiválva 2011. június 7-i dátummal a Wayback Machine-ben, June 2009
- 2009 Gentoo Council Election Results Archiválva 2010. december 23-i dátummal a Wayback Machine-ben, December 2009
- 2010 Gentoo Council Election Results Archiválva 2010. december 23-i dátummal a Wayback Machine-ben, June 2010
- ↑ * 2006 TopCoder Open Logo Design Contest, November 2005
- 2006 TopCoder Collegiate Challenge Logo Design Contest, June 2006
- 2007 TopCoder High School Tournament Logo Archiválva 2011. július 17-i dátummal a Wayback Machine-ben, September 2006
- 2007 TopCoder Arena Skin Contest Archiválva 2011. július 17-i dátummal a Wayback Machine-ben, November 2006
- 2007 TopCoder Open Logo Contest Archiválva 2011. július 17-i dátummal a Wayback Machine-ben, January 2007
- 2007 TopCoder Open Web Design Contest Archiválva 2011. július 17-i dátummal a Wayback Machine-ben, January 2007
- 2007 TopCoder Collegiate Challenge T-Shirt Design Contest Archiválva 2011. július 17-i dátummal a Wayback Machine-ben, September 2007
- 2008 TopCoder Open Logo Design Contest Archiválva 2011. július 17-i dátummal a Wayback Machine-ben, September 2007
- 2008 TopCoder Open Web Site Design Contest Archiválva 2011. július 17-i dátummal a Wayback Machine-ben, October 2007
- 2008 TopCoder Open T-Shirt Design Contest Archiválva 2011. július 17-i dátummal a Wayback Machine-ben, March 2008
- ↑ See:
- Jesse Plamondon-Willard, Board election to use preference voting, May 2008
- Mark Ryan, 2008 Wikimedia Board Election results, June 2008
- 2008 Board Elections, June 2008
- 2009 Board Elections, August 2009
- ↑ section 3.4.1 of the Rules of Procedures for Online Voting
- ↑ See:
- article 6 section 3 of the constitution
- Fellowship vote for General Assembly seats, March 2009
- And the winner of the election for FSFE's Fellowship GA seat is ..., June 2009
- ↑ See:
- Inför primärvalen Archiválva 2012. december 24-i dátummal az Archive.is-en, October 2009
- Dags att kandidera till riksdagen Archiválva 2014. július 23-i dátummal az Archive.is-en, October 2009
- Råresultat primärvalet Archiválva 2012. december 24-i dátummal az Archive.is-en, January 2010
- ↑ * http://wiki.piratenpartei.de/BE:Neuk%C3%B6lln/Gebietsversammlungen/2010.3/Protokoll
- http://berlin.piratenpartei.de/2011/01/18/kandidaten-der-piraten-in-mitte-aufgestellt/
- http://wiki.piratenpartei.de/wiki/images/d/da/BE_Gebietsversammlung_Steglitz_Zehlendorf_2011_01_20_Protokoll.pdf
- http://wiki.piratenpartei.de/BE:Gebietsversammlungen/Tempelhof-Schoeneberg/Protokoll_2011.1
- http://wiki.piratenpartei.de/BE:Parteitag/2011.1/Protokoll_2011[halott link]
- http://wiki.piratenpartei.de/BY:Regensburg/Gr%C3%BCndung/Gesch%C3%A4ftsordnung#Anlage_A
- ↑ Choix dans les votes
- ↑ fr:Spécial:Pages liées/Méthode Schulze
További információk
![Fájl:Commons-logo.svg](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/50px-Commons-logo.svg.png)
- 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