[EM] Any anti-cyclic examples for Kemeny order?

[Markus Schulze]

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