![[example vote graph]](https://m.seehuhn.de/image/vote001-0118.png)
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.
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 B over both
A and C, but I have no preference among the options A
and C
. (For the mathematically inclined reader: a vote is a
partial order on the set of options).
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.
![[example vote graph with one edge removed]](https://m.seehuhn.de/image/vote002-0118.png)
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):
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.
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.
Condorcet voting with Clone-proof Schwartz sequential dropping additionally has the following property (summarised from http://electionmethods.org/CondorcetEx.htm):
plainversion and the
clone-proofversion. The clone-proof version gives no group or party any advantage or disadvantage for having additional candidates that are essentially
clonesof 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:
None Of The Aboveor
Further discussion.
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.
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 are some implementations of the Condorcet voting algorithm:
feature columnabout Voting and Elections.
Copyright © 2012 Jochen Voss. All content on this website (including text, pictures, and any other original works), unless otherwise noted, is licensed under the CC BY-SA 4.0 license.