Author Archives: david

A deterministic improvement to Hare-Clark Single Transferable Vote

Quick note: I’ve been redesigning this in my head and think I have a version that is both simpler and better. Alas what I don’t have is a keyboard. I’ll write up the improved version when I’m back. For now consider this inspiration rather than a good idea.

I was thinking about my problems with Meek’s method and trying to figure out a way around them when I accidentally hit on what might be a good idea. I don’t have time to sit down and work through the implications just yet, and I’m about to head off on a road trip without my laptop, so this is just me writing it down the details so that I don’t forget them.

It starts from Hare-Clark counting instead of Gregory counting: We don’t transfer fractional votes, but only ever transfer whole votes.

However unlike Hare-Clark it is not randomized but is in fact entirely deterministic modulo one detail (that one details is basically that when two candidates are clones of eachother you might have to break some ties arbitrarily).

For this purpose of this piece I’m assuming that ballots are total orders of all the candidates. This method could doubtless be adapted to handle incomplete ballots, but I’ve not thought through the details yet.

The key idea is this: We start by ordering the candidates according to some rank aggregation voting method. This can be more or less anything you want. It could even be completely random if you want, but you’re probably better off using Borda count or Borda majority judgement or something. All that matters is that you get a total ordering of the candidates though, and I’m not sure how much impact on the end result the specific ordering has. It is however essential for making the process deterministic: Once you have this ordering there is no further randomness involved.

We call a candidate more mainstream than another if they rank higher in this ordering. We call a voter more mainstream than another if on the first entry in their rankings that differs the first’s candidate is more mainstream (i.e. it’s the lexicographic order with respect to the candidate order). Given any two voters, either their ballots are identical or one is more mainstream than the other.

Now, the vote proceeds as follows:

At any given point, every vote is allocated to a single candidate. Initially start by allocating every vote to their first choice candidate.

Now we proceed to reallocate votes so that no candidate has more than the quota required for election allocated to them.

To do that, we go over each candidate in order of decreasing number of allocated votes, breaking ties by starting with the more mainstream candidate.

We will reallocate just enough of the candidate’s votes to try to give them exactly the quota of remaining votes (and we will succeed unless in the course of doing so some other candidate reaches quota) by removing the least loyal voter one at a time.

One voter is less loyal to a candidate than another in the following circumstances (the first one that applies wins):

If they rank the candidate they would transfer to higher than the other voter ranks the candidate they would transfer to (the candidate they transfer to is picked in the usual way – the highest rank candidate in their ballot that has not been disqualified and has not reached quota)
If they rank the current candidate lower than the other voter did
If they are less mainstream than the other voter

If neither voter is less loyal than the other then their ballots are identical so it doesn’t matter which one you pick.

For each vote in turn we transfer it to its next preference. If this causes that preference to reach quota we immediately stop, leave all the remaining votes where we are, and begin the process again from the beginning (this is because changing the set of candidates who have reached quota immediately redraws all the loyalty boundaries).

This process continues until all candidates have no more than the quota of votes allocated to them. If this results in all the seats being filled, stop. If it results in some vacancies, it’s now time to disqualify a loser.

The loser is the candidate with the fewest votes allocated. If multiple candidates have the fewest votes allocated, the loser is the least mainstream amongst them.

What happens now could go in various ways: You could either do a complete restart as per the Wright system (but note that I think that you probably should count disqualified candidates when considering ranks for loyalty). Another way that I think would work well is that you reallocate them to their first choice non-disqualified candidate even if that candidate is currently above quota. Votes will then get reallocated by the normal way as per above. This lowers the impact of tactical voting for spoilers in much the same way as the Wright system does but fits in better with how this system works (and is probably fractionally more efficient but I doubt that matters).

Anyway, that’s how the system works. I haven’t analysed it or written an implementation of it yet, but I suspect it’s actually rather good. I guess I’ll find out when I get back in a week or two.

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.

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.

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.

Road Trip Day 5

Attention conservation notice: More road trip stuff, mostly a very rambly brain dump.

The road trip has been going well so far, but I’m actually currently at home taking a short rest stop in it – the plan is to continue up north either tomorrow or maybe the day after.

I also changed my plan and added in a London stop. My friend Felix opened a bar a month ago but I’d failed to make it into London to visit since then. I made a joke a few weeks ago that if Trump became president I’d make a beeline for it and do some heavy drinking. Then it actually happened (which honestly I was expecting, mostly in a “expect the worst and that way all your surprised will be pleasant” sort of way), and I decided it wasn’t a joke after all.

The drinking was indeed quite heavy, so the rest stop is extra welcome on that front, but that wasn’t the main reason. The main reason was so that I can remove a lot of stuff from the car.

I think the biggest planning thing I’ve learned about road trips so far is that one of my initial inclinations was completely wrong: I thought that because a car holds a lot of stuff, I had to worry much less about space constraints and I could just bung everything I thought I might need into it and not worry about it.

This turns out not to be true, because the problem is that although a car has a lot of space, as the amount of stuff you have in it goes up your ability to efficiently access the stuff goes way down as everything gets in the way of everything else.

This means that a bunch of things I brought just because they might be useful are in fact actively harmful by their presence.

In particular I brought a bunch of books with me that I’m clearly not actually going to read on this trip, so I’m leaving them behind. I also brought too many spare shoes, some extra towels, some running gear, etc.

I’m also going to leave my laptop behind. Although it’s fairly light I still don’t like carrying it with me, and leaving it in the car makes me nervous even if I hide it well. So once I leave home again there won’t be any further blogging from me until the road trip is over.

One thing that I will not be removing though is my sleeping in the car supplies. I brought my sleeping bag, a blanket and a pillow with me and I’ve already used them once.

It turns out youth hostels are both better than I expected and yet still a bit hit and miss. The youth hostels in Penzance and the Eden Project were both lovely – in Penzance I stayed in a shared room, but the Eden Project youth hostel uses snoozeboxes, and they’re not really the sort of thing that you can comfortably share with strangers. But after the Eden Project I stayed in the Beer (it’s the name of the town. And as far as I can tell they do not brew any beer) youth hostel down in Devon. Or, rather, I didn’t, as I walked into the shared room and was met with a wave of body odour. I don’t think my potential roommates were at fault – it read more like the room was badly ventilated and inadequately cleaned – but whomever was at fault I didn’t really feel like sleeping in there. I have earplugs and a sleep mask, but no nose plugs.

So I set up camp in my car instead. It was still totally worth the money for the youth hostel because it gave me access to a fairly nice lounge and a shower to use in the morning (and I’d only paid about £10) but I’m pretty happy with that decision.

Another thing I’ve learned is that it’s really useful to have a smaller night bag that you can just decant stuff into rather than bringing your full luggage inside. I didn’t have a suitable one with me (my backpack has too many other things for that), so I ended up buying a knock-off Freitag bag when at the Eden Project, made by a Cornish company called Sourced. It’s quite a nice look, and has been serving me well since then.

My plan to get up early every day has been working in the sense that I’ve been getting up early every day, but if anything I’ve been getting up too early. Very few things seem to be open before 9 and most / many things before 10. As a result I’ve shifted my alarm clock an hour later for the rest of the trip.

But that’s really been the only problem I’ve been finding it surprisingly easy to get up despite running on very little sleep though (I think I’m averaging about five hours). The caffeine alarm clock helps a lot here (augmented with theanine). Who knows, I may even keep a schedule like this up when I get home properly.

Other than all that, things have been going well. I’ve been doing lots of enjoyable walking. The trick seems to mostly just look for bits of green that say Area of Outstanding Natural Beauty on the map and then finding a youth hostel near them. I’ve been quite lucky with the weather for that – there’s been some fairly dicey weather while driving and arriving at places, but the next day the weather has been lovely and given me some good opportunity to explore.

Though it turns out that I’m fairly out of shape for long walking. I’ve only been doing in the region of 2-4 hours per day and it’s left me with fairly sore legs. Some combination of not using those muscles that much (walking on the beach or hills is a lot harder than just normal walking, and I normally don’t do 2-4 hours per day) and my flat feet. Hopefully it’ll get easier once I’ve had a little bit of recovery and then some more practice. This was another reason that I’m relaxing my wake up time a bit – it turns out that daylight still lasts longer than I actually have walking time to fill it, so as long as I get going some time well before about 11 I’m basically not going to run out of time.

Anyway, that’s all for now. There may be some more non road trip blogging tomorrow, but if not this will be the last piece until I’m back.