[EM] a Borda-Condorcet relation

[Kristofer Munsterhjelm]

Stephen Turner wrote:
> Kathy, yes the Borda winner assigns r points to the (n-r)th
> ranked candidate.  It's a method with important problems.
> 
> Robert: yes, that was the point, a sort of
> Condorcet:Borda::median:mean, if you like.  There is no
> new method or algorithm here.
> 
> Kristofer: yes, it is a very simple observation.  Your comments
> about burial are very interesting, and show how
> we might be able to apply analysis of (one of) Condorcet
> or Borda methods to the other.
> 
> Your way of passing from median to mean, I'm not sure
> I understood completely.  Is it something like this?
> 
> - median
> - mean of central 5%
> - mean of central 10%
> - etc
> 
> where "central 5%" would mean that you discard the 47.5%
> highest and the 47.5% lowest values (with multiplicity
> of course), and when these don't give whole numbers,
> interpolate linearly.  Is this right?

More or less, but since the number of voters are exact, there's little 
need to interpolate.

Say that (for the sake of simplicity) the number of voters is odd, so 
that the median is a single value rather than the mean of two, and that 
you have one array for every candidate pair, containing the rank 
differences/distances as you showed in your previous post. Then, define

f(x, y, 0) to be the median rank difference, your c(x, y).
f(x, y, 1) is the mean of the element just above the median, the median, 
and the element just below median.
f(x, y, k) is the mean of the element just above the upper element used 
in f(x, y, (k-1)), the elements used in f(x, y, (k-1)), and the element 
just below the lower element used in f(x, y, (k-1)).

This assumes that all the elements (rank differences) have been sorted 
so that finding the median is as easy as picking the central element 
(value) in the sorted array.

The method would then work like this, in the absence of true ties:
find the minimal p >= 0 so that there exists a candidate X for which, 
for any and all other candidates Y, f(X, Y, p) > 0.

If there's a Condorcet winner, then X is the CW and p = 0, because when 
p = 0, f is equivalent to your c function. We also know that this method 
can't be any less decisive than Borda, simply because at the maximal 
value of p, the Borda winner will satisfy the stopping rule above.

An actual algorithm would gradually increase p until the stopping rule 
is met. The method concedes just enough in the direction of Borda, 
widens the truncated mean just enough, to get an unambiguous result. 
When dealing with weighted votes, the problem becomes a little more 
complex and that's where one would use a sweep-line algorithm.

Practically speaking, one would also use sums instead of means, so that 
expanding the truncated mean is as simple as adding a few more values.

Also note that I haven't dealt with the case where there are true ties 
(e.g. everybody votes A = B). In the case of a true tie, one wouldn't 
want the method to go all the way to Borda, trying to break a tie that 
shouldn't (and can't) be broken.