Communications of the ACM, March 2020, Vol. 63 No. 3, Pages 104-ff
By Dennis Shasha
Is there a natural law that says that if a country consists of mostly non-violent people and a small group willing to use force, then the brutes will win? Is there any way for the decent people to stop the brutes?
Most people who live in dictatorships are decent, so why are their leaders so bad? Is there a natural law stating if a country consists of mostly non-violent people and a small group willing to use force, then the brutes will win? Is there any way for the decent people to stop the brutes?
One answer is a robust representative democracy. Unfortunately, history is filled with examples (even current ones) in which a leader is democratically elected and then becomes a dictator over time. Representative democracy suffers from the loophole that one bad election can mess up everything.
Is there a way to make the world safe, to make it impossible for a would-be tyrant to exceed reasonable authority when the public starts to realize what has happened? The most straightforward way would be for all decisions to be made by referendum, but that is impractical, because governments make thousands of decisions per day and the public simply does not have the necessary information.
Here is a compromise proposal.
Make it possible for, say 1/3, of all representatives to call for a “counter-referendum” on any law that has been passed by the legislature. A counter-referendum is a vote by all the people to decide whether to let a law become active or remove it from the books. Making an electronic referendum (or any vote) cryptographically secure is a topic of active research—but suppose that it were secure and enforceable.
To further ensure the majority does not simply re-pass a law that has been rejected by one or more counter-referendums, if three counter-referendums in a row go against one or more laws passed by the legislature, then the majority legislators requires 2/3 super-majorities to pass any further laws for one year.
On the other hand, voter fatigue is always an issue. So if three counter-referendums in a row fail (that is, a majority of counter-referendum voters support the original legislation for three successive counter-referendums), then there will be no possibility for more counter-referendums for a year.
The majority of legislators decides when to vote (and presumably pass) each law. Once a law passes in the legislature, the minority must decide right away whether to put it up for a counter-referendum, which happens one month after the original passage. In that case, the law becomes active only if it survives the counter-referendum.
For the simplifying purposes of this puzzle, suppose both sides know the probability each law has of surviving a counter-referendum and those probabilities are independent. Trust me, the puzzle is difficult enough even then.
About the Author:
Dennis Shasha is a professor of computer science in the Computer Science Department of the Courant Institute at New York University, New York, USA, as well as the chronicler of his good friend the omniheurist Dr. Ecco.
All are invited to submit their solutions to email@example.com; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html.