Clever Geek Handbook
📜 ⬆️ ⬇️

Schulze Method

The Schulze method (also the Schwartz sequential exclusion method ) is a voting system developed in 1997 by Marcus Schulze .

M. Schulze himself calls it the " beaten path method " ( eng. Beatpath method ). It allows you to determine the winner (with objective counting) using voting ballots in which voters indicate their preferences for candidates, ranking them. This method can also be used to obtain a list of candidates sorted by preference.

This method satisfies the Condorcet criterion : if one of the candidates is the winner when compared with each of the other candidates, then he will also be the winner according to the Schulze method (the method of choosing the President of Russia and France does not satisfy this criterion). In addition to this, the Schulze method allows one to formally determine the winner even when, according to the Condorcet criterion, there is no winner. The Schulze winner always belongs to the Schwartz set .

In the Schulze method, each ballot paper contains a complete list of candidates, and each voter ranks them in order of preference. In the most common format, ascending numbers are used, when the voter puts “1” opposite the name of the most desirable candidate, “2” opposite the second by preference, and so on. Voters may put the same numbers for several candidates, or not fill in this field for some candidates (in this case, it is considered that the voter put such candidates equally below all for which he indicated the number).

There are various heuristics that allow you to determine the winner of a vote based on such source data. To date, the most common is the path heuristic of the Schulze method.

Content

Path heuristics

The basic idea of ​​path heuristics is the concept of indirect victories , the so-called paths .

If, in a pairwise comparison, candidate C (1) wins C (2), candidate C (2) wins C (3), candidate C (3) wins C (4), ..., and C ( n - 1) wins C ( n ), then we can say that there is a path from candidate C (1) to candidate C ( n ). The more voters who prefer the first candidate to the second candidate, the stronger the victory of the first over the second. The strength of the path C (1), ..., C ( n ) is the weakest pair victory of one candidate over another in this sequence.

In other words:

  • Suppose that d [ V , W ] is the number of voters who strictly prefer V to W.
  • A path is a sequence of candidates C (1), ..., C ( n ), where d [C ( i ), C ( i + 1)]> d [C ( i + 1), C ( i )] for all i = 1, ..., n - 1.
  • The strength of the path C (1), ..., C ( n ) is the minimum d [C ( i ), C ( i + 1)] for all i = 1, ..., n - 1, where C ( i ) is the position number i from the beginning of the journey; d [ A , B ] - the number of people who put candidate A higher by one or more positions than candidate B , and if the path in question is defined, then the names of candidates can be replaced by their positions in this path.

The strength of the strongest path p [ A , B ] from candidate A to candidate B is the maximum strength value of all possible paths from candidate A to candidate B. If the path from candidate A to candidate B does not exist, then p [ A , B ] is taken equal to zero.

Candidate A defeats candidate B indirectly if either of the following two conditions is true:

  • The strength of the strongest path from candidate A to candidate B is stronger than the strength of the strongest path from candidate B to candidate A.
  • There is a path from candidate A to candidate B , and there is no path from candidate B to candidate A.

Indirect victories satisfy the condition of transitivity . This means that: if candidate A indirectly defeats candidate B , and candidate B indirectly defeats candidate C , then candidate A also defeats candidate C indirectly.

Procedure

The heuristic of the path uses the following procedure for constructing a graph of paths of preference and determining the strength of paths:

The path p from candidate X to candidate Y is a sequence of candidates C (1), ..., C ( n ) with the following five properties:

  1. C (1) is taken equal to X.
  2. C ( n ) is taken equal to Y.
  3. For all i from 1 to n - 1: d [C ( i ), C ( i + 1)]> d [C ( i + 1), C ( i )].
  4. For all i from 1 to n - 1: d [C ( i ), C ( i + 1)] ⩾ p .
  5. For at least one i from the range from 1 to n - 1: d [C ( i ), C ( i + 1)] = p , where p is the strength of the path from candidate X to candidate Y , that is, p [ X , Y ].

A candidacy A is a possible winner if and only if p [ A , Z ] ⩾ p [ Z , A ] for each other candidacy Z.

Examples

Example 1

d [*, A]d [*, B]d [*, C]
d [A, *]-7033
d [B, *]27-60
d [C, *]6437-

The bold values ​​are d [ X , Y ]> d [ Y , X ]. As can be seen from the table, in this example, each candidate prefers a different candidate - there is the Condorcet paradox . However, the strength of preference varies. The preference given to candidate A over candidate B is greater than the preference given to candidate C over candidate A. And according to the procedure described above, he will be recognized as the winner by the Schulze method.


Example 2

