In the wake of election day, I've been part of a few conversations about the problems with the common first past the post system for single winner elections. There are many choices for different voting systems and they all make some tradeoffs. There are many theorems that establish that such tradeoffs are necessary, but the specifics of impossibility theorems would just serve as a distraction for the purposes of this post. Rather than try to talk about all of the theory behind all of the possible voting system options, I want to talk specifically about approval voting.

Approval voting is easy to describe: A voter may vote for any number of candidates, and the candidate with the most votes wins. The idea is that they vote for all candidates that they "approve" of.

The reason I am writing specifically about approval voting today is because there is a lot of information about it on rangevoting.org. Unsurprisingly, a website with this name is advocating range voting, but it also suggests approval voting as the next best thing. There is a lot of good information on the site, but a lot of it seems to be presented in a way to make Condorcet methods look bad, without mentioning whether approval voting actually fixes the issue or not.

Voter honesty

The front page claims that approval voting encourages honesty as virtue 3. The "executive summary" of this honesty property correctly states that strategically it never pays to claim that you prefer B to A (meaning you vote for B and not A) when you actually believe that A is better than B. The front page also links to this example where most Condorcet methods will incentivize such a lie.

The example is as follows:

• 8 voters consider B > C > A
• 6 voters consider C > A > B
• 5 voters consider A > B > C

In this case, the head-to-heads are A > B, B > C, C > A. This is a so-called Condorcet cycle, and depending on your exact method one of the candidates will win, probably B. But the only reason that A didn't win is that C can beat A in a head-to-head. So the voters that prefer both C and A to B, but voted C > A (in this case, the 6 voters that voted C > A > B), will be incentivized to lie and vote A > C > B instead. If they do that, then A wins the head-to-head against both other candidates and becomes the winner, which is an improvement in the eyes of those 6 voters. Once this switch happens, no single block of voters can improve the result of the election by changing their votes, though of course any two set of two blocks can cooperate to choose the winner. If you were to choose a different winner originally, essentially the same thing would happen with a different block of voters.

Okay, so Condorcet methods have some amount of strategic voting that involves lying. What does approval voting do in this case? Let's assume that originally everyone approved of their top two candidates:

• 8 vote BC | A
• 6 vote CA | B
• 5 vote AB | C

For representing approval votes, I have written the vote in two parts while keeping all of the candidates in the voter's true preference order. So "BC | A" means that they vote for B and C, and have the preference of B > C > A. In this election, A has 11 votes, B has 13, and C has 14, so C wins.

However, the voters who voted BC | A could get a better result by voting B | CA instead. Let's say they do that:

• 8 vote B | CA
• 6 vote CA | B
• 5 vote AB | C

Now A has 11 votes, B has 13, and C has only 6, so B wins. But now the voters who voted AB | C can get a better result by voting A | BC instead:

• 8 vote B | CA
• 6 vote CA | B
• 5 vote A | BC

Now A has 11 votes, B has 8, and C has 6, so A wins. But the B | CA voters can get a better result by voting BC | A!

• 8 vote BC | A
• 6 vote CA | B
• 5 vote A | BC

A has 11 votes, B has 8, C has 14, so C wins. We've reach an equilibrium of sorts, in that no single block of voters can change their preference to directly get a better result. But, of course, the block of BC | A voters and the block of A | BC voters can cooperate to get B elected by voting B | CA and AB | C, respectively, and this is an improvement for both parties.

Additionally, the A | BC voters are incentivized to enable this change even without the cooperation of the BC | A voters. If they believe that C is the most likely candidate to win, then because they would be happier with anyone else, they might as well vote for all of the other candidates to maximize their chances. So, in some sense, this final election is not a true equilibrium either, and we'll loop back to the place we started.

In fact, the linked paper claims that approval voting cannot have an equilibrium in the abscence of a Condorcet winner, although I have not quite convinced myself of the argument yet. In that case it is not clear that approval voting actually results in a superior outcome in these cases, as it is hard to determine what the outcome is in the first place.

This is in contrast to the scenario with Condorcet systems, where the B > C > A voters are getting their last choice, but what vote should they do to maximize their chance of B or C getting elected? Whether B > C > A or C > B > A is more likely to benefit them depends nontrivially on the actions of the other voters, so the equilibrium only breaks in the presence of collaboration between voter blocks.

It is also worth noting that approval voting actually forces voters to be merely "semi-honest", as in a three candidate election they must treat two equally even if they actually have preferences between all three.

More than 3 candidates

