330px Approval ballot svg

In a previous post we described a method to encode votes for multiple choice using base-n encoding of digits. It turns out this method can be generalized to any kind of ballot, provided a small layer of interpretation is added on top for each particular case. Recall that the method described in that post allows encoding a list of positive integers into one single integer that can then be mapped to a multiplicative group (Gq) for encryption. For a list l and maximum possible value x, the encoding is:

CodeCogsEqn 3

What allows generalization is that any ballot content can be encoded as a list of integers, not just the case of multiple choice ballots. Using this fact, ballots can first be expressed as a list of integers and then be encoded with the same mentioned procedure, irrespective of the specific ballot type.

A short note before going on to some examples. When we informally say “list representation” we’re talking about a collection of items together with an ordering (giving a totally ordered set), such that each item in the list can be associated with its index. A list representation, therefore, encodes more than just what items are present, as would be in a set. Each ballot type’s interpretation of a list is therefore in terms of values in the list and possibly their indices. We’ll see how that happens for different ballot types

n out of m

The most common ballot, includes the typical 1 out of m case, where one option (n=1) is selected out of m possibilities.

Parameters: n options to be selected out of m possible

Index: Option number ∈ {0..m-1}

List indices correspond to ballot options.

Value: Whether the option is selected ∈ {0, 1}

List values are either 1 or 0, indicating whether the given option has been selected or not.

Space: 2^m

The space requirement of this encoding is 2^m: the integer used to encode a ballot with m options needs to be at least that size.

Example systems: Plurality, Approval, Plurality at large


In this ballot type, the voter assigns a specific number of points to each option. The points can be limited such that they add up to a certain total (cumulative voting), or they can each have the same range (range voting).

Parameters:n points maximum assigned per option, out of m options

Index: Option number ∈ {0…n-1}

Value: Points for the option ∈ {0…m-1}

Space: n^m

Example systems: Range, Cumulative


In this ballot type, the voter specifies a global preference over options.

Parameters: n options to be selected out of m possible

Index: The option rank ∈ {0…n-1}

Value: The selected option ∈ {0…m-1}

Space: m^n

Example systems: Condorcet, STV


In this ballot type, the voter specifies a local preference between options presented in pairs.

Parameters: maximum n pairwise comparisons to be made out of m possible pair elements

Index: Consecutive odd-even indices are option pairs ∈ {0…2n-1}

Value: The selected option ∈ {0…m-1}

Space: m^2n

Example systemsPairwise-BetaPairwise-BradleyTerry

List encoding implementation

A Scala implementation of the list encoding method which is simply a base-n encoder. You can test it here.

def encode(list: Seq[Int], values: Int) : Long = {
  val radix = values
  var number = 0
  for (d <- 1 +: list) {
      number = (number + d) * radix
  number / radix

def decode(n: Long, values: Int) : Seq[Long] = {
  var number:Long = n
  val radix = values
  var list = ListBuffer[Long]()
  while(number > 0) {
     list.append(number % radix)
     number = number / radix