Answer to puzzle #?? – "Naive-exaggeration-proof" voting systems
(or: is it better to be seen as an "underdog" or a "frontrunner"?)

Puzzle
In plurality voting, it pays to be perceived as one of the two "frontrunners" since it is pointless for strategic voters to waste their vote on any other ("underdog") candidate.

But Clay Shentrup observed that with range (and also approval) voting, it can actually pay for a candidate to be perceived as an underdog – i.e. that increases his winning chances. This, if commonly-true, might have some important implications.

Specifically, with plurality, appearing to be a frontrunner is all-important and takes huge amounts of cash. If we can remove that by switching to some other voting system, cash's importance should diminish.

1. Find an example-election in which, with range voting, the candidates are best off being perceived as underdogs.
2. But find another range-voting election-example in which it is better to be perceived as frontrunner.
3. Consider this "naive-exaggeration" voting strategy (NES): rank the two frontrunners A&B (where you prefer A>B) top & bottom, then rank anybody better than A co-equal top (or if the rules of the voting system forbid that, then just below A) and rank anybody worse than B co-equal bottom (or if that forbidden then just above B) and finally rank anybody between A&B using honest normalized utility.
      Show that with either plain-plurality, instant runoff (IRV), Bucklin, or Condorcet voting systems [in the latter three systems, we assume ballots are strict rank-orderings of the candidates] candidates always want to seem a frontrunner; that is, if all voters employ naive-exaggeration strategy, then in the absence of an exact tie, only perceived-frontrunners can win.
4. Show that with NES range voting in the random elections model with any fixed number C≥3 of candidates, there is positive probability that the election is such that seeming a frontrunner is essential for victory, and positive probability that seeming an underdog is essential for victory. But all in all, show your chances of victory always are greater if you are perceived as a frontrunner – but not by so much that underdogs cannot win – show underdogs will win with probability≥22.9% regardless of the number of candidates≥3. (Find an exact formula for the victory chances of perceived-frontrunners and perceived-underdogs in C-candidate random elections with NES range-voters.)
5. Although the "random election model" is not very realistic, it seems ok for "near C-way tie" elections with C nearly-equal-strength candidates. So the preceding result makes it plausible that money won't reign supreme in range-voting elections, i.e. a low-moneyed candidate regarded by the electorate as objectively comparably or more strong than a "frontrunner" will, in fact, enjoy decent winning chances, with range voting. (Unlike plurality, Condorcet, IRV, or Bucklin, where the perceived underdogs are far more likely to lose.)
6. What if, in the preceding analysis, we replace "range voting" with "approval voting" or some variant thereof?

Call a voting system "naive-exaggeration-proof" if its winners do not change when the labeling of two candidates as "frontrunners" is altered to another two when all (or in another version, just some, the rest being honest) voters use naive-exaggeration strategy only. This is a far weaker notion than Gibbard/Satterthwaite "strategyproof."

Open question: Are there any interesting naive-exaggeration-proof voting systems?

Answers

By Warren D. Smith Oct 2009, also with important contributions by Abd ul-Rahman Lomax, Rob LeGrand & Clay Shentrup. Skip to lesson.

A. Suppose the two frontrunners are "Bush" and "Gore," and the underdog is "Nader."

Result: Nader wins with either honest or naive-exaggeration-strategic range (or approval) voting. If however the two "frontrunners" instead were Nader and Gore, then Gore wins with NES range (or approval) voting. Finally, if the two "frontrunners" instead were Nader and Bush, then again Gore wins with NES range (or approval) voting. So in this example it "pays" for Nader to be perceived as "underdog." And it also pays with NES range voting for Gore to be perceived as underdog; meanwhile Bush doesn't care (he always gets exactly 50% of the naive-exaggeration-strategic vote, no matter who the two "frontrunners" are). So all in all, in this election if it is conducted with NES range voting, an underdog is what you want to seem.

B. In contrast, consider this slightly-different election:

If {Gore, Bush} are the frontrunners, then Gore wins. But if Nader is a frontrunner, he wins. (Bush, again, does not care; he always gets exactly 49% of the naive-exaggeration-strat vote no matter who the two "frontrunners" are.) So it definitely pays in this range-voting election to seem a frontrunner.

C. If all voters use NES, then the strict-rank-order votes will always be of form A>others>B or B>others>A. In that case [assuming there is no exact tie], whoever is the most-popular among the two perceived-frontrunners {A,B} will always win with either IRV (has strict majority; no "runoff rounds" needed), or any Condorcet system, or Bucklin, or plain-plurality voting.

D. We consider range voting under the random elections model. By considering small balls in configuration-space about our two example elections, we see that the probabilities are positive that the election is such that seeming a frontrunner "pays" and that seeming an underdog "pays."

But we shall now show that if a candidate doesn't know anything more about the status of the election than "it is random" then being perceived as a frontrunner improves his election chances (and being seen as an underdog worsens them).

It is convenient to regard the endpoints of the score range as -1 (disapprove) and +1 (approve). With NES range-voting strategy, each frontrunner will get score ±1 with 50% probability from a random voter (but the votes for the two of them will be exactly negated). That is, a frontrunner's vote from a random voter has mean=0 and variance=1. An underdog has probability 1/3 of seeming superior to both frontrunners in the eyes of a random voter (assuming the two candidates anointed by God to be "frontrunners" are randomly chosen from the C; and the superior-seeming underdog than gets +1), probability 1/3 of seeming inferior to both frontrunners (gets -1), and probability 1/3 of seeming in between (gets scaled utility). In other words, each underdog's vote from a random voter has mean=0 and variance=σ²=π^–1/2(4-ln3)/16+2/3≈0.7689749619520989746.

