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

[fsimmons at pcc.edu]

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.