[EM] a Borda-Condorcet relation

[Kristofer Munsterhjelm]

Stephen Turner wrote:
> Dear EM fans!
>       I was wondering if anyone can think of a source
> for the following simple observation, as it might make
> a nice little paper.  It amounts to seeing how the Borda
> count can be made Condorcet-compliant by
> replacing the mean by the median as detailed below.
> 
> All ballots are total rankings of n candidates, and
> X, Y are two distinct candidates.  For any ballot,
> write s(X,Y) for (rank of Y) - (rank of X) which of
> course is the difference of their Borda scores.
> 
> The s(X,Y) are all non-zero integers, at most
> n-1 in absolute value.
> 
> We will suppose that there are no pairwise (i.e.
> Condorcet) ties.
> 
> Given an election profile, write b(X,Y) for the mean
> of all the s(X,Y), and write c(X,Y) for the
> median of the same data set.
> 
> Now b(X,Y)>0 iff X beats Y in the Borda count,
> and b(X,Y)>0 for all Y iff X is the Borda winner.
> 
> Also c(X,Y)>0 iff X beats Y pairwise, and
> c(X,Y)>0 for all Y iff X is the Condorcet winner.
> 
> What makes all this true is the fact that the mean of
> the differences (of the Borda scores for X and Y) equals
> the difference of their means; c(X,Y) is the median of the
> differences, which is not the same as the difference
> of the medians.

I don't know the source, but after thinking a little, the observation 
for c seems simple indeed. Consider the case that A beats B. then the 
list of numbers for which c(A, B) is the median will have more voters 
where A is ranked ahead of B than vice versa, i.e. more positive values 
than negative. Because the median is the middle value, it will thus fall 
on a positive value, as observed.

If B beats A, the same reasoning can be used in reverse. More voters 
will rank B ahead of A than vice versa, so more values will be negative 
than positive, and so the median, too, will be negative.

If there is a tie and equally many rank A ahead of B as B ahead of A, 
then the median will be the mean of two values since the number of 
voters is even, and will be positive if the people who ranked A ahead of 
B put B lower than those who ranked B ahead of A put A lower. This 
assumes that voters who truncate or rank equal are not included, 
otherwise the median could easily be zero.

> If there is no Condorcet winner, then you
> could resort to one of the established methods
> to break the tie (RP, Schulze, minimax, ...)
> 
> If there can be pairwise ties then c(X,Y)>0
> only implies that Y does not beat X pairwise.  There is a
> range 1<=c(X,Y)<=(n/2) - 1 in which either X beats
> Y or they tie - both are possible.  
> 
> As calculating the median is relatively expensive, the
> above probably is not useful as an algorithm.

It's less summable than the ordinary way of doing it. If you have k 
candidates, then there is a maximum of k ranks, so you need 2k bins for 
each c(x,y) value in order to calculate the median. Since there are k^2 
candidate combinations, the total data structure that needs to be passed 
around is on the order of k^3.

It's also easier, I think, to determine the Condorcet winner from an 
ordinary Condorcet matrix, at least in absence of ties. You start by a 
list of all candidates. Repeatedly compare the first and second entry of 
the list and throw away the pairwise loser. When you have only one 
candidate left, check if anyone beats him; if not, he's the CW, 
otherwise there is a cycle.

> Any thoughts?

I thought that perhaps one could apply pairwise methods to the b array 
instead of the c array and get Borda equivalents of Condorcet methods, 
perhaps cloneproofing Borda, for instance. However, such an application 
could not use wv or margins, because the "CW" in that case would be the 
Borda winner, and since there's always a Borda winner, the method would 
never elect anyone but the Borda winner itself.

I also think there's another observation hidden here: that Borda is much 
more susceptible to burial than Condorcet methods. The intuitive 
comparison would be to the median as a robust estimator and the mean as 
one that is easily affected by outliers. That, in turn, suggests that 
Warren's "burial catastrophe" he observed with Borda while working for 
NEC can't straightforwardly be applied to Condorcet methods, because 
while Condorcet methods are affected by burial, they're not affected to 
the extent Borda is.

One could also make a "gradual Black" method by starting with the 
median. If some candidate A has c(A, x) > 0 for all other x, he wins. 
Otherwise increase the width of the median to make a truncated mean, 
then check again. Call the slightly truncated mean version, ct(x,y). If 
someone now has ct(A, x) > 0 for all other x, he wins, otherwise 
increase the width further, and so on. Since there's always a Borda 
winner, the algorithm will terminate; if not earlier, then at the point 
where the truncated mean is no longer truncated at all. This is like the 
suggestion for Median Ratings tiebreaks at 
http://wiki.electorama.com/wiki/Median_Ratings , only applied to c(x,y) 
instead of candidate ratings. In implementing Median Ratings for my 
simulator, I found a sweep-line algorithm for doing this kind of 
tiebreak, and I imagine it could be used to implement the gradual Black 
method, too, if slowly.
(Or one could take the intersection of the top set of c(x,y), and 
ct(x,y), and ct(x,y) widened further, etc, until only one candidate 
remains. It would be a dog, though, complexity wise.)