20

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?

Improve this question
  • 4
    As a sidebar, the title of this question can trivially be answered "no", since the theorem only covers deterministic systems. If all votes are collected and one is chosen at random to pick the winner then there is no opportunity for tactical voting. – origimbo Dec 24 '16 at 9:18
  • 1
    That is partially true, but there is a version of Gibbard's theorem for randomized voting rules. Cf. my more detailed answer. – François Durand Jan 24 '17 at 10:44
  • This thread is interesting, saying that Gibbard's theorem doesn't preclude systems for which honesty is the best strategy: reddit.com/r/EndFPTP/comments/9dcf05/… I don't know how true it is, though. @FrançoisDurand – endolith Sep 12 '18 at 18:28
  • The problem with the thread you mention (as often) is that loose language is fine for explaining scientific results, but not really for discussing them. As someone mentioned, Approval voting comes pretty close : e.g. with 3 candidates, if your preference order is A>B>C, your best strategy is either to vote A or AB, which is "honest" in some sense. But this notion of "honesty" is not at all the same as the notions precisely used in GB theorem. – François Durand Sep 25 '18 at 9:58
  • @FrançoisDurand I guess I have to read through the papers myself and actually understand them. :| – endolith Sep 25 '18 at 16:25
16

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.

Improve this answer
  • Have you heard of the Majority Judgment voting system? Is it considered dictatorial? I'm willing to post this as a seperate question if you think it is worth it – SdaliM Jan 7 '17 at 8:33
  • Interesting question, and I agree with you that it deserves a separate question. Please do, I will reply in this separate post. – François Durand Jan 8 '17 at 8:32
  • 1
    wow, great and extremely clear answer! – Joël Jan 9 '17 at 2:47
  • 1
    In the comments below on the answer by by ohwilleke it is implied that G-S does not apply for Cardinal systems that allow for giving the same rank. As such approval voting would be free from G-S. Is this true? – Keith Feb 20 '18 at 19:24
  • 1
    It depends on what you call G-S theorem. Satterthwaite's version applies only to ordinal voting systems. But Gibbard's version applies to any voting system, including cardinal ones. In particular, it applies to Approval voting. – François Durand Feb 21 '18 at 9:13
2

(?) 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.

Improve this answer
  • I'm not disputing that G-S got their math right; I'm trying to figure out where the misconception is. Are Smith's 5 conditions a restatement of Satterthwaite, but not the more general Gibbard, perhaps? – endolith Jan 24 '17 at 13:53
  • 2
    By "Smith's 5 conditions", you mean the ones at the beginning of this page? Condition 4 ("incentivizes honest scores") is weaker than non-manipulability. Non-manipulability means that, given your preferences, you have a ballot (called "sincere ballot") that is a dominant strategy, i.e. a best response to whatever the other voters do. In contrast, condition 4 states that if you know what they do, you have a best response where your grades are coherent with your ordering. A voting rule can meet this condition: Approval voting, Range Voting, etc. – François Durand Jan 25 '17 at 9:26
  • 1
    The grades/X intricate system has a property that seems better at first sight: it is always a good strategy to provide a sincere grade-style ballot (i.e. giving exactly your utilities). But, as I explained above, the manipulability is simply "hidden under the carpet", namely in the X-style ballot. It is especially obvious when epsilon tends to 0: then, the voting system is equivalent to system X, whatever it is. – François Durand Jan 25 '17 at 9:29
  • Your first point highlights that the G-S theorem is not always a sign of a problem. Approval Voting for example will for the voters to compromise on the ballot. This is exploiting the desire to vote strategically to force compromise. I would argue this is good – Keith Feb 20 '18 at 19:20
  • Indeed, that can be argued. You can also argue that it implies a unfair balance of powers between voters who have a good information about the other voters' ballots and those who don't (among other problems). – François Durand Feb 21 '18 at 9:16
1

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.

Improve this answer
  • 1
    So it doesn't take into account strength of preferences? Does it allow liking two candidates equally? – endolith Dec 23 '16 at 21:55
  • 2
    It does not take into account the strength of the preferences. It also doesn't really allow liking two candidates equally because anyone who votes must pick only one top choice in its assumptions which are realistic. The theory doesn't model "approval voting" in which you vote for everyone you can tolerate which would allow someone to vote for more than one candidate. Efforts to overcome the theorem involve figuring out sensible ways to alter the assumptions of the theory through the voting process like approval voting or an ability to spread your vote in unequal amounts more than one way. – ohwilleke Dec 23 '16 at 21:57
  • 1
    Also worth noting that G-S is only relevant if there are more than two choices available to consider. It has not application to a race where there are only two possible candidates, which is the loophole that the U.S. two party system attempts to exploit to the extent possible with a two major party system. – ohwilleke Dec 24 '16 at 5:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .