Category Archives: voting

Generalized Single Transferable Vote

One of the interesting things I’ve noticed with my recent work on deterministic Hare Clark is that this method generalises to let you take any ranked voting system and turn it into a single transferable vote variant. I’m unsure how useful this is, but I think it’s at least notable.

(Note: I’ve never seen this before, but it’s sufficiently obvious now that I have that I would be surprised if it was truly original to me)

There is a caveat though: Although it takes any ranked voting system, the n=1 case does not correspond to the winner for that ranked voting system. Instead it corresponds to what I’m going to call the instant runoff variant of that voting system. Normal instant runoff voting is then the instant runoff variant of plurality voting.

Lets see how this works.

Instant Runoff Variants

Suppose people cast votes in some unspecified manner – scores, rankings, etc. All we need to be able to tell about these votes is if for a given candidate what other candidates the voter strictly prefers to this candidate (ties are OK and we don’t care about them). We also need to be able to take a vote and restrict it to a subset of the candidates.

Suppose we then have some voting system that takes these votes and produces a total ordering of the candidates (this will need some tie breaker).

The normal version of this system is to output the highest ranked candidate. The instant runoff version of this system instead aims to produce a candidate with broader majoritarian support, and proceeds as follows:

A vote supports a candidate if there are no other (non-disqualified) candidates that it strictly prefers. We disqualify candidates until there is some candidate that is supported by a strict majority of votes (clearly this must be possible – if we disqualify all but one candidate that candidate is supported by 100% of the votes).

We repeatedly iterate the following process:

Run the voting procedure on all votes with all remaining candidates. Now, starting from the highest ranked candidate and working downwards check if this candidate is supported by a strict majority of votes. If it is, that candidate is elected. Stop and return it.

If we get to the end with no candidates elected, disqualify the lowest ranked candidate and start again.

Normal IRV voting is just this construction applied to plurality voting on the highest ranked non-disqualified candidate (the ordering step is a red herring there because at most one candidate can be supported by a majority of first preference votes, but the drop-out is the same once you account for tie breaking).

This will in general produce quite different results from the original voting system – the difference between IRV and plurality shows that, but here’s another example with Majority Judgement. Suppose we’re running majority judgement with four grades (Reject, Tolerate, Accept, Support) and supposed we have three candidates and three voters who grade as follows:

  • Accept A, Reject B, Support C
  • Reject A, Reject B, Tolerate C
  • Support A, Reject B, Reject C

The first median grades are Accept A, Reject B, Tolerate C, so A wins the majority judgement immediately.

But it doesn’t win the runoff version (even without any dropout steps!), because a majority supports C and does not support A: The first two voters both support C as their best option, so C wins despite the relatively lower grade.

Unsurprisingly this will tend to destroy a lot of the character of the underlying voting system and make it behave significantly more like IRV than the original system does, but I still think it retains some of the interesting underlying character because it both prioritises winners who are ranked higher in the underlying system and drops out losers from the underlying system.

Generalised Single Transferable Vote

The above then generalises directly to single transferable vote as follows:

Instead of looking for support from a strict majority we look for support merely from a quota worth of support. When we find it, we remove a quota worth of votes from the set of available votes (either randomly or using a prioritisation mechanism of some sort), mark the candidate as elected and start the process again with those votes and that candidate excluded. We repeat until we have elected a full house of candidates.

In the same way that IRV results from applying the above construction to plurality voting, Hare-Clark STV is what you get if you apply this construction to plurality voting.

All of the adjustments in my previous post – prioritisation, reallocation, etc – apply just as well in this case, but I’ll omit them here for the sake of brevity. Given those adjustments though, what I described is essentially applying this construction to plurality voting with a tie breaker defined by another voting system.


I don’t know how significant this is or how useful this is, but I’ve been wondering for a while how to turn non-ranked, or better ranked, systems into an analogue to STV (which I’m generally of the opinion that it’s a bit of a rubbish system but for the niche it fills it’s also the best system we currently have).

There’s Reweighted Range Voting, which I only came across recently, but I think it’s a less than ideal system. In particular it lacks the coalition forming property that I’ve only recently been convinced is a good idea: It always elects the winner of the single-winner version as one of the winners (this may be bad because that winner might win as a compromise between two coalitions who would each be able to get their own seat in a larger house). I’m also fairly ambivalent on the subject of range voting (and will moderate out the inevitable comments that come from its advocates trying to tell me I’m an idiot for not thinking it’s the best thing ever), but this approach would work just as well for range voting and will probably produce a better result than RRV.

