It we have two candidates A and B and one of the two is to be elected by a vote, then there is a fairly obvious system. Voters cast a vote for either candidate A or a vote for candidate B. However if votes were to be cast for a larger number of candidates then there was a question of how it should be done.
For example one of the earliest forms of democracy in Greece was introduced by Cleisthenes in 508 BC. This was a rather negative form of an election, for each year voters were asked to cast a vote for the politician they most wished to exile for ten years. Votes were written on ostraka, which were broken pots, and from this name comes our present word to ostracise. If no politician received more than 6000 votes then all remained, but if any received more than 6000 then the one with the largest number was exiled. Requiring that someone had over 6000 votes before being ostracised was an added feature to try to ensure that only when a person was unpopular with a large number of voters was exile the result. If there was a fairly even spread of votes, nobody would get over 6000 and, although someone would get the most it would not matter in such a case.
The Venetian state was built up in the 13th century and they elected a Great Council of 40 members which was raised to 60 by the middle of the century. Various electoral systems were used, in particular the Venetians introduced approval voting around this time. In this system, if there are n candidates, then electors cast one vote for every candidate they find acceptable and none for those whom they deem unacceptable. This has a number of attractions as a system, and certainly the winner is the person who is acceptable to the largest number of voters.
Was voting system introduced by Cleisthenes fair? Was the Venetian system of approval voting fair? Of course to answer the question of whether any electoral system is fair one must define what this means. In the case where there are two candidates there is a mathematical argument to show that there is only one system which satisfies the 'obvious' three criteria of fairness:
all voters are equal;
both candidates are treated equally;
if the winning candidate received more votes they would still win.
This voting system is the one in which each voter casts a single vote for the candidate they wish to elect and this was proved in 1952 by Kenneth May.
Where there are more than two candidates the situation is very complicated and several different definitions of 'fair' have been given, as well as many different electoral systems being proposed. For example one suggestion is that if one person is to be elected from a collection of n people then the election is fair if the person elected would have won in a head-to-head contest with every one of the other n-1 candidates. Although this does indeed seem "fair" there is the problem that in many cases there will not be anyone who would beat every other candidate in a head-to-head contest.
Llull, in the 13th century, proposed a voting system based on precisely the principle of "fairness" which we have described above when his advice was sought on how to elect the abbess of a convent. His suggestion was written down in a manuscript which was available to Nicholas of Cusa in the 15th century but a fuller description of Llull's proposal for a voting system was made in another of his manuscripts which was only discovered and published in 2001. Although Llull's system certainly satisfies the property that everyone would agree that the person elected was fairly elected, there is the problem that an election based on these principles may not result in a winner at all.
In 1433 Cusa, having studied Llull's idea and realising that it had deficiencies, proposed a different system which would always result in a winner. Cusa produced a document on how to elect German kings in which he proposed the following system. If there were n candidates for King, then voters should give the candidate they favoured least one point, the next candidate two points and so on until they reached their most favoured candidate for King who they would give n votes. This system is used today for certain elections but it does have the deficiency that the candidate elected may not have been anyone's first choice.
Llull's idea of a fair election was proposed again 500 years later by Condorcet in his Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix (Essay on the Application of Analysis to the Probability of Majority Decisions) published in 1785. This is a remarkable work which gives Condorcet an important place in the history of probability. The work contains the Condorcet Paradox which points out that it is possible that a majority of voters may prefer candidate A over candidate B, a majority may prefer candidate B over candidate C, and yet a majority may prefer candidate C over candidate A. Thus, "majority prefers" is not transitive and so an election based on Llull's definition of "fair" may not yield a winner. A second edition of Condorcet's work, including much new material, was published in 1805 with a different title, namely Eléments du calcul des probabilités et son application aux jeux de hasard, à la loterie et aux jugements des hommes.
Borda was a contemporary of Condorcet and felt that although the system described by Llull, and much later proposed by Condorcet, was fair, it was not workable. Borda proposed the system of ranking candidates by giving each points corresponding to their rank as Nicholas of Cusa had done in the 15th century. There was a vigorous argument between the two mathematicians as to which of the two voting systems was the best but of course since both systems had their strengths and weaknesses, such an argument was bound to be inconclusive.
We have indicated how the Borda and Condorcet principles were put forward in medieval times. Earlier proposals of this type are discussed in :-
We report three medieval works, hitherto unknown to social choice, which discuss procedures for elections when there are more than two candidates. Two of the three propose Borda methods and the third a Condorcet method of successive pairwise comparison. All three discuss problems of manipulation. One of them displays a matrix for pairwise comparisons; this is a work written in 1299, nearly 600 years before the matrix notation was believed to have been invented by C L Do dgson.
In fact it was shown in 1951 by Kenneth Arrow, who won the Nobel Prize for Economics in 1972, that no voting system can be fair in the sense that it will produce a winner who will be preferred to every other candidate and still guarantee that a decisive result will be the outcome of the election. If this leads one to believe that Borda's ranking system must be better than Condorcet's system, then one must realise a major deficiency of this system is that electors can vote tactically rather than giving their true opinions. A voter may favour candidate A as first choice and candidate B as second choice. However placing A first with n votes and B last with 1 vote increases A's chance of winning. Such tactical voting can lead to candidates whom nobody favoured being elected.
The simple system in which each voter gives a single vote to their favourite candidate can also lead to tactical voting. If a voter would like to see candidate C elected but feels that B is the only candidate who stands a chance at stopping A being elected, then the voter may vote for B rather than their first choice C. Such tactical voting was evident in an election in Scotland in the 1990s. At this election there were four 'major' parties (and therefore 4 main candidates in most regions) and voters had a single vote. Not a single Conservative candidate was elected despite the party getting a reasonable proportion of votes, since in regions where the Conservative was thought likely to win, many supporters of the other three parties voted for the candidate they thought most likely to beat the Conservative.
Tactical voting leads one to think of the rigorous formulation of such problems using game theory. In 1944 von Neumann and Morgenstern published Theory of Games and Economic Behaviour which allowed concepts such as tactical voting to be put into a precise mathematical form. However, such formulations led to problems such as the prisoner's dilemma which illustrated the difficult of reconciling the best strategy for an individual with the best strategy for groups of individuals. Does this have any bearing on elections?
Attempts to overcome the deficiencies of voting systems had been proposed long before game theory was invented. One such proposal by Thomas Hare, John Stuart Mill and C C G Andrae in the middle of the 19th century is the single transferable vote system used mainly for electing several candidates. In this system suppose there are n candidates of whom m are to be elected and suppose that k people vote. The quota Q = k/(m+1)+1 is calculated. Each voter ranks the n candidates in order of preference. First preferences are counted and any candidate receiving more than Q first preferences is elected. For each candidate who receives more votes than the quota, the number of votes in excess of the quota is calculated and their second preferences are allocated to the remaining candidates. The process is continued but may not result in m candidates passing the quota Q. In this case the candidate with the least number of votes is eliminated and the second preferences of voters for this candidate are redistributed. The process continues until a result is reached. If m = 1, that is a single person is to be elected, then the system can still be used.
Variants of the system are sometimes used when parties rather than people are to be elected. In the list system, voters vote for parties and candidates are elected from a list put up by each party. The number elected for each party is to be roughly in proportion to the number of votes cast. Different rules have been proposed to compute the number to be elected from each list. The highest-average rule was devised by Victor d'Hondt. Under this rule the party with the most votes gets its top candidate elected and the number of votes cast for this party is then divided by the number of its candidates who have been elected plus one. The process continues until the required number of candidates have been elected. Such list systems, using various ways of approximating the proportions, have been used throughout the 20th century. Under such proportional representation systems it is unusual for one party to gain an overall majority. This is seem but some as a disadvantage of the system, and by others as an advantage.
In fact we should mention the proportional representation work by Dodgson in the 1880s when he considered apportionment of representatives to districts. The author of  argues that:-
Dodgson's work present a complete and unified approach to the electoral reform issues which were being discussed at the time, but in doing so he developed and contributed ideas to game theory and apportionment which are well in advance of the 1880s.
The difficulty with all voting systems is that one can show mathematically that no satisfactory system exists. This was proved by Kenneth Arrow who proved what is known as Arrow's Paradox. The paradox which Arrow proved is counterintuitive for one feels that there must be a satisfactory way of aggregating the wishes of individuals into a policy for society as a whole. This after all is what our whole idea of democracy is based on. Yet Arrow showed that there is no way that the choices of individuals can be aggregated to yield their collective choice under four assumptions which seem clearly 'obvious'. The axioms are:
1. every possible choice by individuals must lead to an aggregate choice;
2. if all individuals make the same orderings then this must also be the aggregate ordering;
3. the aggregate ordering must not depend solely on the choice of a single individual;
4. the aggregate ordering must not depend on individuals in any way other than in respect to their ordering.
With these four axioms Arrow showed that there is no way to aggregate the choices of individuals into an aggregate choice for the society. Despite this result, however, democracies will continue to hold elections and ask individuals to vote to determine policies for all.
Article by: J J O'Connor and E F Robertson
MacTutor History of Mathematics