[EM] eliminations methods like IRV

[Forest Simmons]

Here's some more (as threatened):

An example of iteration:

We start with rankings and a crude method for picking the winner.

Rankings:

34% A>B>C
36% C>B>A
30% B>A>C

Crude Starting Method: Method_0 is just the one we mentioned last time ...
choosing the candidate with the least number of last place votes.

Picking a winner by Method_0 :  A is the winner.

First iteration: Improving Method_0 to get Method_1 :

Step1. Reverse the preferences:
34% A<B<C
36% C<B<A
30% B<A<C

Step2. Use Method_0 to find the best for this reversed problem: best=B.

Step3. Eliminate B.

64% A<C
36% C<A

Step4. Use Method_0 again to eliminate C.

This concludes the first iteration:  A is the only candidate left, so we
consider A to be the loser of the reversed problem, and therefore the
winner of the first iteration method Method_1.

Note that, applying Method_0 to eliminate B and C from the reversed
problem was equivalent to IRV's elimination rule for the original problem,
so Method_1 is just IRV in disguise.  A wins under IRV.

Second Iteration: Improving Method_1 (IRV in this case) by using it to do
the eliminations in the reverse preference problem:

Here's the reverse preference problem again: 

34 A<B<C
36 C<B<A
30 B<A<C

IRV would pick C as the best, so that's the first one to eliminate:

34 A<B
66 B<A

Of these, IRV likes A, so we eliminate A.  We are left with B, so B is the
winner of the second iteration method, Method_2.

Note that in this case, the second iteration has produced the Condorcet
winner.  Applying IRV to the reversed preference problem (to do the
eliminations) has improved on IRV itself.

Note that this process is ideally adapted to recursive programming.



On Wed, 21 Feb 2001, Forest Simmons wrote:

> Can anything be salvaged from IRV?  I think so: it's an ill wind indeed
> that blows no good at all.
> 
> One idea implicit in IRV is this:  Keep eliminating the worst candidates
> from the rankings until the best choice among the remaining candidates is
> obvious.
> 
> The idea is appealing. I like it, and I suppose it is part of the reason
> that IRV (which claims to implement it faithfully) has garnered so much
> support.
> 
> The trouble with implementing the "elimination of the worst" part of the
> idea, is that determining the "worst" is mathematically equivalent to
> determining the "best."  In fact, if you reverse all of the preferences in
> the rankings, best and worst switch places. 
> 
> This symmetry may be considered one source of IRV's problems; when you
> start eliminating candidates from the rankings in the early stages, if you
> eliminate candidates other than the worst, you risk eliminating some of
> the best, if not the best.
> 
> In IRV, you eliminate the candidate with the least number of top
> preference votes. Obviously, the candidate with the least number of first
> place votes is not the worst; if it were, then by symmetry we could say
> that the candidate with the least number of last place votes is the best.
> We could disband this whole EM list and go home.
> 
> Of course, IRV supporters can say it is not really necessary to know the
> worst, just as long as you are not eliminating the best.  In this regard,
> is it possible for IRV to pick the same candidate as both the best and the
> worst?  In other words, is there a pair of examples which are identical
> except for the reversal of preference directions, that both have the same
> winner when IRV is applied?
> 
> I doubt that IRV is that bad.
> 
> But here is a related problem of IRV for which examples are easy to
> supply: When IRV is applied to the reversed rankings to figure out the
> worst candidate, if that candidate is eliminated instead of the one with
> the fewest first place preferences (in the search for the best candidate),
> then continuing IRV as usual results in a different (and better?) choice.
> 
> If this modification does indeed improve on IRV, then it suggests an
> iterative scheme for improving elimination methods. To get the eleventh
> improvement, use the tenth improvement (applied to the reversed order
> preferences) to do the eliminations.
> 
> Note that in this context IRV is just the result of the first iteration
> applied to the crude method that says choose the candidate with the least
> number of last place preferences.
> 
> We shouldn't expect too much from one iteration of an iterative scheme,
> especially when starting from a very crude approximation.
> 
> Under what circumstances would such an iterative scheme converge to a
> solution?  When the method converged would the solution depend on the base
> method?
> 
> If the base method is Condorcet, and there is a Condorcet winner, then
> that winner is chosen immediately without iteration, since Condorcet
> applied to the reversed preferences simply reverses the (partial) order of
> the results. In other words, Condorcet is invariant under this
> transformation.  Is it the only method invariant under this
> transformation?  In other words, when the iteration converges, does it
> necessarily converge to a Condorcet Winner? 
> 
> 
> (More Later)
> 
> 
> Forest
> 
>