News for hackers. Stuff that matters.
Re:A simple experiment suggests a way to encourage truthfulness by aprescott on Friday April 06, 2012 @04:42PM (#3808835)
Just to make this technique a bit clearer, since "subtract 50 and double" was a bit vague to me: you ask 100 people the question about illegal activity, and assume they're going to toss the coin and follow the protocol. That gives you 100 "yes" and "no" answers, of which ~50 "yes" answers are due to following the protocol and can just be ignored. The remaining yes/no answers are from the tails results and that's the data you use to get a final answer. As an illegal opiate producer in Afghanistan who answers "yes", you have plausible deniability by just saying "I got heads."

The fairness of the coin toss means the researcher asking the question doesn't need to know who got which coin result so it can be kept secret.

Re:A simple experiment suggests a way to encourage truthfulness by SpikeGronim on Friday April 06, 2012 @04:58PM (#3808904)
This is a cool concept that is formalized in the "Dining Cryptographers" paper: http://en.wikipedia.org/wiki/Dining_cryptographers_problem . You can use this basic idea to create a completely anonymous broadcast channel.
Re:A simple experiment suggests a way to encourage truthfulness by Terretta on Saturday April 07, 2012 @09:50AM (#3810854)
You explained the subtract 50, but not really the and double.

Revised:

"You ask 100 people the question about illegal activity, and explain they're going to toss the coin and follow the protocol. That gives you 100 "yes" and "no" answers, of which ~50 "yes" answers are yes due to the coin being heads, regardless of whether true yes or false positive, so subtract those yesses out. The remaining yes answers are from the tails results and are not false positives. Because heads/tails is 50% chance, half of your true yesses were on tails, and half on heads. To get back the "hidden" half of yesses you tossed out with the 50 heads results, you double the yesses that came up with tails. That's the data you use to get a final answer."

Re:A simple experiment suggests a way to encourage truthfulness by aprescott on Saturday April 07, 2012 @11:03AM (#3811035)
I figured it would be obvious enough from what I outlined that the yes/no answers from the tails results gives you a proportion of "yes" answers, such as, say, 20/50, which is the proportion you want. The doubling is just 20/50 = 20*2/100. But I can appreciate that maybe someone else doesn't quite see it! :)
Re:A simple experiment suggests a way to encourage truthfulness by noja on Friday April 06, 2012 @07:13PM (#3809364)
Isn't the very key to this that the researcher doesn't see the coin result?
Re:A simple experiment suggests a way to encourage truthfulness by joeyo on Friday April 06, 2012 @08:00PM (#3809470)
That's correct. The researcher doesn't know the outcome of any particular coin toss but knows the outcome, in expectation, for a large number of coin tosses.
Re:A simple experiment suggests a way to encourage truthfulness by Terretta on Saturday April 07, 2012 @09:51AM (#3810856)
The explanation was missing a crucial point:

http://news.ycombinator.com/item?id=3810854

Re:A simple experiment suggests a way to encourage truthfulness by grabastic on Friday April 06, 2012 @07:34PM (#3809403)
Thanks for the explanation... I didnt quite get the trick as it was described in the parent.
Re:A simple experiment suggests a way to encourage truthfulness by tagawa on Friday April 06, 2012 @08:04PM (#3809480)
Thanks for the further explanation. I love it when HN throws up gems like this.