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 where the '|' separates those candidates of whom the voter approves from those of whom he does not. The winner is:
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 where the '|' separates those candidates of whom the voter approves from those of whom he does not. The winner is:
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 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 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 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:
One might think that a voting system could be designed to satisfy most, if not all of these. Unfortunately Arrow's Theorem states that:
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 V^{C} while Condorcet voting has it proportional to C^{2}V. As we are beginning to discover, there is no such thing as a free lunch with voting rules. There is a theorem which states:
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:
Tactical Voting Works John Major might ponder the Gibbard-Satterthwaite Theorem:
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:
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. |
MP in Action > Related Techniques >