[EM] Re: chain climbing methods

[Forest Simmons]

On Mon, 7 Mar 2005, Jobst Heitzig wrote:
...

> Perhaps I should make clear again why I propose randomization in the
> first place:
...

> Methods such as Condorcet Lottery, RBCC, and RBACC accomplish this ...

But the Condorcet Lottery picks the CW with certainty when there is one. 
Wouldn't this encourage the creation of a fake CW?

...

> You then proposed another method, VCRB:
>> Now here's another lottery method I favor because, although it tends
>> to spread the probability around more promiscuously, it has nice
>> properties:
>>
>> First find the highest approval score alpha such that no candidate
>> with approval less than alpha beats (pairwise) any candidate with an
>> approval score of alpha or higher.
>>
>> Then do random ballot relative to the candidates that have approval
>> scores greater than or equal to alpha.
>>
>> That's it.  Let's call it Viable Candidate Random Ballot (VCRB).
>
> That is perhaps better. By definition, each non-winner is beaten by some
> winner. But is also every winner (except a CW) beaten by a winner?

Yes (except when the CW is the approval winner), if you count being beaten 
in approval as being beaten.

Suppose that (according to the ballots) candidate A is both the approval 
winner and the CW.  How likely is it that A is a fake CW?

> And is it really monotonic?

Yes. First of all, moving up (in approval or pairwise) a viable candidate 
relative to some other candidate (viable or not) will not help any 
non-viable candidate become viable, i.e. the new approval cutoff alpha 
cannot be lower than the old.

The question remains, did the candidate X that moved up relative to 
candidate Y, suddenly become non-viable? i.e. did the alpha approval 
cutoff get moved up past X ?

To see that it did not, consider the following characterization of the 
viable candidates. (For simplicity we assume no ties either in approval or 
pairwise.)

A candidate X is viable iff there is a sequence of candidates c1, c2, ... 
cK, such that X=c1 and cK=(the approval winner A), and such that each 
candidate in the sequence beats its successor either in approval or 
pairwise.

[The key to this is the maximality of alpha in the definition of viable.]

So before X moved up relative to Y, there was "beat path" of the indicated 
type from X to A.  Assume without loss in generality that candidate X 
appeared only at the start of that sequence.  Then every step of that 
sequence is still valid, so there is still a "beat path" of that type from 
X to A, so X is still viable.

Forest