I’m far from convinced that this will prove to be the ideal way to produce more general proportional representation systems though, because I think the result is still too similar to STV and will likely inherit many of the failure modes of it.

In particular it will certainly sometimes turn monotonic systems into non-monotonic ones, because if you take plurality voting (a monotonic system, for all its faults) and apply the construction then you get IRV (a non-monotonic system, among its faults). I don’t in general think non-monotonicity is the worst thing ever, but it’s certainly pretty bad.

Still, it seems likely that for some choices of ranked voting system this will prove to be a strict improvement on STV. e.g. if you apply a Condorcet ranking system then in many cases you are likely to get a better result. It also opens the door for more interesting classes of ballots being cast in proportional multi-seat elections, which is promising.

This entry was posted in voting on by .

Deterministic Hare-Clarke STV voting, take 2

I ended up doing a lot of redesign of my deterministic variant on Hare-Clarke STV while driving around. At this point I’m pretty happy with it conceptually and after about an afternoon of experimenting with it I think it might genuinely push back the state of the art in STV counting methods. I’m not currently prepared to say it does because I don’t think my current level of testing is adequate to make that claim, but at the very least initial results are promising.

Here’s how it works.

First we need some definition of terms (many of these are the same as standard STV):

  • We define a priority order over candidates. The idea is that this defines a strict tie breaking order over candidates – when all else is equal, we do the thing that benefits higher priority candidates.
  • We also define a priority order over votes. The idea is that higher priority votes should be “more able to transfer” because they could still be useful. The voter priority will change as candidates get elected.
  • At any point in time, any given vote is either free or assigned to a candidate. A vote may be assigned to at most one candidate.
  • At any point in time, any given candidate is either electedhopeful or disqualified.
  • A vote is available to a candidate if the vote is free and every candidate the vote has ranked higher than that candidate is either elected or disqualified. A (full) vote is always available to exactly one hopeful candidate and may be available to multiple elected candidates.

As usual the goal is to get the desired number of candidates to the elected state.

One of the big differences so far is the introduction of the “free” state for a vote. Instead of having votes all be assigned to candidates and transferring between them, votes only transfer between free and assigned. Further, the only candidates with assigned votes are the elected ones, and we maintain the invariant that every elected candidate is always assigned exactly a quota worth of votes. Votes may then move between allocated and free states, but never between allocation to two candidates.

The voter and candidate priorities require more explanation of the details, but they’re fairly complicated and distract from the overall method, so I’ll explain the details later.

Elections then proceed in a number of rounds as follows. In each round either one or more candidates move from a hopeful state to an elected state or exactly one candidate moves from a hopeful state to a disqualified state. Additionally, votes may move between free and allocated states in ways that preserve the invariant that every candidate has exactly zero (if hopeful or disqualified) or quota (if elected) allocated votes.

Each round first consists of an elect stage. This works as follows:

For each hopeful candidate with at least the quota worth of votes available to it, mark it as elected. Now for each candidate that was elected just now, assign a quota worth of the votes that were previously available to it before the change in status (to prevent a candidate accidentally stealing votes another one needs out from under it). They each each pick the quota worth of votes with the lowest priority available to them.

We repeatedly do this until no new candidates are elected.

If no candidates were elected in the previous stage, we perform a dropout stage: The worst hopeful candidate is marked as disqualified.

Worst is picked more or less as usual: It’s the hopeful candidate with the fewest votes available to it. In the event of the tie, it’s the lowest priority amongst the tied candidates.

If on the other hand some candidates were elected, we now perform reallocation.

The idea of reallocation is that there are low priority votes that are currently free that could replace higher priority votes that are currently allocated, they should.

Reallocation works as follows: For each free vote, starting from the lowest priority and working upwards, go through each candidate they are available to in the order they voted for. If that candidate has any votes allocated to it that are higher priority than the current vote, allocate the current vote to that candidate and mark the current highest priority vote allocated to that candidate as free.

Repeat this process until it runs to completion without making any changes.

This process of alternating election followed by either reallocation or dropout continues until the full set of candidates have been elected.

