ThatsMaths

Selection of leaders by voting has a history reaching back to the Athenian democracy. Elections are essentially arithmetical exercises, but they involve more than simple counting, and have some subtle mathematical aspects [TM085, or search for “thatsmaths” at irishtimes.com].

Rock-paper-scissors, a zero-sum game. There is a cyclic relationship: rock beats paper, paper beats scissors and scissors beats rock [Image: Wikimedia Commons].

The scientific study of voting and elections, which began around the time of the French Revolution, is called Psephology, from the Greek word psephos, a pebble: pebbles were used as counting tallies in ancient times.

The Marquis de Condorcet, a French philosopher, mathematician and political scientist, was one of the founders of the mathematical theory of voting. He had studied under the renowned mathematician d’Alembert and he wrote several books on mathematics. He discovered a counter-intuitive result now called Condorcet’s paradox.

Suppose we have three candidates, Alice, Bob and Chris (A, B and C). If a majority of voters prefer A to B, and a majority prefer B to C, then it would appear obvious that there must be a majority who prefer A to C. This combination of two results is known as transitivity. But Condorcet showed that it may fail to hold. It is possible that more prefer C to A, resulting in a cycle of preferences, A before B before C before A. This is reminiscent of the game Rock-Paper-Scissors, where each choice wins over a second but loses to the third option. A concrete example of Condorcet’s paradox is given below.

Marquis de Condorcet (1743-1794)

During the turbulent French Revolution, Condorcet fled Paris to avoid capture and possible execution. Stopping at an inn, he betrayed his aristocratic status by ordering a twelve-egg omelette. He was immediately arrested and imprisoned, and died soon afterwards in mysterious circumstances.

Condorcet’s studies were considered to be a key contribution to the French Enlightenment. After his death, his widow Sophie undertook to publish all his writings. This work was continued by their daughter Eliza who had married Arthur O’Connor, a United Irishman.

In the 1950s, the mathematical theory of games, devised by John von Neumann, was used to analyse voting systems. Later, Kenneth Arrow used mathematical arguments to show that certain desirable properties of voting systems were mutually exclusive; thus, all systems are inherently limited and compromises are unavoidable. Arrow’s impossibility theorem is the most frequently quoted and applied result in voting theory.

In the single transferable vote system used in Ireland, voters rank the candidates in order of preference. The idea of such a proportional representation (PR) system is that the number of seats won by each party or group of candidates should be proportional to the number of votes cast for them. PR systems tend to result in several political parties, whereas single vote or “first-past-the-post” systems – as used in the UK and USA – usually result in dominance by just two parties.

In the Irish system, the method of counting is set out in minute detail. The method is algorithmic in nature; that is, it may be implemented as a series of clearly identifiable steps, under conditions that are explicit and unequivocal. Although well defined, the process is complicated and gives rise to endless debate and occasional disputes.

Nowadays, the benefits and weaknesses of a voting system are expected to be demonstrable in mathematical terms. Modern research focusses on devising new criteria and new methods of fulfilling them. With high-power computers, it is feasible to simulate elections and to study the practical implications of modifications in voting and counting procedures. Large ensembles of simulations yield statistically robust conclusions.

Condorcet’s Paradox: an Example

Suppose there are three candidates, A, B and C. Each voter chooses the candidates in order, indicating a first, second and third preference on the ballot paper. We write (A > B > C) to indicate that A is chosen first, B second and C third, and we write (A > B) to indicate that A is preferred to B. Voters have six possible choices, shown in the following Table. Suppose there are 110 voters, who make the choices shown in the Table.

Each vote cast implies three preferences. For example, Option 1, (A > B > C ), implies A before B, A before C and B before C, which we write ( A > B ), ( A > C ) and ( B > C ). Counting all six pair-wise preferences, we have the numbers in the Table below. We see there are 60 choices for A over B as against 50 for B over A, so A wins out over B. Similarly, B wins over C and C wins over A. We have a cycle ( A > B > C > A ).

This is paradoxical: it seems that majority wishes contradict each other. The expectation that preferences are transitive, and that ( A > B ) and ( B > C ) imply ( A > C ), is not fulfilled. This is Condorcet’s paradox.

Applying Single Transferable Voting

The question remains: with the voter preferences indicated above, who wins? To determine this, further “rules” must be agreed. We assume that only one candidate is to be elected; that is, we consider a one-seat constituency. We tabulate the number of first, second and third preferences here.

We see that A and B have the same number of first preferences while C has fewer. In the STV system, candidate C is now eliminated, and 30 votes indicating C as first preference are allocated to A or B depending upon the second preference of each. These correspond to Option 3 and Option 6 above. Since Option 3 gives A as second preference, 20 votes are transferred to A. Since Option 6 gives B as second preference, 10 votes are transferred to B.

After this ‘second count’, A has 60 votes while B has 50. Thus, A is elected.

It is paradoxical that, if B had been removed from the process at the outset, the expressed preferences would indicate a preference for C over A, while the result using the STV system is a win for A.