[EM] Re: Total Approval Ranked Pairs

[Ted Stern]

On 14 Mar 2005 at 13:14 PST, Forest Simmons wrote:
> Here's the original recursive procedure that I gave for Approval Seeded 
> Bubble Sort:
>
> 1. List the candidates in order of approval, from top to bottom.
>
> 2. Percolate the bottom candidate as far as possible up the recursively 
> sorted list of the other candidates.
>
> How's that for concise?

Concise?  Yes.  Could the layman grasp it?  No.  But I agree, it is the same
as what I've been suggesting.

>
> Jobst is right: the winner is the lowest approval score candidate that 
> beats all of the candidates with greater approval, which turns out to be 
> the same as the first CW that eventually appears as low approval 
> candidates are eliminated successively.

Okay, I see that now.  Your explanation is clearer ;-).

>
> Furthermore, the set P of all candidates none of which is beaten by any 
> candidate with greater approval turns out to be the set of candidates that 
> are as high or higher than the approval winner in the sorted order.
>

Seems nice, but why is this a nice property to have?  Is there something
special about it?

I think it is nice that the method is so concise.  So much is handled
implicitly.  It's simple enough you could use it in a middle school student
body election.

>
>
>> 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.
>>
>
> Using powers of two for the number of ranks makes the most efficient use 
> of bits. Eight would be just right, requiring just three bits to rank or 
> rate zero through seven:
>
>
> Before marking:
>
>   John Doe  (4) (2) (1)
>
>
> After marking:
>
>   John Doe  (*) (2) (*)
>
> [John Doe's rating is five, the sum of the shaded bits.]
>

Sometimes efficiency is too efficient.  Is 7 highest or lowest?  If 7 is
highest, you need to fill in all 3 blanks to select your first choice (7), 2
blanks for 2nd choice (6), 2 blanks for 3rd choice (5), and 1 blank for your
minimum approval level 4th place (4).  And so on for the ranks below the
approval cutoff.

But if 7 is lowest, it means you have to fill in all 3 blanks for every lowest
level candidate.

Sorry for the gross generalization, but grandma and grandpa aren't going to
like that.  If you're going to save them having to go to an extra election,
they shouldn't have to fill in more than the 2 blanks they would have used for
two plurality elections.  They might be able to deal with 2 more fill-ins, but
not 2*N more!

If what you are after is efficient data storage, go ahead and use 8 ranks.
But the voter enters only 6 ranks, 1 through 6.  As Dave Ketchum has
suggested, reserve 7 for default spoiled (if all ranks 1 through 6 have been
used, otherwise one below the lowest ranked), 8 for unfilled.

On another note, it is interesting to consider Rob LeGrand's example election:

 98:A>C>E>D>B
 64:B>A>E>C>D
 12:B>A>E>D>C
 98:B>E>A>C>D
 13:B>E>A>D>C
125:B>E>D>A>C
124:C>A>E>D>B
 76:C>E>A>D>B
 21:D>A>B>E>C
 30:D>B>A>E>C
 98:D>B>E>C>A
139:D>C>A>B>E
 23:D>C>B>A>E

Considering the top two as approved, the pairwise matrix looks like this:

  319  458  461  485  511
  463  440  461  312  623
  460  460  460  460  460
  436  609  461  311  311
  410  298  461  610  312

Ranking the defeats using minimum approval, secondarily using winning votes,
the defeats are ordered as

        Initial descending approval:
        C,B,A,E,D

        Approval-sorted bubble sort ranking:

        B > A > E > D > C

        Total Approval Ranked Pairs:

        B>C     440 (wv 460)
        A>C     319 (wv 460)
        B>A     319 (wv 463) => B>A>C
        B>E     312 (wv 623)
        A>E     312 (wv 511) => B>A>E
        E>C     312 (wv 461) => B>A>E>C
        E>D     311 (wv 610) => B>A>E>D
        D>B     311 (wv 609) conflict, excluded
        A>D     311 (wv 485)
        D>C     311 (wv 460) => B>A>E>D>C

Total Approval Beatpath: B's total approval beatpath to A is 440 (B's
approval, since B>A is a direct victory).  A's strongest total approval
beatpath to B is 311.

So B wins both Beatpath and Ranked Pairs.  With winning votes only, Beatpath
chooses A and RP chooses B.

Ted
-- 
 Ted Stern                               
   Change reply address to tedstern at u dot washington dot edu