Consider the elections in which 45 voters vote for five candidates: A, B, C, D, E. The votes were distributed as follows:

5 ACBED (i.e. 5 voters put A above C, C above B, B above E, and E above D),
5 ADECB,
8 BEDAC,
3 CABED,
7 CAEBD,
2 CBADE,
7 DCEBA,
8 EBADC.
 
The number of voters who prefer one candidate to another:
d [*, A]d [*, B]d [*, C]d [*, D]d [*, E]
d [A, *]2026thirty22
d [B, *]25sixteen3318
d [C, *]nineteen29th1724
d [D, *]15122814
d [E, *]23272131

The strength of the path is the strength of its weakest link (critical link). The paths in which each transition satisfies d [ X , Y ]> d [ Y , X ] can be constructed using the following pieces of the sequences AC, AD, BA, BD, CB, CE, DC, EA, EB, ED.

The following table shows the strongest paths from candidate X to candidate Y. The critical link of the strongest path is emphasized.

The strongest ways:
... to A... to B... to C... to D... to E
from A ...
 
A- (30) -D- (28) -C- (29) -B
 
A- (30) -D- (28) -C
 
A- (30) -D
 
A- (30) -D- (28) -C- (24) -E
from B ...
 
B- (25) -A
 
B- (33) -D- (28) -C
 
B- (33) -D
 
B- (33) -D- (28) -C- (24) -E
from C ...
 
C- (29) -B- (25) -A
 
C- (29) -B
 
C- (29) -B- (33) -D
 
C- (24) -E
from D ...
 
D- (28) -C- (29) -B- (25) -A
 
D- (28) -C- (29) -B
 
D- (28) -C
 
D- (28) -C- (24) -E
from E ...
 
E- (31) -D- (28) -C- (29) -B- (25) -A
 
E- (31) -D- (28) -C- (29) -B
 
E- (31) -D- (28) -C
 
E- (31) -D
Strengths of the strongest paths:
p [*, A]p [*, B]p [*, C]p [*, D]p [*, E]
p [A, *]2828thirty24
p [B, *]25283324
p [C, *]2529th29th24
p [D, *]25282824
p [E, *]25282831

According to the Schulze method, candidate E will be declared the winner, since p [E, X ] ⩾ p [ X , E] for any other candidate X.

Since 25 = p [E, A]> p [A, E] = 24, candidate E is better than candidate A.

Since 28 = p [E, B]> p [B, E] = 24, candidate E is better than candidate B.

Since 28 = p [E, C]> p [C, E] = 24, candidate E is better than candidate C.

Since 31 = p [E, D]> p [D, E] = 24, candidate E is better than candidate D.

Since 28 = p [A, B]> p [B, A] = 25, candidate A is better than candidate B.

Since 28 = p [A, C]> p [C, A] = 25, candidate A is better than candidate C.

Since 30 = p [A, D]> p [D, A] = 25, candidate A is better than candidate D.

Since 29 = p [C, B]> p [B, C] = 28, candidate C is better than candidate B.

Since 29 = p [C, D]> p [D, C] = 28, candidate C is better than candidate D.

Since 33 = p [B, D]> p [D, B] = 28, candidate B is better than candidate D.

Thus, the Schulze method leads to the following order of candidates: E> A> C> B> D.

Application

