Consider the following voting scheme
- Choose a random person A1.
- A1 chooses a set at random of 30 people. Call the set A2.
- Choose a random set of 9 from the 30 in A2. Call this set A3.
- The members of A3 pick a set of 40 people. This is NOT random. In fact, every person they choose must be approved by at least 7 of the 9. Call this set of 40 A4.
- Choose a random set of 12 from the 40 in A4. Call this set A5.
- The members of A5 pick a set of 25 people. This is NOT random. In fact, every person chosen must be approved by at least 9 of the 12.
- Choose a random set of 9 from the 25 people in A5. Call this set A6.
- The members of A6 pick a set of 45 people. This is NOT random. In fact, every person chosen must be approved by at least 7 of the 9.
- Choose a random set off 11 from the 45 people.
- These 11 chose a final set of 41. They do this by every member choosing a candidate which they may examine in person. The candidates with the most approvals are picked.
- THESE 41 chose the WINNER - but the winner had to get at least 25. (It is not clear if any of them could be the winner.)
- This is a real scheme that was really used.
- This scheme was part of a BREAKTHROUGH!!!! result.
- This scheme is a counterexample to a conjecture about voting schemes.
- This scheme (with parameters) is an example of a voting scheme that is NP-hard to manipulate.
Why did this come up? Bobby Kleinberg gave a talk at UMCP where he brought it up to show that his results (about how randomness can help make mechanisms hard to manipulate) had a real world counterpart. See here for his paper, which has co-authors Jason Hartline and Azarakhsh Malekian.