Does Gibbard–Satterthwaite theorem apply to all voting systems?

Question

People often say "It's been mathematically proven that no perfect voting system is possible" and cite Arrow's Impossibility Theorem, but Arrow's theorem specifically only applies to ranked/preferential systems. In Dr. Arrow's words, cardinal systems "imply more information" and so are not covered by this theorem.

I've seen in various places that the Gibbard–Satterthwaite theorem still applies to these other systems, and therefore they are also inescapably subject to tactical voting, but I've also seen advocates say that G–S theorem likewise only applies to ranked systems, and that score voting meets all the criteria when there are ≤3 candidates. They also claim that "double range voting" evades the G-S impossibility theorem.

So which is it?

Answer 1

Short answer: yes, it does. People often present variants of this theorem that are a lot weaker than its most powerful version.

Whereas Satterthwaite's version only applies to ordinal voting systems, Gibbard's version applies to all deterministic voting systems, including non-ordinal ones. Combining Gibbard's version and a remark made by Satterthwaite, a complete version of the theorem is: "Every deterministic voting system with at least 3 eligible candidates is either dictatorial or manipulable." Here, I use the phrase eligible candidate to mean that the candidate is actually in the image of the voting system (if three candidates exist but you accept that one of them cannot be elected in any situation, then you can consider the simple majority rule on the other two candidates, which is neither dictatorial nor manipulable).

In fact, this result is only a corollary in Gibbard's paper. The main theorem is incredibly powerful in my opinion and deserves to be known more widely: "Every straightforward game form with at least three possible outcomes is dictatorial." A game form is similar the the usual notion of game, except that you do not provide a priori the preferences of the player over the possible outcomes. For example, matching pennies and battle of the sexes can be viewed as two different games corresponding to the same game form. The word straightforward means that, given your preferences, you always have an undominated strategy. In other words, applied to voting systems, it means that whatever your preferences are, you can choose the ballot that best defends your opinion, without knowing what other voters will do.

To finish with the deterministic framework, I'd like to comment on the case where some voters can be indifferent between two candidates or more. As noticed by Satterthwaite, the original theorem immediately implies that, on the subset of configurations where all voters have strict preferences, the system is dictatorial (given the usual assumptions, i.e. non-manipulability and at least 3 eligible candidates). Which is already not very good...

But you can imagine the following system, called sequential dictatorship. Step 1 : if voter 1 has a most-liked candidate, then this candidate is elected. Otherwise, restrict the possible results to her most-liked candidates. Step 2 : if voter 2 has a most-liked candidate (among the remaining ones), then this candidate is elected. Otherwise, restrict the possible results again. And so on. This system is not manipulable, and it is not dictatorial, in the sense that the result does not depend only on voter 1's ballot.

However, it is dictatorial in Gibbard's sense: for any eligible candidate, voter 1 can cast a ballot such that this candidate is elected, whatever other voters do. So, even if indifference is possible, you cannot really escape Gibbard's theorem...

Manipulation of Voting Schemes: A General Result, Gibbard, 1973.

Strategy-Proofness and Arrow’s Conditions: Existence and Correspondence Theorems for Voting Procedures and Social Welfare Functions, Satterthwaite, 1975.

But there is more: in 1977 and 1978, Gibbard extended this result to non-deterministic voting systems. A voting system is unilateral if the outcome only depends on the strategy (i.e. ballot) of one voter. A voting system is duple if the final outcome is restricted to a pair of alternatives. In short, the theorem goes like this: "Any straightforward game form (deterministic or not) is a probability mixture of game forms each of which is either unilateral or duple."

Intuitively, you can design a non-manipulable voting system like this: you draw a voter at random, and the outcome (which is a probability distribution on the candidates) depends only on her ballot. If the outcome attributes a probability 1 to her most-liked candidate, the system is called a random dictatorship. But other systems are possible: for example, probability 2/3 for her most-liked candidate, and 1/3 for her second most-liked candidate.

You can also design a non-manipulable voting system like this: you draw two candidates at random, and voters choose between these two according to a specific voting rule (for example simple majority).

The idea of the theorem is that any non-manipulable voting system is a probability mixture of these two types. For example, you toss a coin, and then you use the first or the second system.

Now, what happens if you add a very reasonable requirement to your voting system, for example unanimity? This word means that if a candidate is the most liked for all voters, then she should be elected with probability 1. With this additional requirement, the only suitable voting systems are random dictatorships. You draw a voter at random (not necessarily uniformly), and this voter chooses the winner.

Straightforwardness of Game Forms with Lotteries as Outcomes, Gibbard, 1978.

Answer 2

The G-S theorem does not apply only to ranked/preferential systems.

The G-S theorem merely assumes that each individual has a ranked set of preferences, not that the voting is conducted in that manner. Indeed, in its most basic original form, it is formulated as a first past the post with an either or choice voting system, although the principle can be generalized more broadly.

Answer 3

(?) Score voting meets all the criteria when there are ≤3 candidates: false.

Consider this voting rule with 3 candidates. As claimed in the webpage you mention, it is always best to give the highest authorized grade to your most-liked candidate and the lowest authorized grade to your most-disliked candidate. But choosing what grade you assign to your middle candidate is strategic. You should give her a good grade if your most-disliked candidate has a strong chance to win (to avoid a catastrophe), and a bad grade if your most-liked candidate has a strong chance to win (to avoid rivalry, i.e. risking a victory of your candidate 2 whereas your candidate 1 could win).

Gibbard's theorem essentially says this: in order to choose the ballot that best defends your preferences, you sometimes need to know what the other voters will do; knowing your preferences is not sufficient.

(?) "Double range voting" evades the G-S impossibility theorem: false.

Remark: since it is a randomized voting rule, we are not talking about G-S theorem but rather Gibbard's second theorem (1978).

First reason is that, as I mentioned earlier, you essentially cannot escape Gibbard's theorem...

In details, since the voting rule is quite intricate, I will first consider the case epsilon = 0. In that case, candidate A (the winner in rule X) is surely elected, hence the voting rule is simply equivalent to the voting rule X. For example, if X is Range Voting, then the composite voting rule is equivalent to Range Voting. Of course, it is manipulable.

Globally, the webpage you mention is full of non-rigorous reasoning. For example: "Because p and the identities of B and C are unpredictable, only honest scoring is risk-free [in your X-style ballot]." That's not correct, because your X-style ballot also determines who A, B and C will be. For example, assume epsilon > 0. If, lucky you, your most-liked candidate is A (the winner of X-style ballots), then you want B and C to be candidates that people dislike, in order to have A surely win in the step 4 of the process. In that case, apart from A, you should give better grades to candidates that are unpopular and worse grades to candidates that are popular, no matter what you really think about them.

Finally, although I will not say that the peer-reviewing process for scientific publications is perfect, a good rule of thumb is to be very defiant about claims that didn't go through this process.