Arrow’s Theorem (or: How I Learned to Stop Worrying and Love Dictatorships)

Elections never really feel fair (or, if talking about the electoral college, are never fair)

Here is an example, say there is an internal election in some political party, to determine the order of members of the party. To do so, each voter votes for their favorite party member, and the party members are ranked by number of votes:

Suppose for example one party member, Adam, is loved by the majority of the voters. But also there is another candidate, Charlie, whose views much align with Adam’s. In fact, most of those who vote for Adam will say their second favorite candidate is Charlie.

Naturally, and ideal result of the election would take this into account, and probably place Charlie in one of the first places in the party. However, in the election system described above, Charlie is more likely to be much lower down the line:

Why is that? While it’s true Charlie is loved by a lot of voters, but she is not the favorite candidate of many voters despite that. Much of Charlies fan’s will vote for Adam instead of her, as they can only vote for one candidate. Due to the votes only reflecting the voter’s favorite candidate, Charlie, arguably unfairly, got shafted down the list.

How can this be fixed? One way is say to have each voter not only vote for their favorite candidate, but list their top three or top five candidates. Then the ranking could somehow take into account the less ‘preferred but still loved’ candidates like Charlie.

Still, why just top three or top five? How about each of the voters ranking all the members of the party in their preferred order? Of course, in a large party, say of 100, ordering all members is not very efficient and time consuming, In a smaller party, say of 5 or 10 members, this method is more reasonable

Given each of the voters rankings, how do we determine the results of the election? Here is one possible way (for the case with 4 canidates): we assign each placement in the rankings a set number of points. Say 1st place is 10 points, 2nd is 5, 3rd is 2, and 4th is no points. Then we give each candidate a score in the following way: they get 10 points for each vote they are in 1st place, 5 for each one they are in 2nd, and so on. The final ranking of the candidates will be from the least number of points to the most (should there be two canidates with the same number the one whose ID number is lower will be ranked lower as well)

Seems pretty fair, right? In practice it is probably fair, but we want more, we want it to be the fairest. So even in extreme edge cases, we could still consider this election system fair. Does it hold up? Well let’s look at two special cases with 3 voters:

First case:

	1st (10)	2nd (5)	3rd (2)	4th (0)
Voter 1	Adam	Charlie	Bethany	Derrick
Voter 2	Adam	Bethany	Charlie	Derrick
Voter 3	Adam	Bethany	Derrick	Charlie

Second case:

	1st (10)	2nd (5)	3rd (2)	4th (0)
Voter 1	Charlie	Adam	Bethany	Derrick
Voter 2	Adam	Bethany	Charlie	Derrick
Voter 3	Adam	Bethany	Charlie	Derrick

At first, there doesn’t seem to be any problem. The only difference between the two results is that in the first Bethany is ranked above Charlie, and in the second Bethany is ranked below Charlie. That’s a small change in the result. But look at what changed in the votes. More precisely, look what didn’t change. In both cases, voter 1 preferred Charlie over Bethany, and voters 2 and 3 preferred Bethany over Charlie instead. What changed was not the relative ranking between Charlie and Bethany, but rather the ranking with respect to the other two candidates. Despite this, in the two results the relative ranking between Charlie and Bethany is different.

In a way, you may consider this unfair. The placements of Adam and Derrick (the other two candidates) feel irrelevant for the placements of Bethany and Charlie relative to each other. In a completely fair voting system, you may want to prevent such things from happening. This leads to the first property of what we may consider an “ideal” voting system:

Independence from irrelevant candidates: The rankings of candidates A and B relative to each other in the results of the election should only depend on their rankings relative to each other in the votes

This leads us to a second property we would want from an “ideal” voting system. If all voters prefer candidate A over candidate B, it’s a no brainer that in the results candidate A will be ranked above candidate. Everyone unanimously preferred him over B. So the second property will be exactly that:

Pareto efficiency: If all voters prefer A over B, A will be ranked above B in the results

(Named after Italian economist Vilfredo Pareto)

All right! We found two properties that may guarantee a completely fair, ‘ideal’ voting system. All we have to do is find a voting system that has these two properties.

Well, here is a bit of a useless one. Say one voter is the dictator, and the result of the vote is his vote, with no regard to the other voters’ opinions. Then, under these properties, the voting system will be ‘ideal’. Indeed, the relative rankings of A and B in the final vote are the same as their relative rankings in the dictator’s vote, so the first property is held. And if all voters prefer A over B, in particular so does the dictator, so in the results A will be above B as well.

So, maybe we should add another, final property:

No dictators allowed: There is no single voters for whom the results of the election depend only on his opinion alone

