On Balinski & Laraki's "majority judgment" median-based range-like voting scheme

Michel Balinski and Rida Laraki, in 2006, proposed a voting method quite similar to range voting, but using median scores rather than average scores, and with an interesting tie-breaking method. They wrote a paper (pdf) about it. An updated version of this paper has now appeared in the Proceedings of the National Academy of Sciences (USA).

The Balinski-Laraki voting method:

1. Voters supply, as their vote, numerical scores for each candidate from a fixed set of scores. (Balinski & Laraki suggested the 6-point scale {1,2,3,4,5,6} with 6=best and 1=worst.)
2. The candidate with the greatest median score wins. (If a candidate has an even number of scores, his lower bi-median is used as his "median" score.)
3. If there is a tie, then we break it by considering the "median scores of rank 1." That is, suppose the median score for each of the tied-set of candidates, is M. Remove one M from each of the tied-candidates' multisets of scores, and recompute their medians. These are "the medians of rank 1." The tied-candidate with the greatest M₁ wins.
4. If there still is a tie, we continue on, computing the "medians of rank 2" which are got by removing one median value from each still-tied-candidate's score-multiset and then recomputing the median; we similarly may define medians of rank 3, 4, etc. We keep going until the tie is broken and we have a unique winner.

B&L give an example.

Who invented this?

The idea of median-based range voting ("highest median rating") had also been considered and discussed by several members of the electorama and range voting bulletin boards during the years 1996-2007. (Even something very similar, if not exactly equivalent, to B&L's tie-breaking scheme had been proposed, although I have not been able to track that particular post down, so it may have just been in emails.)

How does this compare versus ordinary average-based range voting?

Here's a disturbing example created by Rob Lanphier in 1998. In this 99-voter election with 0-100 score range, B wins under the Balinski-Laraki voting method because B's median is 51 versus A's 50:

98 out of 99 voters strongly prefer A over B, but the single voter who slightly prefers B over A is the one that matters – B wins! Most people think that is not a good result; Lanphier considered it so disturbing that (he said at the time) median-ratings should be immediately dismissed from consideration as a voting system. In contrast, with ordinary average-based range voting A would win comfortably (A's average=74.25, B's average=26.25).

Prof. S.J. Brams indeed points out that every voter except one can strongly prefer every rival candidate over B, but median-based range voting still will elect B (Lanphier's example above, but simplified so that only A and B are in the race, shows that; and you can make example elections demonstrating Brams's claim for any number of voters and also any number of extra candidates by adding further A-like candidates).

Think Lanphier's example is contrived and artificial and wouldn't be a problem in the real world? Wrong! I contend the following (while oversimplified) is actually a fairly realistic picture of what honest voting would have been in the USA 2000 presidential election – or at least, of a of a realistic hypothetical election like it:

With these votes, Nader would be the winner with median score 30. But practically every other voting system mankind ever dreamed up would elect Gore. Note that 97% of these voters strongly favor Gore over Nader; 52% favor Gore over Bush; and the average scores are Gore=54.4, Bush=48, Nader=17.7. So Median-based range not only fails to elect the clearly-right winner Gore here, it in fact elects the worst candidate.

To be clear: We are not trying to argue that Gore was actually best, nor Nader actually worst, in the actual USA 2000 election. We are simply trying to present an artificial but realistic scenario somewhat motivated by that election, in which "Gore" is best and "Nader" worst, and in which median-range misbehaves while almost every other voting system works well.

A related problem is Lomax's pizza-flavor choosing vote (0-9 score range), in which 3 friends want to buy a pizza, and one of them is a Jew who cannot eat pepperoni. All like mushroom, but the two non-Jews slightly prefer pepperoni:

Another problem with median-based versus average-based range voting, is that the former is not "consistent with respect to partitioning into districts." For example (now with score-range 0-9):

In contrast, with average-based range voting, if A wins in both districts, then A always wins in the combined country.

Average-based range voting also has the advantage of being much simpler to describe than Balinski & Laraki's voting scheme, and it works on every voting machine in the USA, right now, with no reprogramming or modification required. (Median-based range voting can't say that.)

Dan Bishop pointed out another problem with the median-based system: election results can change if "all zero ballots" are added. As a simple example, consider this 3-voter election (0-9 score range):

If an "all zero ballot" A=0, B=0 is added, then, according to Balinski & Laraki's rules, B is now the winner. In contrast, with average-based range voting provided all voters score all candidates, adding an all-zero ballot never changes results. (This property would enable an interesting new kind of election fraud...)

Average-based range voting also outperforms median-based in graphical comparisons, in computer measurements of Bayesian regret, and in the eyes of the world's most experienced(?) election-practitioners, honeybees. Also, range voting has been used for decades by academic graders, whom I do not think would be willing to switch to medians.

