<p>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 <a href="https://www.kellogg.northwestern.edu/research/math/papers/175.pdf" rel="nofollow">this paper</a>, by Gibbard from 1977, is relevant to that question.</p>

<p>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?</p>

<p>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." </p>

<p>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.</p>

CC BY-SA 3.0
2015-03-17T07:32:02.573Z
This seem to work for 3 voters, but what if there are many voters?
Erel Segal-Halevi
CC BY-SA 3.0
2015-03-18T00:39:00.163Z
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$.
NickJ
CC BY-SA 3.0
2015-03-18T00:39:58.150Z
Here's a question though -- what if you restrict the number of voting systems to be less than the number of voters?
NickJ
CC BY-SA 3.0
2015-03-18T06:03:35.793Z
This is an interesting follow-up question  :) Thanks for the answer.
Erel Segal-Halevi
CC BY-SA 3.0
2015-03-15T21:43:11.797Z
2015-03-16T03:25:06.570Z
2015-03-16T03:25:06.570Z
NickJ
<p>The <a href="https://en.wikipedia.org/wiki/Gibbard%E2%80%93Satterthwaite_theorem" rel="nofollow">Gibbard-Satterthwaite theorem</a> 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.</p>

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

<ul>
<li>3 voters prefer A>B>C;</li>
<li>4 voters prefer B>C>A;</li>
<li>5 voters prefer C>A>B.</li>
</ul>

<p>Consider the following two voting rules:</p>

<ul>
<li><em>plurality</em> - in which C is elected;</li>
<li><em><a href="https://en.wikipedia.org/wiki/Instant-runoff_voting" rel="nofollow">Instant-runoff</a></em> - in which B is elected (after A is eliminated in the first round).</li>
</ul>

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

<ul>
<li>In plurality voting, they should of course be truthful so that their favorite candidate C wins.</li>
<li>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.</li>
</ul>

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

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

<ul>
<li>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;</li>
<li>In instant-runoff voting, although they won't gain from lying, they also won't lose.</li>
</ul>

<p>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.</p>

<p>For the sake of this question, assume that all voters are <em>truth-biased</em>. 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).</p>

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

<p>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.</p>

CC BY-SA 4.0
2019-06-06T16:45:04.353Z
@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.
Bill Clark
CC BY-SA 3.0
2015-02-03T13:43:06.427Z
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.
usul
CC BY-SA 3.0
2015-02-03T14:12:27.197Z
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).
Erel Segal-Halevi
CC BY-SA 3.0
2015-02-06T13:57:56.023Z
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"  http://en.wikipedia.org/wiki/Gibbard%E2%80%93Satterthwaite_theorem
BKay
CC BY-SA 3.0
2015-02-07T16:36:06.727Z
@BKay but doesn't the Gibbard-Satterthwaite theorem relate only to deterministic systems?
Erel Segal-Halevi
<preferences><social-choice>
Tactical voting when the voting rule is unknown
Erel Segal-Halevi
# Tactical voting when the voting rule is unknown

(Asked by: username_0 on 2015-02-02)

The [Gibbard-Satterthwaite theorem](https://en.wikipedia.org/wiki/Gibbard%E2%80%93Satterthwaite_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](https://en.wikipedia.org/wiki/Instant-runoff_voting)* - 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.

**Tags:** preferences, social-choice

> **Comments:**
> **username_2**: 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.  
> **username_0**: 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).  
> **username_3**: 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"  http://en.wikipedia.org/wiki/Gibbard%E2%80%93Satterthwaite_theorem  
> **username_0**: @username_3 but doesn't the Gibbard-Satterthwaite theorem relate only to deterministic systems?  
> **username_1**: @username_0 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.  

---

## 1 answers

### Answer by username_4 on 2015-03-15. Score: 2 | Accepted answer

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](https://www.kellogg.northwestern.edu/research/math/papers/175.pdf), 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.

> **Comments:**
> **username_0**: This seem to work for 3 voters, but what if there are many voters?  
> **username_4**: 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$.  
> **username_4**: Here's a question though -- what if you restrict the number of voting systems to be less than the number of voters?  
> **username_0**: This is an interesting follow-up question  :) Thanks for the answer.  

---

