[EM] Recursive Elimination Supervisor

[Forest Simmons]

Any trivial method can correctly distinguish winner and loser in a two way
contest.  How about a three way contest? 

The answer is the same, yes, any old trivial method can correctly
distinguish winner and loser in a three way contest, IF (this is one of
those big IF's) the method is not just left to its own devices, like some
forlorn latchkey child. 

For example, let's use IRV as a "seed method" for our recursion. IRV does
just fine in a two way single winner contest.  And for definiteness, let's
assume that our version of IRV breaks two way ties by drawing a ballot at
random.

Now, let's go to work on the three way contest:

Step 1.  Have IRV tell us which of the three candidates he thinks should
win, temporarily label this candidate SW (for Seed Winner), and set it
aside for later use.

Step 2.  Have IRV point out from among the remaining two candidates the
one that is the worst (or the tie breaker if they are tied.) IRV can handle
this because it is just a two way contest. Label this candidate RL (for
Recursive Loser).

Step 3. Trade in SW for RL, so that now, of the three, RL is sitting out.

Step 4.  While RL sits out, have IRV pick the winner from the other pair.
(IRV can do this because he can handle a two way contest.) This time label
IRV's pick W for Winner and give IRV a star on his forehead.

Here's why W deserves to be labeled as Winner: The candidate RL found in
step 3 could not be a deserving winner (or at least not uniquely so)
because IRV distinguished him to be a loser from among two candidates, and
IRV doesn't make mistakes on two way contests.  Therefore, a true winner
was to be found among the other two. In step 4 IRV picks a deserving
winner from among the two.

Notice that although IRV is prone to get into trouble when unsupervised,
a little guidance from the older children helps him to earn a gold star.

We have just shown that IRV can pick a three way winner when correctly
supervised.  Similarly (by switching the directions of all the
preferences) a well supervised IRV can pick a three way loser competently.

Now let's help IRV handle a single winner four way contest:

Step 1.  Have IRV pick a seed winner SW from the four candidates and set
this seed winner aside as before. 

Step 2.  Supervise IRV to pick a Recursive Loser RL from the other three
candidates.  IRV does fine on this task with supervision as we just
finished showing.  (This is a recursive step in the general case.)

Note that this RL is not a deserving winner, or at least not uniquely
so.

Step 3.  Trade in SW for RL, and note that with RL sitting out, there must
still be at least one deserving winner among the remaining three.

Step 4.  While RL sits out, supervise IRV to find the Winner W from the
remaining three candidates.  We showed above that IRV can handle this task
under supervision (This is also a recursive step in the general case.) 

It is easy to see that the Winner in step 4 is truly a deserving winner,
since she was competently chosen from a group of three that had to contain
a deserving winner. 

So under appropriate supervision IRV can handle four way contests.

Now let's do the general case.  To avoid the above cumbersome
circumlocutions that result from constant care to include the possibility
of multiple deserving winners, I give a version that doesn't apply when
there are ties or cycles of deserving winners:

Step 1.  Let IRV pick the Seed Winner SW from among the N candidates, and
set this SW aside temporarily.

Step 2.  Recursively supervise IRV to pick the Recursive Loser RL from the
remaining N-1 candidates.  (Our induction hypothesis is that supervised
IRV is competent for finding best and worst among N-1 candidates.) 

Step 3.  Trade in SW for RL, and note that with RL sitting out, the
remaining N-1 candidates must contain the true winner.

Step 4.  While RL sits out, recursively supervise IRV to pick the Winner
from among the other N-1 candidates. 

Comments:  In the first step we let IRV pick the seed winner just to make
him feel important.  The seed winner could be chosen at random, but we
don't want to hurt IRV's feelings, so we let IRV choose the one to set
aside, and give it a fancy name, "the seed winner."  

In practice it would only make a difference if there were multiple
deserving winners. In that case we can think of IRV's influence as
providing flavor to the winner.  Using another seed method besides IRV
would give a different flavored winner.

I'm too tired to write in the circumlocutions for the case of non-unique
deserving winners into this general recursion statement.  Let someone else
copy them from the first two sample induction steps above. 

I haven't done the details on paper, but I believe it can be easily proven
in an induction parallel to the recursion that all (big W) Winners and
"Recursive Losers" (RL's) in the recursion are Condorcet Winners of the
direct and reverse preference rankings, respectively, in the case where
deserving winners are unique. 

This supervisor is a kind of meta-method for enhancing election methods.
As I will point out in a later posting, practical enhancement does not
always require the complete recursion.

This was an exciting find for me.  I hope you find it interesting, too.

Forest