[EM] Swap Cost

[Forest Simmons]

El lun., 21 de mar. de 2022 2:13 p. m., Forest Simmons <
forest.simmons21 at gmail.com> escribió:

> 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
>

No other social order is preferred over its reversed/opposite order by such
a large majority (70 to 30).
This makes BAC a strong contender for "most acceptable" finish order,
especially since the undefeated order BCA is only tied (50 to 50) with its
polar opposite ACB.

Anybody else think BAC should be considered the most generally acceptable?

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/cf7c8fa5/attachment-0001.html>