By Michael A. Rouse & Warren D. Smith
Michael Rouse, in a 2 October Electorama post, figured out how to apply Rivest's "3ballot" secure voting idea for use in Condorcet and Borda rank-order ballot voting methods. However, the Rouse-Rivest scheme is very vulnerable to the "selected pattern attack" and hence cannot be regarded as providing protection against vote-buying and coercion in elections with a large number of candidates. If C!>V where C is the number of candidates and V the number of voters, then the Rouse-Rivest scheme is severely affected by this attack. If C!<<V then it is only mildly affected.
One authentic ballot, one random (or voter-picked) order, and one the reverse of that order.
For example, let's say my true preference is A>B>C. Some political operative wants to buy the vote B>A>C. I would simply pick the following:
Ballot 1: A>B>C (true preference)
Ballot 2: B>A>C ("bought" vote)
Ballot 3: C>A>B (reverse of "bought" vote)
|
Now, I can choose to copy ballot 2 and bring it to the buyer/coercer as my "proof." I can pick any order I want for ballot 2, and simply reverse that order for ballot 3. (Of course, I can put the fake and reverse-fake ballots at any position I want and my "true" ballot in the remaining position.)
Of course, it would be rather tedious. If it were a computer/printer combination, we could have a selection that would automatically randomize one ballot and reverse this for another, and then print out the triplet. (But the voter would have to trust that machine and that randomness, so this is probably a bad idea.)
The attacker (vote buyer or coercer) says to the voter (in a 33-candidate race like the Congo September 2006 presidential race)
I want you to vote A>B>C>...>Z as your 'true' vote, and X>Q>F>...>B and its reverse as your 'fake' vote.
There are 33! possible kinds of votes (which far exceeds the population of the Congo), so the coercer can uniquify easily. Then the coercer, if he does not see all three demanded patterns posted on the bulletin board, exacts horrific punishment on the voter.
This is an excellent illustration of the tremendous devastation the "3-pattern attack" (also called the "selected pattern attack") can wreak. But in range and approval voting, all candidate scoring decisions are independent and can be on separate "ballots" so there is no pattern, so for those voting systems (and apparently those alone), the selected pattern attack is simply not a problem. With Condorcet, Borda, and Plurality voting, etc, the individual candidate-scores depend and hence cannot be separated without making ballot-validity-checking impossible.
Attempts to fix this by separating the rank order ballot A>B>C>D>... into A>B, B>C, C>D etc don't work because they omit the implied A>C, A>D, B>D, etc relations. Attempts to fix it by making the voter vote individually on all possible candidate-pairs runs into the problem that there are an enormous number of candidate-pairs (990 in a 45-candidate election) – far too much information to reasonably ask voters to provide – and also the candidate-pair decisions again depend on each other, e.g. if you say A>B and B>C you are not allowed to say C>A. Anytime a voting system features such dependence, the ballot validity check becomes complicated because, in a 45-candidate election, it needs to examine all 45*3=135 individual chunks of information (or more). Whenever it is complicated, a computer is probably needed, destroying the whole Rivest idea of allowing computers to be avoided, and also raising the horrible possibility (probably very easily possible with future computer technology) that computer is remembering the 3ballots, which would also completely destroy the Rivest 3ballot scheme's claim that undetected cheating by the election counters would be impossible. Whenever a large "bundle" of dependent-information is needed in a vote because of the definition of the voting system (such as in rank-order ballots, or in plurality ballots) the very size of the bundle makes it possible for a voter to "insert a lot of information" into his 3ballot, which enables the selected-pattern attack. Approval and range voting, and them alone among commonly proposed voting methods, avoid that difficulty because all the chunks of information in their votes are independent.