4
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – M. Alaggan Oct 16 '11 at 16:23
  • 2
    $\begingroup$ Link: research.microsoft.com/apps/pubs/default.aspx?id=65075 $\endgroup$ – Suresh Venkat Oct 16 '11 at 23:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Max Oct 24 '11 at 14:34
  • $\begingroup$ 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. $\endgroup$ – Max May 20 '13 at 20:18
4
$\begingroup$

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

$\endgroup$

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.