[EM] Simulations with social welfare functions

[Jobst Heitzig]

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 less 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

______________________________________________________________
Verschicken Sie romantische, coole und witzige Bilder per SMS!
Jetzt bei WEB.DE FreeMail: http://f.web.de/?mc=021193