Okay, now to find our ‘ideal’ voting system with these three properties.

Well…. Surprise! No such system can exist (with more than three candidates)

(Proving) Arrow’s Theorem

The fact that no such election system was discovered by mathematician Kenneth Arrow, and is now known as Arrow’s theorem (Sometimes Arrow’s paradox instead, more on later). This fact is one of many in the mathematical field of social choice (a subfield of game theory), which deals with problems of choosing in a group like the one discussed here. Let’s look at a surprisingly simple proof of this theorem, relying on a central lemma (adapted from the book Game Theory, by Michael Maschler, Eilon Solan, and Shmuel Zamir).

Lemma: If a candidate x is ranked by each of the voters either first place or last place, in the results of the election x will be ranked either first place or last place

Think about it for a bit. Say Joey is one possible candidate, and there are two equal sized camps in the voter pool, one that loves Joey and one that hates him. In a special case, all those who love Joey will place him in first place, and all those who hate him will place him in last place. What the lemma says is that in this special case Joey will either be first or last place in the results. This is a bit surprising, should Joey be first place it feels like it’s ignoring the voice of the camp that hates him. Should Joey by last place, the voice of those who love him feels ignored. Due to the lemma, there can’t be a compromise where Joey is in the middle of the results. It’s either at the top or at the bottom of the list.

Let’s now prove the lemma. Suppose the contrary, that is, there is a situation where candidate x is ranked either first or last by all voters, but is neither first or place in the results (to ease the proof we will call x Xavier instead). In that case, in the results there is a candidate ranked belove Xavier (let’s call her Zoey), and one ranked above him (let’s call them Yibb-Tstlll, the ā̴͎̮n̸̘͙̤̿͌c̴̡̺̃͛ì̵̭͖̝̈́ȅ̴̝͔̯̀n̶̩̐̐̎ͅt̸̳͔̍̑ ̴̫͝ọ̸̃̌n̴̮̓̕͝e̴͚͛, Yibb for short).

Now, suppose we change the votes a bit. For each voter, if they rank Yibb above Zoey, they swap their places so that Zoey will be above Yibb instead, and make no other changes. Should they rank Zoey above Yibb from the get go, their vote remains the same. Note that these changes do not affect the rankings of Zoey relative to Xavier. Remember that each voter ranks Xavier first or last place, the possible swap preformed does not change that. What this means that in the results of the new elections, the rankings of Zoey and Xavier relative to one another will not change, by the property of independence from irrelevant options. In this case, Zoey will still be ranked below Xavier in the results. In the same way, Yibb will still be ranked above Xavier.

But note this: in the new votes, each voter prefers Zoey over Yibb. Then, by the property of Pareto efficiency, in the results Zoey will be ranked over Yibb as well. This is not possible. As stated before, in the results Zoey is ranked below Xavier, who is ranked below Yibb. Thus in the results again will Zoey by ranked below Yibb. A contradiction, as we stated by Pareto efficiency that she’ll be ranked above him.

Thus, we conclude that the assumption that Xavier can be ranked in the middle of the results is impossible, so Xavier must be either first or last place, and the lemma is proven

Now for the main proof. Let’s suppose all the voters stand in a line, numbered from 1 to N:

Let’s take a candidate, say call him Mike. In a specific vote, all voters place Mike in last place. It’s no surprise then that Mike will be last place in the results (you can show this by Pareto efficiency). Then the election takes place again, this time voter number 1 changes their vote, such that Mike is ranked first place (say by swapping first and last place). Afterwards, another election takes place, this time voter number 2 also moves Mike to first place. The process repeats itself N times, until in the final vote all voters rank Mike in first place. Again, unsurprisingly in that final election Mike will indeed be first place.

In each election in the process, each voter ranks Mike either last or first place. So by the lemma from before, in the results Mike will be either last or first place as well. The multiple election process started with Mike in last place, and at the end in first place. And in each election in the middle, Mike was either last or first place. That means that there must be an election where Mike was voted last, but that in the succeeding election he was voted first. Say it was the k-th election

The only difference between the votes in the k-th and (k+1)-th elections, is that voter number k changed their vote such that Mike will be in first place instead of last. That single change radically changed the results of the elections, moving Mike from last to first. We will call this (the k+1-th election) the critical election, and the one before it (the k-th) the pre-critical election.

Suppose voter number k is named Kate. We now make the following claim: any election is solely determined by Kate’s vote, that is, Kate is a dictator

Why is that? Let’s say Alice and Bob are two additional candidates, other than Mike. Note that Alice’s and Bob’s rankings, relative to each other, are irrelevant to Mike’s placement in the critical elections and the election sequence from before. So say, in a arbitrary election (let’s call it election A), Kate ranks Alice over Bob, We claim that in the results of that election, Alice will be also ranked over Bob (no matter what the other voter’s opinions are)