The Schulze method has not yet been applied in general political elections, but it is becoming increasingly popular in private organizations. Today it is used in elections in the following private organizations and parties:

 
An example of an electronic ballot for the election of Wikimedia Foundation curators
  • Annodex Association [1]
  • Blitzed [2]
  • BoardGameGeek [3]
  • Cassandra [4]
  • Codex Alpe Adria [5]
  • Collective Agency [6]
  • College of Marine Science [7]
  • Computer Science Departmental Society for York University (HackSoc) [8]
  • County Highpointers [9]
  • Debian [10]
  • Demokratische Bildung Berlin [11]
  • EuroBillTracker [12]
  • European Democratic Education Conference (EUDEC) [13]
  • Fair Trade Northwest [14]
  • FFmpeg [15]
  • Flemish Student Society of Leuven [16]
  • Free Geek [17]
  • Free Hardware Foundation of Italy [18]
  • Free Software Foundation Europe (FSFE) [19]
  • Gentoo Foundation [20]
  • GNU Privacy Guard (GnuPG) [21]
  • Gothenburg Hacker Space (GHS) [22]
  • Graduate Student Organization at the State University of New York: Computer Science (GSOCS) [23]
  • Haskell [24]
  • Ithaca Generator [25]
  • Kanawha Valley Scrabble Club [26]
  • KDE eV [27]
  • Kingman Hall [28]
  • Knight Foundation [29]
  • Kumoricon [30]
  • League of Professional System Administrators (LOPSA) [31]
  • Libre-Entreprise [32]
  • LiquidFeedback [33]
  • Lumiera / Cinelerra [34]
  • Mathematical Knowledge Management Interest Group (MKM-IG) [35]
  • Metalab [36]
  • Music Television (MTV) [37]
  • Neo [38]
  • Noisebridge [39]
  • North Shore Cyclists (NSC) [40]
  • OpenEmbedded [41]
  • OpenStack [42]
  • Park Alumni Society (PAS) [43]
  • Australia Pirate Party [44]
  • Austrian Pirate Party [45]
  • Belgium Pirate Party [46]
  • Brazil Pirate Party
  • French Pirate Party [47]
  • German Pirate Party [48]
  • Italy Pirate Party [49]
  • Mexican Pirate Party [50]
  • New Zealand Pirate Party [51]
  • Swedish Pirate Party [52]
  • Switzerland Pirate Party [53]
  • US Pirate Party [54]
  • Pitcher plant of the month
  • Pittsburgh Ultimate [55]
  • RLLMUK [56]
  • RPMrepo [57]
  • Sender Policy Framework (SPF) [58]
  • Software in the Public Interest (SPI) [59]
  • Squeak [60]
  • Students for Free Culture [61] ]
  • Sugar Labs [62]
  • Sverok [63]
  • TestPAC [64]
  • TopCoder [65]
  • Ubuntu [66]
  • University of British Columbia Math Club [67]
  • Wikimedia Foundation [68]
  • Wikipedia in French , [69] Hebrew , [70] Hungarian [71] and Russian [72] .

Alternative Voting

The Schulze method is the development of the idea of ​​alternative voting, which is used in elections to various authorities of Australia , New Zealand , Papua New Guinea , Fiji , Ireland , the USA , as well as in a number of political parties, non-governmental organizations, etc.

