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.

Improve this question
$\endgroup$
4
  • 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$
    – Mohammad Alaggan
    Oct 16, 2011 at 16:23
  • 2
    $\begingroup$ Link: research.microsoft.com/apps/pubs/default.aspx?id=65075 $\endgroup$
    – Suresh Venkat
    Oct 16, 2011 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, 2011 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, 2013 at 20:18

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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