An election protocol for implementing random ballot in an accountable manner

Long ago, I proposed that the use of random ballot was a good way to elect a house of representatives. At the time I was only half serious. These days I genuinely think it’s a good idea.

To remind you how this works: Conceptually the idea is that everyone votes as they would under first past the post. Then when it comes time to actually pick the winning candidate, rather than the candidate with the most votes winning you pick a vote at random and use that. Thus the more votes you have, the higher the probability of winning, but you are never certain to win unless you get 100% of the votes.

This subject occasionally comes up in conversation and people complain that the problem with random ballot is that elections have to be accountable and that it’s impossible to make it accountable: You cannot verify the randomization because it’s not repeatable.

Fortunately, this isn’t true. This post is a proposed protocol for how to implement random ballot in a way that has the randomization be fully repeatable and difficult to tamper with. It uses physical sources of randomness as inputs to an electronic voting procedure. The electronic voting is open source, fully deterministic and all inputs to it are published so they may be verified by third parties.

The basic approach is that rather than actually picking a vote at random we tally the votes as we do under first past the post and then use a random number generator to draw a candidate from the resulting distribution. The only tricky bit, which is what this election protocol is designed to ensure, is being able to trust and verify our random number generator.

Edit: It’s been pointed out to me since that there exist much more sensible cryptographic schemes for generating random numbers reliably. Some variation on these should be used instead of the one I proposed here. e.g. each candidate + the people organising the vote counting simultaneously provide a random seed according to this scheme after the votes are counted, then the seeds are revealed, then the calculation is done. So the current details of random number generation are wrong, but I’ll leave them in for posterity. The rest remains valid.

The goals of this design are as follows:

No individual constituency can conspire to change their answer
No central power can conspire to change the overall answers
Once we have counted our votes and obtained our initial random data, everything from that point on is deterministic and verifiable

It involves three components:

Whatever is currently used for tallying votes. i.e. we count up the votes each candidate gets in exactly the same way we currently do
A number of lottery ball machines with 256 balls in it labelled 0 to 255
An open source program which implements our voting procedure

These are deployed as follows:

Firsts votes are counted. These vote counts are published as they currently are. Recounts may be demanded at this point. No recounts are permitted once we start rolling the metaphorical dice, so the whole election is stalled until everyone agrees to stop recounting.

A thing worth noting here is that recounting is much less valuable for random ballot than it is for first past the post: In first past the post if you have 51% of the vote and your opponent has 49%, you’ve won everything and so your opponent really really wants a recount because they’ve got nothing to lose by it. In random ballot you’re near as dammit tied and a recount can make your opponent’s situation worse as well as better, and isn’t likely to do much of either.

Now we have our votes counted it’s time to generate random numbers.

This is where our lottery balls come in. The goal is to generate 64 bits of random data for each constituency, i.e. 8 draws of one byte balls from the lottery machines.

First, each constituency draws 4 balls. They write down the numbers for these but do not publish them.

Then two central authorities which are physically separated and kept out of communication each draw two balls. These results are published.

The random data for each constituency is then the sequence of 4 balls they’ve drawn and 4 balls drawn by the central authority.

What’s the reasoning here?

Well, if the constituency is solely responsible for choosing the random data then they have the possibility of doing something like rejection sampling – they rerun the vote until they get the result they want.

If a single central authority then adds a source of randomness to the mix and they have access to the numbers from some of the constituencies (which they’re not supposed to have, but information can leak), then they can in theorydo similar: Rerun the experiment until they get a more pleasing distribution of seats.

By having two central authorities who are not communicating with eachother you remove the possibility of either of them doing this (they could manage to find a side channel and communicate, but this is hard enough that it makes an already hard problem essentially impossible).

So now we have our vote counts and we have our random numbers. What do we do?

Well, we publish all of these in the open for a start. This makes it possible to verify our calculations.

We now feed them in to our program. The program does the following:

It concatenates all the numbers together into a single 64-bit integer
It hashes that integer (this makes the ability to control any small number of balls in the sequence much less useful)
It uses this hashed integer to seed a pseudo random number generator. I don’t know enough about PRNGs to comment on what is a good one here, but we don’t need fast performance here (even taking seconds per number would be more than fast enough enough) so lets assume it’s one good enough for cryptographic use.
It sorts all the candidates by name
It shuffles that list (this helps a little bit in protecting us against attempts to bias the PRNG towards low or high numbers. I’m not sure it’s a necessary step)
We now generate a random number between 0 and the total number of votes
We use this number to sample from the distribution we got from our vote count (basically counting off from the left until the running total is larger than the vote number we picked)
That sample is our elected candidate

Although there are a lot of “If you could get a hidden communication channel in here and run a lot of simulations really fast and somehow rig the lottery machine to produce the answer you wanted” holes in this, I think they’re almost impossibly difficult to get anything through. The way we combine different information sources means that you need to subvert a lot of different features of the system in order to get a useful influence on the output. I’m reasonably confident that any interference with this procedure is significantly harder and more likely to be detected than more traditional forms of vote rigging, and that the way the information is used in the system is transparent enough to satisfy any reasonable desire for accountability.

Implementing find_or_create correctly is impossible

There’s a method that seems to be present in every single ruby ORM. I assume it’s reasonably common outside for ruby ORMs too, but I hadn’t noticed it before I started using Ruby.

The method is called find_or_create. Its looks something like:

class MyModel
   def self.find_or_create(find_params, create_params)
      self.find(find_params) || self.create(find_params.merge(create_params))
   end
end

(although all code in this post will be ruby, the examples are using a pseudo-ORM that most closely resembles Sequel)

In fact, in many cases, this is exactly what the implementation looks like too.

The thing about this implementation is that it is completely wrong in the presence of concurrency: If you call find_or_create at the same time in two different processes with the same arguments, it will almost certainly result in duplicated creates. If there is a uniqueness constraint then this will cause one of them to error. If there is not, you’ll get two rows when you expected one.

It turns out that as far as I can tell it’s actually impossible to implement this method signature in a sensible way that satisfies the following properties:

The method may always be called
The method does not care about the structure of the table
The method will never result in multiple inserts when called twice with the same arguments (in the presence of no other modifications to the database contents)
Calling the method twice in two different processes will not error unless calling it once would error (in the presence of no other modifications to the database contents)

Here are two proposed implementations.

Just use transactions

This is the most straightforward and general implementation. You just wrap the method in a transaction. The problem is, that we only perform two queries and these absolutely cannot be interleaved, so the transaction in question must be serializable. So the code has to look something like this:

class MyModel
   def self.find_or_create(find_params, create_params)
      database.transaction(:level => :serializable) do
         self.find(find_params) || self.create(find_params.merge(create_params))
      end
   end
end

But this suffers from a problem: What if we’re already inside a transaction? If the transaction is already serializable then that’s fine. If it’s not though there’s nothing we can do to fix this problem.

Additionally, support for correct handling of serializable transactions doesn’t seem to be great. Sequel, which is normally awesome, doesn’t really do the right thing with them (or rather it leaves doing the right thing up to the user and just handles setting the isolation level, which is fine really). But really we need a method that looks something like this:

def serializable_transaction
  if current_transaction
    if current_transaction.serializable?
      return yield
    else
      raise ArgumentError, "Cannot start serializable transaction inside a non-serializable transaction"
    end
  else
    loop do
      begin
        transaction(:serializable => true) do
          return yield
        end
      rescue FailedToSerialize
      end
    end
  end
end

i.e. if we’re already in a serializable transaction we just reuse it. If we’re not inside a transaction we retry the block until we don’t get a FailedToSerialize error (which may happen if you do concurrent modification inside serializable transactions). Note this is pseudo-Sequel. Most of these methods don’t exist in Sequel.

So, given correct support for serializable transactions, we can implement find_or_create as

