6
$\begingroup$

The Gibbard-Satterthwaite theorem implies that, in every non-dictatorial voting system with 3 or more candidates, there is a preference profile in which some of the voters can gain by lying about their preferences. However, usually this gain requires that the voters know the voting rule.

For example, consider a voting system with 3 candidates, A B and C, and 12 voters with the following preferences:

  • 3 voters prefer A>B>C;
  • 4 voters prefer B>C>A;
  • 5 voters prefer C>A>B.

Consider the following two voting rules:

  • plurality - in which C is elected;
  • Instant-runoff - in which B is elected (after A is eliminated in the first round).

Consider the 5 C>A>B voters, and assume all other voters are truthful:

  • In plurality voting, they should of course be truthful so that their favorite candidate C wins.
  • But in instant-runoff voting, they can gain by lying and saying that their best candidate is A, since this will prevent the election of their worst option B.

So without knowing the voting rule, these voters cannot know whether lying about their preferences will help them or harm them.

The situation is different with the 3 A>B>C voters:

  • In plurality voting, they can gain by lying and saying that they prefer B, as this will prevent the election of their worst option C;
  • In instant-runoff voting, although they won't gain from lying, they also won't lose.

So even without knowing the voting rule, these voters can know that voting for B will either help them or at least not harm them.

For the sake of this question, assume that all voters are truth-biased. This means that, if they are not sure whether lying will help them or harm them, they will be truthful. They will only lie if lying may help them and may not harm them. So in the above example, the C>A>B voters will be truthful and the A>B>C voters will lie (assuming the B>C>A voters are truthful).

MY QUESTION IS: Is there a collection of reasonable (non-dictatorial, monotone, etc.) voting rules, such that, in all preference profiles, no truth-biased voter will want to lie?

In other words: we look for a collection of voting rules so that, for every preference profile and every group of voters, there exists a voting rule in our collection where their best response (when all other voters are truthful) is to be truthful.

|improve this question
$\endgroup$
  • $\begingroup$ To make sure I understand the assumption, we want a collection of voting rules so that, for every preference profile and every voter, there exists a voting rule in our collection where their best response is to be truthful. $\endgroup$ – usul Feb 3 '15 at 13:43
  • $\begingroup$ Correct, but add to "their best response is to be truthful", "when all other groups of voters are truthful". (Without this addition, the problem seems to be much more difficult). $\endgroup$ – Erel Segal-Halevi Feb 3 '15 at 14:12
  • $\begingroup$ I believe this is not possible for cases where there are three or more candidates. The Gibbard–Satterthwaite theorem says "...every voting system that selects a single winner either is manipulable or does not meet the preconditions [rather generous to this reader] of the theorem" en.wikipedia.org/wiki/Gibbard%E2%80%93Satterthwaite_theorem $\endgroup$ – BKay Feb 6 '15 at 13:57
  • 2
    $\begingroup$ @BKay but doesn't the Gibbard-Satterthwaite theorem relate only to deterministic systems? $\endgroup$ – Erel Segal-Halevi Feb 7 '15 at 16:36
  • $\begingroup$ @ErelSegal-Halevi yes you're correct. Introducing randomness is a way to get around the theorem. Consider "random dictator" in which one ballot is chosen at random, and used to determine the outcome... the best "strategy" is to vote sincerely, regardless of what any other voters do. Asymptotically, it also selects the "best" outcome (in terms of maximizing global utility) but it's also possible for it to select the worst (utility minimizing) candidate. $\endgroup$ – Bill Clark Jun 6 at 16:45
2
$\begingroup$

You use the term 'deterministic' several times to refer to Gibbard-Satterhwaite, and a related question might specify preferences over risk for voters, and then ask whether there's a non-deterministic voting rule for which truth-telling is incentive compatible. I think this paper, by Gibbard from 1977, is relevant to that question.

As for the question you actually asked, if I understand you correctly, 'truth-biasedness' seems pretty strong. A voter misreports only if both (a) there are no voting rules under which misreporting would hurt her and (b) there is at least one voting rule under which misreporting would help her. So what's wrong with the following?

Say you have 3 voters, and consider 3 voting rules, one for each voter. Voting rule $i$ is: "Choose voter $i$'s most preferred alternative, unless the other two voters both prefer the same alternative and it is not the same as voter $i$'s most preferred alternative."

If the other two voters report truthfully, then a truth-biased voter can't gain from deviating: If voting rule $i$ is in effect and the other two voters differ in their most preferred alternative, then she cannot gain from misreporting because she gets her favorite alternative. If the other two voters both prefer the same option, then regardless of the voting rule that option will be chosen. In the former case there is one voting rule under which misreporting hurts her, in the latter case there are no voting rules under which misreporting helps her.

|improve this answer
$\endgroup$
  • $\begingroup$ This seem to work for 3 voters, but what if there are many voters? $\endgroup$ – Erel Segal-Halevi Mar 17 '15 at 7:32
  • 1
    $\begingroup$ I think the same construction works with $N$ voters. Voting rule $i$ specifies that $i$'s favored alternative is chosen -- unless all other voters unanimously prefer a different alternative. Then either all other voters unanimously prefer a different alternative, in which case no matter what voter $i$ reports that alternative is chosen, or they don't, in which case voter $i$ doesn't want to misreport for fear that we're in voting rule $i$. $\endgroup$ – NickJ Mar 18 '15 at 0:39
  • 1
    $\begingroup$ Here's a question though -- what if you restrict the number of voting systems to be less than the number of voters? $\endgroup$ – NickJ Mar 18 '15 at 0:39
  • $\begingroup$ This is an interesting follow-up question :) Thanks for the answer. $\endgroup$ – Erel Segal-Halevi Mar 18 '15 at 6:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.