[EM] Borda Done Right (with proof of clone consistency and monotonicity)

[fsimmons at pcc.edu]

A modification I am considering:

If all of the candidates are ranked on a ballot, then on that ballot keep the raw range scores without 
normalization, so the lowest ranked candidate Z will be ranked at p(Z) which may or may not be zero.  
But on ballots with one or more truncations do the normalization to ensure that the truncated candidates 
have a final rating of zero.

Also, the method is not summable because the probability distribution values are computed from the 
whole ballot set.  In the case of the benchmark lottery distribution, the first place votes would need to be 
tallied before the ranked ballots could be converted to range form.  The method could be carried out in 
two separate summable steps .. first the top vote talley, and then, given the results of that talley, each 
precinct could encode the rest of the information in a summable way.

> When someone pointed out to Borda that his method led to 
> strategic order reversals, he replied that he 
> only intended it for honest voters. Unfortunately, that's only 
> half the problem; Borda is highly sensitive to 
> cloning:
> 
> Assume honest votes:
> 
> 80 A>B
> 20 B>A
> 
> Candidate A wins by Borda and any other decent method.
> 
> Now clone B:
> 
> 80 A>B1>B2>B3>B4>B5>B6
> 20 B1>B2>B3>B4>B5>B6>A
> 
> B1 wins with a Borda score of 5*80+6*20=520 compared with A's 
> score of 6*80=480 .
> 
> Range, which awards the winner to the candidate with the highest 
> average rating instead of the highest 
> average ranking, doesn't suffer from this problem, since ratings 
> are not constrained to spread out like 
> rankings.
> 
> In short, Range is the cardinal ratings analog of Borda, without 
> the drastic clone problem. There is still 
> an incentive to exagerate sincere ratings to the extent of 
> collapsing to the extremes, but not to the 
> extent of order reversals. Honest voting with Range would give 
> perfectly satisfactory results, unlike the 
> case with Borda.
> 
> But can we find a "Borda Done Right" method based on Rankings 
> instead of ratings?
> 
> Yes. We just need a natural way of converting rankings to 
> ratings that automatically takes clone sets 
> into account, rating their members near each other.
> 
> One way to do that is (for each candidate X) let p(X) be the 
> percentage of ballots that rank X in first 
> place. If X is replaced with a clone set {X1, X2, ...} then the 
> sum p(X1)+p(X2)+ ... will be the same as p
> (X) was before the replacement. Furthermore, if X is moved up 
> in the rankings relative to Y (but no other 
> relative move) then p(X) will not decrease, and p(Z) will not 
> increase for any other candidate Z.
> 
> These two properties (clone consistency and monotonicity) of the 
> "ballot favorite lottery" p are the only 
> ones needed for the following construction and discussion. So 
> the result will apply for any other lottery 
> distribution p that is both clone consistent and monotone.
> 
> We do the transformation from rankings to ratings in two steps: 
> first a conversion to raw ratings, and 
> then a normalization. Since the normalization will preserve the 
> monotonicity and clone consistency, we 
> will concentrate our attention mostly on the raw ratings.
> 
> But just for the record, to normalize a raw ratings ballot, 
> subtract the lowest rating from each of the other 
> ratings and then divide them all by the highest resulting 
> rating. For example if (on some ballot) the raw 
> ratings for the respective candidates are 1, .8, .5, .3, 
> and .2, first subtract the lowest rating .2 fromo 
> each of the other numbers to get .8, .6, .3, .1, and 0, and 
> then divide by the largest of these, namely .8 
> to get
> 1, .75, .375, .125, and 0. This is the affine transformation 
> that normalizes the ratings to a scale of zero 
> to one.
> 
> The more interesting part is the conversion of rankings to raw 
> range scores by use of the lottery 
> distribution p. For a given ballot b and an arbitrary candidate 
> X, the raw score of X is the sum over all Z 
> ranked (on ballot b) equal to or behind (i.e. lower than) X, of 
> the values p(Z). In other words the raw 
> score of X is 
> p(X)+p(Z1)+p(Z2)+ ... where the sum is over all Z ranked below 
> or equal to X on ballot b.
> 
> The way to visualize this is the candidates (or their names) 
> stacked up on top of each other with the 
> highest ranked candidate at the top of the stack, where the 
> spacing between the candidates Z1 and Z2 
> is given by the value of p(Z1) where Z1 is the higher of the two 
> candidates. The total height of the 
> candidate X in this stack of names is the raw score of X. Since 
> the probabilities add up to unity, the 
> candidates ranked equal top will all have raw scores of unity.
> 
> Now suppose that X is replaced with a clone set {X1, X2, ...}, 
> then in the new "stack" of candidates the 
> clone set will precisely fill up the space p(X)=p(X1)+p(X2)+... 
> that separated X from the candidate ranked 
> immediately below X. This is what we mean when we say that the 
> conversion is clone consistent.
> 
> Now suppose that X moves up in the ranking one place by moving X 
> up relative to the other candidates 
> on some of the ballots. If the distribution p changes, then 
> p(X) is the only value that increases. 
> 
> First let's consider the effect on the ballots where no swap was 
> made: If all of the candidates that lost 
> probability are ranked below X, then the raw score of X stays 
> the same, because whatever is subtracted 
> from the ones under X is added to the space immediately below X. 
> In this subcase some of the other 
> candidates' raw scores decrease, but none increase. 
> 
> On the other hand if some of the candidates above X lose 
> probability, then X may well push some of the 
> other candidates upward in raw score, but only by the same 
> amount that X's raw score increases at 
> most. In either of these subcases, no other candidate's total 
> raw range score (over all such ballots) will 
> increase more than X's range score increases.
> 
> On the ballots where X moves up in the rankings, this change 
> itself can only increase X's raw score, and 
> then from there on the considerations are the same as in the 
> previous case.
> 
> In summary, raising X in the rankings cannot increase any other 
> candidate's total raw score more than 
> the increase of X's total raw score. Therefore the conversion 
> is monotone.
> 
> This conversion followed by the normaliztion described above is 
> the complete setup for "Borda Done 
> Right". The Range winner based on the normalized ratings after 
> both steps of the conversion is the 
> winner according to Borda Done Right.
> 
> I suggest that for the purest form, where complete rankings are 
> required for input, the distribution p 
> should be based on the ballot favorite lottery. On the other 
> hand, when truncations and equal rankings 
> are allowed, I suggest the use of the random approval lottery 
> based on implicit approval.
> 
> I emphasize the seemingly subtle point that the purpose of these 
> lotteries is only to define the values of 
> p, not to introduce any randomness into the outcome of this 
> deterministic method. For example, in the 
> case of the random ballot favorite lottery, p(X) is the number 
> of ballots on which X is ranked first divided 
> by the total number of ballots. No random drawings are 
> necessary to determine this number.
> 
> I would also like to point out that any use of range ballots 
> that is resistant to the "ratings inflation" that 
> makes range strategically equivalent ot approval ... any such 
> use of range ballots can also be applied to 
> these rankings that we have coverted to normalized range ballots.
> 
> Andy's chiastic approval is one such approach. Range based 
> Bucklin fits into the same general 
> scheme. It seems to me that finding other valuable uses of range 
> style ballots is a worthwhile endeavor. 
> DSV methods for conversion of Range ballots into approval 
> ballots fall into the same category of using 
> range ballots as inputs. It is exciting to me that we now know 
> some monotone ways of doing this. Any 
> such method could be adapted to ranked ballots via the 
> conversion specified above.
> 
> And don't forget that PR methods, like RRV, based on range style 
> ballots, can now be done with 
> rankings, thanks to the above conversion process.
> 
> That's about all I have time for right now, but I want to 
> continue this thread in the future.