Average-based range voting generalizes to a multiwinner proportional representation voting system called reweighted range voting. (See papers 78 and 91 here.) But there currently is no known way to generalize median-based range voting to do that.

Average-based range voting is readily adapted to the case where voters have different "weights," e.g. type-A voters have 54+π votes whereas type-B voters have only 1 vote each. (Simply multiply the type-A votes by 54+π...) With median-based range voting it is a good deal harder to handle that.

An extremely bothering problem with median-based range voting is its failure of "participation." Consider this situation:

Now suppose you and your spouse (new voters) come. Your votes are both: A=9, B=7, C=0, preferring the current winner A over every opponent. These votes cause A to lose, because the new election is now

In short, you and your spouse's decision to vote honestly, made the election result worse from your point of view. You would have been better off not voting at all ("no-show paradox"). In contrast, with average-based range voting, no-show paradoxes can never occur provided there are no blank (no opinion) votes. They can occur if blanks are allowed and are discarded before averaging. E.g. A scores: 9 0 and four blanks, avg = 4.5; B scores: 5 5 5 5 5 5, avg = 5; B wins; but you now add your vote A=8, B=9. That raises A's average to 17/3=5.667 and B's to 39/7=5.571 so now A wins; this example is valid if there is no quorum rule.

Balinski & Laraki pointed out the following enjoyable property of median-ratings (which had earlier been stated, albeit somewhat more clumsily worded, by electorama posters including Bart Ingles in 1999):

Theorem (Bart Ingles, then M.Balinski & R.Laraki): With median-rating, the winner W has the property that a majority of voters unanimously rates him ≥M, while no majority unanimously rates any opponent ≥M.

In contrast, average-based range voting does not enjoy that property, and indeed both average- and median-based range voting fail the traditional definition of the "Condorcet property." But both average-based and median-based range voting obey a nontraditional definition of that property and both, under reasonable assumptions about the behavior of strategic voters, will elect a Condorcet winner whenever one exists.

However, Ingles' theorem is not as nice as it sounds. Here's an example (0-9 score range, three candidates):

As assured by the theorem, a majority of voters unanimously agree that A≥4, whereas no voter-majority unanimously agrees that B≥4 (or that C≥4). Sounds great at first, but... it is also true that a voter-majority unanimously agrees that A≤6, whereas no voter-majority unanimously agrees that B≤6 (or that C≤6). So by the same logic Balinski & Laraki used to conclude A was the best, we can conclude A is the worst! So it seems as though Balinski & Laraki's logic is self-contradictory. (About reversal failure; average-based range never suffers that.) Personally, in this situation I would prefer to elect C, not A, but that is just my opinion.

Finally, Balinski & Laraki's median-based scheme is more complicated than mean-based range voting.

Shared advantages of median- and average-based range voting

• In both systems voters provide quantitative scores for all candidates, "maximizing voter-expressivity."
• Both systems enjoy "anonymity" (all voters treated equally), "neutrality" (all candidates treated equally), "unanimity" (unanimous winners always win), and "independence from irrelevant alternatives" (the ratings for candidate C do not affect the relative judgments of A versus B).
• Both systems reduce to the same system – approval voting – if the allowed scores are restricted to the two-element set {0,1}, i.e. each voter "approves" or "disapproves" each candidate.
• Both systems are "monotonic," i.e. a voter by increasing her score for X cannot decrease X's winning chances.
• Both systems enjoy immunity to candidate cloning.
• Both have the enjoyable property that betraying your favorite does not pay.
• Both easily allow having no opinion votes.
• And both systems to some extent evade the Arrow and Gibbard-Satterthwaite impossibility theorems (as was remarked by Warren D. Smith in his 1999 paper on range voting).

Conclusion so far

Balinski & Laraki's proposal has a lot in common with ordinary mean-based range voting, but relatively speaking suffers numerous disadvantages. I cannot currently see how it can have enough relative advantages to compensate for that.

Hence I recommend ordinary range voting.

What about "Strategy"?

The 6 Feb. 2009 "Numbers Guy" column in the Wall Street Journal ("And the Oscar Goes to...Not Its Voting System") contained

Balinski & Laraki's PNAS-USA paper contains a lot of theorems aimed at justifying or formalizing the notion that median-based range voting is somehow "optimal" in the sense that it is "least vulnerable to manipulation by strategic voters."

We shall now re-examine that. I personally think that Balinski & Laraki's "optimality" and "vulnerability to strategy" definitions were contrived – with other (but reasonable) definitions, their theorems would fail. Furthermore, even to the extent they are correct, their results may have little impact in the real world – because, e.g. even if a voting method often offers only half the incentive to strategize, then so what – maybe exactly the same voters will strategize anyhow! (B&L offered no evidence to the contrary and indeed the evidence they found in the France 2007 election seems to support my view.)

