Abstract The theory of voting has a long and discontinuous history. Currently the theory takes individual preference rankings over alternatives as given and establishes results involving compatibility or incompatibility of various desiderata concerning ways to aggregate individual rankings into social choices or rankings. From the viewpoint of democracy some of those desiderata are more important than others. We review some of the relevant results in this area. Since the main results are of negative nature, it makes sense to ask whether those results could be avoided if some other view were to be adopted regarding the form of individual
1 Introduction Although it is true that voting is not a sufficient condition for democratic governance, it is certainly a necessary condition thereof. Indeed, along with bargaining it belongs to the most important ways of reaching collectively binding decisions. Voting is resorted in a wide variety of contexts: political elections, decision making in multi-member bodies, electing best entries in song contests, determining the winners in figure-skating, issuing verdicts in juries, electing officers to various positions in public organizations etc. Voting is sometimes used in purely informal and ad hoc settings, such as when a group of people is deciding how
to spend an evening together, or a family is deciding on the name of a just acquired pet.
Perhaps as a consequence of the variety of contexts in which voting is resorted to, it comes in many different forms or procedures. The most common in informal contexts is the plurality voting or one-person-one-vote procedure. It imposes minimal requirements on the voter: he/she (hereinafter she) should only indicate one alternative that she considers superior to others. Whatever else information
she might be able to provide regarding her opinion of the alternatives is simply not used.
In 1770 Jean-Charles de Borda gave a presentation in the French Royal Academy of Sciences pointing out that the plurality voting system may lead to a choice of a highly implausible alternative, viz. one that would be defeated by all other contestants by a pair-wise vote by a majority of voters (McLean & Urken 1995). For this to happen, the voters would need to have preferences over all pairs of alternatives or a preference ranking over them.
Borda’s observation and the accompanying suggestion for a voting system – today known as the Borda Count – received a fair amount of attention in the pre-revolution France and in the immediate aftermath. Borda suggested that the winners be elected on the basis of their positions in the voters’ preference rankings. Each rank would give an alternative a fixed number of points so that the lowest rank would give a points, the next to lowest a+b points, the next a+2b points, etc. The points given to each alternative would then be summed up to a (Borda) score and the alternative with the highest score declared the winner. The essential feature of the system that Borda called the method of marks is that the point difference between any two consecutive ranks is a constant b. This system is today known as the Borda Count. In practice, the values a=0 and b=1 are used. What Borda also showed was that this system can be implemented on the basis of pair-wise votes: by summing the number of votes an alternative gets in each pair-wise vote against other alternatives one gets the Borda score of the alternative.
Borda’s contemporary Marquis de Condorcet became the first critic of Borda’s proposal and an advocate of systems based on pair-wise comparisons. Condorcet showed that the Borda Count may not elect a candidate that would defeat all other candidates in pair-wise contests by a simple majority. Today such a candidate is called the Condorcet winner. The tension between two types of notions of winning was thereby created. One emphasizes the positions that alternatives occupy in voters’ preference rankings: the higher on the average, the better. This view is called positional. The other stresses the pair-wise victories of alternatives: the more alternatives are defeated by a given alternative, the better are the chances of the latter’s becoming the overall winner. This tension between two notions of winning is still visible in the contemporary literature.
After the times of Borda and Condorcet there was a period of more than half a century over which no significant contributions were made to the theory of voting. In the latter half of the 19th century two names should be mentioned. C.L. Dodgson, an Oxford mathematics tutor, wrote several pamphlets on voting systems i.a. apparently re-inventing the Borda Count (see Black 1958). The second name from roughly the same period is E. J. Nanson. He invented a multi-stage elimination method for reconciling the positional and pair-wise winning notions (Nanson 1882).
Nanson’s contribution was followed by yet another period of more than half a century over which no major contributions were made to the theory of voting procedures. The “third wave” of the theory began with the work of Black and Arrow in late 1940’s and early 1950’s (Black 1948; Arrow 1951). This wave is still in full swing. The aim of this article is to provide an overview of the theory of voting: why it is important, how the problems are addressed and which are the main results. The next section gives a motivation for the study of voting. Section 3 deals with those properties of voting systems that we intuitively deem desirable. The next section reviews some important results on the compatibility relationships between these desiderata. We then focus on the “givens” of the theory and look at systems that require less of the voters than complete and transitive preference relations. Thereafter we discuss briefly some systems that boil down to aggregating cardinal utilities of voters.
Voting procedures are used in many contexts. We have procedures for electing presidents, parliaments and other assemblies. We also have procedures for deciding which legislative proposal is to be adopted, which verdict to issue in court cases, and so on. In some cases the outcome of voting – the winner – is a person to occupy an office. In others, the winners constitute a group of persons. The winner may also be a proposition or policy alternative. Given the variety of settings in which voting is resorted to it is not surprising that there are many voting procedures. What is perhaps more unexpected is that there are several procedures used for what appears to be an identical purpose, e.g. electing a president. Yet there are, and, what is more important, they are not equivalent. Indeed, the procedure is an equally important determinant of the voting outcome than the voter opinions. A
hypothetical example illustrates this.
Suppose that there are three candidates, Brown, Jones and Smith, running for presidency. Suppose moreover that the electorate is divided into three groups. Group 1 supports Brown and views Smith as the second best. Group 2 supports Jones and regards Smith preferable to Brown. Group 3, in turn, regards Smith the best, Jones second best and Brown the worst of candidates. Group 1 consists of 40 %, group 2 of 35 % and group 3 of 25 % of voters. The voter opinions can be presented in the following tabular form.
Group 1 (40 %): Brown Smith Jones
Group 2 (35 %): Jones Smith Brown
Group 3 (25 %): Smith Jones Brown
If this is the distribution of opinions reported by the voters in the polls, the outcome is completely dependent on the procedure used. In particular, three often used procedures lead to three different outcomes. To wit, the plurality voting elects Brown as this candidate is ranked first by the largest number of voters. Jones, in turn, would win in plurality runoff (or instant runoff) election since – as no candidate is ranked first by more than 50 % of the voters - Brown and Jones would make it to the second round where Jones beats Brown with the aid of the votes of the Smith supporters. Most pair-wise comparison methods would, in turn, end up with Smith since Smith beats both Brown and Jones in pair-wise contests by a majority of votes. Smith is thus the Condorcet winner.
So, three commonly used procedures end up with three different outcomes in this electorate. In fact, then, any candidate can be rendered the winner by varying the procedure. Is there a way of telling which procedure is “best”? This requires a study of the requirements that we impose on a good voting system and on the extent to which various procedures satisfy those requirements.
3. Procedure desiderata
In the above example the three voting procedures lead to different choices. Nonetheless these three can be seen as generalizations of a common intuitive notion of winning, viz. whichever candidate or alternative is ranked first by an absolute majority – i.e. more than 50 % - of voters should be elected. Obviously, should this kind of opinion distribution or preference profile be encountered, all three procedures would end up with the same winner. A candidate ranked first by an absolute majority of voters is called the strong Condorcet winner. The requirement that eventual strong Condorcet winners should always be elected can be called the strong Condorcet winner criterion. It is satisfied by a large class of voting procedures. Not by all, though. Consider the following 13-voter profile over 3 candidates A, B and C:
8 voters: A B C
5 voters: B C A
Obviously A is now the strong Condorcet winner and would thus be elected by the above three voting procedures. Assume, however, that each voters is allowed to vote for two candidates and that the winner is the candidate receiving more votes than any other candidate. This system would elect B in this example. So would the approval voting which is a system that allows the voters to vote for as many candidates they like so that each voter can give each candidate either one or zero votes (Brams and Fishburn 1983). The winner is the candidate that has more votes (“approvals”) than the others. If we assume that the 8 voters approve of both A and B and the 5 voters either B or B and C, the winner is B. The same outcome ensues from the Borda Count. It can be seen that the two notions of winning advocated by Condorcet, on the one hand, and Borda, on the other, are indeed quite incompatible. Even in highly consensual societies these two requirements may come up with different outcomes. The worse for the Borda Count and approval voting, one could say.
This is not necessarily a correct conclusion, however. Although a strong Condorcet winner is quite robust with regard to eliminating alternatives, it is not robust at all with respect to adding or subtracting voters with opinions that intuitively should make no difference to the outcomes (Saari 1995). To illustrate, consider again the above 13-person voting body and assume that it is expanded by adding 15-voters with the following opinions of the three candidates A, B and C:
5 voters: A B C
5 voters: B C A
5 voters: C A B
The added group of 15 voters is obviously quite incapable of making any difference at all between the three candidates unless some voters’ opinions are given more weight than the others’. So, this group should – intuitively speaking – have no impact on the outcome of voting. But it does if the pair-wise winners determine the outcome. It turns out that after the expansion of the voting body into a 28-member one, A is no more the Condorcet winner. Now it is B. This kind of “instability” casts a shadow over the Condorcet winning criterion. At the same time it should be pointed out that the Borda Count winners are vulnerable to changes in the candidate set: if a candidate is removed, the Borda Count winner may change (Fishburn 1974). Indeed, the ranking determined by the Borda scores may be completely reversed upon adding or subtracting candidates.
Certain kind of stability is, indeed, often regarded as a desirable property of voting rules. The voting outcomes should remain invariant under specific changes in the voting situation. For example, in democratic voting rules, one typically expects that the order in which ballots are cast or re-naming of the voters should make no difference in the voting outcomes. It is the distribution of opinions, not who has a given opinion that should determine the outcome. This often implicitly assumed voting system desideratum is called anonymity. A similar requirement states that a re-labelling of the decision alternatives – e.g. re-naming the candidates – should make no difference to the content of the voting outcomes. After the re-naming the same alternatives should emerge as winners, albeit carrying new labels. This requirement is known as neutrality: the procedures should treat alternatives in a neutral way.
Despite their self-evident nature the requirements of anonymity and neutrality are not always satisfied even settings that are generally deemed democratic. In many voting bodies the vote of the chairperson has a special significance when the opinions of the members are evenly distributed, i.e. when there is a tie. In those special circumstances, the chairperson’s vote is often used as the tie-breaker. Thus, the system is not anonymous. Similarly, in legislative settings, the status quo alternative often has a special status. In the widely used amendment system the legislative proposals and amendments are voted upon in pairs so that the winner of each pair confronts the next proposal according to a specific agenda. Of k proposals k-1 pairwise votes are taken and the winner of the last one is the overall winner. In this system the agenda plays a crucial role in determining the outcome. To illustrate, consider again the preceding 15-voter profile over alternatives A, B and C. Suppose that the agenda of pair-wise comparisons is: 1. A vs. B, and 2. the winner vs. C. Call this agenda I. If each voter votes according to her preferences in both ballots, the winner is C. Now, if the agenda were: 1. B vs. C, and 2. the winner vs. A, the winner would be A under the same assumptions. Let us call the latter agenda II. So, the agenda is decisive under what is called sincere voting, i.e. if all voters reveal their true preferences at each stage of the voting process.
The agenda-dependence of the outcomes does not, however, hinge on the sincere voting assumption. Suppose, instead, that the voters are sophisticated in the sense of resorting to backwards induction in determining their choices at each stage (McKelvey and Niemi 1978). This means that under agenda I the voters first determine who to vote in stage 2. In that stage C is confronted with either A or B depending on the outcome of stage 1. Since stage 2 is the last one, the voters can be assumed to vote according to their preferences. Hence if it is A that faces C in stage 2 the winner is C, while if it is B that is compared with C, the winner is B. Thus, in effect the choice that the (sophisticated) voters are faced with in stage 1 is between B and C even though the agenda says that A and B are being compared. Since the majority prefers B to C, the outcome is B under sophisticated voting. Consider now agenda II. By the same argument, the winner under sophisticated voting is C.
The agenda-dependence of the amendment system makes it non-neutral. In legislative settings it is typically the status quo that confronts whichever alternative survives the preceding stages of the agenda. Under sincere voting it thus has a favourable position with respect to other alternatives. Under sophisticated voting, in turn, it seems to have a disadvantage. In any event the conclusion is that the amendment procedure does not treat alternatives in a neutral fashion.
Another type of stability requirement pertains to the very rationale of voting, viz. the idea that by voting one affects outcomes in a “natural” way. Expressing support for an alternative should increase or at least not decrease its probability of being chosen. More precisely this requirement can be stated in two non-equivalent ways (Nurmi 1999; Campbell and Kelly 2002). (i) Given a preference profile, it should never be harmful for an alternative if some voters rank it higher than in the profile, ceteris paribus. (ii) Given a preference profile, it should never benefit a voter to abstain, i.e. the outcome resulting from abstaining should never be better in the voter’s opinion than the one resulting from her voting according to her preferences. Requirement (i) is known as monotonicity and requirement (ii) as invulnerability to the no-show paradox or participation axiom. The former is an intra-profile property, that is, it considers a given profile of, say, n voters and k alternatives. The latter, in turn, is an inter-profile requirement: it considers two profiles with different number of voters. Yet, they are pretty close to each other. Monotonicity deals with choice sets resulting from the voters’ changing their mind with respect to an alternative vis-à-vis the others, while requirement (ii) considers changes in voting outcomes resulting from eliminating preference rankings from the profile. Despite their intuitive appeal, they are violated by some commonly used voting systems.
Consider the following profile:
47 voters: A B C
2 voters: A B C
25 voters: B C A
26 voters: C B A
Suppose that the plurality runoff system or instant runoff (IRV) is being used. Obviously, A and C will get to the second round, while B is eliminated. In the second round C defeats A by 51 votes to 49. Subtract now the 47 voters mentioned first (nearly a half of the electorate) and conduct a new election for the remaining profile. Now B and C make it to the second round, where B wins. Obviously, the outcome is better from the abstainers’ point of view in the reduced profile than in the original one. Hence the plurality runoff system fails on the participation axiom or, in other words, is vulnerable to the no-show paradox, i.e. not voting may lead to a better outcome than voting.
The single transferable vote (STV) system is also vulnerable to the no-show paradox. This can be seen from the same example since with three alternatives the plurality runoff system and STV are equivalent: eliminating the alternative with the smallest number of first place votes is tantamount to qualifying the two most vote-getters to the second round.
The non-monotonicity of IRV and STV is shown in the following example:
35 voters: A B C
33 voters: B C A
32 voters: C A B
Here the second-round contestants are A and B, whereupon A wins. Suppose now that 2 -14 of those voters with the preference ranking B C A would rank A first, ceteris paribus. Then the runoff contestants would be between A and C with C winning the overall contest. Hence additional support turns the winner (A) into a non-winner.
In the interpretation adopted above, monotonicity requires that additional support, ceteris paribus, is not to render winners into non-winners. In the mechanism design literature one encounters another related concept, viz. that of Maskin monotonicity (Maskin 1985). It states that if an alternative x is a winner in a profile P and if a profile Q is constructed so that x’s position remains the same or improves with respect to all other alternatives, then x is the winner in Q as well. Note that no ceteris paribus condition is imposed on other alternatives vis-à-vis each other. It turns out that Maskin monotonicity is a very strong desideratum: none of the voting systems discussed above satisfies it.
In some voting systems one may encounter a strong version of the no-show paradox. To wit, it may happen that a group of voters with identical preferences may succeed in getting their favourite (i.e. first-ranked) alternative elected by abstaining, while some lower-ranked alternative would win if they vote according to their preferences (Felsenthal 2001). To illustrate the paradox consider the following 19-person profile and Nanson’s method (Nurmi 2005, 34):
6 voters: c a d b
5 voters: a b d c
5 voters: b c d a
1 voter: c b a d
2 voters: c b d a
Nanson’s method ends up with b in this profile. If the last mentioned 2 voters abstain, the choice is C, their favourite.
Monotonicity and invulnerability to the no-show paradox are by no means the only stability desiderata imposed on voting systems. An intra-profile criterion known as consistency requires that coinciding choices made by sub-electorates be preserved in the choices made by the electorate at large. More precisely, for a system to be consistent, the following has to hold for any two mutually excusive and jointly exhaustive subsets of voters: if using the same procedure the subsets end up with at least partially overlapping choices, then those alternatives chosen by both subgroups are also chosen by the electorate at large, i.e. by the union of those subgroups.
This intuitively plausible desideratum turns out to be relatively uncommon among voting systems. For example the plurality runoff system is inconsistent as shown by the following example. The electorate consists of two profiles one of which is:
3 voters: A B C
3 voters: B C A
2 voters: C A B
The other is:
3 voters: A C B
2 voters: C B A
In both profiles A is elected by the plurality runoff, IRV and STV. However, in the combined 13-voter profile the winner is C no matter which of these systems is resorted to.
In contradistinction to these three (and many other) systems, the plurality voting, Borda Count as well as approval voting are all consistent. The same is obviously true of vote-for-two or, in general, vote-for-k systems in which each voter is to vote for a fixed number of alternatives and the winner is the one with a larger vote sum than any other alternative. Consistency of these systems offsets at least to some extent the fact that they all fail on the Condorcet winning criterion, i.e. they all may fail to elect a Condorcet winner.
Somewhat less common stability condition is called the Chernoff property or property alpha (Chernoff 1954). It states that if an alternative is the winner in a set of alternatives, it should be the winner in every proper subset of those alternatives it belongs to, ceteris paribus. Despite its intuitive appeal, this condition is very uncommon among known voting systems. In fact, of those discussed above only the approval voting satisfies it under the assumption that ceteris paribus means that not only the preferences of voters but also their approved alternatives remain the same in each subset considered.
In addition to desiderata pertaining to stability of voting outcomes under various modifications of profiles or alternative sets, there is a property that captures the intuitive notion that under sufficiently large modifications of the preferences, the choice sets should change as well. More specifically, if all voters turn their preferences upside down, i.e. for each pair of alternatives they reverse their opinion, then the outcome of voting should change as well. We say that a procedure exhibits reversal bias if there is a preference profile so that when every voter switches her preference between each pair of alternatives, the voting outcome remains the same as before the change. It is easy to construct examples of profiles where both plurality voting and the plurality runoff and hence IRV exhibit reversal bias (see Nurmi 2005, Saari and Barney 2003).
The desiderata of voting systems are many and, thus, we have touched upon only a small subset of them (see Fishburn 1977, Nurmi 1987, Richelson 1979, Straffin 1980, Smith 2000). Rather than defining voting systems and desirable criteria, a more efficient way to look for good ways to aggregate opinions is to look at the compatibility and incompatibility of various desiderata. In the following section we shall review some of the most important results of this type of work.