FACTOID # 18: Alaska spends more money per capita on elementary and secondary education than any other state.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Cloneproof Schwartz Sequential Dropping

Cloneproof Schwartz Sequential Dropping (CSSD) is a voting system developed in 1997 by Markus Schulze that selects a single winner using votes that express preferences. CSSD can also be used to create a sorted list of winners. CSSD is also known as "Schwartz Sequential Dropping", "Beatpath Method", "Beatpath Winner", "Path Voting", "Path Winner", and "Schulze Method". Voters at the voting booths in the US in 1945 Voting systems are methods (algorithms) for groups of people to select one or more options from many, taking into account the individual preferences of the group members. ...


If there is a candidate who is preferred pairwise over the other candidates, when compared in turn with each of the others, CSSD guarantees that that candidate will win. Because of this property, CSSD is (by definition) a Condorcet method. Note that this is different from some other preference voting systems such as Borda and Instant-runoff voting, which do not guarantee that the Condorcet winner will win in these systems. There is a disputed proposal that this article should be merged with Condorcet criterion Any election method conforming to the Condorcet criterion is known as a Condorcet method. ... The Borda count is a voting system used for single-winner elections in which each voter rank-orders the candidates. ... When the single transferable vote voting system is applied to a single-winner election it is sometimes called instant-runoff voting (IRV), as it is much like holding a series of runoff elections in which the lowest polling candidate is eliminated in each round until someone receives majority vote. ...

Contents

The Schwartz set

The definition of a Schwartz set, as used in CSSD, is as follows: The Schwartz set is a term used in regard to voting systems. ...

  1. An unbeaten set is a set of candidates of whom none is beaten by anyone outside that set.
  2. An innermost unbeaten set is an unbeaten set that doesn't contain a smaller unbeaten set.
  3. The Schwartz set is the set of candidates who are in innermost unbeaten sets.

Procedure

The voters cast their ballots by ranking the candidates according to their preferences, just like for any other Condorcet election.


CSSD uses Condorcet pairwise matchups between the candidates and a winner is chosen in each of the matchups. There is a disputed proposal that this article should be merged with Condorcet criterion Any election method conforming to the Condorcet criterion is known as a Condorcet method. ...


From there, CSSD operates as follows to select a winner (or create a ranked list):

  1. Calculate the Schwartz set based only on undropped defeats.
  2. If there are no defeats among the members of that set then they (plural in the case of a tie) win and the count ends.
  3. Otherwise, drop the weakest defeat among the candidates of that set. Go to 1.

An example

The situation

