From electowiki
See also
2003 Debian Project Leader Election

The following essay is a restoration of a post that I made in April 2003 to This article was restored from the snapshot.

If Debian used Instant Runoff...

Posted Apr 20, 2003 - 01:47 AM by robla

The last Debian Project Leader election was a very close one. Martin Michlmayr won a Condorcet-tallied election in a very close race between him, Bdale Garbee (the incumbent), and Branden Robinson. Doing analysis on these result yields some interesting observations. Among the most surprising is that Branden Robinson would have won had San Francisco's rules for Instant Runoff Voting been used.

I can't say I'm very close to the Debian development process. I used to use a Debian box as my primary home desktop, I wrote one of the scripts that are used to tally the elections, and Electorama is run from a Debian-based ISP. However, I can't say I'm very familiar with the individual candidates and the differences in their platforms. The conclusions I draw below are drawn from the data itself, and not from any insight (or lack thereof) in any external factors.
First, I set about creating a table of first place voters, and what their second choice was. What complicates this is that the ballot allows for multiple first choices. Relatively few Debian developers did this though. Thus, Table 1 contains most of the voters (453 of the 488 total votes). (Please pardon my informality in referring to the candidates by first's not that I'm all chummy with any of them, it's just that they were generally easier to spell/remember than their last names) :-)

Table 1: Voters with one first choice, and what their second choice was

One first place vote 453 Second Place
Moshe Bdale Branden Martin NOTA Multiple
Moshe Zadka 10 n/a 2 1 6 0 1
Bdale Garbee 143 6 n/a 54 67 7 9
Branden Robinson 158 2 68 n/a 65 8 15
Martin Michlmayr 140 7 69 48 n/a 3 13
None of the above (NOTA) 2 1 0 0 0 n/a 1

The first thing you might notice is that Branden Robinson had the most first place votes. The 158 exclusive first place votes he received were 32.4% of the total vote. Short of any sort of tactical voting by supporters of the other candidates, Branden would have won under the First Past the Post electoral system.

Generally speaking, the first choice is not a strong indicator of who the second choice will be (at least, of the three leading candidates). However, there is seems to be a preference toward Martin Michlmayr among Bdale Garbee voters, and vice versa. This would help explain why Branden Robinson lost, despite the strongest core of first place votes.

For sake of completeness, I've also included a breakdown of what those that voted for multiple candidates as their first choice (Table 2).

Table 2: Voters with multiple first choice

Multiple firsts 35
Bdale/Martin 12
Branden/Martin 11
Bdale/Branden 8
Moshe/Bdale/Branden/Martin 1
Bdale/Branden/Martin 1
Moshe/Martin 1
Branden/NOTA 1

Not much to say here really, since it's such a small set of voters. Moreover, all three pairings of top candidates appear in roughly equal numbers, with a handful of uncommon combinations.
Where things start getting interesting is where you start looking at how the election would have gone had it been tallied using Instant-runoff voting. First, we'll look at the results as tallied allowing for ballots with tied preferences (Table 3).

Table 3: IRV Tally, allowing for ballots with tied preferences

1st 2nd 3rd 4th Winner
Moshe Zadka 12 14

Bdale Garbee 165 166 170

Branden Robinson 180 181 183 251
Martin Michlmayr 166 167 174 262 262
None of the above (NOTA) 3 n/a

Martin Michlmayr wins this election, too. However, this victory is achieved by allowing all ballots, and treating ties for first place as a vote for both candidates. Some would call this cheating, others would observe the similarity between this and Approval voting. Regardless, this is not how Instant Runoff is generally done.

The way that Instant Runoff is generally done is by eliminating ballots that have duplicate rankings at the point where the duplicate ranking is being considered. The Center for Voting and Democracy has an explanation of how this works as part of their recommended implementation policy.

Following through on the recommendations there, we get the results as described in Table 4.

Table 4: IRV Tally, using technique implemented in San Francisco

1st 2nd 3rd Winner
Qualifying bal. 453 452 451
Moshe Zadka 10 11

Bdale Garbee 143 143 146
Branden Robinson 158 158 159 159
Martin Michlmayr 140 140 146

Using these rules, Branden Robinson wins the election. However, this is because of a bit of a quirk in the rules. In the event of a last-place tie, both candidates are eliminated (even in this case where this represents a majority of the votes). All it takes is to remove one ballot to completely change the result of the election. For example, let's remove the ballot expressed in the posted results as "V: 41325". Expanded out, this is the list of preferences expressed:

  1. Bdale Garbee
  2. Martin Michlmayr
  3. Branden Robinson
  4. Moshe Zadka
  5. None of the above

Table 5 shows the results of such an election.

Table 5: IRV Tally minus Bdale/Martin/Branden/Moshe vote

1st 2nd 3rd 4th Winner
Qualifying bal. 452 451 450 440
Moshe Zadka 10 11

Bdale Garbee 142 142 145

Branden Robinson 158 158 159 217
Martin Michlmayr 140 140 146 223 223
None of the above (NOTA) 2

By breaking the tie in the third round, Martin Michlmayr narrowly avoids getting knocked out of the third round, and goes on to beat Branden Robinson in the fourth round. This despite the fact that the ballot eliminated actually ranks Martin Michlmayr higher than Branden Robinson.

Of course, this cuts both ways. Eliminating a different ballot yields yet another result. Let's eliminate a ballot marked "V: 43215" instead, which is equivalent to the following preferences:

  1. Martin Michlmayr
  2. Bdale Garbee
  3. Branden Robinson
  4. Moshe Zadka
  5. None of the above

Table 6 shows the new results

Table 6: IRV Tally minus Martin/Bdale/Branden/Moshe vote

1st 2nd 3rd 4th Winner
Qualifying bal. 452 451 450 433
Moshe Zadka 10 11

Bdale Garbee 142 142 146 224 224
Branden Robinson 158 158 159 209
Martin Michlmayr 139 139 145
None of the above (NOTA) 2

This time, the third round tie is broken, instead going in favor of Bdale Garbee. Now it's Bdale Garbee who avoids getting knocked out of the third round, and goes on to beat Branden Robinson in the fourth round. Once again, this is despite the fact that the ballot eliminated actually ranks Bdale Garbee higher than Branden Robinson.

I'd appreciate someone checking my work. I did a lot of this only semi-automatically, constructing kludgy little command lines involving perl, cut, grep, and wc. I've tried to be reasonably careful, but this is clearly a dangling chad kinda situation.

I found this exercise very fascinating, because it was the first actual election for which the Condorcet and Instant Runoff results were different. Of course, voters would have probably been careful to avoid duplicate rankings if they knew that such rankings disqualified their ballots. In the election the ballots were applied to, duplicate rankings were expected and welcomed.

Nonetheless, the wide varieties of outcomes based on altering a single ballot was a pretty surprising result. This exercise shows one weakness of Instant Runoff, which is the arbitrary nature of the elimination process. It also should make the Debian folks glad that they are using Condorcet. :-)