[EM] Ted's Total Approval Beatpath

[Forest Simmons]

Dear Ted,

Your TAB method is what I used to call "Approval Seeded Bubble Sort."

Then after a year of thinking that it was my invention I came across an 
article about the Kemeny Order in which the authors called our bubble 
sort process "Local Kemenization" and suggested using it as a way of 
refining various other orders including the Border order.

One thing that bothered me was lack of reverse symmetry, so I eventually 
came to this version:

Start with the approval order (greatest to least approval <--> top to 
bottom).

While any candidate is beaten by the candidate immediately above her ...

    swap the two adjacent candidates with the greatest "discrepancy"

EndWhile

The winner is the candidate that ends up at the top of the list.

It's like lining up recruits for drill, and sorting them into order of 
height by successive swaps, most urgent first.

"Discrepancy," like defeat strength can be measured in several ways.

If you use margins, or some other symmetric measure, then the final order 
reverses when all of the ballots are reversed.

However this reverse symmetry may not be the best goal when trying to 
discourage manipulation.

Forest


On Sat, 12 Mar 2005, Ted Stern wrote:

> On 12 Mar 2005 at 02:20 PST, Jobst Heitzig wrote:
>
>> Dear Forest!
>>
>> You [Forest] wrote:
>>> Unfortunately, reverse TACC is not monotonic with respect to approval.
>>> If the winner moves up to the top approval slot without also becoming
>>> the CW, she will turn into a loser.
>>
>> That's right.
>>
>> You continued:
>>> However, the following "chain filling" method is monotonic:
>>>
>>> Working from top to bottom of the approval list, fill in a chain by
>>> incorporating each candidate that can be included transitively. The
>>> candidate at the top of the resulting maximal chain is the winner.
>
> At first, I didn't understand what Frest meant by 'transitive, but I gather
> what he mans is, start a chain by adding the first candidate from the sorted
> list (Call that candidate A_i), to the new chain (call that B_j).  When adding
> a new candidate, start at the winning end, and test to see if the candidate
> defeats the first B_j.  If not, follow the list down to the next weaker
> candidate and test again.  Repeat until you find a defeated candidate.  Mark
> the location, but don't insert the A into the B list.
>
> Then start testing from the losing end of the B list.  If the A candidate
> defeats the B candidate, continue following links to stronger B candidates.
>
> If you end up at the same spot each time, the A candidate isn't in a cycle,
> and can be inserted.  Otherwise, you're effectively eliminating it from
> further consideration.  This causes the loss of monotonicity noted by Jobst
> below:
>>
>> This is a nice idea, but upon closer inspection it turns out not to be
>> monotonic, unfortunately. Look at this example: Assume the approval list
>> from top to bottom is A,B,C,D,E, and the defeats are
>> A>B>C>D>E>A>D>B<E>C>A. Then the chain filling begins A>B, C is skipped,
>> D is added to give A>D>B, and E is skipped. Hence A wins. Now reverse
>> the defeat C>A into A>C without changing approvals. Then the chain
>> filling begins A>B>C, D is skipped, and E is added to give E>A>B>C.
>> Hence E wins although the original winner A was raised.
>>
>>> As mentioned above, I wanted to work top down so that I would come to
>>> the Pareto dominators before getting to the Pareto dominated candidates.
>>> Then it doesn't matter if the Pareto dominated candidates are eliminated
>>> at the beginning; the rest of the chain will be the same, including the
>>> top candidate.
>>
>> That's a good point! I think that for this reason, we should proceed
>> trying to find a variation which works top down.
>>
>> Yours, Jobst
>
> Thanks to both of your responses, I have an idea now that I think will work,
> and it should have (my) desired quality of encouraging generous approval
> cutoff and ranking of candidates below the cutoff.
>
> Basically, the idea is simply Beatpath:  Break each cycle at the weakest link.
> But what should be the weakest link?  Why not call it the defeat made by the
> candidate with lowest approval?  We could call this Total Approval
> Beatpath (TAB), but suggest a better name if you want.
>
> Forest's idea can proceed almost identically as before:
>
> (1) Sort candidates by approval, from highest to lowest, into a list
>    {A_1, A_2,..., A_n}.
>
> (2) Initialize a linked list (or chain, if you prefer) of candidates B with
>    Approval Winner A_1.  The beginning of the list is the winning end, and
>    the end is the losing end.
>
> (3) For each A_i, i=2:n,
>
>       B node points to losing end candidate.
>
>       While A_i defeats B-node,
>          follow B-list backward to next stronger candidate,
>          set B-node to that candidate.
>       End while
>
>       Insert A_i before B-node.
>    End For
>
> The winner is the candidate at the left most end of the list.  The list gives
> you the social ordering of the candidates.
>
> This is just like Forest's proposal but doesn't eliminate candidates from the
> B list.
>
> Essentially, each candidate has to run the gauntlet and defeat candidates with
> higher approval before it is inserted in the list.  It may have a cycle with
> higher candidates, but there is always a beatpath down to it with higher
> approval at every step.
>
> This is similar to Jobst's grand compromise and James Green-Armytage's
> Approval-weighted Pairwise, but it isn't necessary to carry along a second
> pairwise array.
>
> It is also easier to implement than standard or cardinal-weighted Beatpath --
> The defeat chain automatically gives you the total approval beatpath strengths.
>
> Why might this be preferable to the other schemes mentioned?
>
> - There is a strong disincentive to bullet vote or truncate (an exercise for
>  the reader, but consider the 35:A>B>>C, 25:B, 40:C, in which B voters ahve
>  truncated their true preference 25:B>A>>C).
>
> - There is a strong incentive to be generous with approval cutoff -- you want
>  your nearest neighbors, if you will, to be considered earliest in the list.
>
> - Much less strategic incentive to equal rank due to the approval cutoff.
>  Voters can express true preferences above the approval cutoff, AND below,
>  without fear of hurting their candidate.
>
> This is too simple to not have been mentioned before ... have I simply missed
> something years ago in the archives?  Is there some major criterion that isn't
> satisfied?
>
> Testing with Jobst's example, I see
>
>        A
>        A > B
>        A > B > C
>        A > B > C > D
>        A > B > C > D > E       ==> A wins.
>
> both times.  Any other examples?
>
> Just to stake a claim in case it hasn't been proposed before, Total approval
> ranking in the first list could be replaced by total cardinal rating.  But I
> don't see any obvious advantage.
>
> Ted
>