[EM] Total Approval Ranked Pairs (Was "Re: Ted's Total Approval Beatpath")

[Ted Stern]

On 12 Mar 2005 at 16:10 PST, Forest Simmons wrote:


> Dear Ted,
>
> Your TAB method is what I used to call "Approval Seeded Bubble Sort."

Hi Forest, thanks for the reference check.  It figures that if anybody
might have considered it earlier, it would have been you or Jobst ;-).

But in my earlier enthusiasm, I mis-spoke in two respects.

First:

If you sort the candidates first by total approval, then do a careful
bubble sort (order of operations *is* important), then this method
turns out to be equivalent to Ranked Pairs (total approval), *not*
Beatpath (total approval).

So you could call it Total Approval Ranked Pairs (TARP), or RP(ta), or
Approval Seeded Bubble Sort, but yes, they're all the same thing.

Just to be clear what I'm talking about, 

    Sort by approval so that the front of the list has highest approval.

    Starting at the second point in the list, move that candidate forward
    (higher) if it defeats higher candidates.  Then start at the 3rd point in
    the list and bubble that candidate upward, etc.

In Matlab/octave notation, say you have the pairwise matrix stored in
the array A, with A(i,i) containing the total approval of candidate
X(i).

These octave (and possibly Matlab) operations will give you the winner:

     I = [1:N] ; % Initialize index array with 1 to N
     
     K = for i=1:N; K(i) = A(i,i); endfor  % Approval sort keys

     [T,J] = sort([K' I'], 1)              % sort by ascending approval,
                                           % also return index array

     I = flipud(J)(:,1)                    % Store descending approval
                                           % indices into index vector

     % Bubble sort, with a bias toward higher approval:
     for j=2:N
       i = j
       while ( A(I(i),I(i-1)) > A(I(i-1),I(i)) )
         % Swap the indices to bubble the i-th candidate upward
         k = I(i-1)
         I(i-1) = I(i)
         I(i)   = k
         i = i - 1
         if ( i == 1 )
            break
         endif
       endwhile
     endfor

I think this is conceptually easier to grasp than to sort all defeats
by the minimum approval of either contestant (total approval defeat
strength), but the end result is the same.  Any contests that are not
considered in the while loop are the same defeats dropped by RP(ta).

Unlike traditional ranked pairs, which is already fairly easy to
explain, you don't have to rank the defeats, you don't have to discuss
"consistency" (cycles), and you don't have to explicitly state that
you're dropping defeats.  All of those arise automatically from the
two sort stages.  IMO, this would definitely have a higher
voter-appeal factor.

TARP also has an intuitive "sports-like" analogy, particularly
appropriate during this first week of March Madness (US college
basketball playoffs):

   "Rank candidate 'seeds' in descending order of approval.  For a
    candidate to move up in rank, it has to defeat all higher seeded
    teams in succession, and only after each of those has itself moved
    up in rank as much as possible."

Jobst, as you said, this may indeed be equivalent to Kevin's
approval-completed Condorcet, but I'd like to point out that there's
no mention of elimination in this implementation, and the result is a
social ordering.

Not eliminating candidates too early, to my mind, is one of
Condorcet's strongest arguments against plurality or IRV.  So whenever
possible, you should avoid any formulation that mentions elimination!

I'll cover the second problem I found below.

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

Is RP(wv) symmetric?

I think total approval ranked pairs is symmetric with respect to the
approval cutoff.  In other words, if "X1>>X2" votes are changed to
"X2>>X1" votes.

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

I'm not sure that I consider lack of symmetry important.

Here's the second problem I realized:

> On Sat, 12 Mar 2005, Ted Stern wrote:
>> - 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 have truncated their true preference 25:B>A>>C).

In TARP (aka ASBS), there is some disincentive to truncate
preferences.  But it is not as strong as I initially thought.  For
instance, in the example immediately above, B could still win with
truncation.  But the A block can use the ATLO-like option of placing
its cutoff above B to force a C win if B tries to truncate.  The B
block would do better to appeal to the C voters to gain a rank below
their approval cutoff.

So strategy-wise, I think TARP / ASBS / RP(ta) is as strong as ATLO or
Approval-weighted pairwise, but easier to implement and explain to
voters.

Jobst, I would even suggest that in many-candidate elections, it is as
easy or easier than River.

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

Well, not as strong an incentive to be generous with approval cutoff as I
thought initially.  But maybe it's enough.

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

I think this still stands.

As others (Kevin?  Gervase?  Alex?) have mentioned during the last
couple of days, it could be easier to simply have two sets of
rankings, some approved and some disapproved.  I think any even number
of options from 6 to 10 would be adequate, with the approval cutoff in
the middle.  Perhaps 6 would be a good starting point for a public
proposal.

Ted
-- 
 Ted Stern                               
   (change reply address to tedstern at u dot washington dot edu)