User:RobLa/Debian2003

See also
2003 Debian Project Leader Election

The following essay is a restoration of a post that I made in April 2003 to Electorama.com. This article was restored from the archive.org 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 name...it'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
NOTA	2

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. :-)