Limits to collective decision making: Arrow’s theorem

What’s the best way for a group of people to make collective decisions? Democracy may be, as Churchill said, the worst system that’s better than anything else, but in practice there’s a lot of variation possible in democractic voting systems. How should we set up voting systems that result in effective collective decisions?

Designing a good voting system seems like a simple task, but it’s surprisingly complicated. A famous result known as Arrow’s theorem, proved by the economist Kenneth Arrow in 1950, vividly demonstrates just how difficult it is. Arrow picked out three properties that (arguably) you would like any good voting system to have – and then mathematically proved that no voting system with all three properties can possibly exist! What is especially remarkable about Arrow’s achievement is that there is no obvious a priori reason to suppose that these three requirements are incompatible. Arrow was a joint recipient of the 1972 Nobel Memorial Prize for economics, in part because of this work.

These notes explain what Arrow’s theorem says, why it’s true (i.e., I give a proof), and discuss briefly what it means for collective cognition. I’ve tried to keep the notes easy to read, favouring a relaxed and discursive discussion over the terse presentation favoured in most mathematical works. I have also tried to assume minimal mathematical background, no more than some facility with basic mathematical notation and mathematical argument. The main drawback of this approach is that the notes have become rather lengthy, clocking in at nearly [tex]3000[/tex] words. Hopefully, however, they’ll be a rewarding read.

