[EM] Simulations with social welfare functions

[Simmons, Forest]

Jobst,
 
Thanks for doing these simulations and getting us thinking along these lines.
 
I wonder how Bucklin would fare in your simulations?  Or how about the quartile variation of Bucklin in which the "bar" is lowered simultaneously on the range style ballots until at least one candidate is rated above the bar on at least 75 percent of the ballots.  If this yields more than one winner, then eliminate winners by random ballot until there is only one left.
 
I like Liberal Fair Choice (LFC).  It works well in the example that Kevin Venzke always worried about:
 
49 C
24 B  (but sincere is B>A>C)
27 A>B>>C
 
No candidate is strongly defeated since the approval order is B>C>A, but more than 51/2 voters prefer C to B, and more than 51/2 prefer A to B, and more than 49/2 prefer A to C.
 
So the winner is chosen by random ballot.
 
What if we modified LFC by using MinOf2 to pick the winner from among the candidates that are not strongly defeated?
 
Or how about going beyond Gini by using MinOf3, or by using MinOf(K) for the largest K that distinguishes a winner, i.e. using random ballot to eliminate all but one candidate?
 
Could we modify LFC for the multiwinner case by relaxing the definition of "strongly defeated" appropriately?
 
For the N winner case, perhaps something like ...
 
Call x "strongly defeated" by y iff approval(y) > approval(x) and fewer than approval(y)/(N+1) voters prefer x to y.

First eliminate the strongly defeated candidates, and then use random ballot to eliminate all but N of the remaining candidates.
 
Something like that.
 
Keep us going on this!
 
Forest
 
From: Jobst Heitzig <heitzig-j at web.de>
Subject: [EM] Simulations with social welfare functions
To: election-methods at electorama.com
Message-ID: <1565735362 at web.de>
Content-Type: text/plain; charset=iso-8859-15

Hello all,

a week ago I suggested using social welfare functions (such as the Gini welfare function) to evaluate election methods.

Now I did some simulations of the following kind:

1. Draw n (e.g. 1000) voter and c (e.g. 3) candidate positions from a d-dimensional (e.g. 2) standard normal distribution.
2. Compute the "utility" u(x,i) of candidate x for voter i as a function of euclidean distance
   (e.g., use exp(-(distance/sigma)^2) for some sigma).
3. Assume that i approves of x iff u(x,i)>mean{u(y,i):y} (this is Weinstein's zero-info approval strategy).
4. Apply a number of competing election methods and compute the resulting social welfare functions.
5. Repeat this a large number of times (e.g. 5000)


The first simulation involved the methods Plurality, Approval, Range Voting, Borda, DFC, and Random Ballot.

Using the utilitarian welfare function (=ave. individual utilities), the methods performed roughly like this:

   Range Voting > Approval, DFC, Borda > Plurality >> Random Ballot

Using the Gini welfare function (=ave. min. of a pair of individual utilities) or similar social welfare functions, the picture was roughly this:

   Random Ballot > DFC, Range Voting > Approval, Borda, Plurality

These results did not much depend on n, c, or d.


In order to get a better quantitative measure of performance, I then added a method "Gini optimal" which determines the lottery that maximizes the Gini welfare function. Relative to the performance of "Gini optimal", the methods performed like this (depending on n, c, and d):

  Random Ballot: 90%-99%
  DFC, Range Voting: 80%-90%
  Approval, Borda, Plurality: 60%-80%


Of course, Random Ballot is not a practical method for several reasons, hence I next tried to find better methods which could compete with it here.
I added the following three methods:

Approval Threshold Random Ballot (ATRB):
>From all candidates which are approved by at least 1/3 of the voters, choose by drawing a random ballot. If no such candidate exists, elect the Approval Winner.

MinOf2:
Draw two range-style ballots at random and elect the candidate whose minimum range value on the two ballots is largest.

Liberal Fair Choice (LFC):
Call x "strongly defeated" by y iff approval(y) > approval(x) and fewer than approval(y)/2 voters prefer x to y.
>From all candidates not strongly defeated, choose by drawing a random ballot.

Relative to "Gini optimal", they performed like this:

  LFC, MinOf2: 90%-95%
  ATRB: 85%-90%


For these reasons, I have the impression that LFC is a very interesting method since it combines many nice features:
- Monotonicity, Clone-proofness, Pareto-efficiency
- Near-optimal social welfare
- Still, the election of extremist candidates can easily be avoided: Only twice the number of voters who support the extremist need to approve some common other candidate in order to make sure the extremist is strongly defeated.

Comments, suggestions?

Yours, Jobst

______________________________________________________________

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/ms-tnef
Size: 8206 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20060525/a8d6613f/attachment-0003.bin>