The flaw in every voting system

More thoughts about voting systems.

We recently created this video with the Polylog team. As usual, there is quite a lot of stuff happening behind the scenes that did not fit in the final video. I decided to put that stuff here both to satisfy more interested/advanced viewers and myself. If you did not watch the video, you should do that first!

If you make it to the end of the post, you will be rewarded with a description of the system for electing the doge which I find quite stunning.

Examples

Before we really start, let’s look at a few of the creatures we are talking about. Three voting systems were mentioned in the video: plurality voting (a.k.a. first past the post or one-round election), the two-round system, and approval voting. Here are a bunch of other voting systems you may have come across:

• Alternative vote/instant runoff/ranked choice voting — a generalization of the two-round system; instead of 2 rounds, you run (#candidates-1) rounds. In each round, you let every voter vote for their favorite and the candidate with the least votes drops from the race, you do this until only the winner remains. For practical reasons, voters vote only once and tell you their full preference ordering, then you simulate this process internally. Together with approval voting one of the most popular voting systems among voting theorists.

• Borda count — every voter orders the candidates. If you put a candidate to i-th place, then that candidate gets (n-i) votes from you. Sum up the votes for each candidate and order them by how many votes they got.

• Range voting — generalization of approval voting where you give any number between 0 and M of votes to each candidate, for some M. Sorting YouTube videos by how many likes they got, is an example of this system because giving -1, 0, or 1 vote is equivalent to giving 0, 1, or 2 votes.

• Range voting with average — The example above is a bit weird, maybe some video has 1000 views and 1000 likes and we put it below a video with 2000 views and 1001 likes although the viewers of the first one clearly enjoyed it more. Another option we have is to sort the videos by the ratio of #likes/#views. This corresponds to how we rank movies in top movie lists by their average rating. This makes sense if there are a lot of candidates to choose from, but it’s not that good for political elections — if the only person that cares enough about Joe Loser to even rate him is Joe himself, funny stuff can happen (similarly, top movie lists typically include only films with at least x reviews for some x).

• STAR voting — As in range voting, you are giving 0 to 5 stars to each candidate. The two candidates A, B with the most stars go into the final round where your vote goes to A if you gave her more stars than B, and vice versa. This system is not very well-known but for me, this is an example of a voting system where I find it extremely hard to come up with a plausible story of how we get strategic voting in real-world situations. Basically, the biggest problem with approval/range voting systems is that you can have two very strong candidates A, B and you like both of them but you like A a bit more than B. Then you have an incentive to give B zero votes so as to increase A’s probability of winning. But in STAR voting, you simply give 5 stars to A and 4 to B.

• Condorcet methods — In the video, we discussed how Condorcet cycles are the reason why all voting methods sometimes have undesirable properties. But maybe Condorcet cycles are quite rare in actual elections. Condorcet methods are trying to leverage that: they are supposed to work well in the absence of Condorcet cycles. In particular, whenever there is a candidate who beats everybody in head to head election, this candidate should be elected as the winner by any voting system from this family. Many Condorcet methods are pretty good - one of my favorites is Schulze method.

Our video also discussed a definition of a voting system that covers plurality and the two-round system but not approval voting (I will mention the more general definition later). Which of the above voting systems are captured by that definition? [Answer:¹ ]

Arrow’s theorem

As far as you believe that voting is important, you should believe that Arrow’s and the Gibbard-Satterthwaite theorem are some pretty important pieces of math. Whenever you try to design a new voting system, compare existing ones, or think of what properties you can expect your voting systems to have, these theorems are the place where you start. Yet, I am not completely satisfied with how these theorems are usually introduced and discussed.

I will now tell you how Arrow’s theorem is usually introduced and a bit different way of introducing it that I like better. Then we will do the same for Gibbard-Satterthwaite.

Wikipedia has a nice article about Arrow’s theorem, I will now follow it to define the theorem. We will use the same definition of a voting system as in our video - the system gets candidate rankings from all voters as the input and sorts all candidates for the output.

There are a bunch of conditions that we want our voting system to have:

1. Non-dictatorship — the dictatorship system is the system that always outputs the preference of a single voter. We don’t want our system to be this system.

2. Pareto-efficiency — if every voter prefers A to B, so should the final order.

3. Independence of irrelevant alternatives (IIA) — as explained in the video, if I only tell you how each voter ranks A versus B, you should have enough information to conclude the relative order of A and B in the final outcome.

Now Arrow’s theorem says the following:

Arrow’s Theorem: For any number of voters and any number m>=3 candidates, the following is true. No voting system can satisfy all three conditions above.

Needless to say, for a mathematician, these kinds of statements are incredibly satisfying. Even more so because for any two conditions, there is a simple example of a voting system that satisfies both of them but not the third one. In fact, let’s see those examples.

1. Drop Non-dictatorship: then you allow the dictatorship voting system that satisfies both 2 and 3.

2. Drop Pareto-efficiency: then you can have a system that is itself the dictator, i.e., for any input it returns always the same order of candidates; this system satisfies both 1 and 3.

3. Drop IIA: Pretty much every normal voting system (plurality, two-round, Borda count, …) satisfies 1 and 2, after you specify how to do symmetry breaking in case of a tie.

But notice this: If you drop conditions 1 and 2, you allow systems that are (from the practical perspective) incredibly perverse, they go completely against the spirit of the problem we are trying to understand here — the aggregation of opinions of many different actors.

Virtually every voting system I have ever seen that deserves to be called a voting system satisfies 1 and 2, but not 3. So the way I think about Arrow’s theorem is: No reasonable voting system satisfies IIA, under a very mild definition of “reasonable”.

What I am saying here of course isn’t controversial, after all, if you read the Wiki page I linked, you can see that the writers understand this and discuss it. Still, our video tried to go further and explain Arrow and Gibbard-Satterthwaite without even mentioning the full statement of these theorems (in the case of Arrow this means the conditions 1 and 2 above). Why can this be helpful?

When I talked with some friends about Arrow’s theorem, I felt like they usually remembered that Arrow’s theorem says that no voting system can satisfy several conditions at once (but who knows what they are), sometimes I even heard “the only reasonable voting system is the dictatorship” which I think is an unproductive take. I am pretty sure no one would remember how the proof of the theorem goes — after all, look at Wikipedia where there are two classical proofs of the theorem. Both of them are quite subtle.

What I would like my friends instead to remember about the theorem is that it says that no (reasonable) voting system can satisfy IIA. Also, the ultimate reason for that is Condorcet cycles which also imply a version of the theorem.

Actually, our video did not cover how you can prove the simpler version of Arrow’s theorem with the video’s definition of “reasonable”, so here it is. It’s basically the first half of the proof of Gibbard-Satterthwaite from the video - look at a Condorcet cycle and the voters that are unhappy about the result to find the contradiction.

Proof sketch of Arrow with this definition: Assume that there are just three candidates, if there are even more of them, the proof stays the same. For any number of voters, there exists a Condorcet cycle with that many voters such that there are three groups of voters whose preferences are ABC (=prefer A over B over C), BCA, and CAB. Consider any reasonable voting system.

We can assume without loss of generality that A is the winner elected by the voting system in our Condorcet cycle; this is because the properties of Condorcet cycle are symmetric with respect to A, B, and C. Consider the voter group BCA and change their ballots to CBA. Our definition of “reasonable” and the property of the Condorcet cycle that each of the three groups has less than half of the voters together imply that C should be the winner in this new scenario. So A and C swap their relative order when we go from the original Condorcet cycle to the new scenario.

But this is forbidden by IIA which says that since B is an irrelevant alternative for A and C, voters changing their opinion of B should not lead to a swap in their relative order.

For me, this proof is pretty intuitive, so I think that if somebody wants to learn a bit about voting theory, it makes more sense to first see this proof and understand how it works, and only then see the general definition of Arrow’s theorem and the general proof of it. In the video, we did unfortunately only mention Arrow’s theorem without the proof because of time constraints.

Gibbard-Satterthwaite theorem

Our video was primarily about the Gibbard-Satterthwaite theorem, not Arrow. Let me first state the standard version of that theorem here:

Gibbard-Satterthwaite theorem: For any number of voters, any number number of candidates, consider any voting system such that at least three different outcomes are possible (= there are at least 3 different scenarios where the system outputs different winners). Also, assume that that the voting system is not a dictatorship. Then this system sometimes incentivizes strategic voting.

Here, for simplicity, the definition of a voting system is that we only want to elect the winner and not sort all candidates, as opposed to the setup of Arrow’s theorem. Not that it matters — if your system can only elect the winner, you can always use it to find the winner, then use it one more time on the remaining candidates to find the second candidate, and so on until you get all candidates ordered. On the other hand, if you can sort candidates, as a special case you can elect the winner. So there is a natural way how you can switch between these two setups. ²

The discussion that we just had about Arrow’s theorem and how it’s more understandable if you first see a simpler version of it applies also to Gibbard-Satterthwaite. In fact, the usual formal proof of it utilizes Arrow’s theorem. This means that it takes quite a long time to prove it from scratch and that’s probably the reason why it’s surprisingly hard to find an explanation of Gibbard-Satterthwaite on the Internet. The full, formal proof simply does not fit in a short blog post/YouTube video.

This may be also the reason why Arrow’s theorem is much more famous than Gibbard-Satterthwaite. I am not very happy with this. Arrow’s theorem is incredibly important from the historical perspective — when Arrow proved it in the fifties, he basically started the field of voting systems theory — but I would say that the biggest reason why we care about the IIA condition is that when it fails, it leads to strategic voting. Also, Arrow’s theorem works only for the definition of the voting system we used in our video, which does not even cover the voting systems you are coming across most often (I am thinking of range voting systems, e.g., rating films, restaurants, and all kinds of other stuff). On the other hand, Gibbard-Satterthewaite covers all voting systems.

This place is probably as good as any other to explain the general definition of a voting system for which Gibbard-Satterthwaite still applies. In the general definition, every voter simply has some actions that they can do. For example, in approval voting with m candidates, everybody has 2^m possible actions — you can give a vote to any subset of candidates. The voting system is simply a function that takes these actions as the input and it outputs the winner.

A voter v has the incentive to vote strategically means the following: If you fix the actions of all other voters than v one way, v wants to take some action a_1 to make the system elect the best candidate according to v’s preference. On the other hand, if you fix the actions of all other voters a different way, v wants to take a different action a_2.

Example: A class decides which film to go to, with three options A,B,C. You like A>B>C and are last to vote. If A and B are tied in the first place, you will vote A. If B and C are tied in the first place, you will vote B. This is strategic voting as defined above, it basically means that your vote depends on the context of other votes.

Nonexample: In informal discussions, strategic voting is used a bit more broadly. For example, in our video, we gave an example where you give dislike to a video even though you kind of like it because you really want some other video to win. This is technically speaking not strategic voting according to our definition, at least if you do this same action in every possible context of other people’ ballots.

Going back to Gibbard-Satterthwaite theorem — it was proven in the early 70’s, independently by Satterthwaite who proved it for the weaker definition of a voting system used in the video, and Gibbard who proved it for the general definition of a voting system. This is why the general version of the theorem is known only as Gibbard’s theorem.³ I want to stress how powerful Gibbard’s theorem is. It really works pretty much always and its conclusion is pretty strong.

A reasonable definition of “reasonable”?

When making the video, we had to though hard about the following problem.

What is the best definition of a “reasonable” voting system?

The question is of course not very well-defined, but we are looking for something like this:

1. The definition is intuitive.

2. It is satisfied by real voting systems people use.

3. It should make sense both for Arrow’s and the Gibbard-Satterthwaite theorem.

4. It should make their proofs simple.

There were two main candidates for the definition of “reasonable” that we considered, and I find neither of them completely satisfactory. Here they are.

“If a majority of voters votes for A, then A should be the winner”. This is the definition we in the end used in the video. It leads to simple proofs of both theorems, as you saw.

The main problem with this definition is that according to it, one of the voting systems we have seen so far is not reasonable (which one?). We hoped this shouldn’t be a dealbreaker for our video, but in general, I find this quite unsatisfactory.

“The system does not prefer any voter to another one. Also, it doesn’t prefer any candidate to another one. “ By this definition, I mean the following:

1. If the ballots that are the input to the system are first permuted, it should not change the outcome of the system.

2. If you swap A and B on every ballot, then A and B should be swapped in the final order.

This is extremely elegant. In fact, maybe you have already been wondering: Why isn’t this part of the standard definition of a voting system!? All voting systems that we mentioned are designed to satisfy this property. But then again, there are reasonable systems that don’t. For example, the Council of the European Union uses the so-called double majority: you need at least 15 of 27 countries + at least 65% of EU population for your proposal to go through. The second condition fails our “reasonability” criteria as each country has a different weight.

But the biggest problem for us was this: No voting system can satisfy this definition! :) Ties are the problem. Basically, if you have two people, one prefers A to B and the other B to A, there is no way to elect the winner and keep this definition of “reasonability” satisfied. If you say that clearly nobody should be elected here and our definition of a voting system should include the possibility of ties, then you are completely right. But then everything becomes a bit clumsy. Also, what about the preschool teacher voting system that always outputs “everybody is the winner”? We need to add at least one more condition to our definition of “reasonable” to forbid this system.

