David R. MacIver

The following experiment design has occurred to me. I think it would be interesting, but I’m not sure it would be quite interesting enough for me to put in the effort to create it.

The domain of experiment is as follows: Given a presumed homogenous group trying to make a decision about a shared goal, what is the best decision procedure (i.e. voting system) for combining their opinions about it into a single decision?

The setup is as follows.

We take a strategy game. I picked reversi as a nice sweet spot between complicated and simple (it also has the nice property that the number of valid moves is quite constrained). Teams of people are assigned to black and white respectively.

A turn is played as follows:

The set of valid moves is generated. If there are no valid moves or only one play proceeds in the obvious constrained fashion without user input.
If there are more than some cap of valid moves pick a random subset of them (I’m not sure this is necessary. The maximum number of valid moves in reversi shouldn’t be very large).
The team then votes in some manner on which move to take.
The move which the voting system declares to be the winner is taken.

Note that this requires that the decision procedure not allow ties. This isn’t a terrible constraint as you can just add a random tie breaker to the decision procedure.

What’s the output of this experiment?

Each game generates the following data point:

Black had N players using voting procedure X
White had M players using voting procedure Y
C won

(it also generates the complete history of the game if that’s useful or interesting, but I suspect that’s too complicated to properly analyze)

A sufficiently large sample of this data can be used to answer a number of questions. The following are particularly interesting:

1. Given the same size of group, does voting procedure X tend to beat voting procedure Y?
2. Given a fixed voting procedure X, what is P(X applied to a group of size N beats a single opponent) as a function of N?
3. Given a fixed voting procedure X, what is P(X applied to a group of size N beats X applied to a group of size M) as a function of M, N

Obviously you can’t then go on from this to say “This is the best voting procedure” as it’s applied to a very simple case, but I think the results would be interesting.

So 12,640,417 people told me the following joke earlier:

Q: If I ask you if I should listen to your advice, and you tell me “no”, what should I do?
A: I don’t know, but I bet the UK is going to spend the next couple decades finding out.

So my slightly crazy article about random ballot was mentioned in the new scientist.

This is, as you might expect, quite exciting. Unfortunately the article gets one really crucial thing about me wrong, and my comment clarifying this on the site has yet to be approved, so I just want to make this clear:

I am not actually advocating random ballot

Observe the following quote from the original article:

I think it has desirable and undesirable features (in particular there’s one really major problem with it), but even with the above list I’m not sure I actually endorse it. Consider this a thought experiment more than a proposal.

“perfect” was in scare quotes for a reason. It has some very nice properties, but it also has a lot of problems (both theoretical and practical). I have no interest in promoting it as the system we should actually be using, it’s just an interesting system to think about it. The reality is that (while it’s not necessarily the system I would have most preferred) I am extremely strongly in favour of the move to AV and will be voting yes on May 5th.

Update: Jacob has now fixed this, mentioning I am “highlighting” it rather than “pushing” it.

As you might have noticed by now, I’m quite strongly pro voting yes to AV in this referendum. Here are some links about that:

Dan Snow’s Alternative is a very simple and compelling explanation of how AV works and why that’s a good thing.

Politics in the Animal Kindom goes into more depth, including some of the problems with the current first past the post system and why AV avoids them.

For a more light-hearted video about AV, watch Is your Cat confused about the referendum on the voting system on the 5th May?. As well as being a hilarious cat video it’s also a good explanation.

In Is AV better than FPTP?, Timothy Gowers writes about the issues around the two systems. It’s very very long, but an extremely good breakdown. It starts out trying to be unbiased, but finishes with “I have largely failed in my aim to adopt a neutral tone. However, that is because most of the arguments put forward by opponents to AV have been clearly wrong”.

Well, yes. Indeed they are

I’ll update this post as I find good links. Feel free to suggest any in the comments / on twitter / etc.

Disclaimer up front: This is not about the referendum. It is a description of an AV variant with mathematically interesting properties. If your opinion on this subject can be described by a hashtag, please move along.