Furthermore, when there are more than 3 candidates, it is no longer true that if you prefer A to B then you'll never vote for B and not A. One example is if you're confident that the race will come down to one of two pairs of candidates, but not sure which one. Specifically, say you prefer A > B > C > D, and you believe that either A and B will get far and away the most votes, or C and D will, but you aren't sure which one. Then you'd strategically want to vote for A and C, but not B and D, so that you can impact both possible elections.

This is mentioned on rangevoting.org, but is conveniently not mentioned on the honesty "executive summary", or even on the page linked for "more details". Furthermore, this new page indicates that in simulations with a "moving average strategy", such dishonest votes occur with nontrivial frequency as the number of candidates increases. The page mentions that the moving average strategy is "less naive" but gives no indication of whether it is better or worse than a simple honest strategy.

Does approval voting elect the Condorcet winner if it exists?

A Condorcet winner is a candidate that would defeat any other candidate in a head-to-head election. It's not hard to see that approval voting can fail to elect the Condorcet winner. If every voter only votes for a single candidate, then approval voting will select the plurality winner, which can certainly fail to be the Condorcet winner.

However, rangevoting.org claims that approval voting with strategic voters will elect the Condorcet winner if one exists, and links to a paper making a siimlar claim. The linked paper is a little bit more cautious and makes the assumption of a unique "best contender", and phrases the "will elect" result as the unique equilibrium, which is a more precise and accurate claim.

The rangevoting.org page has an extremely simplified proof that tacitly assumes that a pure strategy equilibrium exists by refering to "the" approval winner. I was actually so thrown off by this phrasing that for a while I thought that the statement was false! It turns out that the more precise equilibrium claim is true, and the paper's proof appears to be correct, but rangevoting.org's "proof" is overly simplified to the point of not being a valid proof.

In the simplified "proof" voters have knowledge of both who the Condorcet winner is, who we'll call candidate C, and the "Approval winner" (which really should be the candidate with the best head-to-head performance against C), who we call candidate A. They then claim, correctly, that strategic voters will place their approval thresholds between A and C. But this means that A and C get votes equal to their head-to-head, which means that C will get more votes, and therefore the winner of an approval vote will be C.

However, just saying that the approval threshold is between A and C is insufficient to show that C actually wins the election. If there are voters who consider C > B > A, then if those voters put their threshold between B and A, this can cause B to win the election. Here is an example:

• 10 voters consider W > X > Y > Z
• 27 voters consider X > W > Y > Z
• 27 voters consider Y > W > Z > X
• 27 voters consider Z > W > X > Y
• 31 voters consider X > Y > W > Z
• 30 voters consider Y > Z > W > X
• 29 voters consider Z > X > W > Y

In this pool of 181 voters, the head-to-head results would be:

• W vs X: W wins 94-87
• W vs Y: W wins 93-88
• W vs Z: W wins 95-86
• X vs Y: X wins 124-57
• X vs Z: Z wins 113-68
• Y vz Z: Y wins 125-56

W is the Condorcet winner, and in the phrasing of the simplified "proof", we should set the "Approval winner" to be Y. Now if the votes go as follows:

• 10 votes W | XYZ
• 27 votes XW | YZ
• 27 votes Y | WZX
• 27 votes ZWX | Y
• 31 votes XY | WZ
• 30 votes YZ | WX
• 29 votes ZXW | Y

Then the results would be:

• W gets 93 votes
• X gets 114 votes
• Y gets 88 votes
• Z gets 86 votes

and X wins. However, this is not an equilibrium because the ZWX | Y voters can get a better result by dropping their votes for X and voting ZW | XY instead. In this case, the votes would go:

• 10 votes W | XYZ
• 27 votes XW | YZ
• 27 votes Y | WZX
• 27 votes ZW | XY
• 31 votes XY | WZ
• 30 votes YZ | WX
• 29 votes ZXW | Y

with results

• W gets 93 votes
• X gets 87 votes
• Y gets 88 votes
• Z gets 86 votes

and W wins. This set of votes actually is an equilibrium: all voters are already voting for everyone that they prefer over the winner W, and therefore changing their votes would only allow themselves to be hurt. So to be more precise, the equilibrium is given as follows:

• Every voter will vote for everyone who is better than the Condorcet winner.
• Every voter will not vote for anyone who is worse than the Condorcet winner.
• Every voter will choose to vote for the Condorcet winner or not by comparing it to the best contender.

In this strategy, each candidate will get the number of votes that they would get against the Condorcet winner in a head-to-head, and the Condorcet winner will get a number of votes equal to how many they would get in the head-to-head against the best contender. Therefore, the Condorcet winner will get the most number of votes (and more than half of the voting population), while every other candidate will get less than half of the population.

