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:

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

#### Range

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

#### Ranked

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

#### Pairwise

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 systems**: Pairwise-Beta, Pairwise-BradleyTerry

#### List encoding implementation

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | 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 } list.reverse.drop(1) } |