I posted a comment on hacker news yesterday in a thread about the randomized voting system I described. It describes another randomized voting system with preferential voting which is much more reliably guaranteed to elect “sensible” winners (of course, as a result it loses the statistically-PR property of my previous one, so it’s not a replacement in any way, but it’s still a good system). It goes as follows:

1. Every voter ranks some subset of the candidates in order of preference. They are considered to prefer every candidate they list to every candidate they don’t.
2. For each pair of candidates A, B decide whether the majority prefers A to B. A voter prefers A to B if they voted for both and ranked A higher or if they voted for A and not B.
3. For each candidate A prepare a “drop-out list”: The list of candidates B for whom the majority prefers A.
4. If you have one candidate, stop. Elect that candidate.
5. Pick one of the remaining candidates at random. Call this candidate Pivot. If there are any candidates left on Pivot’s drop-out list, those candidates drop out. Else, Pivot drops out.
6. Go to step 2.

This is based on a specialisation of Kwik-Sort (which computes the whole aggregate preference) from “Aggregating Inconsistent Information: Ranking and Clustering”, by Nir Ailon, Moses Charikar and Alantha Newman. The original algorithm is a probabilistically 11/7 tight estimate of the Kemeny optimal aggregation.

Despite the random nature, this approach has many desirable features. In particular it is a generalised Condorcet method – if there are two blocs ProKitten and AntiKitten such that for every A in ProKitten and b in AntiKitten the majority prefers a to b, then the winner will be ProKitten. In particular this system always elects the condorcet winner and never elects the condorcet loser (if either exist), as you can consider them to be a bloc with one entry.

But as the comments yesterday suggested, people really dislike the idea of randomness in elections. I don’t personally agree with this, though I do tend to think that if you can achieve results which are nearly as good without randomness then that is desirable.

So this got me thinking: The fact that the above algorithm is generalised Condorcet isn’t actually in any way dependent on the randomness (it kindof can’t be – otherwise it would only be probabilistically generalised Condorcet, as you could always randomly select the worst option). Thus you can use any voting method you like and select the least popular and the algorithm will still work.

In particular you can use AV. Here’s how it works:

1. Every voter ranks some subset of the candidates in order of preference. They are considered to prefer every candidate they list to every candidate they don’t.
2. For each pair of candidates A, B decide whether the majority prefers A to B. A voter prefers A to B if they voted for both and ranked A higher or if they voted for A and not B.
3. For each candidate A prepare a “drop-out list”: The list of candidates B for whom the majority prefers A.
4. If any candidate has more than 50% of the first votes, that candidate wins.
5. Pick the remaining candidate with the fewest votes. Call this candidate Pivot. If there are any candidates left on Pivot’s drop-out list, those candidates drop out. Else, Pivot drops out.
6. All of the people who voted for a dropped out candidate transfer their vote to their favourite candidate amongst the remaining ones (or abstain if they have no candidates they can stand amongst the remainder)
7. Go to step 4.

This remains a generalised condorcet method: Consider ProKitten and AntiKitten. If the pivot we pick is ProKitten and there are any AntiKitten candidates left, those candidates drop out (if there are not then the winner is obviously ProKitten). If the candidate we pick is AntiKitten then the only candidates who can drop out are AntiKitten because the ProKitten candidates are preferred to this one so are not on its drop-out list.

That only leaves the final step, but it’s obvious that if a candidate has > 50% of the first vote then they must be ProKitten, because otherwise they would be AntiKitten and preferred to ProKitten candidates.

So, we have a mild variation of AV which is generalised Condorcet. Do I think this is the best system? No idea. Haven’t done a detailed analysis of it. But it seems significantly easier to explain to people than many of the Condorcet methods (because despite what a certain hashtag would have you believe, AV is really easy to explain, and this is not substantially more complicated) and retains the intuitive appeal of AV whilst fixing its worst mathematical issues.