MP in Action‎ > ‎Related Techniques‎ > ‎

If you can't Win an Election ... Change the Voting Rules!

This article is based on a talk given by Dr Mike Trick of Carnegie Mellon University, Pittsburgh to the Mathematical Programming Study Group.

With the Conservative Party leadership election in full swing, the Mathematical Programming Study Group had a meeting on the highly topical subject of voting systems. How the winner of an election is determined can have a very large effect on who the winner is, and not just because of tactical voting. This has been the research interest of Mike Trick for some years and he provided an entertaining tour of the subject.

Who Wins? He Who Chooses the Voting Rule

Consider this example. There are 5 candidates and 9 voters with these preferences:

4 voters: d b a | c e
3 voters: e c | b a d
2 voters: c a | b e d

where the '|' separates those candidates of whom the voter approves from those of whom he does not.

The winner is:

  • a with approval voting (each voter can vote for as many candidates as he wishes);
  • b with Borda count voting (5 points to your first choice, 4 to your second, ..., 1 to your last choice);
  • c with Condorcet voting (consider each pair of candidates x and y; the Condorcet winner is the candidate x such that for each y the number of voters who prefer x to y exceeds those preferring y to x; such a Condorcet winner may not exist);
  • d with first-past-the-post voting (one vote per person, the winner is the candidate with the highest number of votes);
  • e with single voting plus runoff (one vote per person; if no candidate wins a majority of the votes cast there is a runoff between the candidates with the two highest scores).

Who Wins? He Who Chooses the Voting Rule

Consider this example. There are 5 candidates and 9 voters with these preferences:

4 voters: d b a | c e
3 voters: e c | b a d
2 voters: c a | b e d

where the '|' separates those candidates of whom the voter approves from those of whom he does not.

The winner is:

  • a with approval voting (each voter can vote for as many candidates as he wishes);
  • b with Borda count voting (5 points to your first choice, 4 to your second, ..., 1 to your last choice);
  • c with Condorcet voting (consider each pair of candidates x and y; the Condorcet winner is the candidate x such that for each y the number of voters who prefer x to y exceeds those preferring y to x; such a Condorcet winner may not exist);
  • d with first-past-the-post voting (one vote per person, the winner is the candidate with the highest number of votes);
  • e with single voting plus runoff (one vote per person; if no candidate wins a majority of the votes cast there is a runoff between the candidates with the two highest scores).

Who Determines the Result? He Who Comes Last

Or consider this. Suppose there are 3 candidates and 17 voters whose preferences are:

6 voters: a b c
5 voters: c a b
4 voters: b c a
2 voters: b a c

With single voting plus runoff the runoff is between a and b, which a wins. If the 2 voters with preference b a c change their first preference from b to a what will happen? As the question is being posed, the answer is obviously not what you might expect. It causes the runoff to be between a and c, which c wins. Thus an increase in votes for the leading candidate in a French presidential election may cause him to lose the election.

Suppose there are 4 candidates and 7 voters with Borda count voting:

3 voters: c b a x
2 voters: b a x c
2 voters: a x c b

The result is a > b > c > x. If x drops out (because he recognises he is last) the votes become:

3 voters: c b a
2 voters: b a c
2 voters: a c b

and the result is c > b > a, i.e. the ordering reverses.

Formalization of Fairness

These examples show the need to have some criteria by which to assess the fairness of voting systems. Possible criteria include:

  • Pareto principle: if every voter prefers x to y then the voting rule should prefer x to y;
  • Condorcet winner criterion: if x would win against every other candidate y in a pairwise contest, then x is the winner;
  • monotonicity: if the voting rule would choose x and x moves up some voter's ranking, then x remains the winner;
  • neutrality: the names of the candidates do not affect the result;
  • independence of irrelevant alternatives: if x is the winner and another candidate is added whom no one prefers, then x remains the winner.

One might think that a voting system could be designed to satisfy most, if not all of these. Unfortunately Arrow's Theorem states that:

The only voting system which simultaneously satisfies:

  • unlimited scope;
  • Pareto principle;
  • independence of irrelevant alternatives;

is dictatorship (i.e. a single voter makes the decision).

It follows that voting systems can only satisfy a weak sense of fairness.

Can we Find the Winner?

Another desirable characteristic of a voting system is that it should be easy to determine the winner. This may be expressed mathematically by considering how many calculations must be performed and how this number varies as the number of candidates, C, and the number of voters, V, increase.

First-past-the-post voting is easiest, with the number of calculations being at worst proportional to V. Borda and approval voting have the worst-case number of calculations proportional to VC while Condorcet voting has it proportional to C2V.

As we are beginning to discover, there is no such thing as a free lunch with voting rules. There is a theorem which states:

Any voting procedure which is:

  • of unlimited scope;
  • anonymous;
  • consistent (i.e. if 2 subsets of voters agree on A, then so does their union);

has the worst-case number of calculations non-polynomial in C.

An example of a voting rule whose number of calculations is non-polynomial in C was devised by Charles Dodgson (Lewis Carroll) to enable him to win an election at Oxford:

If there is a Condorcet winner, he is the winner. Otherwise the winner is the candidate who would become the Condorcet winner with the smallest number of interchanges of preferences.

Tactical Voting Works

John Major might ponder the Gibbard-Satterthwaite Theorem:

Every voting rule is susceptible to false preferences.

In other words, tactical voting works. One voting rule which is less susceptible than most is the Single Transferable Vote. This exists in several forms and is used in parliamentary elections in Ireland. It is used in multi-member constituencies with each voter submitting his order of preferences for the candidates. Reallocation of votes takes place:

  • from elected candidates to the remaining contenders;
  • from weaker to stronger candidates.

It tends to achieve proportional representation but encourages people not to vote for the top candidates.

Finally, the Advantage of Setting the Agenda

A final aspect of voting is that even with no knowledge of the participants' preferences, it is possible to influence the outcome by setting the order of items on the agenda.

Suppose there are 3 candidates a, b and c and that as Chairman I prefer a. Then I should set the agenda as ((b vs c) vs a), i.e. first consider candidate b against c and then set the winner of that against a. We may represent this agenda by the tree:

If there is a Condorcet winner, he will win irrespective of the agenda. But if there is no Condorcet winner, i.e. there is a cycle of preferences a > b > c > a (i.e. a is preferred to b who is preferred to c who is preferred to a) or a > c > b > a , then this agenda will result in a's declaration as the winner.

What if there are 4 candidates? How can I as Chairman help my candidate a? A scheme such as:

is of some assistance. But it favours d over b and c, so if d is preferred to a whereas b or c is not, then a loses. This would happen, for instance if there were the cycle a > b > c > d > a and in addition d > b and c > a. If we knew people's voting intentions in advance we could reorder the agenda to:

Can we do better with no prior knowledge of people's voting intentions? Yes we can. It can be proved that there is a best agenda for 4 candidates. It is:

If you try this with the example you will find that a does indeed win. Now you know why parliamentary proceedings are so tortuous!

To find other articles, refer to the MP in Action page.

Comments