We rely on the secret ballot to prevent vote selling and voter intimidation, but the “secret” ballot isn’t always very secret. In this post I will discuss a problem that very few people know about or understand—one that allows us to give ourselves away using the very choices we make!

The problem is called pattern voting (PV), and it occurs when there are enough choices on a ballot to allow voters to identify themselves using a predetermined voting pattern. Whether or not this is possible is a function of the the number of unique choices on the ballot, the number of voters, and how ballots are counted.

The simplest PV example is an election with one voter. That voter identifies her choices simply by voting, but more realistic scenarios are simple to construct. Consider an election with 10 voters and 3 races with 2 candidates each. Assuming a two-party system, let us say the choices for each race are the democrat (D), republican(R), or no vote (N). If voters follow the rules, this situation leads to the following 27 possible voting patterns:

DDD, DDR, DDN, DRD, DRR, DRN, DND, DNR, DNN, RDD, RDR, RDN, RRD, RRR, RRN, RND, RNR, RNN, NDD, NDR, NDN, NRD, NRR, NRN, NND, NNR, NNN

This is simply a permutation with repetition (3^3). To identify a voter, all that is necessary is to agree before the election on an unlikely voting combination. Up to 9 voters could vote for the same candidate in a select race using unique patterns between them.

As a coercer or vote buyer, all I need to do is give the voter a unique combination (e.g. DNR), and look for that pattern in the ballots during counting or whenever they become publicly available. The voter can either vote the way I told her, guaranteeing that unique pattern in the output, or vote the way she wants hoping the pattern will appear anyway.

The chance of the latter happening is pretty low given the number of voters. Assuming each voter votes randomly, there is less than a 30% ((1-(26/27)^9), see the birthday paradox) chance that a random voter will share the same vote as the coerced voter.

The worst part about this situation is that what I gave above is a best case scenario. Chances decrease if the other voters do not vote randomly, are also being coerced, or do not follow the rules. Unless there’s a particularly bad or good candidate, the likely patterns are straight party (DDD or RRR).

Pattern Voting on a Real Ballot

To make this seem more real, I decided to take Maryland’s 2006 sample ballot I got and calculate the number of unique patterns you could make on it. Note that Maryland used DREs w/out VVPAT, so this is not directly applicable, but it does point out a potential problem when we switch back to optical scan.

There are 30 contests on this ballot. 16 of them have 2 options or 3 choices (yes/no/none), yielding 3^16 patterns. 3 of the races are “choose x” elections, for which the logic is explained in the next section. The rest of the races are detailed below (assuming voters follow the rules):

• Governor: 6 patterns
• Comptroller: 4
• AG: 4
• US Senator: 5
• District 3 Congressional Rep: 5
• State Senator: 4
• House of Delegates (vote for 2 of 6): C(6, 2)+C(6,1)+C(6,0) = 15+6+1 = 22
• County Executive: 4
• County Council District 1: 4
• Circuit Court Judge (vote for 4 of 8): C(8, 4)+C(8,3)+C(8,2)+C(8,1)+C(8,0) = 70 + 56 + 28 + 8 + 1 = 163
• States Attorney: 4
• Circuit Court Clerk: 4
• Judge of the Orphans Court (vote for 3 of 9): C(9,3)+C(9,2)+C(9,1)+C(9,0) = 84 + 36 + 9 + 1 = 130
• Sheriff: 4

To get the total number of patterns, we multiply it all together:

3^16*6*4*4*5*5*4*22*4*4*163*4*4*130*4 = 1.97271752×10^20 = 197,271,752,498,675,712,000

There are only 5,615,727 people in Maryland, and fewer in the county. Not all of these people are registered to vote. If you counted at each polling place, the numbers would be noticeably worse. Also remember that this is a conservative number. You could easily sell over half the ballot and have plenty of patterns left over!

Calculating Your Ballot’s Secrecy

It’s not too hard. Each race has a certain number of choices, and all you have to do is calculate these numbers and multiply them together. If you want to see the number of unique choices after targeting a specific race, for 1 choice election methods you remove that race from the multiplication. For rank choices, n out of m, or range/approval voting you simply remove the candidate you want to win from the calculation.

Below is a guide to help you figure out how many unique patterns appear on your ballot. n is the number of candidates in the election, r is the range or number of choices you can make.

• Choose 1: n+1
• Choose r: sum(C(n,r), 0, r) — this can express choose 1, too.
• Approval: 2^n
• Range: (r+1)^n — this can also express approval
• Ranked Choice: P(n,r) ==> n!/(n-r)!

Of course, this is assuming the voters follow the rules. Otherwise, the answer is 2^(number of dots) (because each dot can either be chosen or not). You can see wikipedia’s combinatorics page for more.

Fighting the Pattern Vote

The bad news is that few people pay attention to this problem, but the good news is that it can be mitigated. To defeat pattern voting, you have to reduce the number of choices that are associated with each other. Except for Ranked Choice, which is special, the key is treating each race separately, and in some election methods you need to treat each candidate separately. This is (sometimes) easier said than done.

In paper ballot systems you have a few choices. You could keep the ballots secret, and use only trusted counters (machines or people). You could have one ballot per race. You could also have a machine that cuts ballots after they are used. DREs w/ VVPAT would need a different mechanism than a paper rolltape to work. Because DREs w/out VVPAT can report results in aggregate, they avoid the PV problem.

As far as I know, every E2E system can handle PV, and some can handle PV with ranked choice. My colleague Stefan Popoveniuc wrote a paper about how this is accomplished in Punchscan and Scantegrity.

The problem with ranked choice is that you can’t hide the relationship between rankings. You need to know it to do the counting. In this scenario, the only choice for traditional systems is secret counting. Digital systems have the possibility of zero knowledge proofs to prove that the counting was correct, however.

That’s it for part 1 of this series. Part 2 will be on the effect of identifying marks (including write-ins and serial numbers), Part 3 will be on surveillance.

Special thanks to my proof readers: Taral, Emily, Jeremy, Scott, and Ben.

• Part 2: Identifying Marks
• Part 3: Surveillance

This entry was posted on Monday, June 16th, 2008 at 10:34 pm and is filed under Privacy. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.