[EM] Re: Chain Climbing --> Chain Filling

[Ted Stern]

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
-- 
   Change reply address to tedstern at u dot washington dot edu
   for direct replies.

 Frango ut patefaciam -- I break so that I may reveal