[EM] Fixing Kemeny-Young

[Forest Simmons]

I've always admired the basic idea of Kemeny-Young, namely a cost metric
for conversion of one ranking into another ... simply the number of
transpositions (elementary swaps) required.

The deal-breaker draw-back of the Kemeny cost metric is that it is clone
dependent ... if it were independent of clones the " cost" of transposing
AB to BA would be the same as the net cost of transposing the rank order of
respective clones of A and B:

the order a1a2a3b1b2b3
 to the order b3b2b1a3a2a1

Long ago the basic de-cloning idea came to me, but only recently has it
begun to take shape in a truly satisfactory form.

The basic idea was to make use of a clone independent probability
distribution on the candidates (i.e.  "candidate lottery") to weight the
transpositions.

In this context clone independence means that when A is replaced by the
clone set {a1, a2, a3} the probability of A is distributed among the clones
of A:

P(A)= P(a1)+P(a2)+P(a3) .

So if the cost of transposing AB to BA is P(A)P(B), the algebraic expansion
of

(a1+a2+a3)*(b1+b2+b3)

to a sum of products of the form

Sum(a(j)*b(k))

distributes the cost among the clones as desired.

The next question is which distribution among the many possibilities would
be most appropriate.

The first one that comes to mind is the benchmark lottery ... "random
favorite", which is indeed clone free, but among other drawbacks it puts
too much stock in first place preferences.

A more subtle problem is that, when you think about it long enough, you
start to realize that the natural cost of switching AB to BA is not
necessarily the same as switching back.

Think of the context ... we have thousands if not millions of proposals
(nominations) of possible finish orders to evaluate.

To do so we use our metric to see the total cost of converting all of the
ballot orders to each of the nominated orders, in turn. The nominated order
incurring the least total order conversion cost over all ballots is the
winning order.

Now suppose you and like minded voters highly approve of A, but despise B
with a passion, and that the proposed winning order puts B ahead of A.

How appropriately would P(B)P(A) reflect your anguish at the prospect of A
being demoted from your ballot preference order to the proposed finish
order putting B ahead of A.

If P(B) were zero, the product would be zero ... would that reflect your
disappointment ... a cost of zero?

No way!

So what we need are two distinct distributions ... one for the ascending
member and one for the descending member of the pair.

The ascending cost should reflect disapproval ... mental anguish at
contemplation the rise of a bad guy, while the descending cost should
reflect candidate approval ... the pain of seeing your favorite being moved
downward is proportional to how beloved the candidate is.

So let f and g, respectively, be random Top and random Bottom
probabilities. Then the cost of going from a ballot preference of A>B to a
social preference of B>A should be the product f(A)*g(B).

This is not yet the last word on the most appropriate distrbutions, but
with this much of a hint, any EM List reader that has survived this far
should be able to flesh out the rest of the story!

Enjoy,

-Forest
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220113/206e57b1/attachment.html>