After much debate, the realm has decided dragon jousting may not be the best way to choose its leaders, and has begun transitioning to democracy. Your company was hired to survey the citizens of the land and predict which candidate will win. There’s a lot riding on this: if you get it wrong, heads— well, your head— will quite literally roll. Can you predict the winner? Dennis Shasha shows how.
Transcript:
After much debate, the fantasy realm you call home has decided dragon jousting may not be the best way to choose its leaders and has begun transitioning to democracy. The candidates are a giant orange troll and an experienced tree statesman.
An all-powerful eyebrow has hired your company— The Dormor Polling Agency— to survey the citizens of the land and predict who will win. A lot is riding on this: heads— well, your head— will quite literally roll if you get it wrong. Your job is to go from door to door, ask voters whether they prefer the troll or the tree fellow, and use the results to project how the election will go.
Your fellow citizens want you to succeed and would tell you the truth… but there’s a problem. Few are willing to admit they support the troll on account of his controversial life choices. If you were to ask a troll supporter who she’ll vote for, there’s a good chance that she’ll claim to support the tree man, skewing your results.
You’re about to begin your rounds when a stranger offers you some cryptic advice: “Here’s the question that will save your neck: what have you got in your pocket?”
You reach into your pocket and pull out a silver coin with the current king’s head on one side and his tail on the other. How can you use it to conduct an accurate poll?
The trick here is to use the coin to add a random chance to your interaction to give troll supporters deniability. In other words, you’re looking for a system where when someone says “troll,” it could either be because the coin somehow told them to or because they support the troll— and you’d have no way to tell the difference. You’ll also need to know how frequently the coin skewed the results so that you can account for it in your calculations.
One solution is to have every pollee go into their house and flip the coin. If it lands heads, they should tell you “troll,” whether or not they support him. If it lands tails, they should tell you their actual preference.
Here’s what happens: you poll 200 voters, and 130 say they’ll vote for the troll. For about 50% or 100 of them, the coin will have landed heads. So you can subtract 100 troll votes off his total and know the troll’s real support is 30 to 70, and he’s very likely to lose.
The election comes around, but before the results can be certified, a third-party candidate swoops in and burns the tree fellow to a crisp. The freshly signed and deeply flawed constitution mandates that this challenger gets to take his victim’s place in a new election.
The Dormor Polling Agency sends you back out on the streets with your trusty coin. Only this time, no one is comfortable admitting their preference: supporting the troll is still shameful, and nobody wants to express support of a dragon who murdered his way into the race.
But your job is your job. How do you conduct an accurate poll now?
This time, instead of masking just one candidate preference, you need some way to disguise both. At the same time, you also need to leave space for some portion of the people polled to express their true preferences. But a coin toss only has two possible outcomes… right?
Suppose you have everyone flip the coin twice— now there are four possible results. You can tell the people who flip heads twice in a row to report support for the troll; those who get tails twice to report dragon; and those with any other combination to declare their true preference. The chances of getting either two heads or two tails in a row are 50% times 50%— or 25%. Subtracting that proportion of the respondents from each candidate’s score should give you something close to the real distribution.
This time, 105 respondents announced themselves in favor of the troll and 95 for the dragon. The coin will make 25% or 50 respond troll, and another 50 respond dragon out of the total. Subtracting 50 from each result reveals that voters seem to prefer the troll by a margin of about 55 to 45.
It’s close, but as predicted, the troll wins the election, and you live to poll another day.
