"Bayesian Regret for dummies"

(Executive Summary)

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.

Mathematical definition.

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 simulation, 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 within the simulation, e.g. from a random subsample of "people") of how the other voters are going to act.
   (Note. Some people here have gotten the wrong impression that this is assuming that voters will be "honest" or that we are assuming that honest range voters will use candidate-utilities as their candidate-scores. Other people thought we insisted on i.i.d. normal random numbers as utility values [or that some other specific randomized utility generator was insisted upon]. All those impressions are incorrect; these assumptions are not made.)
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 if this election was unlucky for E, then it will be positive because W and X will be different candidates.

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: The Bayesian regret of an election system E may differ if we

1. Vary the number of voters,
2. Vary the number of candidates,
3. Vary the kind of "utility generator" (e.g. could be based on different numbers of "issues" with different methods for generating the locations of the candidates in "issue space"),
4. Use different kinds of assumed "voter strategy" (possibly including "honesty"), and/or try different mixes of honest & strategic voters in the pool, or
5. Put different amounts of "voter ignorance".

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 the computer simulation study: (paper #56 here). This study measured Bayesian regrets for about 30 different election methods. 720 different combinations of "knob settings" were tried. The amazing result is that, in all 720 scenarios, range voting was the best (had lowest Bayesian regret, up to statistically insignificant noise). We repeat: range was the best in every single one of those 720 with either honest voters, or with strategic voters.

Here is a simplified table of results (from only 2 of the 720 scenarios, and only 10 of the voting systems). (Each tabulated Bayesian regret value is an average over a million or more randomized simulated elections.) Some more BR data. And some more BR data as a picture (taken from W.Poundstone's book; also available in black and white).

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 (instant runoff)  .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 voting-strategy assumed by the simulation) 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: strategic voters always vote for one of the two perceived frontrunners since other votes are extremely likely to be "wasted." For IRV: we again assume strategic voters will rank their favorite among the two pre-election poll "frontrunners" top, as a strategic move to maximize their vote's impact and prevent it from being wasted. [This assumption about strategic voter behavior really should have been stated in the theorem statement.] (See this example or this one to convince yourself that kind of strategy often is the unique strategically-sensible vote in the IRV system as well as many other ranked-ballot systems, and see this for data indicating the vast majority of Australian IRV voters act this way – if ≥75% act this way the theorem follows, but the data indicates 80-95% act this way.) Then 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. (Note: actually the optimum strategy for IRV voting is not known, so my computer sim and this here theorem are assuming the "strategic voters" use this simple and not-always-optimum, IRV strategy, which however is usually a lot better than honesty, indeed see this mathematical proof it asymptotically always is optimum strategy in a random-election mathematical model subject to certain kinds of limited voter knowledge about the others.) QED.

Remark. This theorem also works for Condorcet voting (under same assumptions about voter behavior).

Where have we seen Bayesian regret before?

Bayesian "regret" (also called "loss") is just the maximum possible utility minus the Bayesian "expected utility." This is not a new concept. It dates back to the earliest days of statistics (1800s) and it has been used in at least a dozen papers on non-voting-related subjects. The only thing "new" here is applying this well known concept to voting methods. And that idea also was thought of by others besides me, e.g. Merrill and Bordley.

View of bad decision-quality as a "tax"

Let's make a quick estimate to translate this into pocketbook terms.

Suppose thanks to a poor voting method, our elections 5% of the time make avoidable bad decisions. That has an effect analogous to a 5% tax on society. Unlike a real tax, though, this tax does not get used for any useful purpose, it just gets wasted. And furthermore this is a stupid waste – that could have been trivially avoided by adopting better voting systems. Over time, that 5% keeps adding up and up. After a century of annual compounding, 5% interest would represent a multiplicative factor of 132. That is, your country, by the trivially easy move of adopting (versus not adopting) a better voting method, would under this estimate be one hundred and thirty two times richer. If however this 5% bad-decision rate were only equivalent to a 1% tax, then we'd only get 2.7 times richer. Either way, this is a massive improvement for very little effort.

Return to main page