In the two previous posts we saw a general definition of degree of privacy for voting and a method to attack privacy in weighted voting. In the latter post we remarked

The problem is that calculating the terms in the entropy expression is in general intractable due to combinatorial explosion; computing those values is only possible for small numbers of voters and weight categories.

In this post we generalize the inference method to probabilities and therefore degree of privacy. We then apply it to the previous examples of successful attacks, and check for consistency. Since those examples have small values, the method is expected to be computationally feasible.

Recall that the problem can be framed in terms of polyhedral geometry and integer programming. An election is a polytope whose feasible region corresponds to the possible outcomes consistent with public data, including the result. Points are described in terms of the vote grouping function

and the set of points consistent with a result **r** is

where **t** is the tally function and **a _{p}** encodes voter selections implied by

**p**. In order to calculate probabilities and degree of privacy we need to arrive at expressions for

**m**(v, c, r) and |

**A**| in

_{r}The first step is noticing that each point actually corresponds to a *set* of possible outcomes, point coordinates specify the number of voters from a weight group **w _{n}** that selected each choice

**c**. But does not specify exactly

_{n}*which*voters are in that group. This results in a higher multiplicity of outcomes for each possible assignment to said group. This is described by a binomial coefficient in

The multiplicity of a point is thus

To obtain the total multiplicities for |**A _{r}**| for a result

**r**we simply sum over all the points consistent with that result

This is the overall total multiplicities. Next we need to select those corresponding to specific votes. The fraction of the outcomes for point in which voter **v** chose **c** is then

As before, to obtain the multiplicities for a result **r** we simply sum over all the points consistent with that result

We now have expressions for the two terms required to calculate probabilities and degree of privacy.

#### Listing lattice points with Polymake and PPL

In the previous post we needed to calculate the *number* of points in the feasible region of the election polytope. In this case our expressions not only depend on the number of points, but on their coordinates. We need to list these points instead of just counting them, and then calculate multiplicities and proportions for each. For this we turn to the Polymake software and one of its backend tools, the Parma Polyhedral Library. We will use examples from the previous post as test elections.

This is the data for Example 2

Choices | Yes, No |

Yes tally | 94 |

Weights | 17, 8, 4, 2 |

Voters | 2, 6, 6, 10 |

Lattice points | 19 |

we use the following script to convert the data into a polymake polytope and compute the lattice points

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
use application 'polytope'; my $inequalities = [ [2, -1, 0, 0, 0], [6, 0, -1, 0, 0], [6, 0, 0, -1, 0], [10, 0, 0, 0, -1], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1] ]; my $equations = [ [-94, 17, 8, 4, 2] ]; my $e = new Polytope(INEQUALITIES=>$inequalities,EQUATIONS=>$equations); print $e->LATTICE_POINTS; |

we get

there are 19 rows, which correspond to the point count obtained with Latte as shown in the data. These points are then input to the calculations we obtained above to yield the degree of privacy and probabilities. This is implemented here

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
object D2 extends App { val lines = scala.io.Source.fromFile(args(0)).getLines val voters = args.slice(1, args.length).map(_.toInt) println(s"Processing file '${args(0)}' with groups [${voters.mkString(" ")}]..") // we skip the first column and take n number of variables val lineValues = lines.map(_.split(' ').slice(1,voters.size + 1)) // calculate total points for each voter casting Yes, plus overall total val totals = lineValues.map { line => val lineInts = line.map(_.trim.toInt) val withVoters = lineInts.zip(voters) // multiply binomial coefficients for all coordinates val total = withVoters.map { case (a, b) => binomial(b, a) }.reduce(_.multiply(_)) // the fraction of points in which the voters cast Yes val points = withVoters.map { case(a, b) => total.multiply(BigInteger.valueOf(a)).divide(BigInteger.valueOf(b)) } // the last array holds the total multiplicities for each point points :+ total } val arr = totals.toArray println(s"Found ${arr.size} lattice points") // sum multiplicities for each point, m(v, c, r) val sums = arr.transpose.map { values => values.reduce(_.add(_)) } // overall multiplicities, Ar val allSpace = new BigDecimal(sums(sums.length - 1)) println(s"Total solutions $allSpace") // probabilities = m(v,c, r) / Ar val ps = sums.dropRight(1).map(new BigDecimal(_).divide(allSpace, 5, RoundingMode.HALF_UP)) println("p = " + ps.mkString(" ")) // entropies val hs = ps.map { prob => val p = prob.doubleValue val q = 1 - p -(p * (Math.log(p) / Math.log(2)) + ((1-p) * Math.log(1-p) / Math.log(2))) } // degree of privacy, with 2 options Hm = 1, so a = H(x) println("d = " + hs.mkString(" ").replace("NaN", "0")) /** * Binomial coefficient */ def binomial(n: Int, k: Int): BigInteger = { var ret = BigInteger.ONE; for(i <- 0 to k-1) { ret = ret.multiply(BigInteger.valueOf(n-i)).divide(BigInteger.valueOf(i+1)) } ret } } |

which when run gives us

The probabilities and degree of accuracy are highlighted in red. Note how the degree of accuracy for the two voters in the first group is 0, we know they voted **Yes** with certainty. This matches what we expect given the successful attack data shown in the previous post. Also shown is the total number of possible outcomes consistent with the result, which in this case is 142,442. We can do the same for Example 1.

Choices | Yes, No |

Yes tally | 1503 |

Weights | 61, 24, 18, 12 |

Voters | 15, 10, 20, 30 |

Lattice points | 83 |

for which we get

where again we observe the expected value of **d** = 0 among the results. Other probabilities are closer to 0.5 and therefore **d** values are closer to 1.0, but still leaking some information.

#### Summary

In this post we have combined results from the previous two posts to arrive at a method to obtain probabilities and degree of privacy for weighted plurality elections. We have seen how this requires taking point multiplicities into account, based on lattice point coordinates and not just point totals. We used polymake and ppl for lattice point listing, and then implemented the calculations in code for the case of |**C**| = 2 (Yes/No) elections. Applying this to the examples of the previous post gave us probabilities over voter’s choices; the presence of values p = 1.0 and **d** = 0 are consistent with successful attacks shown there. Although the implementation shown is limited to Yes/No case the method could be implemented for general values of |**C**|. We have not seen how the polyhedra tools and code scales to large values of voters, where points and multiplicities could explode.