My notes are based on a very nice paper by John Geanakoplos (Cowles Foundation discussion paper No.1123RRRR, available at http://cowles.econ.yale.edu, and reprinted in Economic Theory (2005), 26: 211-215), which gives three proofs of Arrow’s theorem. The proof I give is Geanakoplos’ first (and simplest) proof. Note that there are other (related) results in the literature which go by the name Arrow’s theorem. Understanding the version presented here should enable you to understand the variants with a minimum of fuss. Arrow’s original paper appeared as “A Difficulty in the Concept of Social Welfare” in The Journal of Political Economy, Volume 58, page 328 (1950).

Voting systems

To explain what Arrow’s theorem says, we need to define more precisely what we mean by a voting system. We imagine a population of [tex]n[/tex] “voters”, to whom we assign convenient labels , like [tex]1, \ldots, n[/tex]. This population might be, for example, all the mentally competent people over the age of [tex]18[/tex] in some country (e.g., Australia).

These voters are going to vote amongst [tex]m[/tex] alternative options, which we’ll label with capital letters, [tex]A, B, C, \ldots, Z[/tex], to keep distinct from the voters. These voting options might be the political parties running for control of the Federal Government, for example.

What each voter does is produce an ordered ranking of the options, with ties allowed. For example, voter number [tex]3[/tex] might rank [tex]B[/tex] as number [tex]1[/tex], [tex]A[/tex] and [tex]C[/tex] as a tie for number [tex]2[/tex], [tex]D[/tex] as number [tex]3[/tex], and so on.

(You might wonder whether [tex]D[/tex] shouldn’t really be ranked number [tex]4[/tex], in view of the tie between [tex]B[/tex] and [tex]C[/tex] for the ranking of [tex]2[/tex]. Below we’ll make an assumption about the voting system that means that only the relative ranking matters, not the exact value of the number assigned, and so we’re justified in ignoring this issue.)

A helpful shorthand is to write [tex]S >_v T[/tex] to indicate that voter [tex]v[/tex] ranked [tex]S[/tex] strictly ahead of [tex]T[/tex]. For example, maybe voter [tex]v[/tex] ranked [tex]S[/tex] as [tex]2[/tex] and [tex]T[/tex] as [tex]4[/tex]. It’s worth keeping in mind that this notation for ordering is the reverse of the conventional numerical order – politicians usually campaign to be “number [tex]1[/tex]” rather than “number [tex]10[/tex]”! Similarly, we’ll write [tex]S \geq_v T[/tex] to indicate that voter [tex]v[/tex] ranked [tex]S[/tex] at least as highly as [tex]T[/tex]; this allows that maybe [tex]S[/tex] and [tex]T[/tex] had the same rank. By the way, we’ve been using [tex]S[/tex] and [tex]T[/tex] here simply to indicate generic voting options; we’ll do this throughout, occasionally using [tex]U[/tex] as well.

As an example, imagine there are [tex]5[/tex] voters choosing among [tex]3[/tex] alternatives, [tex]A, B, C[/tex]. The overall voting profile might look something like this:

• Voter [tex]1[/tex]: [tex]A \rightarrow 1[/tex]; [tex]B \rightarrow 1[/tex]; [tex]C \rightarrow 2[/tex].
• Voter [tex]2[/tex]: [tex]A \rightarrow 3[/tex]; [tex]B \rightarrow 1[/tex]; [tex]C \rightarrow 2[/tex].
• Voter [tex]3[/tex]: [tex]A \rightarrow 2[/tex]; [tex]B \rightarrow 1[/tex]; [tex]C \rightarrow 1[/tex].
• Voter [tex]4[/tex]: [tex]A \rightarrow 1[/tex]; [tex]B \rightarrow 1[/tex]; [tex]C \rightarrow 1[/tex].
• Voter [tex]5[/tex]: [tex]A \rightarrow 3[/tex]; [tex]B \rightarrow 2[/tex]; [tex]C \rightarrow 1[/tex].

A voting system is a function which takes the profile as input, and produces a single social ranking of the options as its output. For example, we might add up the numerical value of the votes associated to each voting option, and then order the options accordingly. So, for example, option [tex]A[/tex] above has a total vote [tex]1+3+2+1+3=10[/tex], option [tex]B[/tex] a total [tex]1+1+1+1+2=6[/tex] and option [tex]C[/tex] a total [tex]2+2+1+1+1=7[/tex]. As a result, in this voting system the social ranking has [tex]A[/tex] as [tex]3[/tex], [tex]B[/tex] as [tex]1[/tex], and [tex]C[/tex] as [tex]2[/tex].

Once a voting system has been fixed, we write [tex]S > T[/tex] to indicate that [tex]S[/tex] has a higher social rank than [tex]T[/tex]. Similarly, we write [tex]S \geq T[/tex] to indicate that [tex]S[/tex]’s social ranking is at least as high as [tex]T[/tex]’s.

What makes a good voting system?

What properties should a good voting system have?

Obviously, this is a potentially controversial question! Arrow’s theorem is based on several reasonable properties that, arguably, we should expect to be satisfied in any good voting system.

The first property is that the voting system should respect unaninmity, in the sense that if [tex]S >_v T[/tex] for all voters, then we should have [tex]S > T[/tex]. Restating this verbally instead of symbolically, if every voter prefers [tex]S[/tex] to [tex]T[/tex], then the social ranking should place [tex]S[/tex] ahead of [tex]T[/tex]. This is pretty obviously a highly desirable property for any voting system to have – imagine if the electoral commission announced that candidate [tex]A[/tex] had won, despite the fact that every single voter ranked [tex]B[/tex] ahead of [tex]A[/tex]!

The second property is that the voting system should respect the independence of irrelevant alternatives, meaning that the relative social ranking of [tex]S[/tex] and [tex]T[/tex] (higher, lower, or the same) depends only on the relative ranking of [tex]S[/tex] and [tex]T[/tex] by individual voters, and isn’t influenced by the position of other options (e.g., [tex]U[/tex]).

It’s rather less obvious that any good voting system will respect the independence of irrelevant alternatives. For example, the simple voting system I described above (where we summed the votes) turns out not to have this property, yet it’s not so obviously a bad voting system.

However, for the purposes of this discussion we’re going to assume that this property of respecting the independece of irrelevant alternatives is regarded as highly desirable. Can we design a voting system which respects both unanimity and the independence of irrelevant alternatives?

It turns out that if there are just two voting options, [tex]A[/tex] and [tex]B[/tex], then it’s possible to design a voting system with this property. We could, for example, just sum up the the respective votes of the two voting options, and declare the winner to be whichever option has the lower total.

What happens if there are three voting options, [tex]A, B[/tex] and [tex]C[/tex]? What Arrow’s theorem shows in this case is that in any voting system which respects unanimity and the independence of irrelevant alternatives there must automatically be a voter, [tex]d[/tex], who can act as a dictator for the voting system, in the sense that if [tex]S >_d T[/tex], then [tex]S > T[/tex], no matter how the other voters rank their options!

Stated another way, what Arrow’s theorem shows is that the requirements of respecting unanimity and the independence of irrelevant alternatives are incompatible with a third desirable requirement, namely that the voting system not be a dictatorship.

In full generality, what Arrow’s theorem shows is as follows:

Arrow’s theorem: Suppose we have a voting system to rank [tex]3[/tex] or more voting options. Suppose that system respects unanimity and the independence of independent alternatives. Then there must be a dictator for the voting system.

This theorem ought to shock you. How can the assumptions of unanimity and independence of irrelevant alternatives possibly imply the existence of a dictator?

I’ll now give a short proof of Arrow’s theorem, to give you some feeling for why the theorem is true. However, much of interest can be said about Arrow’s theorem even if you don’t understand the proof, so if you’re so inclined you should feel free to skim or skip the following proof. Of course, those who want to understand Arrow’s theorem deeply should spend some time trying to prove it themselves, before reading the proof in detail.

Proof of Arrow’s theorem: The first step of the proof is to argue that if every voter ranks [tex]S[/tex] either strictly first or strictly last, then [tex]S[/tex]’s social ranking must be either strictly first or strictly last. To see this, we use a proof by contradiction, supposing that in fact [tex]S[/tex]’s social ranking is neither strictly first nor strictly last. That is, we suppose that there exist [tex]T[/tex] and [tex]U[/tex] such that [tex]T \geq S \geq U[/tex]. Suppose we rearrange each voter’s rankings so that [tex]U >_v T[/tex], but without changing the relative ranking of [tex]S[/tex] and [tex]T[/tex], or of [tex]S[/tex] and [tex]U[/tex], so the rearrangement doesn’t affect the fact that [tex]T \geq S[/tex] and [tex]S \geq U[/tex]. (Understanding why such a rearrangement can always be done requires a little thought, and maybe some working out on a separate sheet of paper, which you should do.) Unanimity then requires that [tex]U > T[/tex], which is inconsistent with the fact that [tex]T \geq S \geq U[/tex]. This is the desired contradiction.

Suppose now that we start out with a profile in which [tex]S[/tex] is ranked strictly first by every voter, and thus by unanimity must be ranked strictly first in the social ranking. Suppose we move through the voting population, and for each voter in turn change their ranking for [tex]S[/tex] from strictly first to strictly last. When this has been done for all the voters, unanimity implies that [tex]S[/tex] must be ranked strictly last, and so at some point we see that there must be a voter (who will turn out to be the dictator, [tex]d[/tex]), whose vote change causes [tex]S[/tex] to move from first to last in the social ranking.

Consider the voting profile immediately before [tex]d[/tex] changes their vote. We will say that any profile which has the same rankings for [tex]S[/tex] as this profile is an [tex]S[/tex]-profile. Similarly, an [tex]S'[/tex]-profile is one which has the same rankings for [tex]S[/tex] as the profile just after [tex]d[/tex] changes their vote. It follows from the independence of irrelevant alternatives that the overall ranking of [tex]S[/tex] must be first in any [tex]S[/tex]-profile, and last in any [tex]S'[/tex]-profile.

Suppose now that [tex]T[/tex] and [tex]U[/tex] are voting options that are not equal to [tex]S[/tex]. Suppose [tex]d[/tex] ranks [tex]T[/tex] higher than [tex]U[/tex], i.e., [tex]T >_d U[/tex]. We will show that we must have [tex]T > U[/tex], no matter how the other voters rank [tex]T[/tex] and [tex]U[/tex]. That is, [tex]d[/tex]’s vote dictates that [tex]T[/tex] be ranked above [tex]U[/tex] in the social ranking. To see this, first we rearrange the profile so that it becomes an [tex]S[/tex]-profile, without changing the relative ordering of [tex]T[/tex] and [tex]U[/tex] anywhere, and so not affecting whether [tex]T > U[/tex] or not. We can do this simply by changing each voter’s ranking for [tex]S[/tex] in an appropriate way, placing it either at the top or the bottom of their ranking. Second, we change [tex]d[/tex]’s rankings so that [tex]T >_d S >_d U[/tex]. This can be done without changing the relative ranking of [tex]T[/tex] and [tex]U[/tex], and so does not affect whether [tex]T > U[/tex]. We call the resulting voting profile after these two rearrangements the final profile. Observe that in the final profile we have [tex]S > U[/tex], since if [tex]d[/tex] changes [tex]S[/tex] to be ranked strictly first then we have an [tex]S[/tex]-profile. Similarly, in the final profile we have [tex]T > S[/tex], since if [tex]d[/tex] changes [tex]S[/tex] to be strictly last, then we have an [tex]S'[/tex]-profile. As a result, we have [tex]T > S > U[/tex] in the final profile, and thus [tex]T > U[/tex]. But we constructed the final profile so that [tex]T > U[/tex] holds only if [tex]T > U[/tex] also in the actual voting profile, and so we must have had [tex]T > U[/tex] in the actual voting profile, as we desired to show.

The final step of the proof is to argue that [tex]d[/tex] can also dictate the order of [tex]S[/tex] and [tex]T[/tex], for an arbitrary [tex]T \neq S[/tex]. To see this, pick an element [tex]U[/tex] which is neither [tex]S[/tex] nor [tex]T[/tex], and consider an [tex]S[/tex]-profile in which [tex]U[/tex] is placed strictly last everywhere that [tex]S[/tex] is first, and vice versa. The results of the first and second paragraph of this proof imply that [tex]d[/tex] can change the rank of [tex]U[/tex] from last to first simply by changing their vote. We now apply the same argument as in the paragraph before this, but with [tex]U[/tex] taking the place of [tex]S[/tex], to argue that [tex]d[/tex] can dictate the relative ordering of [tex]S[/tex] and [tex]T[/tex]. QED

Arrow’s theorem is a striking result in the theory of collective decision making. It shows the great advantages that can come by formalizing ideas in a simple mathematical model – the fact that the model can lead to striking unforseen conclusions that entirely change our perception of the phenomenon. More prosaically, by thinking closely about our values and our desired social outcomes, we can try to formalize models of those properties, and then study which models of collective decision making best respect those properties (if, indeed, any such models exists).

What of the implications of Arrow’s theorem for voting? It is, of course, true that the restrictions in Arrow’s theorem can be relaxed, and there is a large literature studying other models of voting and the extent to which they can be made fair. I’m not an expert on this literature, and so won’t comment other than to point out that economists have, of course, not been silent on the matter in the 50 plus years since Arrow’s paper!

My own interest in the subject is due to a more general hobby interest in the problem of collective cognition. In particular, I’m interested in the question of how we can design institutions which result in good collective decision making. It seems that the subject of institutional design is still in its infancy, and I find it remarkable how small a fraction of “institution space” humans have explored. One of the most interesting things about the web, in my opinion, is that it has greatly cut the cost of developing new institutions, and as a result we’re seeing new institutional models, and new types of collective cognition, develop at an incredible rate.