As the other Václav from our Polylog team put it, our video already has “a lot of surface and not so much volume”, meaning a lot of definitions and not so much proof action going on. Now imagine 5 more minutes of discussing subtleties with ties…

So in the end we went for the first option, but I am not completely happy with it. If you can think of other interesting options to choose from, let me know in the comments! As far as I know, this is an interesting open exposition problem. ⁴

Takeaway

Our video was supposed to be accessible to as many people as possible, but there were also several more advanced and often neglected ideas that we tried to gesture at:

• Arrow’s and the Gibbard-Satterthwaite theorems should be looked at as saying that “reasonable” systems fail to have some nice properties.

• The proofs of the theorems are not so complicated to understand if you don’t shoot for the most general definition of “reasonable”.

• Arrow’s theorem actually does not apply to many important voting systems.

• The Gibbard-Satterthwaite theorem is perhaps more interesting and fundamental than Arrow’s.

• Both theorems are worst-case in nature. They are good to know but this is just the beginning of a more complicated discussion of which voting systems fail how often and in which way.

If we managed to convey at least some of those points without confusing you, then we were successful. :)

The last point is especially important — although Arrow and Gibbard-Satterthwaite are very qualitative theorems (they apply to every voting system in the same way), the reality is more quantitative (some voting systems are better than others). Unfortunately, capturing that is complicated.

