Monday, March 28, 2011

An unusual Voting Scheme

(I want to thank Bobby Kleinberg for bringing this to my attention.)

Consider the following voting scheme
  1. Choose a random person A1.
  2. A1 chooses a set at random of 30 people. Call the set A2.
  3. Choose a random set of 9 from the 30 in A2. Call this set A3.
  4. 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.
  5. Choose a random set of 12 from the 40 in A4. Call this set A5.
  6. 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.
  7. Choose a random set of 9 from the 25 people in A5. Call this set A6.
  8. 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.
  9. Choose a random set off 11 from the 45 people.
  10. 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.
  11. 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.)
Which of the following is true?
  1. This is a real scheme that was really used.
  2. This scheme was part of a BREAKTHROUGH!!!! result.
  3. This scheme is a counterexample to a conjecture about voting schemes.
  4. This scheme (with parameters) is an example of a voting scheme that is NP-hard to manipulate.
I would have guessed that it is a contrived scheme to serve as a counterexample, but NO- this scheme was really used to pick the new doges of Venice from 1268 until roughly 1768. Why so complex? To avoid anyone rigging the election. You can read more about it here. I suspect it would be hard to manipulate, though I don't think it is known to be NPC 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.
Posted by at

9 comments:

  1. arnab1:58 PM, March 28, 2011

    In step 2, A1 chooses an arbitrary set of 30 people, right? Otherwise, I don't see the point of A1.

    ReplyDelete
  2. GFW5:54 PM, March 28, 2011

    Er, what's to stop someone from waiting around until the 41 are chosen, and then simply paying off 25 of them?

    ReplyDelete
  3. Anonymous6:53 PM, March 28, 2011

    In 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
  4. Geoff Knauth9:34 PM, March 28, 2011

    @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.

    ReplyDelete
  5. Anonymous2:00 AM, March 29, 2011

    The process of electing EU's executive branch is way more complicated than that...

    ReplyDelete
  6. Anonymous3:39 AM, March 29, 2011

    from Wikipedia:

    "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..

    ReplyDelete
  7. Miranda Mowbray5:50 AM, March 30, 2011

    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
    We 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

    ReplyDelete
  8. Anonymous8:08 AM, March 30, 2011

    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).

    ReplyDelete
  9. Anonymous10:33 AM, March 30, 2011

    There appear to be high costs and risks associated with being the Doges. Why would someone WANT this position?

    ReplyDelete

Subscribe to: Post Comments (Atom)