[EM] Simulation results (Approval, utility, Schulze efficiency)

[Kevin Venzke]

Hi all,

I've been sitting on this for a while, but I'm thinking I'll post it now:


Here are some results from the simulation I recently wrote about:

(Description of it:)
1. It generates randomly-sized factions, and their sincere utilities for every candidate.
2. The sincere Schulze winner is found.  The complete rankings are derived from the utilities.  
(Sincere ties in utility are very rare.)
3. The Approval winner is found according to several methods for generating odds.  Every voter 
uses "better than expectation" strategy.  This means that they approve every candidate for whom 
their utility is greater than their expectation for the election.  A voter's expectation is the 
sum of (voter's utility for J)*(odds of J winning) for every candidate J.
4. Both Schulze and Approval ties are resolved in favor of candidates with earlier letters.
5. The simulation reports which of Schulze and Approval elected a candidate with higher average 
utility, or whether they picked the same candidate.  It keeps track of this information, as
well as the average absolute gain in utility over the Schulze result.

Here are the methods for generating Approval ballots:
"Two Evils": Every voter believes that candidates A and B have 50% odds each of winning, and that 
every other candidate has 0%.
"First Preference Proportion": Every voter knows every other voter's sincere favorite, and 
believes that each candidate's odds of winning are equal to the proportion of voters whose 
favorite they are.
"Utility Maximizer Known": Every voter knows which candidate has the highest average utility, and 
believes that this candidate has a 90% chance of winning, with the other 10% divided evenly among 
the other candidates.
"Schulze Winner Known": Every voter knows which candidate is the sincere Schulze winner, and 
believes that this candidate has a 90% chance of winning, with the other 10% divided evenly among 
the others.
"Zero-Info": Every voter believes that every candidate has an equal chance of winning.
"Acceptables": No odds.  Every voter votes as though their expectation is equal to 50 (the maximum

being 100).  This means they could approve all or none of the candidates.
"Bullet-Voting": Every voter bullet-votes for their favorite.  (Donald Davison's recommended 
Approval strategy.)
"Random Candidate": A candidate wins at random.  (Not really Approval.)

For the following results, there were always five factions and 10,000 trials.  I did five and 
seven candidates with each of the above.

The format is:
Method: Number of candidates:
percentage of scenarios where Approval winner had higher average utility than the Schulze winner,
percentage where Schulze's winner had higher than Approval's,
percentage where the two agreed on a candidate,
average absolute utility gain of Approval's result over Schulze's.
(Again, utility ranges from 0 to 100.)

Two Evils: 5: 17.65, 26.51, 55.84, -1.43
Two Evils: 7: 20.93, 32.67, 46.40, -1.895
First Pref Proportion: 5: 16.64, 15.25, 68.11, +.095
First Pref Proportion: 7: 21.46, 21.72, 56.82, -.042
Util Maxer Known: 5: 25.38, 4.81, 69.81, +1.55
Util Maxer Known: 7: 31.03, 4.49, 64.48, +2.07
Schulze Winner Known: 5: 5.86, 4.64, 89.50, +.102
Schulze Winner Known: 7: 6.76, 5.44, 87.80, +.165
Zero-Info: 5: 22.90, 21.83, 55.27, +.203
Zero-Info: 7: 26.79, 27.48, 45.73, -.004
Acceptables: 5: 23.17, 24.43, 52.40, -.06
Acceptables: 7: 26.23, 26.93, 46.84, -.09
Bullet-Voting: 5: 7.07, 18.86, 74.07, -1.78
Bullet-Voting: 7: 7.78, 25.80, 66.42, -2.86
Random Candidate: 5: 8.96, 70.49, 20.55, -14.83
Random Candidate: 7: 8.55, 77.12, 14.32, -17.04

Based on these absolute utility gain figures, it seems I haven't included an Approval scenario 
where the "greater utility" argument for Approval looks compelling.  My original reason for 
writing this simulation was to look into that.  (It's probably worth noting the two Approval 
scenarios where the utility gain actually increased with the addition of two candidates: Schulze 
Winner Known and Util Maxer Known.)

It seems more interesting to look at the "Schulze efficiency" of these Approval scenarios.  To 
sort them:

Five candidates:
Schulze (100%), Schulze Winner Known (89.5%), Bullet-Voting (74%), Util Maxer Known (70%), FP 
Proportion (68%), Two Evils (55.8%), Zero-Info (55.3%), Acceptables (52.4%), Random Candidate 
(20%).

Seven candidates:
Schulze (100%), Schulze Winner Known (88%), Bullet-Voting (66%), Util Maxer Known (64%), FP 
Proportion (57%), Acceptables (46.8%), Two Evils (46.4%), Zero-Info (45.7%), Random Candidate 
(14%).

It's surely a fluke that "Two Evils" outperforms "Zero-Info" here.  I have to doubt that random 
information could be better than none at all.

Any thoughts?


Kevin Venzke
stepjak at yahoo.fr



	

	
		
Yahoo! Mail : votre e-mail personnel et gratuit qui vous suit partout ! 
Créez votre Yahoo! Mail sur http://fr.benefits.yahoo.com/

Dialoguez en direct avec vos amis grâce à Yahoo! Messenger !Téléchargez Yahoo! Messenger sur http://fr.messenger.yahoo.com