[EM] More results about computer simulations of elections - without need of a computer!

[Warren Smith]

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

We continue to 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.

But in this post we shall consider some rank-ballot voting methods that allow rank-equalities.

Thm 7.  
Suppose we are using a Condorcet method but this time allowing rank-equalities.
Suppose there are two random but pre-fixed candidates A and B.
Suppose the voters behave thusly:
Each gives either A or B (whichever they consider better - call him T) top rank.
Then they rank everybody else honestly (generically with no equalities) except
that anybody who would have been ranked above T is instead ranked coequal-top with T.

Then:  either A or B will, with 100% probability asymptotically for V=large,
win the election, i.e. the same winner results as with strategic plurality voting.

Proof sketch:
Because that winner X will be Condorcet winner.
For each Y not in {A,B},  X is ranked above Y one-half of the time,
is ranked equal with Y at top 1/6 of the time, and is ranked below Y
one-third of the time (all almost-surely in the V=large limit by
the law of law numbers...).  So X pairwise-defeats all Y (whether we use margins
or winning-votes, does not matter).  Q.E.D.

Note 8.
All results derived in this simplistic election-model are, of course, attackable as unrealistic,
but still have some interest.  As you can see, approval voting with the strategic
voter behavior of approving everybody above (U_A+U_B)/2, performs better average-utility-wise
than every Condorcet method with the above strategy in this model, because approval
with that voter behavior tends to improve over strategic plurality voting.

It is very interesting, however, that if voters adopt the following alternate
strategy for Condorcet:
 Give either A or B (whichever they consider better - call him T) top rank.
 Give the other bottom-rank (call him Z).
 Then rank everybody else honestly (generically with no equalities) except
 that anybody who would have been ranked above T is instead ranked coequal-top with T,
 and anybody who would have been below Z is instead ranked coequal-bottom with Z.
Then:
it is unclear to me who will win, and I do not see any reason it generally must be A or B.
[If you try to redo the above proof, then
X is ranked above Y one-third of the time, below one-third, coequal bottom 1/6, coequal top 1/6,
up to additive noise of order o(1) in the V=large limit, and so we cannot draw a conclusion that
anybody is going to be a Condorcet winner.  In fact in general I would
expect no Condorcet winner will exist if C is reasonably large.]

In other words: claims have been made that my notion that voters would "bury"
their least-liked among {A,B} to bottom rank, was silly, 
that it was stupid for Condorcet voters to behave that way, etc.

But those claims now seem wrong - because as we now see, if voters behave in this 
burial-manner, then in this randomized election model, they will be able to get a winner better
than the strategic-plurality-winner, but without the burial (as in thm 7) they will
just get the same winner as with strategic-plurality voting.


Thm 9.
Suppose we are using an IRV (or Condorcet)
method but this time allowing rank-equalities, where
all equalities X=Y in votes are replaced by X>Y and Y>X etc in all possible ways
(i.e. C! near-copies are made of each vote to allow this) which is the usual
very nasty-to-deal-with proposal for allowing IRV to handle rank-equalities in votes.

Suppose there are two random but pre-fixed candidates A and B.
Suppose the voters behave thusly:
Each gives either A or B (whichever they consider better - call him T) top rank.
Then they rank everybody else honestly (generically with no equalities) except
that anybody who would have been ranked above T is instead ranked coequal-top with T.

Then:  either A or B will, with 100% probability asymptotically for V=large,
win the election, i.e. the same winner results as with strategic plurality voting.


Proof sketch:
For Condorcet:
For each Y not in {A,B},  but with X in {A,B} is ranked above Y  7/12 of the time,
and is ranked below Y  5/12 of the time (all almost-surely in the V=large limit by
the law of law numbers...).  So X pairwise-defeats all Y (whether we use margins
or winning-votes, does not matter, in fact the two are the same with this method of handling
X=Y votes).  So an X in {A,B} will be a Condorcet winner.

Now for IRV:
X is ranked top by V/2+o(V) voters before vote-alteration and after alteration is
top-ranked by 3V/(2C)  voters.   Meanwhile Y is top-ranked 1/3+o(1) 
of the time before vote-alteration and after alteration is
top-ranked by V/C  voters.   So each Y will get eliminated (and since the vote-transfers
are independent random, this will happen in subsequent IRV rounds also)
Q.E.D.


So again, this whole random-number election model is not terribly realistic,
(and my old sims had also involved a number of more-complicated but more-realistic models)
but the points I want to make are that 
(1) we can often tell what will happen without need of a computer
(2) we can PROVE in this model that strategic-approval voting with the (U_A+U_B)/2 threshold,
has superior social-utility to both strategic Condorcet and IRV voting with any of several
strategies I have discussed and with or without allowing rank-equalities in votes, 
which lead to Condorcet and IRV electing the same winner as strategic plurality so
that they are not an improvement over plurality.
(3) But strategic approval with certain other voter strategies will not be better
than strategic plurality.
(4) If on the other hand our voters are assumed honest rather than strategic, then
honest range voting (meaning: give favorite=100, most-hated=0, and linerly interpolate
the others between)  has superior social-utility to honest Condorcet and IRV voting - says
the computer.

So: range voting is better for honest voters in this model.  It is better for strategic
voters in this model (with certain notions about the strategies the voters will use).
So put those theorems in your pipe, and smoke them.

wds