class MyModel
   def self.find_or_create(find_params, create_params)
      database.serializable_transaction do
         self.find(find_params) || self.create(find_params.merge(create_params))
      end
   end
end

What’s the problem?

Well, firstly, the inability to use this inside non-serializable transactions is rather a big deal. We like transactions, but we don’t want to be making our transactions serializable if we can possibly avoid it.

Secondly, serializable transactions are not always supported and may be really bad ideas on some databases – e..g. they might just cause a global lock. On PostgreSQL this method should behave mostly acceptably, but it’s still not ideal due to the lack of ability to nest it.

So here’s a version which imposes a different limitation:

Rely on uniqueness constraints

class MyModel
   def self.find_or_create(find_params, create_params)
      begin
         return self.find(find_params) || self.create(find_params.merge(create_params))
      rescue UniqueConstraintViolation => e
         find_again = self.find(find_params)
         if find_again
            return find_again
         else
            raise e
         end
      end
   end
end

How does this work?

Well, we rely on there being a constraint enforced on the find params. If there is a uniqueness constraint that they satisfy then trying to do the insert if the find would have succeeded will reliably error.

If however there is some other unique constraint that might be violated – e.g. if some strict subset of the find params or some of the create params have a unique constraint on them – we may through a unique constraint violation for entirely unrelated reasons. This is why we test if the row is in the database and rethrow the unique constraint violation if it’s missing.

Note that one failure mode for this is if someone in another process inserts then deletes this row. This will result in us rethrowing a UniqueConstraintViolation where it would have succeeded if we immediately did an insert. I’m not bothered by that.

I think basically all my use cases for find_or_create key off a unique value in the find params, so this is the one I’ve been using mostly. It’s strictly less general than find_or_create normally is, but has the pleasant advantage of actually being correct.

Interviewing companies

So, as previously mentioned on Twitter, I’m looking for work. If you’re maybe interested in hiring me, check out my CV and drop me a line.

But that’s not what this post is about. Let’s not talk about me here, let’s talk about you.

I’ve always held the very firm stance that when a company is interviewing you, you are also interviewing them – are these people you’d like to work with, does this seem like a decent place to work, etc.

Despite that, when we got to that awkward point at the end of the interview where they say “So, have you got any questions for us?” I was just as bad as everyone else and mostly said “No, not really”. I still formed an opinion about the company, but it was based on how they interacted with me and whether I liked them. It was very unstructured – the only really structured question I considered was “Imagine I was a terrible fit for this role. Do I think I could have made it through this interview process?”. If the answer to that question was yes then I would consider the company to have failed their interview.

But really good interviewing skills aren’t enough for determining whether a company is worth working at. You need a lot more than that. So I was mostly going on the standard “Do I like the cut of their gib?” school of interviewing. This is a school of interviewing that as I have learned as I’ve got more experienced at hiring people is, not to put too find a point on it, complete and utter bollocks.

So, based on a recursive application of my company interviewing technique, I should have failed. Fortunately no one picked me up on that, and fortunately I’ve ended up working with some great people at some pretty good companies.

But I’d like to do better. When we get to that “So, do you have any questions?” stage I want to be able to smile, say “Well, actually” and pull out a notebook.

So now I’m trying to figure out what those questions should be. I’ve got a set of the questions I actually want answers to, and they go roughly as follows:

Are you secretly terrible people?
Is your development process completely dysfunctional?
Is the way your development team interacts with the rest of the company completely dysfunctional?
If your company succeeds, is this actually going to make the world a better place for anyone who isn’t one of your investors?
Is your company going to fail horribly?

Unfortunately I don’t think I’ll get very accurate answers if I ask those questions outright, so I’m looking for questions that will give good indications to the answer to these.

Of course, I expect most potential employers to google my name, read this post, and realise what I’m secretly asking, so this is all a wonderful little game of recursive double bluff. It also means that the questions should be good enough that any answers that aren’t outright lies will reveal the truth.

Here are some questions I’ve got so far. I’ll update these lists as I get suggestions from others or think of new ones myself.

Are you secretly terrible people?

