[EM] Need IRV examples; voting show

[Forest Simmons]

Somewhere up this thread Blake Cretney brought up the idea that some
Condorcet methods may satisfy a certain modified consistency criterion.

If the method gives a complete ranking as output, and if two subsets of
ballots produce the same ranking, then the output based on the union of
the two subsets should agree with the two partial results.

The Kemeny Order is a Condorcet ranking that satisfies this modified
consistency criterion.

To see this, consider that in any metric space if H and K are finite sets
of points and p is a point that minimizes the sum of distances from point
x to points of H, as well as from x to points of K, then p minimizes the
the sum of distances from x to the union of H and K.

The Kemeny order is obtained by precisely this kind of minimization
process.

[The "points" are the permutations of candidates, and the "distances" are
the required number of elementary swaps to go from one permutation to
another.]

Note that if the permutation is not a "beat path" then there is some pair
of adjacent candidates in the permutation that would be preferred to be
reversed by a majority of the voters. Performing that swap would decrease
the distance by one each to that majority and increase the distance by one
each to the minority that preferred it to remain unswapped.

Therefore the total distance (hence average distance) is decreased by
performing the swap.

Therefore if the permutation is not a beat path, then it is not the Kemeny
order.  In other words, being a beat path is a necessary (though not
sufficient) requirement for a permutation of candidates to be the Kemeny
order.

Therefore, the Kemeny order always picks a member of the Smith set as
"winner."

In summary, the Kemeny order is an example of a Condorcet order that is
order consistent with subsets that unanimously agree on the order, which
is what Blake was looking for, if I remember correctly.

Forest

----
For more information about this list (subscribe, unsubscribe, FAQ, etc), 
please see http://www.eskimo.com/~robla/em