Notes

  1. ↑ Election of the Annodex Association committee for 2007 , February 2007.
  2. ↑ Condorcet method for admin voting . Archived April 26, 2005 to Wayback Machine , January 2005.
  3. ↑ See:
    • Important notice for Golden Geek voters , September 2007.
    • Golden Geek Awards 2008 - Nominations Open , August 2008.
    • Golden Geek Awards 2009 - Nominations Open , August 2009.
    • Golden Geek Awards 2010 - Nominations Open , September 2010.
    • Golden Geek Awards 2011 - Nominations Open , September 2011.
  4. ↑ Project Logo Archived October 3, 2015 at Wayback Machine , October 2009.
  5. ↑ Codex Alpe Adria Competitions (Neopr.) . 0xaa.org (January 24, 2010). Date of treatment May 8, 2010. Archived February 2, 2013.
  6. ↑ Civics Meeting Minutes , March 2012.
  7. ↑ Fellowship Guidelines (unopened) (PDF) (link not available) . Date of treatment June 1, 2011. Archived on September 28, 2011.
  8. ↑ Report on HackSoc Elections , December 2008.
  9. ↑ Adam Helman, Family Affair Voting Scheme - Schulze Method .
  10. ↑ See:
    • Constitutional Amendment: Condorcet / Clone Proof SSD Voting Method , June 2003.
    • Constitution for the Debian Project , appendix A6.
    • Debian Voting Information .
  11. ↑ Appendix 1 of the constitution . Archived July 18, 2011 on Wayback Machine
  12. ↑ See:
    • Candidate cities for EBTM05 , December 2004.
    • Meeting location preferences , December 2004.
    • Date for EBTM07 Berlin , January 2007.
    • Vote the date of the Summer EBTM08 in Ljubljana , January 2008.
    • New Logo for EBT , August 2009.
  13. ↑ Guidance Document (neopr.) . Eudec.org (November 15, 2009). Date of treatment May 8, 2010. Archived February 2, 2013.
  14. ↑ Article XI, section 2 of the bylaws Archived July 26, 2011 on Wayback Machine
  15. ↑ Democratic election of the server admins . Archived October 2, 2015 at Wayback Machine , July 2010.
  16. ↑ Article 51 of the statutory rules .
  17. ↑ Voters Guide , September 2011.
  18. ↑ See:
    • Eletto il nuovo Consiglio nella Free Hardware Foundation Archived December 25, 2008 at Wayback Machine , June 2008.
    • Poll Results , June 2008.
  19. ↑ 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.
  20. ↑ See:
    • Gentoo Foundation Charter Archived on August 22, 2011.
    • Aron Griffis, 2005 Gentoo Trustees Election Results Archived October 3, 2015 at Wayback Machine , May 2005.
    • Lars Weiler, Gentoo Weekly Newsletter May 23, 2005 . Archived October 2, 2015 on Wayback Machine
    • Daniel Drake, Gentoo metastructure reform poll is open . Archived October 3, 2015 at Wayback Machine , June 2005.
    • Grant Goodyear, Results now more official . Archived September 25, 2015 at Wayback Machine , September 2006.
    • 2007 Gentoo Council Election Results . Archived December 23, 2010 at Wayback Machine , September 2007.
    • 2008 Gentoo Council Election Results . Archived December 23, 2010 at Wayback Machine , June 2008.
    • 2008 Gentoo Council Election Results . Archived December 23, 2010 at Wayback Machine , November 2008.
    • 2009 Gentoo Council Election Results . Archived June 7, 2011 at Wayback Machine , June 2009.
    • 2009 Gentoo Council Election Results . Archived December 23, 2010 to Wayback Machine , December 2009.
    • 2010 Gentoo Council Election Results . Archived December 23, 2010 at Wayback Machine , June 2010.
  21. ↑ GnuPG Logo Vote . Archived December 16, 2006 at Wayback Machine , November 2006.
  22. ↑ § 14 of the bylaws . Archived April 29, 2010 on the Wayback Machine
  23. ↑ User Voting Instructions (unopened) (inaccessible link) . Gso.cs.binghamton.edu. Date of treatment May 8, 2010. Archived February 2, 2013.
  24. ↑ Haskell Logo Competition , March 2009.
  25. ↑ Article VI, section 10 of the bylaws (unavailable link) , November 2012.
  26. ↑ A club by any other name ... , April 2009.
  27. ↑ section 3.4.1 of the Rules of Procedures for Online Voting .
  28. ↑ See:
    • Ka-Ping Yee, Condorcet elections , March 2005.
    • Ka-Ping Yee, Kingman adopts Condorcet voting , April 2005.
  29. ↑ Knight Foundation awards $ 5000 to best created-on-the-spot projects , June 2009.
  30. ↑ See:
    • Mascot 2007 contest , July 2006.
    • Mascot 2008 and cover 2007 contests , May 2007.
    • Mascot 2009 and program cover 2008 contests , April 2008.
    • Mascot 2010 and program cover 2009 contests , May 2009.
    • Mascot 2011 and book cover 2010 contests , May 2010.
    • Mascot 2012 and book cover 2011 contests , May 2011.
  31. ↑ Article 8.3 of the bylaws .
  32. ↑ See:
    • Choix de date pour la réunion Libre-entreprise durant le Salon Solution Linux 2006 , January 2006.
    • Entrée de Libricks dans le réseau Libre-entreprise , February 2008.
  33. ↑ Concepts (neopr.) . Home page of LiquidFeedback . Interactive Democracy. Date of treatment December 26, 2012. Archived February 2, 2013.
  34. ↑ Lumiera Logo Contest , January 2009.
  35. ↑ The MKM-IG uses Condorcet with dual dropping . See:
    • MKM-IG Charter.
    • Michael Kohlhase , MKM-IG Trustees Election Details & Ballot . Archived December 9, 2012. November 2004.
    • Andrew A. Adams, MKM-IG Trustees Election 2005 . Archived December 9, 2012. December 2005.
    • Lionel Elie Mamane, Elections 2007: Ballot . Archived December 9, 2012. August 2007.
  36. ↑ Wahlmodus (German) . Metalab.at. Date of treatment May 8, 2010.
  37. ↑ Benjamin Mako Hill , Voting Machinery for the Masses , July 2008.
  38. ↑ See:
    • Wahlen zum Neo-2-Freeze: Formalitäten , February 2010.
    • Hinweise zur Stimmabgabe , March 2010.
    • Ergebnisse , March 2010.
  39. ↑ 2009 Director Elections .
  40. ↑ NSC Jersey election Archived March 26, 2009 to Wayback Machine , NSC Jersey vote , September 2007.
  41. ↑ Online Voting Policy .
  42. ↑ See:
    • 2010 OpenStack Community Election , November 2010.
    • OpenStack Governance Elections Spring 2012 , February 2012.
  43. ↑ Voting Procedures (unopened) (inaccessible link) . Parkscholars.org. Date of treatment May 8, 2010. Archived on April 13, 2013.
  44. ↑ National Congress 2011 Results , November 2011.
  45. ↑ § 6 (10) of the bylaws . Archived May 11, 2012 on Wayback Machine
  46. ↑ Ik word Piraat! (unavailable link) , August 2012.
  47. ↑ § 11.2.E of the statutory rules . Archived March 23, 2013 on Wayback Machine
  48. ↑ 11 out of 16 regional organizations and the German Pirate Party federal organization use LiquidFeedback for internal party voting. In 2010-2011, the Pirate Parties Neukölln ( link ), Mitte ( link ), Steglitz-Zehlendorf ( link ), Lichtenberg ( link ), and Tempelhof-Schöneberg ( link ) adopted the Schulze method for intra-party elections. Also, the Berlin Pirate Party (in 2011) ( link ) and Regensburg Pirate Party (in 2012) ( link ) approved this method for intra-party elections.
  49. ↑ Rules adopted on December 18, 2011 (inaccessible link) .
  50. ↑ Vote Result for Name Definition (inaccessible link) .
  51. ↑ 23 January 2011 meeting minutes .
  52. ↑ See:
    • Inför primärvalen , October 2009.
    • Dags att kandidera till riksdagen , October 2009.
    • Råresultat primärvalet , January 2010.
  53. ↑ Piratenversammlung der Piratenpartei Schweiz , September 2010.
  54. ↑ Article IV, section 4 of the constitution . Archived November 9, 2012 on Wayback Machine
  55. ↑ 2006 Community for Pittsburgh Ultimate Board Election , September 2006.
  56. ↑ Committee Elections , April 2012.
  57. ↑ LogoVoting Archived June 13, 2010 at Wayback Machine , December 2007.
  58. ↑ See:
    • SPF Council Election Procedures . Archived July 16, 2011 on Wayback Machine
    • 2006 SPF Council Election , January 2006.
    • 2007 SPF Council Election , January 2007.
  59. ↑ Process for adding new board members , January 2003.
  60. ↑ Squeak Oversight Board Election 2010 , March 2010.
  61. ↑ See:
    • Bylaws of the Students for Free Culture , article V, section 1.1.1.
    • Free Culture Student Board Elected Using Selectricity. [http://web.archive.org/web/20101215060556/http://blog.selectricity.org/?p=4 Archived December 15, 2010 at Wayback Machine , February 2008.
  62. ↑ Election status update , September 2009.
  63. ↑ Minutes of the 2010 Annual Sverok Meeting , November 2010.
  64. ↑ Article VI, section 6 of the bylaws . Archived January 30, 2012 on the Wayback Machine
  65. ↑ See:
    • 2006 TopCoder Open Logo Design Contest , November 2005.
    • 2006 TopCoder Collegiate Challenge Logo Design Contest , June 2006.
    • 2007 TopCoder High School Tournament Logo . Archived July 17, 2011 to Wayback Machine , September 2006.
    • 2007 TopCoder Arena Skin Contest . Archived July 17, 2011 to Wayback Machine , November 2006.
    • 2007 TopCoder Open Logo Contest . Archived July 17, 2011 to Wayback Machine , January 2007.
    • 2007 TopCoder Open Web Design Contest . Archived July 17, 2011 to Wayback Machine , January 2007.
    • 2007 TopCoder Collegiate Challenge T-Shirt Design Contest . Archived July 17, 2011 to Wayback Machine , September 2007.
    • 2008 TopCoder Open Logo Design Contest . Archived July 17, 2011 to Wayback Machine , September 2007.
    • 2008 TopCoder Open Web Site Design Contest . Archived July 17, 2011 at Wayback Machine , October 2007.
    • 2008 TopCoder Open T-Shirt Design Contest . Archived July 17, 2011 at Wayback Machine , March 2008.
  66. ↑ Ubuntu IRC Council Position , May 2012.
  67. ↑ See this mail .
  68. ↑ 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.
  69. ↑ Choix dans les votes .
  70. ↑ See for example here (May 2009), here (August 2009), and here (December 2009).
  71. ↑ See here and here .
  72. ↑ See:
    • Result of 2007 Arbitration Committee Elections .
    • Result of 2008 Arbitration Committee Elections .
    • Result of 2009 Arbitration Committee Elections .
    • Result of 2010 Arbitration Committee Elections .

Links

  • Markus Schulze, Tiebreakers, Subcycle Rules, August 1998
  • Markus Schulze, Maybe Schulze is decisive, August 1998
Source - https://ru.wikipedia.org/w/index.php?title= Schulze Method&oldid = 100831870


More articles:

  • Kriyaman Karma
  • Let my people go!
  • Stomatosuch
  • Thermal Transfer
  • Asr
  • Aitarea Aranyaka
  • Afak
  • Annaba
  • Rose, Barbara
  • Johansson, Johan Petter

All articles

Clever Geek | 2019