I’m struggling on this one to be honest. A lot of my questions here are hiring policy related, but that’s more because of my recent lines of thought than because it’s a useful indicator. It’s also difficult to ask some of these questions because they sound like “Are you violating the laws regarding employment?” and “Are you going to hire me?”

What’s your office sense of humour like?
What’s your racial and gender diversity like in the company? If it’s not good, do you know why and is it something you’re trying to change? How?
Follow up from the previous one. Do you do anything to deal with implicit biases in your interviewing process
Is the company committed to the London Living Wage for ancillary staff? (suggested by my friend Ruth Ball)

Is your development process completely dysfunctional?

I think this is the one I’m strongest on, as I have a reasonable amount of direct experience of both how to be dysfunctional and how not to be here…

How do you organise work that needs to be done?
Who sets deadlines? How much feedback is involved in this process?
Do you find you usually hit the times you’ve committed to? If not, do you know why not?
How often do you encounter bugs in the system? What do you do when you do?
How much technical debt do you have? Is it going up or down over time?
Suppose it is decided that a feature is needed, and that I’m the one to implement it. What happens between now and the point where that feature hits production?

Is the way your development team interacts with the rest of the company completely dysfunctional?

Again, I lack good questions here.

How do your developers interact with sales and marketing?
Do your developers talk to customers directly?
Do the rest of your company have a good view of what the dev team are doing?
Do the dev have a good view of what the rest of the company are doing?
What opportunities will there be to work closely with other departments? (suggested by my friend Ruth Ball)

If your company succeeds, is this actually going to make the world a better place for anyone who isn’t one of your investors?

Christ if I know how to ask this one. It suffers a bit from “If I knew how to make the world a better place, I’d be doing it already”. Here’s a starting point:

Who are your customers?
How does it help your customers?
In particular, what can they do now that they couldn’t do before?

Is your company going to fail horribly?

I’ve pretty much just got the obvious questions:

Have you got a business model?
Is that business model already making you money? Enough to turn a profit?
If it isn’t already, what makes you think that business model is going to work?
How do you track whether that business model is working?
What are you going to do when you discover it’s not working?

Suggestions, please

I’d love suggestions. Also just feedback on which of these questions you like, which of these questions you think are terrible, etc.

Majority Judgement implementation in python

So I’ve done my first Proper open source library in ages. It’s a Python implementation of the majority judgement voting algorithm.

You can check out the source on Github or just use the pypi package.

If, you know, you find yourself in need of an implementation of majority judgement in python. I admit that’s not very likely.

Majority judgement basically works as follows: Every voter assigns a grade to each candidate in a discrete list of ordinal grades (e.g. terrible, bad, ok, good, great). You then tally these grades and rearrange the grades for each candidate in a sequence. You then compare these sequences lexicographically to determine who won. The first element is always the (lower) median, and each point in the sequence is the lower median of the tail from that point on.

So e.g. a candidate with three OK grades, two bad ones and one great one would get the sequence:

OK, OK, Bad, OK, Bad, Great

A candidate two had two OK grades, two bad ones and two great ones would get

OK, OK, Bad, Great, Bad, Great

So would differ in the fourth position with the second candidate getting “great” and the first getting “OK”, so the second candidate would win.

However, implementing it this way for very large electorates is on the inefficient side, so the library I released contains an optimisation: Basically instead of generating a list it generates a run length encoded list. This is nice because you can often tell how many runs you’re going to need in advance so you don’t have to generate the whole list and compress. It’s also much faster to compare heavily compressed run length encoded lists – you can compare long stretches at a time rather than having to go through one element at a time.

Another optimisation that this library performs is that the evaluation is lazy: We only ever work out as much of the sequence as is needed.

An optimisation this library doesn’t perform yet but that I want it to is that there’s another type of structure I’d like to compress: Frequently you end up with situations where you’ve got a long sequence which looks like Ok, Good, Ok, Good, OK, Good, etc. repeating for a long stretch of time (e.g. you can get this when you’ve got just two grades assigned to a candidate and the same number of each). I’d like to compress those down in a similar manner to the run length encoding. I roughly know how the code for that will look, I just haven’t

