"BAYESIAN REGRET FOR DUMMIES"
Q. I was asked to explain "Bayesian regret" and
why (at least in my view) it is the "gold standard"
for comparing single-winner election methods.
OVERSIMPLIFIED INTO A NUTSHELL:
The "Bayesian regret" of an election method E is
the "expected avoidable human unhappiness"
caused by using E.
MORE PRECISE ANSWER:
Bayesian regret is gotten via this PROCEDURE:
1. Each voter has a personal
"utility" value for the election of each candidate.
(E.g., if Nixon is elected, then voter Dan Cooper will
acquire -55 extra lifetime happiness units.)
In a computer sim, the voters and candidates are artificial,
and the utility numbers are generated by
some randomized "utility generator" and assigned
artificially to each candidate-voter pair.
2. Now the voters vote, based both on their private utility
values, and (if they are strategic voters)
on their perception from "pre-election polls"
(also generated artificially in the sim, e.g. from
a random subsample of "people") of how
the other voters are going to act.
3. The election system E elects some winning candidate W.
4. The sum over all voters V of their utility for W, is
the "achieved societal utility."
5. The sum over all voters V of their utility for X,
MAXIMIZED over all candidates X, is
the "optimum societal utility" which would have been
achieved if the election system had magically chosen the
societally best candidate.
6. The difference between 5 and 4 is the "bayesian regret"
of the election system E, at least in this experiment.
It might be zero, but if E was bad or the election was unlucky for E, then
it will be positive.
We now redo steps 1-6 a zillion times
(i.e. running a zillion simulated elections) to find the
average Bayesian regret of election system E.
COMMENTS:
Bayesian regret of an election system E may differ if
1. vary the number of voters,
2. vary the number of candidates,
3. vary the kind of "utility generator",
4. use different kind of assumed "voter strategy", or
5. put different amount of "voter ignorance".
To describe the latter, we can put in
voter ignorance by artificially adding random noise to the
voter's private utility values, and then having the voter act
based on those distorted values. The higher the amplitude
of the noise, the more ignorance there is.
So there are at least 5 different "knobs" we can "turn" on our
machine for measuring the Bayesian Regret of an election method E.
RESULTS OF MY COMPUTER STUDY:
from http://math.temple.edu/~wds/homepage/works.html #56
This study measured Bayesian regrets for about 30 different election methods.
144 different combinations of "knob settings" were tried.
The amazing result is that, in all 144 scenarios, range voting
was the best (had lowest Bayesian regret, up to statistically insignificant
noise) in EVERY SINGLE ONE of those 144 with either honest voters,
or with strategic voters.
HERE IS A SIMPLIFIED TABLE
of results (from only 2 of the 144 scenarios, and only 10 of the voting systems).
(Read in constant-width font. Each tabulated Bayesian regret value is an average
over a million or more randomized simulated elections.)
column A: 5 candidates, 20 voters, random utilities.
column B: 5 candidates, 50 voters, utilities based on two "issues".
A B
magic optimum winner 0 0
honest range .04941 .05368
honest borda .13055 .10079
honest IRV .32314 .23786
honest plurality .48628 .37884
random winner 1.50218 1.00462
strategic range=approval .31554 .23101
strategic borda .70219 .48438
strategic plurality .91522 .61072
strategic IRV .91522 .61072
Incidentally, note that with strategic voters (at least using the strategy
I assumed here) strategic plurality and strategic IRV seem to
be the same! That is because of the devastating
THEOREM:
Generically (i.e. if no ties),
IRV and Plurality voting with strategic voters
will yield the same winner in a large election:
Namely the most popular among the two
pre-election poll "frontrunners"
will always win...
PROOF SKETCH:
For plurality voting, this was well known: strtaegic voters always vote
for one of the two perceived frontrunners since other votes
are extremely likely to be "wasted".
For IRV: the two poll-frontrunners will garner all the top-rankings from
strategic voters, thus never being eliminated until
the final round, whereupon the most popular one will win.
This is assuming a strategy where voters always rank one of the frontrunners top
and the other bottom to "maximally exaggerate"
and try to maximize their chances of affecting the election.
They consider it pointless to top-rank anybody else because that person
(they figure) has far tinier chance of winning.
(Note: the optimum strategy for IRV voting is not known, so my computer sim
was using this, non-optimum, IRV strategy, which however is usually a lot
better than honesty.)
QED.