The variance formula arises from these two integrals
∫∫∫_{-∞<x<y<z<+∞} [(2y-x-z)/(z-x)]² P(x) P(y) P(z) dx dy dz = π^-1/2(4-ln3)/32 ≈ 0.051154147642716153988
∫∫∫_{-∞<x<y<z<+∞} P(x) P(y) P(z) dx dy dz = 1/6
where P(x)=(2π)^-1/2exp(-x²/2) is the standard normal density function.

It should be obvious therefore that it is better to seem a frontrunner, because if you have a finite set of normal deviates each with mean=0, the one with the greatest variance seems obviously to be the one with the greatest chance of being the maximum. (And in the limit of an infinite number of independent voters, we do get normal vote-totals thanks to the "central limit theorem.") In fact, in the infinite #voters limit, the exact chance that the most-popular among the two apparent-frontunners will win, assuming there are 2 frontrunners and N≥0 underdogs running, is

where

Then each underdog wins with probability [1-P_N(σ)]/N, and in all the probability that some underdog wins is [1-P_N(σ)].

The integral can sometimes be evaluated in closed form:

With our numerical value σ≈0.8769121746 we have

To repeat: in a 3-candidate NES range voting "random elections model" election, the victory chances for each frontrunner are

whilst the victory chance for the underdog is ≈22.92%, so it pays to be perceived as a frontrunner.

Shentrup reports: "Those numbers look right. A quick run of my simulation program (1000 elections, 3 candidates, 40 voters, 100% tactical voters) yields:

      Frontrunner winner:loser ratio is 2277:3723 for (37.95±0.63)% 
  Non-frontrunner winner:loser ratio is  723:2277 for (24.10±0.78)%"

Note, these error bars are optimistically narrow; to be more conservative about them they should be multiplied by √6 and √3 respectively.

We can use the "saddlepoint method" of asymptotic analysis to determine the asymptotic behavior of P_N(σ) when N→∞. It is a known fact that 1-F(x)∼P(x)/x when x→+∞ (see, e.g. Handbook of Mathematical Functions or derive it via repeated integration by parts). Using this fact one may show that the integrand's peak is located at x_peak∼σ·ln(N²/[2σ⁴π])^1/2. I will not guarantee I did not make a mistake, but it appears that this can be used to show that P_N(σ) ∼ N^-0.78 when N→∞ with our value of σ. This at any rate is numerically approximately correct. This is large enough to give frontrunners chances greater by an unboundedly large factor (factor∼N^0.22 when N→∞) than those of any underdog – but nevertheless small enough so that when N→∞ the probability→100% that an underdog will win! And apparently an underdog victory can be expected at least 22.9% of the time no matter what the value of N≥3.

E. Lesson: This suggests to me that (a) range voting will not fall into "massive 2-party domination," and (b) range voting will be susceptible to the influence of cash, but less so than IRV, Condorcet, Bucklin, and Plurality voting.

F. The fact that, with NES range voting, "frontrunners" tend to have an advantage, can be viewed as a defect of range voting (even though, as we've seen, range voting is better in this respect than Bucklin, IRV. Condorcet, and Plurality). If so, the question is how to fix it. One repair-attempt is to use approval voting. If approval voters employ "bisector" NES strategy – i.e. they approve candidates above the utility midway-point between the two "frontrunners" – then we get the same mean and variance for every candidate vote-total. Unfortunately that fix will not work in the real world because it is strategically better to place your threshold, not midway between the frontrunners, but instead closer to the most-likely-to-win frontrunner. If voters do that then the variances for underdogs are reduced and we are back with the same problem as before.

An attempt to fix that would be to use approval voting with the additional rule that each voter must approve exactly half the candidates. (Assume there are an even number.) However, this "half approval" system suffers various problems:

1. It violates the "favorite-betrayal criterion": Say your preferences are A>B>C>D, and you have good reason to believe that the vote totals so far rank them D>B>C>A (or D>C>B>A). Then your most effective vote is arguably for B and C, "betraying" your favorite A. (Meanwhile, ordinary approval and range voting satisfy the FBC.)
2. It probably will encourage lazy and ignorant voters to "donkey vote" randomly or alphabetically for a lot of the candidates. ("Ballot rotation" can try to diminish the harm from ordering-donkeys.)
3. The "exact half" requirement causes negative correlations between the underdog vote totals. These are similar (albeit less severe) to the way that, due to perfect anticorrelation for the two frontrunners with NES voting, exactly one frontrunner will get over 50% approval. These correlations alter the picture so the frontrunner and underdog chances actually are not the same, thus undermining the entire concept.
       For example, with plain approval voting for three candidates, the underdog, even with exactly 50% coin-tosses used by each voter to decide underdog-approval, still would have worse election chances since the underdog might get below 50% approval, whereas the top frontrunner with NES voters will always exceed 50%. In fact, the underdog's winning chance is exactly 1/4, which note is less than 1/3.
       The negative-correlation effects exactly cancel out only in case of four candidates: then, and only then, we get exactly equal chances (in the random-election model with "half-approval" voting) for "underdog" and "frontrunner" victories.

But a closer examination reveals, in the "perfect" 4-candidate case, that half-approval voting still can "favor frontrunners" in the right elections. (Some elections favor frontrunners, some underdogs, with overall balance.)

(There may be a better repair-attempt, but I'm skeptical anything will really work.)

The open question: I do not know the answer. My initial conjecture is "no."

Return to puzzles

Return to main page