Although this is a very early stage of the library, I’m actually pretty happy to label it production ready. It’s not going to change much except in implementation details as the interface is basically “It looks like a list but behind the scenes it’s doing cunning things”, and the test coverage is probably the highest of any project I’ve worked on – it’s got about half again as many lines of tests as lines of code and all those tests are heavily parametrized so there are effectively nearly 600 test cases for < 200 lines of code. Branch coverage is 100% and I intend to keep it that way.

Update on resampling voting systems

In my previous post I wrote about resampling the results of voting systems. I defined a function \(S(n)\) which was the probability of the result changing when you sampled N voters from the population with replacement.

One of the questions I asked was what happens as \(N \to \infty\). I now have a partial answer to that.

This solution only addresses voting systems where you can get the answer by looking at the proportions of votes. Such voting systems can be regarded as functions

\[ \nu : \mathbb{P}(V) \to \mathbb{P}(C) \]

Where \(\mathbb{P}(X)\) is the set of probability distributions on \(X\), \(V\) is the set of possible votes and \(C\) is the set of possible candidates.

I’m pretty sure most conventional voting systems can be viewed in this way, or can be modified to be viewed this way. My only slight concern is that most of them are concerned with integer tallies. However I think they mostly have scaling properties that mean they can be viewed this way anyway (I haven’t checked this properly and I’m pre-coffee at time of writing this post, so this may be an obviously stupid belief).

At the very least however my two examples in the previous post can definitely be viewed this way: First past the post is the function that takes the highest element and produces a probability distribution that returns that with probability 1 (it needs a tie breaking rule. A reasonable one might be a uniform distribution across the highest values). Random ballot we have \(V = C\) and the function is just the identity function. Picking a random Condorcet winner and alternative vote can both be converted with only slightly more effort, so I think there’s at least a reasonably large subset of voting systems which can adopt this formalism.

Anyway, this formalism done, we can answer the question for most such voting systems about what the limiting behaviour of \(S(n)\) is:

Given a voting system \(\nu\) and a point \(x \in \mathbb{P}(V)\), if \(\nu\) is continuous (when regarding \(\mathbb{P}(V)\) as a subset of \(\mathbb{R}^{|V|}\)) at \(x\) (the original distribution of votes in our population) then \(S(n) \to \sum_{c \in C} \nu(x)(c)^2 \), the probability that running the election twice will produce the same result.

Why? Well, basically because by continuity we can find a neighbourhood of \(x\) which makes the distribution of running the voting system on anything in that neighbourhood arbitrarily close to the distribution of \(\nu(x)\). We can then make \(n\) sufficiently arbitrarily large that by the law of large numbers the distribution of the population is going to be within that neighbourhood with probability arbitrarily close to 1. So we can make the distribution of the vote outcomes arbitrarily close to the distribution of the original outcome by making \(n\) large enough, and hence the result follows.

When is this continuity assumption satisfied?

Well, deterministic voting systems are never continuous for all \(x\). Why? Topology! The input space is a connected set, the output space is a discrete set (it’s the set of vectors which have one coordinate set to 1 and all others set to 0). However most of them are continuous away from the boundaries I think – that is, if you’ve not had to invoke some tie breaker mechanism you’re probably continuous at that point (I saw some good visualisations of this a while ago but I can’t find them right now). First past the post in particular is continuous if you don’t have a tie.

Anyway, given this result, I’m largely satisfied as to what the large \(n\) behaviour of \(S(n)\) is.

I’m still interested in the small \(N\) question. I think it’s fairly clear that \(S(1)\) may be quite far from 1 indeed. For example in alternative vote, \(S(1)\) will give you the probability of having the highest number of first votes and will completely ignore the crucial secondary and higher votes. I suspect \(S(3)\) is an interesting number, as it’s the first point at which you can have interesting majority behaviours starting to take effect.