Consider the following voting scheme
- Choose a random person A_{1}.
- A_{1} chooses a set at random of 30 people. Call the set A_{2}.
- Choose a random set of 9 from the 30 in A_{2}. Call this set A_{3}.
- The members of A_{3} 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 A_{4}.
- Choose a random set of 12 from the 40 in A_{4}. Call this set A_{5}.
- The members of A_{5} 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 A_{5}. Call this set A_{6}.
- The members of A_{6} 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.
In step 2, A1 chooses an arbitrary set of 30 people, right? Otherwise, I don't see the point of A1.
ReplyDeleteEr, what's to stop someone from waiting around until the 41 are chosen, and then simply paying off 25 of them?
ReplyDeleteIn the American system of Presidential elections, GFW's question could equally be asked; why bother spending $700 million to win an election when it would be cheaper to buy electoral votes for a million dollars each?
ReplyDelete@anonymous3: If you were really buying electoral college votes, there would be a bidding war--a million dollars a vote is far too low for such high stakes. It could push the cost beyond $700 million. As silly as it is spending money on campaigns rather than on developing great ideas, at least it generates economic activity and a few new ideas. If we aren't as good at exporting products as we used to be, at least we still know how to sing and dance.
ReplyDeleteThe process of electing EU's executive branch is way more complicated than that...
ReplyDeletefrom Wikipedia:
ReplyDelete"Athenian democracyFifth century BC Athenian democracy developed out of a notion of isonomia (equality of political rights), and random selection was a principal way of achieving this fairness.[1] Greek "democracy" (literally meaning "rule by the people") was actually run by the people: administration was in the hands of committees allotted from the people and regularly changed. Although it may seem strange to those used to modern liberal democracy, the Athenian Greeks considered elections to be essentially undemocratic.[2][3] This was because citizens chosen on merit or popularity contradicted the democratic equality of all citizenry. In addition, allotment prevented the corrupt practice of buying votes as no one could know who would be selected as a magistrate, or to sit on a jury."
perhaps applying these principles could make todays "democracy" a little bit more democratic..
Dieter Gollman and I wrote a paper analysing this voting scheme. You can read it at http://www.hpl.hp.com/techreports/2007/HPL-2007-28R1.pdf
ReplyDeleteWe show that it gives some opportunities to minorities while ensuring that more popular candidates are more likely to win, and offers some resistance to corruption of voters. We also suggest a reason why it's so complicated.
Arnab, step 1 selects a random group of people. We think the reason that steps 1 and 2 were not combined was to compensate for technical limitations of the lot-drawing process: see section 6 of our paper.
GFW, as soon as the set of 41 people had been identified, they were locked up together in a guarded room until they'd made their decision. It would have been pretty difficult to get in to bribe them.
Cheers, Miranda.
Miranda Mowbray
Geoff, anon 3's point is still made and perhaps you "answered" GFW too (though the response above reveals why the payoff idea wouldn't work on the 41).
ReplyDeleteThere appear to be high costs and risks associated with being the Doges. Why would someone WANT this position?
ReplyDelete