Puzzle #??: Information ignored by voting methods, and "true" expressivity

Suppose that at least some positive-constant fraction of the information voters say on their ballots, always is ignored by a voting method (when using those ballots to compute the election-winner). Then we shall say the voting method is "information-ignoring."

Information-ignoring voting methods seem antithetical to democracy since the whole purpose of a voting method is to gather information from voters then use it. Also they can seem "misleading" and "unfair."

E.g. we saw in puzzle 34 that Instant Runoff Voting (IRV) is information-ignoring in the sense that, in a V-voter, C-candidate election, the IRV winner-choosing algorithm can be programmed in such a way that it will never examine more than (H_C-1/2)V of the VC "cells" on the V ballots (ignoring the rest) where H_C=1+1/2+1/3+...+1/C≈ln(C). Dramatically, when C→∞ this is asymptotically 0% of the cells. In other words, IRV in this limit ignores asymptotically 100% of the information the voters supply! An IRV voter can express the opinion Bush>Gore on her ballot, but IRV ignores that, while paying attention to Gore>Bush on somebody else's ballot. IRV deceives voters into thinking their rank-orderings matter, but in fact, most of the time the IRV process ignores almost all of the order.

This also is deceptive in this sense. With IRV, a voter can input any of C! possible rank-orderings for C candidates, which is about Clog₂C bits of apparent information on her ballots. This seems on the face of it superior expressivity to approval voting, which allows only 2^C possible ballot-types, i.e. only C bits of information. However, really, the average number of bits of information actually examined by the IRV process is ≤(H_C-1/2)log₂C, which is far smaller than approval voting.

1. For the "majority judgment" (MJ) median-score-based voting method (and others like it): show that the median of N real scores can be computed by a randomized algorithm that uses 1.5N+o(N) pairwise >/< comparisons in expectation, and by a deterministic algorithm that uses 2.942N+o(N) in the worst case. Indeed, this number of comparisons suffices not only to determine the median, but also to count the number of scores greater than, less than, and equal to it. In other words, this kind of voting method can compute the final scores for every candidate by examining only 1.501 "bits" of information on average from each score on each ballot (in the limit N→∞ of a large number of permitted score-levels). After computing the candidates' median scores, MJ then "breaks ties." Show this tie-breaking step can be done without extracting any further information from the ballots.
2. Can MJ be viewed as, like IRV, "ignoring asymptotically 100% of the information voters supply"?
3. Show that Approval, standard (highest-average wins) Range voting, Borda count, Condorcet, and plain Plurality all are not information-ignoring.
4. Compute (to decent accuracy) the "true expressivity" (in non-ignored bits per ballot) of all those voting methods, for a C-candidate election.
5. Is there any reason it might be good for a voting method to ignore information solicited from voters?

Answer

A. A simplified version of the Floyd-Rivest median-finding algorithm works as follows. [R.W.Floyd & R.L.Rivest: The algorithm SELECT for finding the ith smallest of n elements (Algorithm 489) Communications of the ACM 18 (1975) 173; corrected analysis by Krzysztof C. Kiwiel: On Floyd and Rivest's SELECT algorithm, Theoretical Computer Science 347,1-2 (Nov. 2005) 214-238]. First, extract a random subset of the N scores, with cardinality S=min{N^2/3(lnN)^1/3, N-1}. Sort the subsample using a sorting algorithm that uses O(SlogS) comparisons. With high probability, the median of the full N-score set will lie within the score-interval delineated by the middle (SlogS)^1/2 elements in that sorted order. Count the number of scores greater than, less than, equal to the high-endpoint, and equal to the low-endpoint, and within this interval. From now on we shall only consider the simplest case when all scores are distinct. In that case we need only three, not five, kinds of counts. (The same results hold when tons of equal-scores are allowed, but the description gets messier. Another way to handle them is to add an artificial infinitesimal pre-perturbation to all scores to cause "distinctness.") This can be done using ≤1.5N score-pair comparisons in expectation. If the "> and <" counts each are below N/2 then the median indeed lies within the interval at a position deducible from the counts. (Otherwise, the most simple approach is to declare failure and re-run the whole algorithm with new randomness; a better approach recurses on the correct sub-array.)

Indeed, with a bit more care this may be shown to perform 1.5N+o(N) comparisons not only in expectation, but also with high probability; also W.Cunto & I.Munro [Average case selection, Journal of the ACM 36,2 (1989) 270-279] showed that 1.5 is least possible for any randomied median-finding algorithm.

The worst-case comparison count required to determine the median of N numbers (using a deterministic algorithm) is a still-open problem in computer science. Better and better upper and lower bounds have been produced by a succession of analysts using more and more complicated arguments. It is not tremendously hard to see at least N-1 comparisons, indeed at least 1.5N-2, are needed and 13N+O(1) suffice [Blum, Floyd, Pratt, Rivest, Tarjan: Time bounds for selection, JCSS 7 (1973) 448-461]. The latest and greatest bounds, due to Dorit Dor and Uri Zwick [Median Selection Requires (2+ε)N Comparisons, SIAM J. Discrete Maths. 14 (2001) 312-325; Selecting the Median, SIAM J. Computing 28 (1999) 1722-1758] using extremely compicated arguments, show that at least 2.000000000000000000000001N±o(N) comparisons can be required (otherwise algorithm can be forced by an input-choosing adversary to get the wrong answer in some cases) and 2.942N+o(N) suffice.

MJ's "tie breaking" step can be done using only the counts of scores greater than, equal to, and less than the median, and those counts are produced by the above median-finding algorithms (or at least, by Floyd-Rivest's) as a free side-effect.

B. Yes. In the limit L→∞ of a large number of allowed score-levels, the MJ voting method will ignore asymptotically 100% of the bits of information in the scores voters supply. (Each comparison that returns either "A<B" or "not" extracts a single bit of information so the comparison count bounds the extracted bit-count.) However, Balinski & Laraki (the main proponents of the MJ voting method) recommend having exactly L=6 allowed score levels not L→∞. In that case, only about half the information is ignored.

C. The candidates' total scores (whether approval, Borda, or range voting) depend on every score (and every bit thereof) so examining them all is inescapable if you want to assure getting the right values. If you only care about the election-winner, not all total scores, then we can set up a situation where, after the algorithm has examined all ballots but one, the final ballot breaks a C-way tie. Or, after examining all ballots except for just one entry (with the correct ballot formats...), that one creates or breaks a tie. Hence an algorithm cannot assure correctness unless it examines everything. (The same is essentially true for Condorcet methods – almost all the info needs to be examined – but we omit the trickier details.)

D. The "true expressivities" (in non-ignored bits per ballot) of various voting methods (C-candidate elections, L score levels) are as follows (valid to within constant multiplicative factors and also asymptotically exact in L→∞ and C→∞ limits with L>C; we have ranked the voting methods in order from most to least truly-expressive in those limits):

If L=3 score levels are used, then MJ's apparent expressivity is C·log₃3≈1.58C bits per ballot, which then is closest to the true (asymptotic) expressivity 1.5C. That perhaps is some sort of argument that it is somehow "best" to use Majority Judgment with 3 score levels – you'll be "misleading" voters the "least."

E. It has been argued by N.Tideman that IRV's ignoring of information is good in the sense it can discourage "strategic voting." Similarly M.Balinski & R.Laraki have argued this for MJ. They both are correct to at least some degree about that, although it is far from obvious whether the benefits are worth the sacrifice.

Return to puzzles

Return to main page