[EM] Later no harm, Condorcet, and randomization

[Jobst Heitzig]

Since the topic of "Later no harm" came up again, I would like to point
out that some randomization can make a Condorcet methods fulfil that
criterion in a certain sense.

As we know, no deterministic method can fulfil "Later no harm". For the
sake of completeness, here's again a simple counter-example to prove that:

    Preferences:
    sincere   cast
1   A>B>C     A>B>C
1   B>C>A     B>C>A
1   C>A>B     C>A>B
2   C>B>A     C
2   B>A>C     B
2   A>C>B     A

Assume that A wins with certainty with these cast ballots. Then the last
two voters cannot cast a later preference by voting A>C without making
the less preferred C the Condorcet Winner. When B or C is the original
winner, the same is true for another pair of voters, hence the method is
either not Condorcet or fails "Later no harm" or must involve randomness.

Now let us look what happens when we use a simple randomized method such
as "Elect the CW when s/he exists, otherwise use Random Candidate". Then
each of A,B,C will get probability 1/3 with the above cast ballots. Now
when the last two voters switch to voting A>C, then C is the CW and gets
probability 1. Although this is "harm" to their favourite A since A's
probability decreases from 1/3 to 0, it is also of some positive use for
the two voters because it also decreases their LAST choice's probability
from 1/3 to 0 !

So, randomized methods can be both Condorcet-efficient and fulfil the
following version of "Later no harm" for randomized methods:


Definition: "Later no probability moves down only" (LNPMDO)
-----------------------------------------------------------
Assume that the candidates are  A1,...,An,  and that some voter who has
sincere preferences  A1>A2>...>An  switches from voting  A1>...>Ak  to
voting  A1>...>Ak>A(k+1)  for some  k.  Assume further that for some  p,
 the probability that one of  A1,...,Ap  wins is decreased by this
change. Then there must be some  q>p  such that the probability that one
of  A1,...Ap,...,Aq  wins is increased instead!


In other words: If some amount of probability moves down in the voter's
ranking, then below that position some amount of probability must also
move up in the voter's ranking. In particular, the least preferred
possible outcome can be no worse than before, so that voting later
preferences helps avoiding the worst choices!

For a deterministic method, this is equivalent to "Later no harm", since
then it just demands that the winner (=probability 1) cannot move down
the voter's ranking, am I right?

So, here we have a version of "Later no harm" which is consistent with
Condorcet, but perhaps there are still better versions of that
criterion? Perhaps we can even require that the amount of probability
moving up in the voter's ranking must be at least as much as the amount
of probability moving down?

Also, the method which I used to show the consistency of the two
criteria above is of course bad in most other respects, so we should now
look whether good randomized methods such as Condorcet Lottery, RBCC, or
RBACC also fulfil LNPMDO...

Jobst