[EM] Re: How to describe RAV/ARC

[Forest Simmons]

On Wed, 16 Mar 2005, Araucaria Araucana wrote:

> On 15 Mar 2005 at 14:12 PST, Forest Simmons wrote:
>> Here's my sales pitch (to EM members) for RAV/ARC:
>>
>> When candidate X beats Y in both approval and by head-to-head choice,
>> let's say that X strongly beats Y.
>>
>> If X strongly beats Y then both approval and pairwise methods agree that Y
>> should not win.
>>
>> What happens if we eliminate all of the candidates that are strongly
>> beaten?
>>
>> The remaining candidates form a set P that are totally ordered by the
>> ordinary pairwise beat relation.

Notice that this set P is the set of all candidates of which none is 
defeated by any candidate higher up on the approval order.

>>
>> The top of this totally ordered chain is the RAV/ARC winner.
>>
>> That ends my EM sales pitch for RAV/ARC. [I would use a different pitch
>> for the general public.]
>
> [First post using gmail address instead of mailinator]
>
> Hi Forest,
>
> According to this sales pitch, RAV/ARC does not have quite the same effect as
> Approval-seeded Bubble Sort [aka Total Approval Ranked Pairs, Tournament
> Voting (approval-seeded)].

It picks the same winner, but it doesn't give a social order of all of the 
candidates.

I think that "total order" might be the confusing phrase.  "Total order" 
means transitive and antisymmetric.  It doesn't mean that it orders all of 
the original candidates.

The order is total on the set P defined above.

>
> Using ABS, it is possible that a candidate X could end up ranked below the
> Approval Winner AW, but because a higher-seeded candidate Y defeats X but is
> defeated by AW, X cannot end up in your set P.

What your example shows is that P is sometimes a proper subset of the 
candidates that end up (in the sorted list) higher than or equal to the 
AW.

In other words, being in P will guarantee ending up higher than or equal 
to the AW in the final sorted order, but it is not a necessary condition.

In the example below the set P is {A1, A2, AW}.


In this example, as in the general case, if X and Y are two members of P, 
then

           X beats Y pairwise

                   iff

          X has less approval than Y.

In other words, the identity map, when restricted to P, is an order 
reversing order isomorphism between the pairwise beat order and the 
approval order.

Since the approval order is numerical, it is a total order.

Since the bubble sorted order (restricted to P) is order isomorphic (by 
the above order reversing isomorphism) it is also a total order.

You opined that approval doesn't give order information, but when I 
approve candidate A but do not approve candidate B, you can safely deduce 
that I prefer A over B.

On the other hand, if I rank A over B, you can only tentatively deduce 
that I prefer A over B, since most methods based on rankings are 
vulnerable to strategic manipulation.

That's why I say that although the order information in rankings may be 
more complete than the order information in approval, the order 
information in approval is more reliable.

So when the approval order on a set like P is exactly opposite to the 
order deduced from ranked ballots, I believe that the approval order 
should be taken as seriously as the pairwise order.

One way out of this impasse is to give all of the candidates in P a chance 
of winning.

The monotonic, clone free way of doing this is random ballot restricted to 
the set P.

>
> Consider the following situation with the following RP (wv) ordering:
>
>   A1>A2
>   A2>A3
>   A3>A1
>   A1>AW, A1>X, A1>Y
>   A2>AW, A2>X, A2>Y
>   A3>AW, A3>X, A3>Y
>   AW>Y
>   Y>X
>   X>AW
>
> Seeding by descending order of approval, we start with
>
>     AW A2 A1 A3 Y X
>
> There are two cycles:  A1>A2>A3>A1, AW>Y>X>AW.
>
> ABS ends up with the following social ordering:
>
>   A1>A2>A3>AW>Y>X
>
> A1 wins, and also wins via other strong wv methods.  Now consider the three
> interesting situations here:
>
> - The approval winner is not in the Smith Set.
>
> - Pairwise, X>AW, but approval wise, Approval(AW)>Approval(X).
>  Pairwise and Approval disagree.
>  So X should be a member of your set P, but it isn't in ABS.

But X is strongly beaten, so by definition of P, candidate X is not a 
member of P.

All I claimed above is that the set P is totally ordered in two 
diametrically opposed ways.

I made no claim about anything outside of P.

I think you were mislead by the technical use of the word "total" 
thinking, perhaps, that it referred to the totality of the original 
candidates, which it did not.

>  Do you want the least approved candidate, also not a member of the Smith
>  Set, to be included in P?
>  Or is the higher-ranked approval Beatpath AW>Y>X considered a pairwise
>  defeat?
>
> - Approval order above AW is not strictly increasing.

There is no candidate with approval above that of the AW.

>
> So is ABS equivalent to RAV/ARC as you and Jobst have asserted, or is it
> slightly different?  Or is your pitch inaccurate?

The RAV/ARC pitch is accurate, but in the section on lotteries after my 
RAV/ARC pitch, I made one mistake:

I claimed in passing that if you didn't eliminate the strongly beaten 
candidates, the candidates that were as high or higher than the AW in the 
sorted list would constitute the set P.  But as your example shows, this 
set Q is sometimes a proper superset of P.

Whether we should choose (by random ballot) from P or from Q deserves 
further study.

Forest