[EM] election-methods at electorama.com

[Warren Smith]

Some results about computer simulations of elections - without need of a computer!
----------Warren D Smith------Dec 2005--------------------------------------------

Consider the following cheapo model of simulating an election. Each candidate to
each voter has a utility which is an independent uniform random in the interval [0,1].
There are some fixed number C of candidates and some number V of voters
where we shall assume V is LARGE:

Thm 1.  
Suppose all the voters magically know the identity X of the max-summed-utility candidate.
Suppose each voter votes approval-style by approving of all candidates with more utility 
than f*U_X, where U_X is X's utility (to that voter) and f is a constant 
(for example f=10% or f=90%) with 0<f<1.
Then: with 100% probability in the V=large limnit, X will win the election.

Proof: X gets 100% approval. Any other candidate gets approval 0.5*f approximately. Q.E.D.

Note 1a.  Actually the above proof works for ANY pre-fixed candidate X,
who instead could be the Schulze winner, the worst-summed-utility candidate, or whoever.
X still will be elected.

Thm 2.
Suppose each voter votes approval-style by approving of all candidates with more utility 
than U_X*f+U_Y*(1-f), where U_X is X's utility (to that voter) and X is the best
among {A,B} and Y the worst (in that voter's eyes) and A and B are two
randomly selected candidates (but fixed once and for all after their choice, which happens
immediately before the election; think of A and B as the two "major-party" candidates)
and f is a constant (for example f=90%) with 0.5<f<1.

Then: the most popular among {A,B} gets elected with 100% probability in the V=large limit,
i.e the same winner strategic plurality voting would elect.

Proof: the most popular among {A,B} gets over 50% approval.  Each other
candidate gets (2-f)/3<0.5 approval in expectation.  Q.E.D.

Note 3.
This suggests that if f=50% exactly, then we should expect approval voting
results better than strategic plurality voting.

Thm 4.
Suppose each voter votes condorcet-style with strict-rank-order ballots
by ranking his favorite among {A,B} top.  
(It doesn't matter how he rank-orders the rest of his vote.  Some have
criticized me for employing "burying."  But: burying or not is irrelevant here.)

Then: the most popular among {A,B} gets elected with 100% probability in the V=large limit,
i.e the same winner strategic plurality voting would elect.

Proof: he is the majority-winner, i.e. Condorcet winner.  Q.E.D.

Thm 5.
Suppose each voter votes IRV-style with strict-rank-order ballots
by ranking his favorite among {A,B} top.  
(It doesn't matter how he rank-orders the rest of his vote.)

Then: the most popular among {A,B} gets elected with 100% probability in the V=large limit,
i.e the same winner strategic plurality voting would elect.

Proof: majority-winner.  Q.E.D.

Note 6.
Observe that Approval voting in note 3 therefore will be expected to do better
social-utility-wise than any Condorcet or IRV method (with this model and these voter strategies).

Summary:
These facts make some of Kevin Venzke's simulations look, in retrospect, pretty stupid.
They also make some of mine look stupid.  I.e, we in some cases wasted a considerable
amount of computer & programming time to report something we could have noticed immediately.
However, I am happy to report that it appears Venzke is looking dumber than I am,
since I did lots of other kinds of sims (e.g. non-uniform randomness, etc) not
covered by the above, but he didn't.   :)

wds

PS.  To answer some venzke queries, yes, Social Utility (Bayesian Regert) certainly
is useful even if all voters are strategic, but it also is useful if some or all of
them are honest.   If comparing voting system A versus B by using social utility,
I would tend to want to make ther honesty:strategy fraction among the voters be the SAME
for both A and B, to compar apples with apples.  This is not required, but
it seems more fair.  If you make Schulze voters alwys be honest and thus never susceptible
to DH3, then a comparison with some other voting system with 100% or 50% strategic
voters, will of course give a bias in favor of Schulze.  

My "honest" approval voters simply approved the above-average candidates.  (There were also
other notions of honesty and strategy one could try, I am just naming the simplest
ones that I simulated.  I also simulated others.)