Ultimately, what we care about is not strategic voting per se, it is something like: “If we use this voting system, on average, how happy are voters going to be with the result?” For example, the dictatorship voting system is bad because, in most situations, the dictator is going to be a crappy alternative for most voters.

The important observation is that this fuzzy objective correlates with strategic voting — to give an example, plurality voting is a bad voting system because it leads to the so-called spoiler effect where a popular candidate A might not win only because voters “split” their votes between A and a similar candidate A’. But you can view this problem as a problem of strategic voting — voters are forced by the system to vote for A even if they like A’ a bit more. So strategic voting is a helpful way to understand problems with voting systems, but the objective we actually care about is something fuzzier, harder to describe and to agree on. See this for more discussion.

As I said in the beginning, Arrow and Gibbard-Satterthwaite are the place where we start a discussion about voting systems. But it is just the start.

Bonus: Electing a doge

By a doge, I of course mean the leader of Venice.

Leonardo Loredan, a Venetian doge, in fact, one of the more important ones

Here is how the election process went.

“Whenever the time came to elect a new doge of Venice, an official went to pray in St. Mark’s Basilica, grabbed the first boy he could find in the piazza, and took him back to the ducal palace. The boy’s job was to draw lots to choose an electoral college from the members of Venice’s grand families, which was the first step in a performance that has been called tortuous, ridiculous, and profound. Here is how it went, more or less unchanged, for five hundred years, from 1268 until the end of the Venetian Republic.

