Profile of the Boot Process of a Debian System. Profile of the Boot Process of a Debian System, generated using a custom Python script. … read more

Per-option quorum. Analysis of per option quorum conditions for the Debian voting system. … read more

Quorum in the Debian Voting System. The use of quorum requirements in the Debian Voting System … read more

By Jochen Voss, last updated 2012-02-18

The Debian Project uses an
interesting voting system to make formal decisions. This system is, for
example, used to determine the Debian Project Leader or to determine the
outcome of general resolutions

of the project. Information about
past votes and about how to initiate new votes can be found at the
Debian Voting Information page.
Current votes, properties of the voting system, and related topics are
discussed at the
debian-vote mailing
list.

The authoritative description of the Debian voting system is contained in the Debian constitution. The present text tries to give a less formal and more accessible description of the voting system. Please direct any comments or questions about this article to Jochen Voss.

The voting system used in the Debian project is a modification of the Condorcet Voting System with Schwartz Sequential Dropping. This voting system is named after Marie Jean Antoine Nicolas de Caritat Condorcet, an 18th century French mathematician. His most important work was on probability and the philosophy of mathematics. The Condorcet voting system, together with some other voting systems, is discussed at the electionmethods.org web site. In the following paragraphs I give a short description of the system. An alternate description can be found at the Condorcet Voting Explained page.

There is a list of available options. I will denote these by the
uppercase letters *A*, *B*, *C*, …; here. Each voter
ranks these option in order of preferences. The order does not need to be
complete. Example: a valid vote would be I prefer

. (For the mathematically inclined reader: a vote is a
partial order on the set of options).*B* over both
*A* and *C*, but I have no preference among the options *A*
and *C*

For each pair *X* and *Y* of options we count how many voters
prefer *X* over *Y* and how many voters prefer *Y* over
*X*. If the first number is larger, then *X* defeats *Y*;
if the second number is larger, *Y* defeats *X*; if both numbers
are equal, there is a tie. We can construct a graph from this information
as follows: the options are the vertices, and whenever *X* defeats
*Y* we add an edge from *X* to *Y*. An example graph
is shown in figure 1. Note that the graph can
have several unconnected components and there may be cycles in this graph.
In the example *A*, *B*, and *C* form a cycle. It is easy
to see that there is always at least one cycle or single element, which is
not defeated by other options. The collection of all these elements is
called the Schwartz set. The Schwartz set in the
example consists of the options *A*, *B*, *C*,
and *E*. For a large number of voters there will typically be no
cycles or isolated elements in the graph and the Schwartz set will
typically consist of a single element.

Figure 1. *A* beats *B*, *B*
beats *C*, *C* beats *A*, *B* and *C* beat
*D*. Nobody has an opinion about E. The Schwartz set consists of the
options *A*, *B*, *C*, and *E*.

If there are cycles in the Schwartz set, we remove edges from the graph
to break these up. Since removing an edge corresponds to ignoring some
votes, we remove the edge where the number of ignored votes is minimal,
i.e. the edge *X*→*Y* where the
number of votes which prefer *X* over *Y* is minimal. If there
are several edges with this number of votes, they are all removed at once.
Removing edges can make the Schwartz set smaller. We repeat this procedure
until the Schwartz set contains no more cycles. Assume that for our
example from figure 1 the removed edge turns out to be
*C*→*A*. Then we get the new graph shown in
figure 2. The Schwartz set is now reduced to
options *A* and *E* and does no longer contain cycles.

Figure 2. After removing the edge
*C*→*A* the vote graph contains no more cycles. The
Schwartz set now consists of the options *A* and *E*.

After we have broken up all cycles, the Schwartz set consists of isolated points only. The corresponding options are the winners of the election. Typically there is only one winner. In the very rare case that the final Schwartz set contains more than one element, some additional method is needed to determine the winner. For the Debian voting system the voter with the casting vote (the project leader or the chairman of the Technical Committee) decides in this case.

An obvious question is why one would use such a complicated voting system. The answer is twofold: firstly, Condorcet voting is better than other voting systems. This is explained below. And, secondly, in actual use the system isn't really that complicated: The voter only has to rank the available options and even may rank options equal. For elections with many voters the only complicated step in determining the winner (the tie resolution mechanism) is almost never used because ties have a very low probability.