Indeed, we modify election A, such that each voter before Kate (voters 1 to k-1) ranks Mike last place, and each voter after k ranks Mike first place (voters k+1 to N). We do it in such a way that each voter’s ranking of Alice and Bob relative to one another doesn’t change. Additionally, Kate changes her vote so that Mike is between Alice and Bob. The relative rankings of Alice and Bob in this modified election (call it election B) isn’t different from the one in A. So by independence from irrelevant options, the rankings of Alice and Bob relative to each other in the results of election A and election B are the same.

Election B has these two important properties:

• Each voter’s ranking of Bob relative to Mike is the same as their ranking of Bob relative to Mike in the pre-critical election. Specifically, voters 1 to k rank Bob above Mike, and voters k+1 to N rank Bob below Mike
• Each voter’s ranking of Alice relative to Mike is the same as their ranking of Alice relative to Mike in the critical election. Specifically, voters 1 to k-1 rank Alice above Mike, and voters k to N rank Alice below Mike

Using independence from irrelevant options and the first property above, in the results of the pre-critical election and election B, Mike’s ranking relative to Bob will be the same. But remember that in the pre-critical election Mike is last place in the results, in particular he is ranked below Bob. So in election B, Mike will be ranked below Bob as well. Similarly, using the second above property, in the results of election B Alice must be ranked above Mike. But Mike himself is ranked above Bob, so in the results of election B, Alice must be ranked above Bob.

Finally, remember that we chose election B in a way that in the results of it and election A, the rankings of Alice and Bob relative to each other remains the same. Since Alice is ranked above Bob in the results of election B, she’s also ranked above him in the results of election A, which is exactly what we wanted to prove.

Well, that was a lot wasn’t it? Luckily we are almost done. We proved Kate solely controls the relative position of candidates other then Mike. It remains to show that Kate also controls Mike’s position in the rankings, then we finally prove that Kate must be a dictator.

Let’s say Nancy is another candidate in the election. We could have repeated the entire proof from before, but replacing Mike with her. That would have given us a voter that controls the relative rankings of all candidates apart from her. Note that it’s not yet certain that this voter is Kate again. Let’s suppose that voter is not Kate, but Lars.

We assumed that there are more than three candidates, so we can take two candidates, Jim and Tim, who are different from each other and from Mike and Nancy. From what was shown before, we know Kate solely controls the relative position of everyone but Mike. In particular she solely controls the positions of Jim and Tim relative to one another. Similarly, Lars solely controls the relative positions of everyone but Nancy. So he too solely controls the relative positions of Jim and Tim. Contradiction, since if Kate and Lars have differing opinions on the relative positions of Jim and Tim, there won’t be any possible results to the election.

So the voter who controls the relative positions of everyone but Nancy must again be Kate. In particular, we deduce that Kate must control the relative position of everyone to Mike. Adding this to what we shown, we deduce that Kate solely controls the positions of everyone in the election. Thus, Kate is a dictator. Q.E.D

A Paradox? Not really…

Arrow’s theorem, which we just proved, is often called Arrow’s Paradox instead. However, I chose to refrain from calling it such. Although it is rather paradoxical that there cannot be a ‘completely’ fair election, the reality is that the properties we wanted were too strict. More specifically, the property of independence from irrelevant options was too strict. As we saw in the proof, it was the main thing that allowed us to move from a general voting caucus to a more crazy, edge case one. All these moves, with some help from Pareto efficiency let us reach the “paradoxical result”.

One final thing to note: let’s say the elections were not to rank the candidates, but rather to choose the best one. Like before, the voters vote their personal rankings of the candidates. Will a similar result to Arrow’s theorem hold here too? The answer is yes.

That result is known as the Gibbard-Satterthwaite theorem. Interestingly, what counts as a ‘fair’ election in that result seems more reasonable than what was in Arrow’s theorem. The two properties are as follows:

• Majority Rule: If all voters place a certain candidate in first place in their vote, that candidate wins the election
• Monotonicity: If a certain candidate wins one election, and in another election their position in each voter’s vote is either the same or better, they will win the other election

One might ask, if the result of the Gibbard-Satterthwaite theorem is arguably more interesting and more ‘paradoxical’, why wasn’t the post about it instead? Well the unfortunate thing is that the proof of Gibbard-Satterthwaite actually heavily relies on the proof of Arrow’s theorem. Then it wouldn’t be much of a surprise that a surprising result will lead to another surprising one, wouldn’t it?