<p>There's a trivial protocol whose expected value is the correct mean: everybody announces their preference, and one is chosen at random. No player (acting alone) can do better than to announce their true preference. I haven't yet looked at the collusion-resistance of this protocol (I would guess it depends on the exact payoff functions).</p>

CC BY-SA 3.0
2011-10-17T15:36:12.017Z
2011-10-17T15:36:12.017Z
Max
<p>This question did not originate in my research, but I think it's interesting. It is somewhat underspecified. I'd be interested in an example in any particular case.</p>

<p>We have $n$ parties that between them must choose a value $x \in \mathbb{R}$. Each party has a preferred value $p_i$ for $x$, but we must find a compromise. Let's say we want the mean of the preferences.</p>

<p>Now, anybody who has been involved in politics will know that taking the middle way between <em>stated</em> preferences can be gamed by stating a more extreme position than the actual preference, so that the mean lands closer to it. Is there a protocol that lets us find (an approximation to) the mean of the true preferences? </p>

<p>As an analogy, one can take the second-price auction, where everybody is best served by bidding their true valuation.</p>

CC BY-SA 3.0
2011-10-16T16:23:00.283Z
The paper "Mechanism Design via Differential Privacy" gives a approximately truthful mechanism for auctions which also provides some sort of resilience against coalitions as a biproduct of differential privacy. The mechanism they provide is called the Exponential Mechanism and depends generally on sampling, but is not necessarily efficient. I am not sure if this is what you want nor if it helps but it looks related.
Mohammad Alaggan
CC BY-SA 3.0
2011-10-16T23:49:17.777Z
Link: http://research.microsoft.com/apps/pubs/default.aspx?id=65075
Suresh Venkat
CC BY-SA 3.0
2011-10-24T14:34:15.020Z
From that paper I have learnt that this kind of "reverse game theory", where one is designing a game in order to encourage a certain strategies, is called "mechanism design". Perhaps a mechanism-design tag would be useful, but I don't have enough rep to create it.
Max
CC BY-SA 3.0
2013-05-20T20:18:16.350Z
It seems to be well known in economics that if you do this with the *median* instead of mean, everybody maximizes their payoff by being honest.
Max
<cr.crypto-security><gt.game-theory>
A protocol for honest compromise
Max
# A protocol for honest compromise

(Asked by: username_0 on 2011-10-16)

This question did not originate in my research, but I think it's interesting. It is somewhat underspecified. I'd be interested in an example in any particular case.

We have $n$ parties that between them must choose a value $x \in \mathbb{R}$. Each party has a preferred value $p\_i$ for $x$, but we must find a compromise. Let's say we want the mean of the preferences.

Now, anybody who has been involved in politics will know that taking the middle way between *stated* preferences can be gamed by stating a more extreme position than the actual preference, so that the mean lands closer to it. Is there a protocol that lets us find (an approximation to) the mean of the true preferences?

As an analogy, one can take the second-price auction, where everybody is best served by bidding their true valuation.

**Tags:** cr.crypto-security, gt.game-theory

> **Comments:**
> **username_1**: The paper "Mechanism Design via Differential Privacy" gives a approximately truthful mechanism for auctions which also provides some sort of resilience against coalitions as a biproduct of differential privacy. The mechanism they provide is called the Exponential Mechanism and depends generally on sampling, but is not necessarily efficient. I am not sure if this is what you want nor if it helps but it looks related.  
> **username_2**: Link: http://research.microsoft.com/apps/pubs/default.aspx?id=65075  
> **username_0**: From that paper I have learnt that this kind of "reverse game theory", where one is designing a game in order to encourage a certain strategies, is called "mechanism design". Perhaps a mechanism-design tag would be useful, but I don't have enough rep to create it.  
> **username_0**: It seems to be well known in economics that if you do this with the *median* instead of mean, everybody maximizes their payoff by being honest.  

---

## 1 answers

### Answer by username_0 on 2011-10-17. Score: 4 | Accepted answer

There's a trivial protocol whose expected value is the correct mean: everybody announces their preference, and one is chosen at random. No player (acting alone) can do better than to announce their true preference. I haven't yet looked at the collusion-resistance of this protocol (I would guess it depends on the exact payoff functions).


---

