How to turn AV into a Condorcet system

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.

This entry was posted in voting on by .

7 thoughts on “How to turn AV into a Condorcet system”

1. AlexS

In both descriptions point 2 currently reads:
“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 B and not A.”

“or if they voted for A and not B” ?

2. Eric

Hi David,

I’m interested by decision methods as well and many of them have been carefully studied and there are many other “desirable” properties than being Condorcet that a method could/should have. I’d like to point out for you a thesis which unfortunately is in French only AFAIK: “About some paradoxes in social choice and in multicriterion decision making” (http://bit.ly/je1FEE). It basically shows that many decision methods can lead to different types paradoxes. For example, one of them is that in some methods, if a voter raises his preferences for a candidate, the global preference for that candidate will decrease!

Eric.

3. Clay Shentrup

A better system would be Approval Voting. Not only does it generally outperform Condorcet methods according to the One Right Metric, Bayesian Regret, but it also may in practice be a better Condorcet method than real Condorcet methods.

http://ScoreVoting.net/AppCW.html

And it’s just vastly simpler and more transparent than any Condorcet method.

Condorcet systems are generally extremely vulnerable to tactical exaggeration, which partially explains why Approval Voting does so much better in Bayesian Regret calculations.
http://ScoreVoting.net/CondBurial.html
http://ScoreVoting.net/DH3.html

4. david Post author

Hi Eric. Unfortunately the thesis is not only in French (which I can muddle through) but is also behind a paywall :-(

I suspect both of the systems described can suffer from this problem though – I think the random one you may always get that you increase a candidate’a chances when you raise your preference for them, but without doing the maths I’m probably completely wrong. It is however a randomized version of something which doesn’t have that problem (I think?), so I am hopeful.

I need to check, but would expect the AV based one to suffer from it in similar cases to where normal AV does.