This will be an equilibrium because everybody is voting for exactly one of the Condorcet winner and the best contender. If some number of voters drop votes for the Condorcet winner, this will cause the best contender to win, which is a worse result for them. Similarly, if some number of voters add votes for any other candidate and cause this candidate to win, that will be a worse result for them.

This is presented as "for practical purposes, Approval is a Condorcet method." I'm not sure that I would consider this mathematical statement to have any bearing on the situation in practice. We're assuming that the entire voting population knows the preferences of the entire rest of the voting population beforehand. But how would they get this information? If the entirety of the voter population agrees on who the Condorcet winner is, why don't we make the source of that information the actual election?

Bayesian Regret

There's lots of data on rangevoting.org about so-called "Bayesian Regret", in which every voter has a "true" utility that they'll gain for each winner. People aren't necessarily good at judging their utility gains, so each voter gets a noisy value instead. Then they vote based on that noisy value. The Bayesian Regret is the difference between the total utility gain of the best candidate versus the candidate that actually got elected using the true utility values.

So when we run simulations, we get this graph. Wow! Approval voting is so good! The "honest" value is a little bit worse than honest Condorcet, but strategic voting clearly hurts Condorcet methods significantly more than it hurts Approval.

But wait, what does "honest" approval mean? Casting a vote just for my favorite candidate is an honest vote, as I didn't misorder any of the candidates. But if everyone does that, we'll just get the plurality winner. So how can approval and plurality possibly not overlap at all? Surely the approval range should at least cover the "honest" plurality regret number.

The answer is that the source of these numbers, this paper, defines "honest approval" voting in a particular way where voters compute the average utility of all of the candidates and vote for everyone who would give them higher utility than that. Here's a quote from the paper, which you can find on page 19. (The author of the source paper is one of the co-founders of rangevoting.org, so this is a case of differing presentation but not a case of misunderstanding).

System 16 is actually on the borderline between "honest" and "strategic" voting, since 16 is the most strategic form of honest approval voting, cf. lemma 1, given that no poll-data is known.

The "strategic" strategy used in the paper is to set the threshold between the two frontrunning candidates, specifically to their average. That is system 17 in the paper:

System 17 is also on the borderline, since each voter always produces an "honest" approval-type vote, but attempts to do so by choosing his utility threshold strategically in view of the poll results.

So both "honest" and "strategic" approval voting are on the border of honest and strategic. No wonder they don't give substantially different results! Compare to the treatment of Condorcet methods:

What I am calling "strategic" voters is not necessarily the same thing as what I have elsewhere called "rational" voters. Rational voters choose the vote maximizing their expected utility in some statistical model of the remaining voters. Strategic voters try to be near-rational, but in the interests of simplicity I have not tried always to find the exact optimal vote, sometimes settling for a vote which presumably yields higher expected utility than the honest vote, but not as high as the rational vote.

So what is the particular strategic Condorcet strategy?

Strategic Condorcet Least Reversal, Copeland, Black, hare, & Coombs STV (22, 28, 29, 23, 25): give the best of the two frontrunners the max vote and the worst the min vote. Order the remaining \(c - 2\) candidates honestly. This is a plausible-sounding strategy, since it maximizes the chances that the disliked frontrunner will be eliminated in some STV round and minimizes the chances the liked frontrunner will be; similarly this minimizes the number of Condorcet vote-reversals the more liked frontrunner must endure, while maximizing the number for his opposing frontrunner.

In other words, the "strategic" voters being compared here are voters that are maximally exaggerating about the two frontrunners. As far as I see, there is no justification that this actually improves the expected utility for the voter over honest voting. It appears to be attempting to maximize the "burying" idea, but if the two frontrunners are close to each other, these strategic voters will be causing all of the other candidates to go about even with the two frontrunners as well, and therefore making those other candidates much more likely to win, as they need a substantially smaller number of honest voters to bring them into the Condorcet cycle.

It is true that if literally every voter follows this strategy with the same two frontrunners in mind, then one of those two frontrunners will get a majority of top votes, and therefore be the Condorcet winner. However, this don't seem to have any bearing on whether doing this strategy is actually beneficial. If there are only two candidates with a chance to win, then the only relevant part of your ballot is the head-to-head comparison between them. Burying works only in cases with a Condorcet cycle, but in that case in what sense are there two frontrunners?

I haven't had the time to do further analysis, but it would not surprise me if these strategic voters were actually decreasing their expected utility compared to voting honestly. If the so-called "strategic" voters are hurting themselves, it is utterly unsurprising that they also hurt the society at large.

How do you choose an approval threshold?

