The Strategic Cancellation Lemma

Loosely speaking, the strategic cancellation lemma says that, under a voting method like STAR, Approval, or Minimax which passes the opposite cancellation criterion, it is strategically optimal for voters with opposite preferences to vote in opposite ways. (A more rigorous formalization of this and a proof is at the bottom of this post for mathematically inclined readers.) To begin with, let’s go over what it means to have “opposite preferences” or to “vote in opposite ways”.

Suppose my utilities for who wins an election are {Alice: 10, Bob: 4, Carol: 0, Dan: 1}. This means that I most want Alice to win the election; Bob is my second choice and Carol is my last choice. It also means that I consider Bob to be mediocre and Dan to be almost as bad as Carol, and that I’d be indifferent between:

• Option A: Alice wins 40% of the time and Carol wins 60% of the time; and
• Option B: Bob wins 100% of the time.

A voter with the opposite preferences would have the utilities {Alice: 0, Bob: 6, Carol: 10, Dan: 9}. This voter’s desire to maximize their own utility from the election is equivalent to a desire to minimize my utility from the election.

What it means to vote in the opposite way depends on the voting method in question. Using the last example:

• Under Approval, if I only vote for Alice, the opposite way to vote is to vote for every candidate other than Alice.
• Under STAR, if I vote Alice: 5, Bob: 1, Carol: 0, Dan: 0, the opposite way to vote is Alice: 0, Bob: 4, Carol: 5, Dan: 5.
• Under a ranked method, if I vote Alice>Bob>Dan>Carol, the opposite way to vote is Carol>Dan>Bob>Alice.

Applications of the strategic cancellation lemma

The strategic cancellation lemma elegantly disproves many false claims about Approval and STAR, such as that strategic voters will always bullet vote under Approval or will always vote 5–1–0 or 5–0–0 in a three-candidate STAR election; while it may be strategically optimal for some voters to vote in such a way, it cannot be simultaneously optimal for voters with the opposite preferences to also vote that way. More broadly, the strategic cancellation lemma functions as a basic sanity check for any claim on how a voting method that passes the cancellation criterion fares in a given scenario. In the chicken dilemma, it draws attention to how voters in the smaller faction should vote when most analysis focuses on the larger faction. It can also be used to show the incoherence of many other claims regarding strategic voting. An example from FairVote’s anti-STAR hit piece:

As an example, consider the 2017 French presidential election. The French president is elected in a two-round runoff election: voters cast one vote for any candidate, and if no candidate earns a majority, the top two participate in a runoff election. Going into the first round, there were four very strong candidates: Emmanuel Macron (centrist), Marine Le Pen (right wing), François Fillon (conservative), and Jean-Luc Mélenchon (left wing). Polls in advance of the first round showed two things very clearly: all four had very similar levels of base support (about 20 percent each, with the other 20 percent split among seven other candidates). And if Macron finished in the top two, he would likely beat any competitor head-to-head.

Suppose this election took place using STAR voting, instead of a two-round runoff election. Supporters of any candidate other than Macron would have two strong incentives: help their favorite reach the runoff round, and also keep Macron out of the runoff round. For instance, Mélenchon’s enthusiastic base would maximize his chances of winning by giving him a score of 5, giving Macron a score of 0, and then giving Le Pen and Fillon scores of 4, even if they would prefer Macron to either Le Pen or Fillon. That way, Mélenchon would be more likely to face either Le Pen or Fillon in the runoff round, in which their ballot would count as one vote for Mélenchon. If enough Le Pen and Fillon supporters do something similar, then they could collectively keep Macron out of the runoff round. In turn, their favorite candidate would have a chance to win against a weaker opponent than Macron.

Let’s suppose that FairVote is right and a Mélenchon supporter with the utilities {Macron: 6, Le Pen: 0, Fillon: 4, Mélenchon: 10} is best off voting Macron: 0, Le Pen: 4, Fillon: 4, Mélenchon: 5. Then a Le Pen supporter with the opposite preferences would be best off voting Macron: 5, Le Pen: 1, Fillon: 1, Mélenchon: 0. This is both absurd and in contradiction to FairVote’s claims of what is strategically optimal — and this contradiction disproves FairVote’s claims. It’s easy enough to rebut FairVote without the strategic cancellation lemma, but it’s still a useful tool that can handle many such claims in one fell swoop.

It’s still possible for a voting method for which the strategic cancellation lemma is applicable to run into issues with strategic voting. This can happen when voters with an opposite preference don’t exist (or at least are a small minority). Consider a Borda Count election with four candidates: Edna, Felice, Greg, and Horrible Horus. Every voter has utilities like {Edna: 10, Felice: 5, Greg: 4, Horus: 0} or {Edna: 5, Felice: 4, Greg: 10, Horus: 0}, with roughly equal numbers of supporters for each of the first three candidates, and every voter agrees that Horrible Horus is the worst candidate. The standard criticism of Borda Count is that a voter with the utilities {Edna: 10, Felice: 5, Greg: 4, Horus: 0} voter is best off casting a dishonest ballot like Edna>Horus>Felice>Greg. The strategic cancellation lemma says that, if this is strategically optimal, an opposite voter (who would have utilities {Edna: 0, Felice: 5, Greg: 6, Horus: 10}) would be best off voting Greg>Felice>Horus>Edna — but this is irrelevant because such a voter doesn’t exist.

The strategic cancellation lemma can also be useful in more abstract settings. If you’re trying to incorporate strategic voting into a computer simulation that’s looking at more than just one-sided strategy, it’s worth checking that the proposed strategies are consistent with the strategic cancellation lemma. Of course, this doesn’t apply to voting methods like IRV or Plurality which fail the cancellation criterion.

Precise formulation and proof

Let m be a function that takes any number of ballots as input and outputs a winner (i.e. a voting method), U be a function that gives a voter’s utility for any possible winner, b be any ballot, and B be a random variable corresponding to all other ballots that will be cast in the election. Then a strategically optimal ballot for this voter is g ∈ argmax(E[U(m((b; B))]) and a strategically optimal ballot for a voter with the opposite preferences is e ∈ argmax(E[-U(m(b; B))]) = argmin(E[U(m(b; B))]). (E denotes expected value.)

Strategic cancellation lemma: Suppose that the voting method m passes the cancellation criterion, such that for any ballot b there exists a ballot b^-1 such that m(B) = m(b, b^-1; B). Also suppose that, where c is any ballot, the set of optimal ballots argmax(E[U(m(b; B))]) = argmax(E[U(m(b, c; B))]) and argmax(E[-U(m(b; B))]) = argmax(E[-U(m(b, c; B))]); that is to say, the addition of a single ballot to the election does not change what is or is not a strategically optimal ballot for the voter or for a voter with the opposite preferences. Then E[U(m(e; B))] = E[U(m(g^-1; B))], i.e. it is strategically optimal for a voter with the opposite preferences to vote with the opposite ballot.

Proof: Suppose the conclusion does not hold. Then E[U(m(e; B))] < E[U(m(g^-1; B))] and E[U(m(e, g; B))] < E[U(m(g^-1, g; B))] = E[U(m(B))] = E[U(m(e, e^-1; B))] in contradiction to the optimality of g.