[EM] Forced strictly-dishonest strategy is common in Schulze-beatpaths voting

[Warren Smith]

I will sketch a proof that, in Schulze beatpaths voting in "random"
N-candidate V-voter elections (V-->infinity, N fixed):
  with probability > a positive constant C (where C goes to 1 as N-->infinity):
     at least a constant fraction K of the voters (where K goes to 3/4
as N-->infinity)
     will regard it as strategically forced that they order D>E for at
least one
     candidate-pair {D,E} for which they honestly prefer E>D.  By
forced I mean,
     they'll feel if they don't do this, they'll have lower expected utility.

This remains true if equal rankings are permitted in rank-order votes (and
I'm going to do the argument for "margins," but it ought also to work
for "winning votes"
after appropriate alterations).

This will only be a proof sketch not a proof, and in fact there are
some messy details I am intentionally eliding which ought to be doable
but it'd be a pain.

The model I will use of strategic voting is this.  First an election
is done with honest votes.  Next, voters are presented the full
pairwise matrix and election results, and asked, in hindsight (and
they are asked individually in isolation), whether they'd like to
strategically alter their vote.  The election is then redone.  But the
second election
is a slightly different voter set (e.g. some voters randomly die or
are born between the two) so a voter cannot be 100% sure her
vote-change will do what she hopes.

The model I will use of probability is this.  Each of the (N-1)N/2
pairwise margins in the initial honest election is an i.i.d.
0-centered normal random deviate.

In contrast, in this same model but with range voters (not Schulze), I
think strict-dishonest strategic votes basically will not occur,
though "semi-dishonest" votes still will (which, e.g. say A=B when
honestly A>B).

OK, here is the argument.
Let L=floor(log_2(N)).
First I claim that with high probability (in fact going exponentially
to 1 as N-->infinity)
for every ordered pair (A,B) of candidates, there are going to be at least
(1/(3*N))*(N-2)*(N-3)*(N-4)*...*(N+1-L)
different L-defeat beatpaths walking from A to B
of the form A beats cand1 beats cand2 ... beats B.

You can see that just from coin-tossing arguments and standard tail bounds.

Second I claim there will (with probability-->1 when N-->infinity) be
no Condorcet winner.
[This is a known theorem.]

Third, the combinatorics and the
i.i.d. nature of the pairwise margin normals now implies that
the two "crux" defeats, i.e. that decide who the victor shall be (call
the winner A
and the one most likely to instead become the winner after the random
birth+death changes, B)   are (with probability-->1 when N-->infinity)
defeats NOT directly involving either A or B.  They are say, {E,F}
and {G,H}.

So best strategy for any single voter in isolation then is to vote (say)
"E>F" and "G>H" regardless of her honest feelings about E,F,G,H.
This will be dishonest with chance 3/4.

She has to do this otherwise she reduces the chance her preferred among {A,B}
will win.  The chance anybody else besides A,B will win is (in the
eyes of that voter) negligible.
Q.E.D.



-- 
Warren D. Smith
http://RangeVoting.org  <-- add your endorsement (by clicking
"endorse" as 1st step)
and
math.temple.edu/~wds/homepage/works.html