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 ---- Election-methods mailing list - see http://electorama.com/em for list info
