'Concorde' Voting Method and Circular Ties
On Sun, June 11, 2000 at 4:05 PM, I wrote:
>
>The tiebreaker specified in A.6.5 also needs some work, but I won't go into
>that now :-)
On Mon, June 12, 2000 at 3:59 PM, Darren O. Benham wrote:
>
>In the end, it takes a lot to change our constitution and I fail to see
what
>would be gained.
>
Well, since you asked...
To understand the problem with Debian's existing voting method, it's useful
to know some of the history of pairwise voting. I'll present that first,
but feel free to skip it if you already know this stuff (this is a longish
post).
Pairwise Voting and Ranked Ballots
Debian's 'Concorde' voting method belongs to a family of 'pairwise' voting
methods that were invented by the Marquis de Condorcet, an 18th century
French mathematician. He argued that when there are a number of options to
choose from in an election, the winner should be that option which beats
every alternative in a series of two-way contests. This ensures that the
winning option is genuinely preferred by a majority of voters to all the
other contenders. Unfortunately, it would be very tedious/impractical to
hold a series of separate two-way elections between all the available
options, since the number of elections needed is equal to the square of the
number of options under consideration (10 options -> 100 elections).
However, if one assumes that the relative preferences of individual voters
are transitive (that is, if a voter prefers A to B, and B to C, this also
implies s/he prefers A to C), it is possible to use a single ranked ballot
to gather the necessary information from each voter. The pairwise votes can
then be derived mechanically from the ranked ballots. Assuming voters are
rational (and why hold elections at all if you assume they are not?), this
is a reasonable assumption to make, and it allows pairwise methods to be a
practical way of choosing a single winner from many alternatives.
Social Ranking not necessarily Transitive
It's natural to suppose that what's true for individual voters would also be
true for an entire electorate; namely, that it should be possible to create
an unambiguous 'social ranking' of all the options which reflects the
relative preferences of the group, and that this social ranking would also
be transitive. It turns out, however that this intuition is not correct.
While carrying out research on pairwise methods, Condorcet discovered what
we now refer to as "Condorcet's paradox". He showed that contrary to
expectation, the opinions of majorities are *not* always transitive. Even
when we have an electorate composed of rational individuals, each expressing
transitive preferences between options in an election, the majority opinions
may not be transitive -- that is, if a majority prefers option A to option B
(A>B) and a majority prefers option B to option C (B>C) it is NOT
NECESSARILY TRUE that a majority will prefer option A to option C (A>C).
Consider the following example:
90 voters, 3 options {A,B,C}.
25 vote A>B>C
30 vote B>C>A
35 vote C>A>B
where '>' is used to mean 'is preferred to' (in Debian's notation, this
would be 25*[123], 30*[312], 35*[231]). If we try to find the winner of
this election using the procedure specified in Debian's Constitution, we
first determine which options are dominated:
"A.6.2 Option A is said to Dominate option B if strictly more ballots
prefer A to B than prefer B to A."
Applying this rule, we get:
A dominates B, 60:30
B dominates C, 55:35
C dominates A, 65:25
To determine winners, we apply the following rules:
"A.6.3 All options which are Dominated by at least one other option are
discarded, and references to them in ballot papers will be ignored.
A.6.4 If there is any option which Dominates all others then that is the
winner."
Hmmm... *all* the options are dominated by at least one other option, so
according to A.6.3, they must be removed from the election (unfortunately,
leaving us with no eligible options!). Also, A.6.4 cannot be met, since
there is not an option which dominates all the others. Perhaps the
tiebreaker specified in A.6.5 will help?
"A.6.5 If there is now more than one option remaining Single Transferable
Vote will be applied to choose amongst those remaining: ..."
Nope. Since their are *no* options remaining at this point, the tiebreaker
is useless and cannot resolve the issue. It is likely that when this rule
was devised, the above situation was not considered possible, and that only
simple ties like "A ties B, 45:45" would be encountered. A.6.5 *can* help
resolve these types of ties, since neither A nor B have been dominated in
this situation, and are therefore still eligible for election. This strange
"circular tie" confounds Debian's rules. The only remaining hope is for
A.6.6:
"A.6.6 In the case of ties the elector with a casting vote will decide. The
casting vote does not count as a normal vote; however that elector will
usually also get a normal vote."
While it is arguable that this rule could be used to resolve the issue if
one regards the voting cycle (A>B>C>A>B>...) as a "tie", it is also arguable
that the rule doesn't apply at all, since there are no eligible options from
which to pick. I suspect that A.6.6 was intended as a final tiebreaker in
case the Single Transferable Vote method described in A.6.5 was unable to
break a tie among the eligible options, and that there would be some
opposition if the DPL were to rely on this rule to choose one of the
'dominated' options {A,B,C}.
Because of Condorcet's paradox, some change to Debian's "Concorde Vote
Counting" procedure is needed to handle this situation in a satisfactory
manner. It would be wise to formally revise the method to resolve this
potential problem in advance, while the available solutions can still be
considered in an objective and disinterested way. If this is not done, I
can imagine what might happen when a voting cycle is first encountered under
Debian's current rules:
1) At first, there will be considerable bafflement, with people amazed that
their system of voting could produce such a bizarre result. Some people
might call for the entire system to be replaced with a system that's more
familiar (such as plurality/"first-past-the-post") that doesn't seem to have
this problem (neglecting the fact that these alternatives also have much
more severe problems).
2) People will start trying to determine which option *should* win the
election, and if the issue is important enough, they will tend to advocate
solutions that will pick the winner they personally prefer. The rationale
given for picking *any* particular winner can be made to sound plausible.
For example, you might hear:
- "I think option X should be chosen, since choosing X would be opposed by
the fewest number of voters, and is therefore the most acceptable choice."
- "I think Y should be elected, because Y dominated more options than any of
the alternatives."
- "I think we should choose randomly. *All* the options have been
dominated, so they are all equally good/bad."
- "Option Z should win because it was the first choice of the largest number
of voters."
ad infinitum...
The fact is, that some of the above ideas are fairly good, others are quite
bad, and none of these tiebreakers are as good as some of the methods that
have been developed and extensively studied elsewhere (such as on the EM
list, or in the academic Social Choice literature). The main problem will
be that even if someone within Debian proposes a good tiebreaker, it might
be seen as being advocated for the wrong reasons. The tiebreaker that gets
adopted under such circumstances is unlikely to be a good choice in the
long-term, and the surrounding controversy could be needlessly divisive.
By now, you may be wondering how serious a problem this is likely to be in
practice. Changing Debian's constitution might seem to require more effort
than is justified by this rather minor problem -- after all, in Debian's
entire history, there has never been a voting cycle, so this might not be
all that important. It may be that you will be lucky and *never* encounter
Condorcet's paradox, especially since Debian developers don't use the voting
system very often. However, I have carried out some simulations of pairwise
methods which show that circular ties will occur naturally about 5% of the
time. This is a small but significant proportion of elections -- if
Debian's results are similar to the model, you can expect to encounter a
circular tie about once every 20 elections or so, on average, so I
personally think that it *will* happen within the Debian project sometime
within the next few years.
The main problem with Debian's current rules are that they are indecisive
when confronted with a circular tie; there is also the minor problem I
mentioned earlier about unstated assumptions in the interpretation of
truncated ballots. Since the problem of indecisive rules cannot be solved
without amending the Constitution, it makes sense to carefully choose one of
the better methods of resolving ties. A wide range of tiebreakers are
available to solve this problem, but they vary significantly in quality and
it is difficult to make good choices from among the available options
without thorough study. Members of the Election Methods list (Mike
Ossipoff, myself and others) have studied this problem extensively, and we
would be pleased to provide you with a specific recommendation as to how the
problem would be best solved. As well, Rob Lanphier (a software developer
who operates the EM list) and I have both developed GPLed implementations of
our preferred methods in both Perl and Python that could probably be adapted
to your existing system of vote-counting, if a constitutional amendment is
approved.
If you or any other Debian developers agree that this is a problem that
should be fixed, please contact either me or Mike Ossipoff, and we will help
you choose a suitable tiebreaker and develop the wording for a proposed
constitutional amendment that would implement the changes. We have already
discussed the matter amongst ourselves, and have selected one or two
first-rate methods that we would recommend for Debian, as well as some
simpler approaches that would probably also be adequate. It would probably
be best if one or two interested Debian members discuss this matter with us
privately, and help us develop a single, polished proposal that could then
be taken back to Debian as a whole for consideration (to avoid boring
everyone here with a subject that's probably not of much interest or direct
relevance to the Debian project).
Please let us know if you are interested in working on this.
Sincerely,
Norman Petry
Reply to: