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.

Conclusion

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 .