[EM] A new simulation
Jobst Heitzig
heitzig-j at web.de
Sat Nov 1 17:33:31 PDT 2008
Hi folks,
I have recently done a large simulation in order to study the following
questions:
1. How does Random Ballot perform according to different measures of
social utility?
2. How probable is it that the option having the largest social utility
is a Condorcet Winner? And how likely would this option receive 100%
winning probability in FAWRB?
3. How probable is it that a compromise can be found which will receive
100% winning probability in FAWRB? And how good are such compromises
according to different measures of social utility?
Hoping for an interesting discussion of the results,
Jobst
Main results
------------
1. Random Ballot performs quite well: On average, the Random Ballot
lottery achieved 93.7% the total utility of the option with the largest
total utility, and 98.4% the Gini welfare value of the option with the
largest Gini welfare value.
In only 5% of all situations, this measure of relative performance
was less than 88.3% resp. 94.5%!
(See columns REL_RANDOM_BALLOT_TU_MEAN, REL_RANDOM_BALLOT_GINI_MEAN,
REL_RANDOM_BALLOT_TU_P5, and REL_RANDOM_BALLOT_GINI_P5 in the result file)
2. In about one in five [one in six] situations, the option having the
largest total utility [largest Gini value] was not a Condorcet Winner.
This means in particular that in all majoritarian methods (including
Condorcet and Range Voting), the "optimal" option was not likely to win
because some majority preferred a different option over it!
In FAWRB, the "socially optimal" options would receive 100% winning
probability only in about one in a thousand situations. This can be
interpreted to indicate that such a "unanimous" FAWRB-compromise will
usually have to be a negotiated compromise which combines several
options or is based on one option and redistributes utility by some
side-payment mechanism.
Note: The simulations did not check what the actual winning
probability in FAWRB would be, only whether it would be 100%.
3. However, in more than 77% of the situations, the assumed utility
transfer mechanism was able to construct a compromise option which would
receive 100% winning probability in FAWRB.
In these situations, the constructed compromise also had about 1%
more total utility on average and 7.7% more Gini value on average than
the best of the original options. In more than 95% of the cases, it had
a higher Gini value than any of the original options. This shows that
unanimous FAWRB-compromises are not only possible, but also efficient.
However, in only 42% of the situations the constructed compromise
would also beat all of the original options pairwise. This is due to the
fact that these compromises usually distribute some utility away from
the majority in order to compensate minorities. It also indicates that
majoritarian methods are not very good at electing really broad
compromises but rather elect centrist options which don't give much
utility to minorities.
Simulation methodology
----------------------
The simulation was based on the same utility model as in Warren's IEVS
simulation software (see http://www.rangevoting.org/IEVS/IEVS.c,
although I did not use that software but SAS), with one extension noted
in the text below:
1. N voters and M options were simulated to have a "position" in a
D-dimensional "issue" space, for different values of N, M, and D. The
positions were drawn as independent and identically distributed random
vectors.
Option positions were normally distributed. Voter positions either
followed the normal or a skewed "wacky" distribution (see Warren's
software for a definition of the latter).
2. For each voter and option, their distance was computed as the
LP-distance, for different values of P.
3. Individual utility values were computed as
B^(-d) / sqrt(.6D + (distance/B)²),
where the bandwidth B was either constantly 1 or determined as an
option-specific uniformly distributed value between .5 and 1.5. The
latter variant is an extension to Warren's model which tries to take
into account that some options may distribute utility more narrowly and
others more broadly.
4. For each option, both the total utility (=sum) and the Gini welfare
function (=expected minimum of the utility values assigned by two
voters) were computed as alternative measures of social utility.
The options maximizing these measures were determined and it was
checked whether these options were identical for both measures, whether
they were Condorcet Winners, and whether they would win with certainty
in FAWRB.
5. To measure the performance of Random Ballot, also the total utility
and Gini welfare function of the Random Ballot lottery were computed
(using expected utilities) and divided by the respective maximal values,
giving the relative total utility and relative Gini values of Random
Ballot.
It was also checked whether the Random Ballot lottery beat all other
options in pairwise comparison.
6. To simulate whether a good compromise option could be found which
would win with certainty in FAWRB, I assumed that utility could in
principle be transferred (this is a concept suggested by Warren several
times in the context of our discussion of different measures of social
utility):
For each option, a total number of "utility transfer units" was
computed as either the total utility, or the sum of squared individual
utilities, or the sum of exponential individual utilities (these
variants took into account that it is often argued that utility is not
proportional to the most common transfer unit, money, but rather to a
concave function of it, such as the square root or log).
It was then checked whether these "utility transfer units" could be
redistributed on the voters in such a way that each voter would prefer
the resulting "compromise option" so clearly to the Random Ballot
lottery that it would be elected with certainty in FAWRB. (Such a
constructed compromise option could be interpreted as implementing one
of the original options and then performing some side-payments.)
Whenever such a compromise existed, its total utility and Gini value
were computed and it was checked whether it would beat all other options
in pairwise comparison.
Parameter values and iterations
-------------------------------
The whole simulation was performed a thousand times for each of the 2880
possible combinations of the following parameter values:
- N = 10, 100, or 1000 voters
- M = 2, 3, 5, 10, or 20 options
- D = 1, 2, 5, or 10 dimensions
- P = 1, 2, 4, or infinity
- Normally or wacky distributed voter positions
- Constant or uniformly distributed option bandwidth
- Type of utility transfer units: linear, square, or exponential
Detailed results
----------------
You can download detailed results from
http://62.75.149.22/aggsimresults.zip (20 MB)
This is a zipped csv-file containing one line for each combination of
parameter values, with the following columns:
Categorizing columns:
N_VOTERS: N
N_ISSUES: D
VOTERS_TYPE: 1=normal, 2=wacky
OPTIONS_TYPE: 1=constant, 2=varying bandwidth
TU_TYPE: 1=linear, 2=square, 3=exponential utility transfer units
N_OPTIONS: M
LP: type of distance: 1=city-block, 2=euclidean, 4=L4, 0=maximum
(If one or more of these categorizing columns contain a missing value
(.), this means that the corresponding line represents a marginal of the
seven-dimensional parameter space, that is, that it summarizes
simulations for all values of the corresponding parameters, not just for
one particular parameter value. The first line in the file, e.g., is the
grand margin summarizing all 2880000 individual simulations)
Statistics columns:
_FREQ_: no. of simulations falling into this category
MEAN_OPTION_POS_MEAN: Mean option position, averaged over simulations.
MEAN_VOTER_POS_MEAN: Mean voter position, averaged over simulations.
RANDOM_BALLOT_ENTROPY_MEAN: Measure of "how random" the Random Ballot
lottery actually was, averaged over simulations.
MAX_TOTAL_UTU_MEAN: Maximum utility transfer units of a single option,
averaged over simulations.
NEEDED_TOTAL_UTU_MEAN: Amount of utility transfer units needed for a
FAWRB-compromise to exist, averaged over simulations.
HAVE_COMPROMISE_MEAN: Estimated probability for such a compromise to
exist (=fraction of simulations in which such a compromise existed)
MAX_TU_MEAN: Maximum total utility, averaged over simulations.
RANDOM_BALLOT_TU_MEAN: Total utility of Random Ballot, averaged over
simulations.
REL_RANDOM_BALLOT_TU_MEAN: Total utility of Random Ballot divided by
maximum total utility, averaged over simulations.
TU_MAXIMIZER_WINS_IN_FAWR_MEAN: Estimated probability that the option
with the largest total utility would win in FAWRB with certainty
(=fraction of simulations in which this was the case)
COMPROMISE_TU_MEAN: Total utility of the FAWRB-compromise, averaged over
simulations in which such a compromise existed.
REL_COMPROMISE_TU_MEAN: Total utility of the FAWRB-compromise divided by
maximum total utility, averaged over simulations in which such a
compromise existed.
COMPROMISE_HAS_MAX_TU_MEAN: Estimated probability that the
FAWRB-compromise has a larger total utility than any of the original
options (=fraction of simulations in which this was the case)
MAX_GINI_MEAN,
GINI_MAXIMIZER_WINS_IN_FA_MEAN,
RANDOM_BALLOT_GINI_MEAN,
REL_RANDOM_BALLOT_GINI_MEAN,
COMPROMISE_GINI_MEAN,
REL_COMPROMISE_GINI_MEAN,
COMPROMISE_HAS_MAX_GINI_MEAN:
Analogous statistics using the Gini welfare function instead of total
utility.
TU_GINI_MAXIMIZERS_EQUAL_MEAN: Estimated probability that the same
option maximizes both the total utility and the Gini value (=fraction of
simulations in which this was the case)
PCT_BEATEN_BY_RANDOM_BALL_MEAN: Percentage of options pairwise beaten by
the Random Ballot lottery, averaged over simulations.
RANDOM_BALLOT_BEATS_ALL_MEAN: Estimated probability that the Random
Ballot lottery beats all options pairwise (=fraction of simulations in
which this was the case)
PCT_BEATEN_BY_TU_MAXIMIZE_MEAN: Percentage of options pairwise beaten
(or identical to) the option having the largest total utility, averaged
over simulations.
TU_MAXIMIZER_BEATS_ALL_MEAN: Estimated probability that the option
having the largest total utility beats all other options pairwise
(=fraction of simulations in which this was the case)
PCT_BEATEN_BY_GINI_MAXIMI_MEAN: Percentage of options pairwise beaten
(or identical to) the option having the largest Gini value, averaged
over simulations.
GINI_MAXIMIZER_BEATS_ALL_MEAN: Estimated probability that the option
having the largest Gini value beats all other options pairwise
(=fraction of simulations in which this was the case)
PCT_BEATEN_BY_COMPROMISE_MEAN: Percentage of options pairwise beaten by
the FAWRB-compromise lottery, averaged over simulations in which such a
compromise existed.
COMPROMISE_BEATS_ALL_MEAN: Estimated probability that the
FAWRB-compromise beats all original options pairwise (=fraction of
simulations in which this was the case)
..._STDDEV: the same measures not averaged but their standard deviation.
..._MIN: minimum values of all these measures
..._P5: 5th percentiles of their distributions
..._Q1: 1st quartiles
..._MEDIAN: medians
..._Q3: 3rd quartiles
..._P95: 95th percentiles
..._MAX: maximum values
SAS Code
--------
proc iml worksize=1000000000; /*1GB*/
file log;
n_iterations=1000;
pi = constant('PI');
utility = j(1,5,.);
create sasuser.simresult var {
n_voters n_issues voters_type options_type
tu_type n_options lp iteration
mean_option_pos
mean_voter_pos
random_ballot_entropy
max_total_utu
needed_total_utu
have_compromise
max_tu
random_ballot_tu rel_random_ballot_tu
tu_maximizer_wins_in_fawrb
compromise_tu rel_compromise_tu compromise_has_max_tu
max_gini
gini_maximizer_wins_in_fawrb
random_ballot_gini rel_random_ballot_gini
compromise_gini rel_compromise_gini compromise_has_max_gini
tu_gini_maximizers_equal
pct_beaten_by_random_ballot random_ballot_beats_all
pct_beaten_by_tu_maximizer tu_maximizer_beats_all
pct_beaten_by_gini_maximizer gini_maximizer_beats_all
pct_beaten_by_compromise compromise_beats_all
};
had_example1=0;
do _nv=1 to 3; /*1..3*/
put "_nv" _nv;
do _ni=1 to 4 /*1..4*/;
put "_ni" _ni;
n_voters = {10 100 1000}[_nv];
n_issues = {1 2 5 10}[_ni];
nvi = n_voters#n_issues; a = 1:nvi; b = (2#a-1)#pi/4/nvi;
wkc = shape((-1)##a # cos(b),n_voters,n_issues);
wks = shape(sin(b),n_voters,n_issues);
do voters_type=1 to 2; /*1..2*/
put "voters_type" voters_type;
do options_type=1 to 2;
do tu_type=1 to 3;
put "tu_type" tu_type;
do _no=1 to 5; /*1..5*/
do _lp=1 to 4; /*1..4*/
n_options = {2 3 5 10 20}[_no];
lp = {1.0 2.0 4.0 0.0}[_lp];
one=j(n_voters,n_options,1);
do iteration=1 to n_iterations;
/* random normal option and voter positions: */
option_pos=j(n_issues,n_options,.);
call randgen(option_pos,'NORMAL');
if options_type = 2 then do;
option_width=j(n_issues,n_options,.);
call randgen(option_width,'UNIFORM');
option_width = .5+option_width;
inv_option_width = 1/option_width;
end;
if voters_type=1 then do;
voter_pos=j(n_voters,n_issues,.);
call randgen(voter_pos,'NORMAL');
end; else do; /* wacky voter pos.: */
voter_class=j(n_voters,n_issues,.);
voter_norm1=voter_class;
voter_norm2=voter_class;
call randgen(voter_class,'UNIFORM');
call randgen(voter_norm1,'NORMAL');
call randgen(voter_norm2,'NORMAL');
voter_class = (3#voter_class<1)-(3#voter_class>=2);
voter_pos = voter_class#wkc +
(voter_class^=0)#sqrt(1+voter_class#3/5)#wks#voter_norm1
+
(voter_class=0)#1.21129#((voter_norm1<>voter_norm2)-1/sqrt(pi));
end;
mean_option_pos = option_pos[:,:];
mean_voter_pos = voter_pos[:,:];
/* Lp distances: */
dist_to_the_p=j(n_voters,n_options,0);
factor=j(1,n_options,1);
do i=1 to n_issues;
if options_type = 1
then abs_diff = abs(one#option_pos[i,]-one#voter_pos[,i]);
else do;
abs_diff =
abs(one#option_pos[i,]-one#voter_pos[,i])#inv_option_width[i,];
factor = factor#inv_option_width[i,];
end;
if lp>0
then dist_to_the_p = dist_to_the_p + abs_diff##lp;
else dist_to_the_p = dist_to_the_p <> abs_diff;
end;
/* utilities: */
if options_type = 1
then utility =
1/sqrt(.6*n_issues+dist_to_the_p##(2/(lp+(lp=0))));
else utility =
factor#((.6*n_issues+dist_to_the_p##(2/(lp+(lp=0))))##(-.5));
/* favourites and max. utilities: */
favourite = utility[,<:>];
favourite_utility = utility[,<>];
/* total utility and Gini per option: */
tu = utility[+,];
uranks = utility; do x=1 to n_options; uranks[,x] =
rank(utility[,x]); end;
gini = ((2#(n_voters-uranks)+1)#utility)[+,]/(n_voters##2);
max_tu = tu[,<>];
max_gini = gini[,<>];
tu_maximizer = tu[,<:>];
gini_maximizer = gini[,<:>];
/* random ballot probabilities and utilities: */
random_ballot_prob =
(utility=(one#favourite_utility))[+,]/n_voters;
random_ballot_entropy =
-(random_ballot_prob#log(random_ballot_prob+(random_ballot_prob=0)))[,+];
random_ballot_utility = (random_ballot_prob#utility)[,+];
random_ballot_tu = random_ballot_utility[+,];
rel_random_ballot_tu = random_ballot_tu/max_tu;
random_ballot_gini =
((2#(n_voters-rank(random_ballot_utility))+1)#random_ballot_utility)[+,]/(n_voters##2);
rel_random_ballot_gini = random_ballot_gini/max_gini;
/* min. compromise utility per voter: */
min_compromise_utility =
(favourite_utility+4#random_ballot_utility)/5;
tu_gini_maximizers_equal = (tu_maximizer=gini_maximizer);
tu_maximizer_wins_in_fawrb =
((utility[,tu_maximizer]>min_compromise_utility)[><,]=1);
gini_maximizer_wins_in_fawrb =
((utility[,gini_maximizer]>min_compromise_utility)[><,]=1);
/* total utility transfer units per option: */
/* needed utility transfer units for unanimous compromise: */
/* total utility of unanimous compromise: */
if tu_type=1 then do;
total_utu = tu;
max_total_utu = total_utu[,<>];
needed_utu = min_compromise_utility;
needed_total_utu = needed_utu[+,];
compromise_utility =
needed_utu+(max_total_utu-needed_total_utu)/n_voters;
end; else if tu_type=2 then do;
total_utu = ((utility+10)##2)[+,];
max_total_utu = total_utu[,<>];
needed_utu = (min_compromise_utility+10)##2;
needed_total_utu = needed_utu[+,];
compromise_utility =
sqrt(needed_utu+(max_total_utu-needed_total_utu)/n_voters)-10;
end; else if tu_type=3 then do;
total_utu = exp(utility)[+,];
max_total_utu = total_utu[,<>];
needed_utu = exp(min_compromise_utility);
needed_total_utu = needed_utu[+,];
compromise_utility =
log(needed_utu+(max_total_utu-needed_total_utu)/n_voters);
end;
total_utu_maximizer = total_utu[,<:>];
/* unanimous compromise exists: */
have_compromise = (max_total_utu>needed_total_utu);
compromise_tu = ifn(have_compromise,compromise_utility[+,],.);
compromise_gini =
ifn(have_compromise,((2#(n_voters-rank(compromise_utility))+1)#compromise_utility)[+,]/(n_voters##2),.);
rel_compromise_tu =
ifn(have_compromise,(compromise_tu)/(max_tu),.);
rel_compromise_gini =
ifn(have_compromise,(compromise_gini)/(max_gini),.);
compromise_has_max_tu =
ifn(have_compromise,compromise_tu>max_tu,.);
compromise_has_max_gini =
ifn(have_compromise,compromise_gini>max_gini,.);
/* options beaten by total utility/Gini maximizers or
compromise: */
beaten_by_random_ballot =
((one#random_ballot_utility>=utility)[:,]>.5);
beaten_by_tu_maximizer =
((one#utility[,tu_maximizer]>=utility)[:,]>.5);
beaten_by_gini_maximizer =
((one#utility[,gini_maximizer]>=utility)[:,]>.5);
beaten_by_compromise =
ifn(have_compromise,((one#compromise_utility>=utility)[:,]>.5),.);
pct_beaten_by_random_ballot = 100#beaten_by_random_ballot[,:];
pct_beaten_by_tu_maximizer = 100#beaten_by_tu_maximizer[,:];
pct_beaten_by_gini_maximizer = 100#beaten_by_gini_maximizer[,:];
pct_beaten_by_compromise =
ifn(have_compromise,100#beaten_by_compromise[,:],.);
random_ballot_beats_all = (pct_beaten_by_random_ballot=100);
tu_maximizer_beats_all = (pct_beaten_by_tu_maximizer=100);
gini_maximizer_beats_all = (pct_beaten_by_gini_maximizer=100);
compromise_beats_all =
ifn(have_compromise,(pct_beaten_by_compromise=100),.);
append;
end;
end; end; end; end; end;
end; end;
quit;
proc means data=sasuser.simresult(drop=iteration) noprint qmethod=p2;
class n_voters n_issues voters_type options_type tu_type n_options lp;
output mean= std= min= p5= q1= median= q3= p95= max=
out=sasuser.aggsimresults / autoname;
run;
More information about the Election-Methods
mailing list