[EM] Simulations

[Richard Moore]

I have listed below the results of simulations of various
methods. First, I have some explanatory notes.

1. The standard for evaluating the winner of each trial is 
majority potential (MP), which I defined in an earlier post
as the number of pairwise victories a candidate scores 
against other candidates from a fixed "background" pool 
(which is substantially larger than the actual field in
each election). The background pool size for these sims was 
49 candidates, and each trial election featured five 
candidates randomly selected from the background field.
The 49 candidates are distributed evenly through a 2-D,
square-bounded region of "policy space".

2. There are 961 voters distributed evenly through the same
policy space region. Voter utilities for each candidate are
a linearly decreasing function of the L1 (city block)
distance between voter and candidate. I will follow this
up with a second set of results in which the voters are not
uniformly distributed, but that will take several hours to
run.

Candidate and voter distributions are both uniform and 
non-random -- i.e., all voters and candidates are equally
spaced at integer values of the two policy variables.

3. For Plurality, Borda, and Approval, I modeled strategic
voting as follows: I randomly designated two front runners
from the 5-candidate field. I created a strategy matrix
weighting the candidates by factors of Pii = 18 (i is a
front runner), Pii = 8 (i is not a front runner), Pij = -9
(i and j both front runners), Pij = -3 (only one of i and
j is a front runner), and Pij = -1 (neither i nor j is
a front runner). I multiplied this matrix by the voter's
utilities. In Plurality, I then selected the candidate
with the highest result; in Borda, I ranked the candidates
in descending order of the results; and in Approval, I
selected all candidates with positive results. The strategic
(non-zero-info) results for each method are listed in the
rows with "/NZI" in the heading. I did not try to model
strategic voting for IRV or Condorcet methods.

I originally tried to select front runners based on the
product of a candidate's MP and a random number, but the 
result of this technique was that the support for the 
top-rated candidate was, more often than not, boosted by 
front-runner status, and all three methods improved with 
strategic voting. Since this struck me as a dubious result, 
I decided random selection of front runners was a more
valid technique.

4. Methods evaluated are Random Choice, Random Ballot
(not exhaustive; if the Random Ballot results in a tie,
the tie is decided by Random Choice), IRV, Plurality (aka
Lone Mark), Plain Condorcet, SSD (if I have implemented it 
correctly), Borda, and Approval. For the two Condorcet 
methods, I used margins, not winning votes. Random Ballot
is used as the tie-breaker for the other methods (but in
IRV, I used Random Choice to break ties during elimination 
rounds, and Random Choice was used if there was a tie for
a defeat-dropping decision in Condorcet).

5. Reporting is in the form of a histogram, listing the
number of times the method picks the highest, 2nd highest,
3rd highest, and so on, based on the MP rating system
described above.

There were 4000 trials in this simulation. Comments follow 
the results.

WINNER MAJORITY POTENTIAL RANKING HISTOGRAMS FOR EACH METHOD

Random Choice Histogram:
	1: 926	2: 839	3: 834	4: 810	5: 591	
Random Ballot Histogram:
	1: 1449	2: 961	3: 774	4: 526	5: 290	
Plurality Histogram:
	1: 2602	2: 867	3: 373	4: 130	5: 28	
Plurality/NZI Histogram:
	1: 2002	2: 1144	3: 577	4: 239	5: 38	
IRV Histogram:
	1: 3299	2: 599	3: 96	4: 6	5: 0	
Plain Condorcet Histogram:
	1: 3871	2: 123	3: 5	4: 1	5: 0	
SSD Histogram:
	1: 3871	2: 123	3: 5	4: 1	5: 0	
Borda Histogram:
	1: 3662	2: 262	3: 67	4: 9	5: 0	
Borda/NZI Histogram:
	1: 3481	2: 436	3: 79	4: 4	5: 0	
Approval Histogram:
	1: 3646	2: 324	3: 29	4: 1	5: 0	
Approval/NZI Histogram:
	1: 3564	2: 398	3: 36	4: 2	5: 0	

Random Choice: While we might expect a flat histogram, that 
is not the case because there are often tied MP ratings for
candidates, meaning many elections do not have all ranks
represented. E.g., if two candidates are tied for first 
place MP, then second place is skipped.

Plurality: Only about 65% success rate for picking the top
candidate, dropping to 50% with strategic voting.

IRV: Better than I expected, with about an 82% success
rate.

PC and SSD: I didn't find any differences between these two
methods, and I've come to suspect there may not be any when
the voter distribution is uniform, though I can't prove that
conjecture. (I can prove it for the case where utilities are
based on L2 distances, but L1 yields behavior that is much 
more complex.) Top choice success rate is better than 95%.

Borda: Almost 92% success rate, dropping to 87% when 
strategic voting occurs. More immune to strategy than Plurality.

Approval: 91% success rate, dropping to 89% with strategic
voting, so this is the most stable of the NZI-tested methods.

  -- Richard