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.)
----
Election-Methods mailing list - see http://electorama.com/em for list info
