Bayesian Regret of Single-Winner Election Methods as one Big Fat Equation

People wanted to see "the formula" for Bayesian Regret. Actually, I'd never written the whole thing all in one whacking big equation before. But doing so has educational value, so here goes:

Let's unpack that:

C Is the set of candidates, and |C| is its cardinality (i.e. the number of candidates).
V Is the set of voters, and |V| is its cardinality.
E Is the election method, and BR(E) is its Bayesian Regret [and the whole point of the formula is to tell you how to calculate BR(E)].
S Denotes the strategy used by the voters to choose their votes. (For example, S could be "honest voting." A more-sophisticated S might be "a 53-47 mix of 'artificially demote my favorite's top rival to bottom' with 'honest'.") Note that BR depends upon S as well as E.
M Denotes the probability measure (on the space of utilities). Note that BR depends upon M as well as E.
Uv(c) Denotes the utility (a real number) to voter v of the event "candidate c wins the election."
WU,S(E) Denotes the winner (which is a candidate in C) of the election that would happen using election method E, assuming that the voters employ voting strategy S, and that the utilities they have for electing the candidates are described by U.
The sum over voters ∑v The purpose of this sum is to compute the total regret for all of society, of the event "W(E) gets elected" versus the optimum possible event "c gets elected" where c is the utility-maximizing candidate.
The max over candidates maxc Its purpose is to make sure we compute the regret with respect to the best possible winner. Note that because of this, the sum always has nonnegative value, causing BR(E)≥0 for every election method E.
The integration ∫...dM(U) The purpose of this integration is to find the expected regret over the entire probability-space of all possible election scenarios, using the correct probability measure M. This space is |V|·|C|-dimensional (and hence the integration really is a multiple integration of that dimensionality) because location within it is described by |V|·|C| utility values, one for each voter-candidate pair.

Good election methods E are those with small regret BR(E).

It is possible by means of this formula and "Monte Carlo integration" on a computer, to evaluate (as a number) BR(E) for any given election method E, approximately to any desired number of decimal places of accuracy, provided you know |C|, |V|, S, and M and you have a fast-enough computer. And if you do not know those things you still can try different simplified "models" for them and see what happens – hopefully the best election methods will just be good in a way fairly insensitive to modeling assumptions. (That pretty much happens with range voting.)

This hope will not necessarily be fulfilled, but then you'll be able to see for which kinds of scenarios we get large regret. For example, if in 3-candidate elections with cherry-flavored dishonest/strategic voting, some election method E suffers enormous regret, then the computer and this formula would have found that out for us, allowing E's designer to now try to modify E to make it perform better under those circumstances.

The formula also (if E, M, and S are simple enough) can sometimes make it possible to just do the integral exactly using the human mind (not a computer). Both these things have been done.

Return to main page