Good properties of Condorcet voting (summarised from http://electionmethods.org/evaluation.htm):

- Monotonicity Criterion (MC)
- With the relative order or rating of the other candidates unchanged, voting a candidate higher will never cause the candidate to lose, nor will voting a candidate lower ever cause the candidate to win.
- Condorcet Criterion (CC)
- If one candidate is preferred over each of the other candidates, that candidate is the Ideal Democratic Winner (IDW). If all votes are sincere, the Ideal Democratic Winner will win if one exists.
- Generalised Condorcet Criterion (GCC)
- If all votes are sincere, the winner is a member of the Smith set.
The Smith set is the smallest set of candidates such that every member of the set is preferred to every candidate not in the set.

- Strategy-Free Criterion (SFC)
- If an Ideal Democratic Winner exists, and if a majority prefers the
IDW to another candidate, then the other candidate will not win if that
majority votes sincerely and no other voter falsifies any preferences.
Note: sometimes (When good options are ranked equal) there can be an IDW which is not preferred by a majority of voters over some other candidate.

- Generalised Strategy-Free Criterion (GSFC)
- If a majority prefers a member of the Smith set to another candidate who is not in the Smith set, then the other candidate will not win if that majority votes sincerely and no other voter falsifies any preferences.
- Strong Defensive Strategy Criterion (SDSC)
- If a majority prefers one particular candidate to another, then they have a way of voting that will ensure that the other cannot win, without any member of that majority reversing a preference for one candidate over another or falsely voting two candidates equal.
- Weak Defensive Strategy Criterion (WDSC)
- If a majority prefers one particular candidate to another, then they have a way of voting that will ensure that the other cannot win, without any member of that majority reversing a preference for one candidate over another.

Condorcet voting with Clone-proof Schwartz sequential dropping additionally has the following property (summarised from http://electionmethods.org/CondorcetEx.htm):

- Clone-proof Criterion
- The Schwartz Sequential Dropping (SSD) method has a
plain

version and theclone-proof

version. The clone-proof version gives no group or party any advantage or disadvantage for having additional candidates that are essentiallyclones

of each other. Except for the case of ties, the two versions give the same result.

The Debian voting system differs from plain Condorcet voting in several points:

- It introduces the concept of a default option.
This option is either
None Of The Above

orFurther discussion

. - It introduces the concept of a
per-option quorum. The reason for the introduction
of this per-option quorum (cited from Buddha Buck's
summary of the rationale for the general resolution)
is as follows:
The proposers of this amendment also feel that it is worthy to drop from consideration any other option that is not approved by a minimum number of voters or has more not-approved votes than approved votes. Only votes that have a minimum number of approved votes and are approved by more people than don't approve it are considered in the cSSD process.

The effects of this change are studied in detail on my Quorum in the Debian Voting System page. - It introduces the concept of a super-majority. Super-majority requirements should assure that even a minority of electors can inhibit some fundamental decisions. This is used as a special protection for the Debian constitution.
- It somewhat restricts the way the voter can express his preferences.
Currently with the Debian voting system there is no way to vote
I prefer

.*A*over*B*, and*C*over*D*, but I have no further opinion

The implementation of quorum and supermajorities sacrifices most of the good properties of the Condorcet voting system, but a majority of Debian developers seems to think that this implementation has benefits which outweigh the loss of these properties.

On separate pages I provide more examples which might help to illustrate the Debian voting system:

- There is a page about the Debian General Resolution GR2004-004.
- The Quorum in the Debian Voting System page contains many constructed examples.

There are some implementations of the Condorcet voting algorithm:

- The official debian voting system devotee is maintained by Manoj Srivastava. He publishes his scripts in an arch repository. You probably need the arch revision control system to make use of this.
- I wrote an independent implementation of the
algorithm used in the Debian voting system. The program can read the
official tally files.
- debian-vote version 0.8, 2008-12-20
- archive: debian-vote-0.8.tar.gz (66KB)

signature: debian-vote-0.8.tar.gz.asc

sha1: 928b91e321230f28bea7d6de1727ad81c9b864da

md5: 216282debefb9358b008777280fe3094

- archive: debian-vote-0.8.tar.gz (66KB)
- debian-vote version 0.7, 2005-04-11
- archive: debian-vote-0.7.tar.gz (55KB)

signature: debian-vote-0.7.tar.gz.sig

sha1: f75e188f9d1b93640c2a456fe6be73da25c226b9

md5: 7a2ae6b24c98a89a212d006897698d88

- archive: debian-vote-0.7.tar.gz (55KB)

- There is an implementation of the original Condorcet algorithm with Clone-proof Schwartz Sequential Dropping near the bottom of electionmethods.org's Condorcet voting page.
- Andrew Myers' Condorcet Internet Voting Service helps you to perform your own votes.

- Wikipedia has an entry about Condorcet voting
- The American Mathematical Society has a
feature column

about Voting and Elections. - Elections: Results and Voting systems by David Barnsdale
- A Glossary for Democracy
- the Debian Voting Information page

Copyright © 2012, Jochen Voss. All content on this website (including text, pictures, and any other original works), unless otherwise noted, is licensed under a Creative Commons Attribution-Share Alike 3.0 License.