Skip to main content

Can you solve the fantasy election riddle? - Dennis E. Shasha

1,534,453 Views

1,194 Questions Answered

TEDEd Animation

Let’s Begin…

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.

It is often the case that enhancing individual privacy entails increased cost. In this puzzle, anyone who answers based on coin flips is essentially wasted as far as the poll is concerned. For example, if everyone who flips a coin twice and ends with two heads must say candidate A and everyone who ends with two heads must say candidate B, then the pollster learns nothing from roughly half the respondents. Suppose that the pollee doesn’t trust the pollster but might trust five friends. Could some spokesperson for the five friends respond to a pollster with a statement like this: “Among us 5, x of us express support for A and 5-x for B, but two of us flipped coins twice which perhaps determined their votes. The other three express their true preferences.” What kind of privacy guarantee could one get?

Login to answer question

About TED-Ed Animations

TED-Ed Animations feature the words and ideas of educators brought to life by professional animators. Are you an educator or animator interested in creating a TED-Ed Animation? Nominate yourself here »

Meet The Creators

  • Educator Dennis E. Shasha
  • Director Igor Coric, Artrake Studio
  • Narrator Addison Anderson
  • Director of Production Gerta Xhelo
  • Editorial Director Alex Rosenthal
  • Producer Bethany Cutmore-Scott
  • Script Editor Alex Gendler
  • Fact-Checker Eden Girma

More from How Things Work