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

[Forest W Simmons]

Jobst Heitzig wrote:

>Dear Paul!
>
>you asked:
>> Is clone independence strictly more important than determinism?
>
>I would rather say, a sufficient *non-determinism* is much more
>important than clone independence since all deterministic majoritarian
>methods suffer from serious strategy problems whenever there is no
>sincere Condorcet Winner (in such a situation there is always a majority
>which has an incentive to change the winner by voting strategically). As
>I have pointed out a number of times, only methods which resolve cycles
>with a sufficient amount of randomness are more stable against such
>strategic threats!

The tricky part is finding the right probabilities for the candidates.

If you give all of the candidates equal probability, then it is to the 
advantage of non-CW supporters to distort their votes in a way that 
will artificially enlarge the Smith set (eg. from one, to more than one 
member) so that their  less popular candidate will be as likely to win 
as any other.

Somehow more popular candidates need to have greater probability, but 
exactly how to measure popularity, and how to best assign the 
probabilities is an unsolved problem.

The simplest way to (at least nearly) pull this off seems to be Rob 
LeGrand's ballot-by-ballot approval method applied to a set of ordinal 
ballots that has been shuffled into a random or pseudo-random order.

[Rob sets the approval cutoff (on the current ballot) next to the 
current approval champ on the side of the current approval runner up.]

In Rob's simulations this method has always picked the CW (in cases of 
its existence) even though the method doesn't strictly satisfy the 
Condorcet Criterion, since it is possible that highly "non-random" 
sequences of ballots can be chosen at random, just as it is possible, 
though unlikely, to generate the sequence

                     HHHHHHHHHTTTTTTTTT

of H's and T's randomly.


Forest

P.S.  Here's an example:

40 ABC
30 BCA
30 CBA

If these are run through ballot-by-ballot in the order that they appear 
in the above list (all 40 of the ABC ballots followed by all 30 of the 
BCA ballots followed by the CBA ballots), then clone C will end up with 
the highest total approval (60), and B (the CW) will barely beat out A, 
the Condorcet Loser, by half a point (40.5 to 40).

[These totals could vary by plus or minus a point depending on how you 
initialize the approval and where you put the cutoff when all three 
candidates have the same current approval.]

If you randomize the ballot sequence, B will win with a probability of 
more than  99.99999%.

This should be good enough for practical purposes, but it will take 
extremely enlightened voters to understand the benefits of 
randomization or pseudo-randomization.  

Pseudo-randomization is best because of its reproducibility.  The fact 
that pseudo-random is really deterministic (like the result of 
successive perfect shuffles) might make this more palatable to some 
voters.  But most of them will rightly consider the number of shuffle 
steps as an arbitrary feature of the method.

If some information theorist could show us how to come up with an 
optimal number of shuffles (of a certain type) relative to some 
information theoretic measure of randomness (entropy, say) we could 
claim that the number of shuffles was not arbitrary.

>----
>Election-methods mailing list - see http://electorama.com/em for list 
info
>