[EM] Local Kemenization

[Forest Simmons]

A paper that has been referred to from time to time on this EM list (I'll
try to find the reference later) suggests ordering the candidates
according to your favorite method (perhaps Approval) and then "Locally
Kemenizing" the result to bring it closer to the Kemeny order (which is NP
hard to compute).

The local kemenization procedure suggested is to bubble sort the
preliminary order, so that the final order will be locally kemeny optimal,
i.e. no candidate beats the candidate immediately above it pairwise.

The question arises, why not sink sort?

For example, suppose that A beats B beats C beats A, and the preliminary
order (obtained by Approval or Borda, say) is CBA.

If we bubble sort, we start at the top switching C and B to get BCA, which
is locally kemeny optimal.

If we sink sort, we start at the bottom switching B and A to get CAB,
which is also locally kemeny optimal.

Is there some neutral rule for getting a locally kemeny optimal order from
a given preliminary order?

How about switching the members of the pair that has the greatest claim on
being out of order?

Continue until the list is locally kemeny optimal.

There can be no cycling in this procedure since once two candidates are
switched they can never be switched back.

Next week I'll give some further applications of this idea.

Forest