Communications of the ACM
Last byte
Stopping Tyranny
Credit: Getty Images
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.
Figure. If laws are passed with probabilities of surviving a counter-referendum of 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1 in that order, which should the minority contest?
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.
Warm-Up: Suppose there are 10 laws the majority party can pass but each of five has a probability of 0.999 to survive a counter-referendum and each of five has only a 0.01 chance of surviving. Suppose further the minority party will invoke counter-referendums for all laws. In which order should the majority party pass the 10 laws with the goal to maximize the number that become active?
Solution to Warm-Up: The majority party should pass the laws having a 0.999 to survive ones first. In such a case, there is a probability of 0.9993 = 0.997 that the minority party will lose the first three counter-referendums and then the majority party will be able to make all 10 laws active without further risk of counter-referendums, even for the laws that have only 0.01 chance of surviving a counter-referendum. Clearly the minority party should pick its battles better.
Warm-Up 2: If the minority party decides not to call for counter-referendums on all laws from the majority party, for which ones should it invoke counter-referendaums assuming the majority party first passes the five laws with a 0.999 of survival and then the five laws with a 0.01 chance of survival?
Solution: One possibility is for the minority to oppose only those laws with a 0.01 chance of surviving a counter-referendum. The minority has a 0.993 (approximately 97%) chance of stopping the election after the first three unpopular laws. Another interesting possibility is to contest some of the 0.999 laws, because if the minority wins on those, then there is the possibility of stopping more laws. However, that strategy runs the risk of losing three counter-referendums in a row. In either case, slightly more than five laws will be passed.
OK, I think you are ready now. The goal for the majority is to pass as many laws as possible and the goal for the minority is to prevent the majority from doing so.
Question: Suppose the majority passes laws with survival probabilities 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1 in that order. Which should the minority contest with counter-referendums to minimize the number of laws that become active? Recall the minority must decide which laws to contest as soon as they pass.
Solution (kind of): I do not have a good theory, so I wrote a program that explores the possibilities. Based on my program, the minority should ask for counter-referendums for laws starting with survival probability 0.6 and then the rest that have lower survival probabilities. In such a case, the expected number of laws that will pass is approximately 5.3.
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?
Question: Would the majority party be better off (in terms of total number of laws passed) if it permuted the order in which it passed these laws?
Solution: There may be several better permutations, but at least this one 0.3, 0.5, 0.8, 0.7, 0.6, 0.4, 0.9, 0.2, 0.1 does seem better, raising the expected number of laws to 5.4. In this case, again, the minority should contest every law that has a 0.6 probability of surviving or less.
Upstart: Given a set of potential laws that the majority wants to pass, each with a probability of surviving a counter-referendum, what is the best strategy for the majority side to use in order to pass as many laws as possible, no matter how clever the minority is? The majority can order the laws in any order and may drop some.
Footnotes
All are invited to submit their solutions to [email protected]; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
The Digital Library is published by the Association for Computing Machinery. Copyright © 2020 ACM, Inc.
No entries found