One issue that I haven't seen discussed anywhere is that I believe it is easier to sort candidates than to score them by utility. Let's make an example out of sushi. Let's make a list of some different types of sushi:

• Tuna
• Yellowtail
• Salmon
• Salmon Roe
• Eel
• Sea Urchin

If you've eaten each of these types of sushi, you can probably rank them. When I'm looking at a ranking I can look at a comparison and think "If I could have just one of these two types of sushi, which one would I prefer?" And for me this would give the ranking Salmon Roe > Salmon > Yellowtail > Tuna > Eel > Sea Urchin. So with not too much trouble, I can construct an honest ranked vote.

But what about an approval vote? For "honest" approval voting as defined above, I need to determine my average utility between all six options. How do I determine if Tuna is better than the average of all six? I can't ask myself if I'd rather have six pieces of tuna or one of each, because the variety is going to win every time.

If Salmon and Tuna were the frontrunners, the "strategic" idea would ask me to determine whether Yellowtail is better or worse than the average of Salmon and Tuna. If the frontrunners were next to each other in my ranking, then casting my vote would be easy. But for most people that won't be the case.

On the topic of strategic votes, if we were voting Condorcet style and you told me that Salmon and Tuna were the frontrunners, would I really change my vote in order to maximize the chance that Salmon wins over Tuna? Maybe if I hated Tuna I could be convinced to lie and say I hate it more than I actually do, or if I love Salmon I might be convinced to put it above Salmon Roe. But in reality, I like Salmon Roe a lot more than both, and Eel and Sea Urchin quite a bit less. I have a hard time imagining that I would want to give Salmon Roe less of a chance, or Eel and Sea Urchin more of a chance, just to increase the chance that Salmon wins over Tuna.

A simple strange scenario for approval voting

Let's imagine we're voting on dinner for a large group of people. There are two contenders: steak and lobster. In a group of 101 people, maybe 57 prefer steak and 44 prefer lobster. An approval vote between two candidates is just the same as a majority vote, so steak will win.

Okay, now let's imagine that someone decides to nominate a third candidate: garbage. Well, nobody wants to eat garbage for dinner so nobody is going to vote for it. But the question is how many people will now change their vote to include both steak and lobster, to minimize the chance of garbage winning?

If enough people change, and these vote changes aren't split evenly between the steak-voters and the lobster-voters, the result of the vote could be reversed. Any claim that the approval winner does not change when irrelevant alternatives are added implicitly assumes that approval thresholds do not change when candidates are added or removed, which is an assumption that I find unreasonable.

This particular scenario actually does not cause Condorcet methods any problem, even in the presence of strategic voters. If the 57 steak voters vote steak > garbage > lobster, and the 44 lobster voters vote lobster > garbage > steak, then steak is still the Condorcet winner, as it wins both head-to-heads 57-44.

Conclusion

Based on what I've seen, the frontrunners for voting systems are Condorcet (probably Schulze), Approval, and Range voting. It seems to be a common sentiment (and one that I hold) that if a Condorcet winner would exist with honest votes, then it is a good choice, if not the best choice, for the winner of the election. The arguments against Condorcet methods are then that the system is hurt by strategic voting, and the incentives to be dishonest will cause the honest Condorcet winner to lose in an unacceptable number of circumstances.

If rational voting in Condorcet systems does actually lead to a Condorcet winner losing, this would be a strong argument. However, none of the references that I have seen so far have even attempted to establish a rational voting strategy in Condorcet systems, and therefore there is no evidence for or against the existence of this effect.

Even if this effect doesn't exist, range voting advocates will argue that we can do even better than the Condorcet winner by having people state the magnitude of their preferences. But as I said before, I am unconvinced that people can judge such magnitudes as easily as they can judge their order of preferences. Furthermore, rational range voting almost always leads to casting approval-style votes, so it's not clear how much of the societal gains that are possible from honest range voting will actually be realized.

So I remain unconvinced between these three systems. Here are the main open questions that I have, which may or may not be straightforward to resolve.

• How well do humans do at attempting to replicate the "scaled utility" strategy for range voting?
• What portion of voters will vote strategically in the case of range voting, and thus cast only approval-style ballots?
• Does the "strategic" voting method for Condorcet methods that involves exaggerating the two "frontrunners" actually increase individual utility? If so, what is the definition of frontrunner in which it does?
• Is it possible to characterize a "rational" method for Condorcet voting?
• How do humans choose their approval threshold in practice?
• What are the mixed-strategy equilibria for approval and range voting when there is no Condorcet winner?
• What are the equilibria for Condorcet voting systems?