Conceptually, that’s pretty much all there is to it other than the definition of priorities.

What constitutes a good priority for candidates is a somewhat open question, but I’ve been working on the assumption that it’s basically a rank aggregation order for the votes. I’ve been using Borda Majority Judgement, for no particularly good reason other than it seems to produce slightly nicer results in general than Borda score and given that I had some code around for calculating Majority Judgement it was easy enough to do. This still requires some experimentation though.

Given the priority order for candidates though, there is a natural and effective way of calculating a priority order for votes.

The idea is that we first prioritise votes that are less satisfied, then given two equally satisfied votes we priorise ones that agree more with the priority order for candidates.

We work with the reduced vote that you get after you’ve discarded all disqualified candidates.

Now, to determine which of two votes are higher priority we first look at the first index in the vote of a candidate which has not been elected. (So e.g. if I voted “A, B, C” and A and C have been elected then my list here would be “1”, as indices start from 0). Given two candidates, we compare these lists of indices lexicographically. If one is before the other, that vote is higher priority.

Or, in other words, if the first unelected candidate in my ranking is higher ranked than in yours, my vote is higher priority and vice versa. If they are the same, we look at the next unelected candidates, and so on.

If this results in a tie, we now compare priority orders. We look only at the unelected candidates on our ballot. Find the first candidate where the two votes differ. The vote with the higher priority candidate there is higher priority.

If still tied, do the same but for elected candidates (this step doesn’t matter, but prevents us having to break ties arbitrarily). If the votes are still tied after that then they are identical up to disqualified candidates (which don’t matter), so pick whichever.

Small Elections and Anecdotal Results

This seems to work pretty well. In a lot of cases it just agrees with Gregory or Meek counting – the large majority of STV elections it doesn’t seem to matter very much which method you pick, it’s only in edge cases that it makes a difference.

But there are some interesting edge cases where I think it comports itself fairly well.

The following election is one:

  • Two votes: 0, 1, 2, 3
  • Three votes: 0, 2, 3, 1
  • Two votes: 2, 0, 3, 1

In this election it produces a result that no fractional counting method can and happens with quite low probability in standard Hare-Clarke voting, but I feel that it’s quite defensible as the correct result: It elects candidates 0, 1 and 2. Gregory or Meek counting would elect candidates 0, 2, and 3.

The reason for this is that the quota is two, and there are exactly two votes who would support 1 given the option (you could achieve the same effect with larger number of votes and have the number supporting being slightly above the quota if you liked). This means that if any fraction of their vote transfers away then it is no longer possible for candidate 1 to be elected.

When Meek and Gregory counting disagree it doesn’t always seem to side with one or the other. e.g. in the following election it agrees with Gregory counting but not Meek:

  • Four votes: 0, 3, 2, 1
  • Five votes: 3, 0, 1, 2
  • One vote: 3, 2, 1, 0

When electing three candidates, Gregory and this method elect 0, 1 and 3 while Meek elects 0, 2 and 3.

There doesn’t appear to be any deep reason about which it agrees with here: The difference between Gregory and Meek is about which candidate drops out after 0 and 3 have been elected – under Meek candidate 2 retains a slightly higher score, so stays in.

In this method however there are no disqualifications at all, it just finds a mutually amicable assignment of votes. No drop out happens because everything worked out fine in the electoral phase (anecdotally this seems to happen a lot). A reallocation is performed, but it doesn’t affect the results if you disable it.

This could easily have gone the other way. The following election picks the same candidates as Meek which is different from Gregory:

  • Three votes of 0, 1, 2, 3
  • Two votes of 0, 3, 1, 2
  • One vote of 1, 0, 2, 3
  • One vote of 1, 0, 3, 2

When electing three candidates, Gregory elects 0, 1 and 2. Meek and this method elect 0, 1 and 3.

The reasons are much the same as before: The difference between Gregory and Meek counting comes down to which drops out after all the possible candidates have been elected, whileas this method just happily goes and finds a set of compatible votes:

  • Candidate 0 gets two “0, 1, 2, 3” votes
  • Candidate 1 gets “1, 0, 3, 2” and “1, 0, 2, 3”
  • Candidate 3 gets  two “0, 3, 1, 2” votes

Unfortunately sometimes this system can demonstrate arguable worse results. In the following election it exhibits non-monotonic behaviour where the fractional methods behave correctly (though there are cases where the fractional methods also demonstrate non-monotonic behaviour. It’s intrinsic to STV):

Three votes [0, 1, 2, 3, 4],
Four votes [1, 0, 4, 3, 2],
Two votes [4, 0, 2, 1, 3],

When electing 4 candidates, all three methods agree this should elect 0, 1, 3 and 4. However, if we take one of the final votes of “4, 0, 2, 1, 3” and raise 3 from last to first place, all of a sudden we elect candidate 2 instead of 3 under this method, while the fractional votes remain unchanged.

I don’t have a straightforward explanation for why this happens here. For some reason this causes 4 to get elected using the votes that would have been used for three instead of the ones it used previously, but it’s not completely obvious to me why. It’s possible this might be a bug in my implementation. I’ll update this section when I know more.

Update: This happens because the rule for electing multiple candidates simultaneously has unexpected consequences. In the original case, 0, 1 and 4 are all elected in the same round. In the case where a ranking for 3 has been increased, 4 is elected in a separate round. This has unexpected consequences. I’ll look into seeing whether changing the rule here is an improvement..

Even if this is correct, I’m not too worried. Non-monotonicity is a known flaw of STV so it’s not surprising this method exhibits it, even if it is slightly surprising it exhibits it in a place where Gregory counting does not.

In none of these examples did this method need to either disqualify candidates or redistribute votes. Here’s an example where it does need to redistribute votes:

  • One vote 0, 1, 2, 3
  • One vote 3, 0, 1, 2
  • Four votes 3, 1, 2, 0

When electing three candidates, Gregory, Meek and this method all agree that the correct candidates to elect here are 0, 1 and 3.

However, if you disable reallocation then this method does not agree, and elects 2 in place of 0. The reason for this is that the vote “3, 0, 1, 2” originally gets used to elect candidate 3, but once candidate 1 has become elected it gets swapped out for a “3, 1, 2, 0”. This gives 0 and extra vote, which causes it to become elected instead of dropping out.

This example would be different given a different priority order on candidates, but similar ones exist for any order.


For the cases where no candidates drop out when this method is run I feel from a philosophical point of view that it’s just obviously better than fractional methods: It successfully arranges a quota worth of actual voters for each candidate, all of whom have a full initial prefix of their vote. You can imagine a process of mutual negotiation and swapping amongst voters to get there, at which point the single transferable vote requirement is satisfied.

Anecdotally this seems to happen a lot – the system is very good at finding such a satisfaction. I suspect this is in small or large part a function of how I’m generating examples to look at, but it’s still an encouraging sign.

For the cases where drop-out then happens I’m less convinced about the system making equitable choices, but it’s probably no worse than STV normally is (the drop out round is in many ways the least convincing part about STV), and may be better depending on how you calculate the priority order.

All told this is a really promising looking system. I’ll put together some proper open source code for trying it out at some point in the near future, along with some more serious evaluations.


This entry was posted in voting on by .

A failure mode of single transferable vote

I’ve just realised a fairly bad failure mode of single transferable vote. It was obvious that it must happen once I saw the possibility, but I wasn’t previously aware of it and I had to throw my election generating machinery at it to find an example.

The property is this: If you increase the number of seats you are electing, candidates who were elected with the smaller number of seats may no longer be elected with the larger number of seats.

Here’s a small election demonstrating this:

  • One vote of 2, 0, 1, 3
  • Two votes of 0, 1, 2, 3
  • Two votes of 1, 0, 2, 3
  • Five votes of 2, 3, 1, 0

If you run this election (I tried it with the Gregory method and no restarts, but it doesn’t actually seem to matter which method) with two seats to be elected then you elect candidates 1 and 2. If you run it with three seats to be elected then you elect candidates 0, 2 and 3 – candidate 1 now fails to gain a seat at the larger table.

The reason this happens is as follows: In both cases candidate two clears the quota on first choice votes and is elected immediately. But with two seats rather than three the quota is higher, so they lose more of their vote. As a result, candidate 3 is penalised more harshly. In both cases again there is no second candidate who immediately gets a second seat, so someone has to drop out of the race. With two seats, the votes that are pushing for candidate 3 have lost more ground and candidate 3 no longer has enough strength to stay in the race and drops out, transferring the remaining votes from the large voting bloc to candidate 1. Meanwhile, with three seats candidate 3 beats out candidate 1, leaving it as the loser who drops out of the election at that point.