Imagine an election for the capital of Tennessee, a state in the United States that is over 500 miles east-to-west, and only 110 miles north-to-south. Let's say the candidates for the capital are Memphis (on the far west end), Nashville (in the center), Chattanooga (129 miles southeast of Nashville), and Knoxville (on the far east side, 114 northeast of Chattanooga). Here's the population breakdown by metro area (surrounding county): State nickname: Volunteer State Other U.S. States Capital Nashville Largest city Memphis Governor Phil Bredesen Official languages English Area 109,247 km² (36th)  - Land 106,846 km²  - Water 2,400 km² (2. ...

  • Memphis (Shelby County): 826,330
  • Nashville (Davidson County): 510,784
  • Chattanooga (Hamilton County): 285,536
  • Knoxville (Knox County): 335,749

Let's say that in the vote, the voters vote based on geographic proximity. Assuming that the population distribution of the rest of Tennessee follows from those population centers, one could easily envision an election where the percentages of votes would be as follows: Census. ...

42% of voters (close to Memphis)
1. Memphis
2. Nashville
3. Chattanooga
4. Knoxville

26% of voters (close to Nashville)
1. Nashville
2. Chattanooga
3. Knoxville
4. Memphis

15% of voters (close to Chattanooga)
1. Chattanooga
2. Knoxville
3. Nashville
4. Memphis

17% of voters (close to Knoxville)
1. Knoxville
2. Chattanooga
3. Nashville
4. Memphis

The results would be tabulated as follows:

Pairwise Election Results
A
Memphis Nashville Chattanooga Knoxville
B Memphis [A] 58%
[B] 42%
[A] 58%
[B] 42%
[A] 58%
[B] 42%
Nashville [A] 42%
[B] 58%
[A] 32%
[B] 68%
[A] 32%
[B] 68%
Chattanooga [A] 42%
[B] 58%
[A] 68%
[B] 32%
[A] 17%
[B] 83%
Knoxville [A] 42%
[B] 58%
[A] 68%
[B] 32%
[A] 83%
[B] 17%
Pairwise election results (won-lost-tied): 0-3-0 3-0-0 2-1-0 1-2-0
Votes against in worst pairwise defeat: 58% N/A 68% 83%
  • [A] indicates voters who preferred the candidate listed in the column caption to the candidate listed in the row caption
  • [B] indicates voters who preferred the candidate listed in the row caption to the candidate listed in the column caption
  • [NP] indicates voters who expressed no preference between either candidate

Pairwise winners

First, list every pair, and determine the winner:

Pair Winner
Memphis (42%) vs. Nashville (58%) Nashville 58%
Memphis (42%) vs. Chattanooga (58%) Chattanooga 58%
Memphis (42%) vs. Knoxville (58%) Knoxville 58%
Nashville (68%) vs. Chattanooga (32%) Nashville 68%
Nashville (68%) vs. Knoxville (32%) Nashville 68%
Chattanooga (83%) vs. Knoxville (17%) Chattanooga: 83%

Note that absolute counts of votes can be used, or percentages of the total number of votes; it makes no difference.


Dropping

Next we start with our list of cities and their matchup wins/defeats

  • Nashville 3-0
  • Chattanooga 2-1
  • Knoxville 1-2
  • Memphis 0-3

Technically, the Schwartz set is simply Nashville as it beat all others 3 to 0.


Therefore, Nashville is the winner.


Ambiguity resolution example

Let's say there was an ambiguity. For a simple situation involving candidates A, B, and C.

  • A > B 72%
  • B > C 68%
  • C > A 52%

In this situation the Schwartz set is A, B, and C as they all beat someone.


CSSD then says to drop the weakest defeat, so we drop C > A and are left with

  • A > B 72% (as C has been removed)

Therefore, A is the winner.



(It may be more accessible to phrase that as "drop the weakest win", though purists may complain.)


Summary

In the (first) example election, the winner is Nashville. This would be true for any Condorcet method. Using the first-past-the-post system and some other systems, Memphis would have won the election by having the most people, even though Nashville won every simulated pairwise election outright. Using Instant-runoff voting in this example would result in Knoxville winning, even though more people preferred Nashville over Knoxville. There is a disputed proposal that this article should be merged with Condorcet criterion Any election method conforming to the Condorcet criterion is known as a Condorcet method. ... The first-past-the-post electoral system is a voting system for single-member districts, variously called first-past-the-post (FPTP or FPP), winner-take-all, plurality voting, or relative majority. ... When the single transferable vote voting system is applied to a single-winner election it is sometimes called instant-runoff voting (IRV), as it is much like holding a series of runoff elections in which the lowest polling candidate is eliminated in each round until someone receives majority vote. ...


Satisfied criteria

CSSD satisfies the following criteria:

  1. Majority criterion
  2. Monotonicity criterion
  3. Pareto criterion
  4. Condorcet criterion
  5. Smith criterion (aka Generalized Condorcet criterion)
  6. local independence from irrelevant alternatives
  7. Schwartz criterion
  8. Strategy-Free criterion
  9. Generalized Strategy-Free criterion
  10. Strong Defensive Strategy criterion
  11. Weak Defensive Strategy criterion
  12. Summability criterion
  13. Independence of clones

CSSD violates the following criteria: The majority criterion is a voting system criterion, used to objectively compare voting systems. ... A voting system is monotonic if it satisfies the following so-called monotonicity criterion given below. ... Pareto efficiency, or Pareto optimality, is a central concept in game theory with broad applications in economics, engineering and the social sciences. ... The Condorcet candidate or Condorcet winner of an election is the candidate who, when compared in turn with each of the other candidates, is preferred over the other candidate. ... In voting systems, the Smith set is the smallest set of candidates in a particular election who, when paired off in pairwise elections, can beat all other candidates outside the set. ... AKA is an initialism for Also Known As. ... The Generalized Condorcet criterion or Smith criterion for a voting system is that it picks the winner from the Smith set, the smallest set of candidates such that every member of the set is preferred to every candidate not in the set. ... In voting systems, independence of irrelevant alternatives is the property some voting systems have that, if one option (X) wins the election, and a new alternative (Y) is added, only X or Y will win the election. ... The Schwartz set is a term used in regard to voting systems. ... Definitions A sincere vote is one with no falsified preferences or preferences left unspecified when the election method allows them to be specified (in addition to the preferences already specified). ... Definitions A sincere vote is one with no falsified preferences or preferences left unspecified when the election method allows them to be specified (in addition to the preferences already specified). ... Definitions A voter votes X equal to Y if the voter doesnt vote X over Y, and doesnt vote Y over X, but votes X over someone, and votes Y over someone. ... The weak defensive strategy criterion is . ... Statement of Criterion Each vote should map onto a summable array, where the summation operation is associative and commutative, and the winner should be determined from the array sum for all votes cast. ... Strategic nomination is the manipulation of an election through its candidate set (compare this to tactical voting, where the manipulation comes from the voters). ...

  1. Participation criterion
  2. Consistency criterion
  3. Invulnerability to compromising; see Tactical Voting
  4. Invulnerability to burying; see Tactical Voting

It isn't known whether CSSD satisfies the following criteria: Statement of Criterion Adding one or more ballots that vote X over Y should never change the winner from X to Y. Complying Methods Plurality voting, Approval voting, Cardinal Ratings, Borda count, and Woodalls DAC method all pass the Participation Criterion. ... A voting system is consistent if, when the electorate is divided arbitrarily into two parts and separate elections in each part result in the same alternative being selected, an election of the entire electorate also selects that alternative. ... In voting systems, tactical voting (or strategic voting) occurs when a voter misrepresents his or her sincere preferences in order to gain a more favorable outcome. ... In voting systems, tactical voting (or strategic voting) occurs when a voter misrepresents his or her sincere preferences in order to gain a more favorable outcome. ...

  1. Favorite Betrayal criterion

In social choice theory, the Favoriate Betrayal criterion is a criterion for evaluating voting systems. ...

Use of CSSD

CSSD is not currently used in government elections. However, it is starting to receive support in some public organizations. Organizations which currently use CSSD are:

  1. the Debian project (See here (http://www.debian.org/devel/constitution) and here (http://www.debian.org/vote/2003/vote_0002)!)
  2. the Software in the Public Interest (SPI) project (See here (http://www.spi-inc.org/corporate/resolutions/resolution-2003-01-06.wta.1)!)
  3. the UserLinux project (See here  (http://www.userlinux.com/cgi-bin/wiki.pl?Policy)!)
  4. the Park Alumni Society (PAS) (http://www.parkscholars.org/) (See here (http://www.parkscholars.org/voting.php)!)
  5. the Blitzed (http://blitzed.org/) project (See here  (http://wiki.blitzed.org/Condorcet_method_for_admin_voting)!)
  6. the Leader of the Free World (LFW) (http://www.leaderofthefreeworld.com/) project (See here  (http://www.leaderofthefreeworld.com/eng/faq.html)!)
  7. the L'Expérience Démocratique (DemExp) (http://www.demexp.org/) project (See section 14.6 of this paper (http://www.linux-france.org/~dmentre/demexp/demexp-server-book-0.4.pdf)!)
  8. the Glasnost (http://glasnost.entrouvert.org/) / Easter Eggs (http://www.easter-eggs.org/) / libre-entreprise (http://www.libre-entreprise.org/) project
  9. the Green Mountain Mutual Aid (GMMA) (http://www.sover.net/~tr11/faqs.htm) project
  10. the Kingman Hall (http://kingmanhall.org/) (See here (http://wolog.net/102718.html) and here (http://wolog.net/111588.html)!)
  11. the Johns Hopkins Animation Club (JHAC) (http://jhac.acm.jhu.edu/bylaws.doc)
  12. the Haifa Linux Club (Haifux) (http://www.haifux.org/) (See here  (http://mirror.hamakor.org.il/archives/linux-il/01-2004/8135.html)!)
  13. the Free Software Club of Kirksville (FSCK) (http://fsck.truman.edu/) (See here (http://www5.cs.cornell.edu/cgi-bin/andru/civs/results?id=E_614716deda9a4073)!)
  14. the College of Science Students' Advisory Council (COSSAC) (http://www.google.com/search?q=cache:_gIgJxS77egJ:www.buckyball.org/mediaWiki/index.php%3Ftitle%3DCOSSAC_Constitution+condorcet+cossac+beatpath+SSD+%22schwartz+sequential+dropping%22&hl=en)
  15. the NationStates Wiki (NSwiki) (http://ns.goobergunch.net/wiki/index.php/Main_Page) project (See here (http://ns.goobergunch.net/wiki/index.php/NSwiki:Logo_candidates/Vote)!)
  16. the Sparta Wiki (http://varasa.homeunix.org:8088/~mjb/pmwiki/pmwiki.php/Main/HomePage) project
  17. the Wikipedia project to establish a consensus (See e.g. here and here!)
  18. the Five-Second Crossword Competition (FSCC) (http://www.rsabey.pwp.blueyonder.co.uk/rpc/fscc/) (See here  (http://www.rsabey.pwp.blueyonder.co.uk/rpc/home/elect.html)!)

Furthermore, the fact that CSSD is a part of Debian's voting software ("Debian Vote Engine", Devotee) means that it is the standard voting system in all Debian user groups (DUGs). Debian, created by the Debian Project, is a widely used distribution of free software developed through the collaboration of volunteers from around the world. ... Software in the Public Interest, Inc. ... UserLinux is a Linux distribution that aims to provide businesses with a freely available, high quality operating system accompanied by certifications, service, and support options designed to encourage productivity and security while reducing overall costs. ... Wikipedia is a Web-based, free-content encyclopedia, which is written collaboratively by volunteers. ... Debian, created by the Debian Project, is a widely used distribution of free software developed through the collaboration of volunteers from around the world. ...


External resources

  1. A New Monotonic and Clone-Independent Single-Winner Election Method (http://www.mcs.vuw.ac.nz/~ncj/comp303/schulze.pdf) by Markus Schulze ( mirror1 (http://www.citizensassembly.bc.ca/resources/submissions/csharman-10_0409201706-143.pdf), mirror2 (http://lists.gnu.org/archive/html/demexp-dev/2003-09/pdflQW7IlpAfC.pdf))
  2. Descriptions of ranked-ballot voting methods (http://cec.wustl.edu/~rhl1/rbvote/desc.html) where CSSD is called "Schulze"
  3. Election Methods Resource (http://www.condorcet.org/emr/index.shtml) where CSSD is called "Schulze"
  4. Election Systems (http://www.ghg.net/redflame/peter/swuusi.pdf) where CSSD is called "Schulze's Beatpath Method"
  5. The Maximize Affirmed Majorities voting procedure (MAM) (http://www.alumni.caltech.edu/~seppley) where CSSD is called "Path Winner"
  6. Voting Calculator (http://condorcet.ericgorr.net) where CSSD is called "Beatpath Winner"
  7. Condorcet Internet Voting Service (http://www5.cs.cornell.edu/~andru/civs/) where CSSD is called "Beatpath Winner"
  8. The Debian Voting System (http://seehuhn.de/comp/vote.html)
  9. A Survey of Basic Voting Methods (http://fc.antioch.edu/~james_green-armytage/vm/survey.htm) where CSSD is also called "Schwartz Sequential Dropping" and "Schulze"
  10. electionmethods.org where CSSD is also called "Schwartz Sequential Dropping" and "Beatpath Winner"
  11. Single-Winner Methods (http://www.barnsdle.demon.co.uk/vote/sing.html) where CSSD is also called "Schwartz Sequential Dropping" and "Beatpath Winner"
  12. Accurate Democracy (http://accuratedemocracy.com/voting_rules.htm) where CSSD is called "Schwartz Sequential Dropping", "Beatpath" and "Schulze"
  13. A mailing list containing technical discussions about election methods (http://lists.electorama.com/pipermail/election-methods-electorama.com/)

  Results from FactBites:
 
A Survey of Basic Voting Methods (6352 words)
Sequential dropping may be the reasonably good base method that is easiest to define and explain.
Next it drops the weakest defeat, that is, it replaces the weakest defeat with a pairwise tie.
CSSD proceeds by dropping the weakest defeat, which is T’s 7-5 defeat over R. Now the new Schwartz set consists only of A and R, as both are minimal undominated sets in themselves.
Cloneproof Schwartz Sequential Dropping - InformationBlast (613 words)
Cloneproof Schwartz Sequential Dropping (CSSD) is a voting method developed by Markus Schulze that selects a single winner using votes that express preferences.
CSSD is also known as "Schwartz Sequential Dropping", "Beatpath Method", "Beatpath Winner", "Path Voting", "Path Winner", and "Schulze Method".
CSSD uses Condorocet pairwise matchups between the candidates and a winner is chosen in each of the matchups.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m