[EM] Swap Cost

[Forest Simmons]

In an EM list message dated 13 Jan 2022 under the heading "Fixing Kemeny
Young," I proposed a clone free cost function to replace the  Kendall-tau
metric that is responsible for the clone dependence of Kemeny-Young:

http://lists.electorama.com/pipermail/election-methods-electorama.com/2022-January/003348.html

Since then I have been referring to that function as "de-cloned
Kendall-tau," but from now on, I will call it (more descriptively) "Swap
Cost," because it is a measure of the general regret or disappointment
resulting from the replacement of one candidate ranking with another ...
and that cost is the sum of the costs of the transpositions or "swaps" that
it takes to convert the original ranking into its replacement order.

Click on the above link for a detailed description and
rationale/explanation of the desired clone independence.

The examples given hereafter will make the procedural details abundantly
clear.

For now, suffice it to say that in order to convert one ranking into
another we need to know (for each candidate k) the fraction or percentage
f(k) of the ballots that specify k as favorite, as well as the fraction or
percentage f'(k) that specify candidate k to be "anti-favorite," or most
disapproved.

The disappointment cost of a single swap is the product f(k)f'(j) where, of
two adjacent ranked candidates k and j,  candidate k is lowered and j is
raised, so that the order kj is transposed to jk.

So the more k is top choice, the greater the disappointment from k getting
lowered, and the more j is last choice, the more disappointment from j
being raised.

This directional sensitivity is totally absent in Kendall-tau for which
every transposition incurs precisely the same unit cost, no matter which
candidate is being raised or lowered.

This directional cost dependence is like a taxicab fare where the
time/distance from point X to point Y is not in general the same as the
from Y to X.

The classic treatise on this kind of path length asymmetry between "ida y
vuelta" is a monograph entitled, "What is Distance?", by Julij A. Šrejder.

One of the greatest advantages of having a suitable cost function on
rankings is that it allows a standard adaptation of any single winner
Universal Domain method to be used as a basis for finding a finish order:

The key is that just as a ranked ballot shows a preference of one candidate
over another, the Swap Cost reveals support of a ballot for one finish
order over another:

If the swap cost of converting the ballot B ranking to finish order O1 is
less than the cost of converting the B ranking to order O2, then we say
that ballot B supports O1 over O2, or speaking anthropomorphically, "B
prefers O1 over O2."

Once we have a ballot based preference relation on the potential finish
orders, we can use any Universal Domain single winner method to find that
finish order.

For example River. Unlike Ranked Pairs or BeatPath CSSD, River does not
automatically produce a finish order in the course of finding the single
winner.

But once we have a preference relation (given by Swap Cost for example) on
candidate rankings then we can apply the River formalism with the set of
potential finish orders playing the role of the set of alternatives ...
i.e. the potential finish orders become the "candidates," and the Swap Cost
gives the (proximity inferred) ballot preferences among these
candidate-alternatives.

We'll do a detailed example of this tomorrow.

But tonight let's just celebrate our new tool (Swap Cost) for converting
any UD single winner method M (like River) into a finish order method
similar to Kemeny-Young, but clone proof (unlike Kemeny-Young), provided
the base method (like River) is clone-proof ... before Kristofer pops our
bubble!

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