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