The Debian Voting System

By , last updated .

Contents

Introduction

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.

Description of the Debian Voting System

Introduction to Condorcet voting

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.

[example vote graph]

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]

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.

Good properties of Condorcet voting

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 the clone-proof version. The clone-proof version gives no group or party any advantage or disadvantage for having additional candidates that are essentially clones of each other. Except for the case of ties, the two versions give the same result.

Debian modifications of Condorcet voting

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

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.

Examples

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

Implementation

There are some implementations of the Condorcet voting algorithm:

Further Reading