[EM] Any anti-cyclic examples for Kemeny order?
Markus Schulze
markus.schulze at alumni.tu-berlin.de
Thu Oct 7 05:12:01 PDT 2004
Dear Mike Rouse,
you wrote (6 Oct 2004):
> I was just wondering if there were examples of three-way circular ties
> in that "unwind" the wrong way in the Kemeny order. For example, if the
> cycle is A>B>C>A, it would put the order as A>C>B. (There is probably
> a relatively trivial example somewhere on the net if there is, I just
> don't remember seeing it).
Suppose N is the number of candidates.
Suppose d[X,Y] is the number of voters who strictly prefer candidate X
to candidate Y.
Suppose K(1),...,K(N) is the Kemeny ranking of the candidates.
Then d[K(i),K(i+1)] >= d[K(i+1),K(i)] for all i = 1,...,(N-1).
Otherwise, suppose that there is a j with d[K(j),K(j+1)] < d[K(j+1),K(j)].
Then you can find a ranking with a better Kemeny score simply by switching
K(j) and K(j+1).
Therefore, it is not possible to find an example where the Kemeny-Young
method "unwinds" a cycle in its opposite direction. (The same is true
for Tideman's ranked pairs method.)
Markus Schulze
More information about the Election-Methods
mailing list