However, B&L's work is not completely valueless. As our examination will show, there are circumstances under which median-based range voting should outperform mean-based range; and we shall develop understanding of just what circumstances favor median and which favor mean.

Note also that there is a family of voting systems intermediate between mean- and median-based range voting: trimmed mean range voting.

Balinski & Laraki's point seems to be that for a substantial class of voters, there is zero incentive in median-based range voting to score somebody dishonestly. I'm not sure, though, that this really matters.

Let's examine the situation. Suppose the median score for Gore is 6 and for Bush is 5 and the score-range is 0-to-9.

• If your honest scores are Bush=4, Gore=8, you have zero incentive to strategize in the sense that Bush and Gore will get the same median score even if you vote Bush=0, Gore=9.
• Similarly if your honest scores are Bush=8, Gore=3, again you have zero incentive to strategize.
• But if your honest scores are Bush=7, Gore=8, you do have incentive to strategize by voting Bush=0, Gore=9 since this will move the medians in the relative directions you want.
• Similarly if your honest scores are Bush=3, Gore=4, you do have incentive to strategize by voting Bush=0, Gore=9.

Considering the cases, in a tight 2-way race with median-based range voting about 50% of the voters have zero incentive to strategize and 50% have incentive.

B&L seem to think that therefore, there will be lots of honest voting. However a different way to look at it is: no voter in this Bush-Gore scenario is hurt by strategizing, but 50% of them are hurt by not strategizing. Therefore everybody will strategize, i.e. vote dishonestly – exactly the opposite of B&L's goal!

Oops.

When we actually look at real-world data from humans using average-based and median-based range voting, what do we find? In all the cases I am aware of so far, the voting seems similar and the election outcomes seem similar. For example, in B&L's own data set of 1752 voters from France 2007 there clearly was strategic voting going on since by far the most popular score was "zero" – which also is exactly what happened in every range voting study I am aware of, including our own, see e.g.
http://www.rangevoting.org/Beaumont.html,
http://www.rangevoting.org/RangePolls.html,
http://www.rangevoting.org/PsEl04.html.

On the other hand, there also was a lot of honesty going on since intermediate scores were very popular. Which also is exactly what happened in every range voting study I am aware of, including our own. The same finish-order 1.Bayrou, 2.Royal, 3.Sarkozy, happened with both median-based and average-based range voting.

So, while I admit this has not been a maximally-careful examination of the data, I fail to see any noticeable difference in voter behavior with median- versus mean-based range voting. Also in a considerable majority of cases it seems both procedures elect the same winner.

In all my Bayesian Regret studies so far (early 2009), mean-based range voting outperformed median-based with any strategic+honest voter mix. However, all those studies involved voters who "flipped a probability=p coin" to decide whether to be honest or strategic. In other words, their decision to be strategic was unrelated to their politics. I could have, but did not, try to have voters whose p-values were correlated with their politics. For that kind of voter, it seems possible that you might be able to get better (i.e. smaller) Bayesian Regret for median-based than for mean-based range voting. Median should also enjoy relative advantages in situations where the honest voter-opinions are sharply peaked.

Median-Favoring Example. Suppose the honest scores for each candidate are sharply peaked distributions, e.g. almost all Gore scores are near 61, almost all Bush scores are near 55, etc, on an 0-99 scale. (Say, to be concrete, almost all honest Gore scores are within 61±2 and Bush scores within 55±2.) Further, suppose a goodly chunk of the voters (e.g. 25%) decide to try to throw the election by strategically exaggerating their opinions of Bush and Gore to 99 and 0 respectively. Note we are supposing all this exaggerating is entirely one way favoring Bush.

I suspect both these suppositions are unrealistic. However, one could imagine them. Median-based range voting then would still give Bush about 56 and Gore about 60, i.e. would be almost entirely immune to this strategic conspiracy, but mean-based range voting would succumb to it and elect Bush.

But if these 25% of "99-0" voters were not "dishonest" but in fact were expressing their honest opinions (for example, say the 25% are Jews and Gore has a plan to kill all Jews, so the honest scores really do form a 2-peaked distribution), then median-based range voting would here be making a big mistake!

More generally, whenever there is a 2-peaked score-distribution for some candidate, median is going to pay almost no attention to the sizes of the two peaks and hence will output a pretty crazy judgment.

Figure-skating judging is an environment where these advantages-for-median (or for "trimmed mean" range voting) seem present. But it does not look to me like large political elections enjoy these median-favoring features (at least, not usually).

Summary: Conditions favoring Median versus Mean-based range voting

Our range-voting exit poll study of the 2004 USA presidential election sought but found no evidence Kerry and Bush supporters differed in how strategic they were. I suspect these median-favoring conditions hold substantially better for skating-judging than for large political elections. However, it would be better if this "suspicion" and limited evidence could be replaced by a much greater amount of more-solid evidence.