Thirty electors were chosen by lot, and then a second lottery reduced them to nine, who nominated forty candidates in all, each of whom had to be approved by at least seven electors in order to pass to the next stage. The forty were pruned by lot to twelve, who nominated a total of twenty-five, who needed at least nine nominations each. The twenty-five were culled to nine, who picked an electoral college of forty-five, each with at least seven nominations. The forty-five became eleven, who chose a final college of forty-one. Each member proposed one candidate, all of whom were discussed and, if necessary, examined in person, whereupon each elector cast a vote for every candidate of whom he approved. The candidate with the most approvals was the winner, provided he had been endorsed by at least twenty-five of the forty-one.”

— Anthony Gottlieb, "Win or Lose," The New Yorker.

And a diagram for those of you who don’t find the process crystal clear:

https://www.theballotboy.com/electing-the-doge

What I find particularly striking is how this process uses some of the interesting voting system ideas like randomness or approval-like voting. A bit too complex if you ask me, but remember, this thing survived pretty much unchanged, like, 500 years of the Middle Ages, so who am I to judge it?

Links

I am pretty sure there are some nice explanations of Arrow and Gibbard-Satterthwaite out there — if you know some, or if you know some nice sources related to voting theory, post them in the comments! Here are some links you might like.

There is a very nice YouTube video with some examples of strategic voting in real world systems.

https://olsak.blog.idnes.cz/blog.aspx?c=642275 — We took Mirek’s story about monkeys from this text, but in the end approached the topic quite differently.

https://www.lesswrong.com/posts/D6trAzh6DApKPhbv4/a-voting-theory-primer-for-rationalists

Wulf Gaertner: A primer in social choice theory

Nisan, Roughgarden, Tardos, Vazirani: Algorithmic Game Theory

Condorcet.

Do you like this style?

Let me know if you like this kind of longer, less polished, and less organized posts in the comments section. Making this kind of post is much much much much less effort than making a video.

We used Midjourney to create images in our video. You can tell it to combine an image of a monkey with an image of an avocado; we used that feature with mixed results.

1. The first two systems and the last one.

2. If you are into fancy comparisons: This is pretty much the same argument as why the axiom of choice is equivalent to the well-ordering principle.

3. Yes, it is confusing.

4. I like this term, it’s stolen from here.