I haven’t really thought through the implications of this. It’s not news to me that STV has some weird edge cases, but this is a particularly annoying one of which I was not previously aware.

Updates: First off, I’ve actually been convinced that this is a feature not a bug. What essentially happens is that compromise candidates between coalitions who don’t have enough support for their favoured candidates come together to support a mutually acceptable less good candidate. When the number of seats available becomes larger they have more space to go their own way.

Secondly, here’s an example of this happening with only three candidates:

  • Five votes: 0, 1, 2
  • Four votes: 1, 0, 2
  • Eight votes: 2, 1, 0

If you run this to elect one candidate (i.e. normal IRV) then you’ll elect candidate 0, because 1 drops out in the first round and transfers the needed number of votes to 0. If you run it to elect two candidates, both 0 and 2 immediately have enough votes to beat the quota and are elected immediately.

Notably, 1 is also the Condorcet winner in this election.

This entry was posted in voting on by .

A Small STV Election for Meek’s Method

I’m continuing my experiments to figure out the strengths and weaknesses of different types of single transferable vote. I thought I’d explore Meek’s Method.

The following small election produces a different (unambiguous) result depending on whether you use Meek’s method or normal Gregory counting:

We are trying to fill three seats, with four candidates (named 0, 1, 2, 3) competing for those seats. Six votes are cast for them as follows:

  • One vote of 3, 0, 1, 2
  • Two votes of 0, 1, 2, 3
  • Three votes of 3, 0, 2, 1

Both Meek and normal Gregory counting elect candidates 0 and 3, but they differ on whether they elect 1 or 2. Meek elects candidate 1, Gregory elects candidate 2.

The reason for this is that in the first round both methods elect candidates 3 and 0 (the quota to meet here is 2 votes). With normal Gregory counting all of the votes that cast 3 as their first vote now transfer to their third preference, because 0 is already elected. With Meek, the cost of electing 0 is more spread out between all of the votes, so the strong bloc who have candidate 2 as their third choice preference got more weight.

I feel like in this case it’s probably fairer for 1 to be elected than 2: The candidates who voted for ‘3, 0’ as their first choice are doing a lot better than the candidates who voted for ‘0, 1, 2, 3’ by the third round – they have their two favourite candidates – so giving the latter more weight in the ranking is probably fair. In Gregory counting they are instead penalised heavily because the they were made solely responsible for bringing in candidate 0 despite the fact that it was everyone else’s second favourite candidate which they would have happily voted in next round if 0 hadn’t made the quota in the first round.

I’m glad I did this experiment though, because it taught me two important things:

  • I think Meek’s method probably produces noticeably fairer results in many cases.
  • I don’t trust Meek’s method at all and suspect many or most implementations of it are subtly broken.

To unpack on the latter: This implementation was very hard to get right. I’m still not 100% sure I have, and I definitely wouldn’t have without a lot of assertions, testing it using Hypothesis, and implementing everything as arbitrary precision fractions rather than floating number so I could do a lot of cross checking.

Additionally, it required at least one significant change to the method that is both obviously necessary and don’t seem to be documented anywhere at all:

With the method as described it is possible for a candidate to retain more than 100% of the vote that is allocated to them, so you need to cap the weights at 1 if an elected candidate currently has less than the quota (this can happen because they get some large percentage of their vote passed on from other elected candidates), or everything goes horribly wrong and you start getting candidates with negative numbers of votes. You also have to handle a possible divide by zero here if in the initial rounds of the iterative process an elected candidate actually has no votes at all.

On top of that, all implementations in the wild probably use floating point rather than arbitrary precision numbers. On the one hand this is a good thing because the arbitrary precision method proved to be incredibly slow – the calculations involved produce massive blow-ups in the size of the fractions, so everything basically ground to a halt after a fairly small number of iterations. On some slightly larger elections (e.g. I saw one trying to elect 7 out of 8 candidates)  it essentially never terminated.

This probably means you’re getting a lot of rounding errors in practice if using floating point numbers, which makes me somewhat reluctant to use the system in practice. If I were to use it I would probably insist on a software floating point library so as to have a reproducible result on different machines. A fixed point solution might also work her.e

