[EM] Swap Cost

[Forest Simmons]

Here's an example of how to use River to get a finish order by making the
potential finish order play the role of candidates:

Let's use the following ballot profile:

4 A>B>C
3 B>C>A
2 C>A>B
1 C>B>A

The respective facteion favorite percentages are 40, 30, 30, while the
respective anti-fovorite percentages are 40, 20, 40.

The Swap Costs for converting the ballot order A>B>C into the respective
potential finish orders
ABC, BAC, ACB, BCA, CAB, & CBA, are ...
0, 8, 12, 24, 28,& 36, so this order of increasing swap cost is the rank
order of the potential finish orders induced by the ballot A>B>C.

For example, the swap cost of converting ABC to CBA is the sum of the costs
of transposing AB, AC, & BC, the cheapest sequence of swaps for converting
ABC into its opposite order CBA. The sum of these elementary swap costs is
given by ...
[A\][B/]+[A\][C/]+[B\][C/]
= (4×2+4×4+3×4)/100, or 36%.

Similarly the costs for converting the ballot order B>C>A to the finish
orders (..
BCA,BAC,CBA,CAB,ABC,&ACB, are ...
0, 12,12,24,24,&36.

Costs of converting CAB to ...
CAB, CBA,ACB, BCA,ABC,&BAC are
0, 8, 12, 14, 18,&26

Cost of converting C>B>A to ...
CBA,BCA,CAB,BAC,ACB,ABC ...
0, 6,12, 18, 24, 30
Let's check CBA to ABC cost:
[C\][B/]+[C\][A/]+[B\][A/]
3×2+3×4+3×4 = 30

Preferenc summary for finish orders ..

40 ABC>BAC>ACB>BCA>CAB>CBA
30 BCA>BAC=CBA>CAB=AB6C>ACB
20 CAB>CBA>ACB>BCA>ABC>BAC
10 CBA>BCA>CAB>BAC>ACB>ABC

Pairwise scores ...
BAC>ACB 80 to 20
BCA>CBA 70 to 30
ABC>ACB 70 to 30
BAC>CAB 70 to 30
ACB>CAB 60 to 40
ACB>BCA 60 to 40
CAB>CBA 60 to 40
BCA>BAC 60 to 40*
BCA>ABC 60 to 40
CBA>ACB 60 to 40
ABC>BAC 60 to 40
ACB>BCA 60 to 40
CBA>ABC 60 to 40
BAC>CBA 40 to 30
ABC>CAB 40 to 30

The River procedure applied to the above defeat strengths yields BCA as the
winning alternative ... in fact, BCA is unbeaten pairwise, and tied only by
ACB, the first candidate to be disqualified by River ... the strongest
defeat being ACB's defeat by BAC, defeat strength 80 to 20.

So BAC is the clear winner among potential finish orders.

How about standard River? Both A>B and C>A are equally strong and
compatible with the strongest defeat B>C. So there  seems to be some
ambiguity about which defeat to lock in next. If A>B is locked in next,
then A>B>C would be the finish order. If C>A, is locked un next, then B>C>A
would be the finish order.

But we have just seen how applying Rver to the potential finish orders as
candidates in their own rights (made possible by Swap Cost) totally
resolves this ambiguity: BCA is unbeaten pairwise among potential finish
orders.

How about the standard (clone dependent) Kemeny-Young method finish order?

-Forest


El vie., 18 de mar. de 2022 9:41 p. m., Forest Simmons <
forest.simmons21 at gmail.com> escribió:

> 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/20220321/be0b6f44/attachment.html>