[EM] five monotonic methods ...

[Forest W Simmons]

Markus showed that some methods that pick from the uncovered set are 
not monotonic.  In fact, it's easy to create non-monotonic methods, 
including (blush) the five that I recently claimed were monotonic.  I 
found a subtle hole in my proof.  The lemma is sound, but not quite 
sufficient to prove those methods monotonic.

However a standard modification turns all of those methods into 
montonic ones, mutatis mutandi.

Method 1' : Draw an arrow from each covered candidate to the highest 
approval candidate that covers it.  Start at the approval winner A, and 
follow the arrows until you reach an uncovered candidate, the method 
winner.

Method 2' :  Draw an arrow from each covered candidate X to the 
candidate against which X scores the fewest pairwise votes.  Start with 
the approval winner A and follow the arrows to the method winner.

Method 3' : Set up the arrows as in Method 2' , but start with the 
candidate that is ranked on the most ballots and follow the arrows.

Method 4' : Set up the arrows as in methods 2' and 3'.  Then follow the 
arrows from a candidate chosen by random ballot to the method winner.

Method 5' :  Randomly select a ballot B.  Draw an arrow from each 
covered candidate to the highest ranked candidate on ballot B that 
covers it.  Follw the arrows from the highest ranked candidate until 
you reach an uncovered candidate.

You can see how to manufacture more methods along these lines.

This time proof of monotonicity does follow from the lemma, which I 
repeat here for completeness:

If an uncovered candidate X covers Y, and this X moves up in rank on 
one or more ballots while all of the other candidates retain their 
original relative ranks to each other, then X remains uncovered and the 
set of candidates that cover Y does not change.

Proof of monotonicity:

Let c1, c2, c3, ... be the sequence of candidates leading to the winner 
W which is the first uncovered candidate in the sequence.

By the transitivity of the covering relation W covers every member of 
this sequence (except itself).

If W moves up in the rankings relative to the other candidates and they 
retain their relative positions to each other, then the lemma applies, 
so W still covers every member of the sequence, but W may occur earlier 
in the sequence because of it improvement in the ranks.  Then the 
sequence will stop there because (as per the lemma) W is still 
uncovered.

Now that you've seen this proof, can you see the subtle hole in my 
previous proof?

Here's a hint.  Let C(x) be the set of candidates that cover x, and let 
U(x) be the set of uncovered candidates that cover x.  The lemma says 
that C(x) doesn't change when one of its members moves up in the ranks, 
but that does not preclude U(x) from changing as one of its members 
moves up in the ranks.

Note that the sets of arrows in each of these methods form a kind of 
drainage system into a set of sinks, the set of uncovered candidates. 

So these methods yield diagrams like the River diagrams of Jobst's 
River method, but it is easier to describe where to put the arrows.

Once you know what "cover" means, it is very easy to state each of 
these methods.

For the record, I would like to propose method 1' with the additional 
feature that voters be given multiple ballot options:

They should be able to vote ranked ballots, ranked with approval 
cutoff, approval ballots, favorite as proxy ballots, favorite as 
refiner of approval, etc.

What do you think?

Forest