Interestingly, Meek’s method is used in practice by several countries. It’s not totally clear to me how they deal with these issues, or how much that would matter in practice.

This entry was posted in voting on by .

I still believe in democracy

I’m a dual citizen – my mother is from the US, my father is from the UK, so I’m a citizen of both countries.

As you might imagine, I’m quite disappointed in both of my countries this year.

I thought I wasn’t going to write about this, because most of my opinions on the subject are fairly standard, but it occurred to me that actually there’s something I do want to say and it’s quite important. It’s not intended as a disagreement with anyone in particular, it’s more an affirmation of my beliefs.

And that belief is this: Despite the fact that in both of my countries a majority or near-majority of votes were cast for an option I believe to be a disaster, I still believe that the way out of this is more and better democracy.

A quote from the then prime minister of Norway, Jens Stoltenberg, after the the right-wing terrorist attack by Anders Breivik, has stuck with me ever since:

“We are still shocked by what has happened, but we will never give up our values,” Stoltenberg said. “Our response is more democracy, more openness, and more humanity.”

I am still shocked by what has happened, but I will never give up my values.

And one of those values is that a country should help all of its citizens achieve the best possible version of their lives, and it should do so with their active participation in the process. The solution isn’t to ignore their voices, it’s to help them and involve them in making better decisions for everyone together.

This doesn’t require us to accept the results – Democracy is far more than simple majority rule, and dissent and protest are integral features of a well functioning democracy – but it does require finding some sort of common ground.

Not everyone will be able or feel safe to participate equally in the process of finding it – many of us are far more at risk than others – but I think that makes it more important for those of us who can participate to try to help do so.

Common ground feels particularly difficult right now, with so much of the population having embraced outright racism and self-destruction, but I still think it’s achievable. More importantly, I think it’s still achievable without giving in to or compromising with that racism.

One of the most important things I’ve learned in my career is that just because someone has the problem doesn’t mean that they know what the solution is – often they think they know what the solution is but are entirely wrong, and usually when you ask them what the problem is they will tell you about their solution.

If this is true in comparatively simple things like software, it’s certainly true in fiendishly complicated things like national and international politics, where people (including me) are even less likely to understand the problems and are even more likely to feel strongly about the solutions.

But generally when you provide people with a solution that actually works and solves their underlying problem, they eventually let go of their wrong solution.

There are definitely some hard core of supporters for Trump and Brexit who are actually just terrible people (there’s certainly a large subset of supporters for Hillary and remain who are also terrible people. This feels less central to their causes, but then I would think that), but I choose to believe that they are not the majority of them, and that most of them are just people who have problems and have grasped on to wrong solutions.

Those solutions are ones I find especially objectionable, and ones I have no intention of tolerating, but ultimately I still think the fix is the same: Talk to people, involve them, and work together to find a solution that works for everyone.

But I don’t know how to get from here to there.

I’d like to end this with some great suggestions about how to fix our politics, but I just don’t know.

I still think electoral reform and proportional representation are vitally important – I don’t think it’s a coincidence that both the UK and the US are among the worst democracies for actual representation – but it’s not like an immediate switch to proportional representation would help us given how the population actually voted (or maybe it would? Perhaps some large fraction of Trump and Brexit supporters would have voted for a more nuanced option given the ability to do so? I don’t know).

I still think the press and their coverage of the issues are a major part of the problem, but I don’t know how to fix that – freedom of the press is important, and much of the problem really comes from the financial incentives of news as it currently stands. This feels like a problem where I don’t have a more specific solution than “fix capitalism”, which tends not be a viable solution.

I still think economic insecurity plays a major role in fostering hate, and that the way to fix that is going to be some form of universal basic income, but I have no idea to get from here to there either.

But all of that makes this feel like a “This Major Political Event Proves That I Was Right All Along” post, and I don’t know if I was. I still think I’m right, but maybe there’s something else going on here.

So I don’t know. This is not, in the end, a solutions post. It’s what it started out as: A values post.

I still believe in democracy, and I don’t think we have a way out of this that doesn’t somehow engage with the large subset of our population who have made disastrous decisions.

I am still shocked by what has happened, but I will never give up my values. My response is more democracy, more openness, and more humanity.

Now we just have to figure out what that looks like.

This entry was posted in voting on by .