[EM] determinism (was New Condorcet/RP variant)

[Jobst Heitzig]

Dear Forest!

Your wrote about ROACC:
> However, here's what bothers me about the method.  Suppose that there 
> are three classes of clones X, Y, and Z, such that every member of X 
> beats every member of Y, and every member of Y beats every member of Z, 
> and every member of Z beats every member of X.
> 
> Then under ROACC, the winner comes from class X iff the first candidate 
> chosen in the random order comes from class Y.
> 
> So if the respective class sizes are x, y, and z, then the probability 
> that the winner is from class X is given by  y/(x+y+z), which can take 
> on the value of any rational number between zero and one.

That is absolutely true. We see from this that with non-deterministic
methods like ROACC, there are two quite different levels of cloneproofness:

The *weak* level of cloneproofness is this: When candidate C is replaced
by a set S of clones then (a) a non-C- resp. non-S-candidate should have
a zero probability if and only if it had zero probability before the
cloning, and (b) an S-candidate X should have zero probability when C
had zero probability before or when X would have zero probability when
only the S-candidates were considered. This level of cloneproofness is
attained by ROACC since for ROACC the set of candidates with non-zero
probability is exactly the Banks Set.

The *strong* level of cloneproofness is this: When candidate C is
replaced by a set S of clones then (a) any non-C- resp. non-S-candidate
should have the same probability as before the cloning, and (b) any
S-candidate X should have the probability that C had before, multiplyed
with the probability X would have if only the S-candidates were
considered. This level of cloneproofness is *not* attained by ROACC as
your example perfectly shows.

The reason for this is that in each step of ROACC, a candidate is drawn
uniformly at random, and already the uniform distribution violates the
strong cloneproofness. So, in order to make ROACC cloneproof in the
stronger sense, we would have to use a different "base distribution"
which would have to respect clones already. However, I fear that it will
be quite difficult to find such a distribution...

Let us try to find such a base distribution for small numbers of
candidates: In the 2- and 3-candidate cases A>C and A>B>C<A, it would
have to give A prob. 1, since A>B>C<A can result both from cloning A or
from cloning C. In the 3-candidate cycle A>B>C>A, it could give each
prob. 1/3. For those 4-candidate cases which possess a CW or Condorcet
loser, the distribution is then already determined from the 2- and
3-candidate cases. Also the remaining 4-candidate case A>B>C>D>A>C,B>D
it would give A,B,D each 1/3 and C 0 since {B,C} is a set of clones and
B>C. This determines the base distribution for each set of up to 4
candidates:


CLONEPROOF BASE DISTRIBUTION:

n  defeats          clones?   probabilities
                              A   B   C   D

2  A>B                        1   0

3  A>B>C<A          {B,C}     1   0   0
   A>B>C>A                    1/3 1/3 1/3

4  A>B>C>D<A>C,B>D  {B,C,D}   1   0   0   0
   A>B>C>D<A>C,B<D  {B,C,D}   1   0   0   0
   A>B>C>D<A<C,B>D  {A,B,C}   1/3 1/3 1/3 0
   A>B>C>D>A>C,B>D  {B,C}     1/3 1/3 0   1/3


Perhaps that could easily be extended to 5 candidates, but that has
already much more cases: Those cases in which the Smith Set is smaller
than 5 candidates have zero probability outside the Smith Set and are
determined by the above smaller cases. Then there is a cyclically
symmetric case
   A>B>C>D>E>A<C<E<B<D<A
which requires giving 1/5 to each. The remaining cases can be assumed to
have A>B>C>D>E>A>C, so that the four question marks in C?E?B?D?A allow
for at most 16 different cases (6 of which are still equivalent do
others up to relabeling):
                          A   B   C   D   E
a  A>B>C>D>E>A>C>E>B>D>A  1/5 1/5 1/5 1/5 1/5 (cyclically symmetric)
b  A>B>C>D>E>A>C>E>B>D<A  1/3 0   1/3 0   1/3 (AB and CD clones)
c  A>B>C>D>E>A>C>E>B<D>A  1/3 0   1/3 1/3 0   (DE and AB clones, like b)
d  A>B>C>D>E>A>C>E>B<D<A  ? (no clones)
e  A>B>C>D>E>A>C>E<B>D>A  1/3 1/3 0   1/3 0   (BC and DE clones, like b)
f  A>B>C>D>E>A>C>E<B>D<A  1/3 1/3 0   0   1/3 (BCD clones)
g  A>B>C>D>E>A>C>E<B<D>A  ?
h  A>B>C>D>E>A>C>E<B<D<A  1/3 1/9 1/9 1/9 1/3 (BCD clones)
i  A>B>C>D>E>A>C<E>B>D>A  0   1/3 0   1/3 1/3 (EA and BD clones, like b)
j  A>B>C>D>E>A>C<E>B>D<A  1/3 0   0   1/3 1/3 (ABC clones, like f)
k  A>B>C>D>E>A>C<E>B<D>A  0   0   1/3 1/3 1/3 (EAB clones, like f)
l  A>B>C>D>E>A>C<E>B<D<A  ?
m  A>B>C>D>E>A>C<E<B>D>A  ?
n  A>B>C>D>E>A>C<E<B>D<A  ?
o  A>B>C>D>E>A>C<E<B<D>A  1/9 1/9 1/3 1/3 1/9 (EAB clones, like h)
p  A>B>C>D>E>A>C<E<B<D<A  ?

It is not clear to me how the remaining question marks should be answered...

Also, I don't see how it could be determined for arbitrary candidate
numbers. And, which is perhaps even more problematic, I don't see at all
how we could make sure the resulting method will become monotonic!

Anyway, assume that we base ROACC on such a "strongly cloneproof base
distribution", that is, a distribution in which cloning does neither
change the probabilities of the other candidates nor the conditional
probability inside the set of clones. Then ROACC will also be strongly
cloneproof!

In the case A>B>C>D>A>C,B>D, for example, the original ROACC would give
A 1/4+1/4=1/2, B 1/4, C 0, and D 1/4 probability, whereas the modified
ROACC would give A 1/3*1+1/3*0=1/3, B 1/3, and D 1/3. Surprisingly, for
all 2-,3- or 4-candidate cases, the modified ROACC distribution is
exactly the same as the above base distribution... and I'm not sure
whether this is a coincidence...

Yours, Jobst