Game theory "Bayesian Regret" is something different. In voting, it's "VSE"

In 2000, Warren Smith used the term “Bayesian Regret” to talk about the expected gap in utility between the outcome of a given voting method over a set of candidates and the highest-utility candidate from that set. This concept of a utilitarian “regret” measure of voting quality was not original to him; for instance, it had already been used by Bordley 1983 and Merrill 1984. But these earlier authors had simply called it “regret”; it was Smith who added the word “Bayesian”.

Smith’s work was important and groundbreaking. He was much more systematic than earlier authors in applying this concept to various voting methods and various voter models. But I’m writing here not about the value of the concept itself, which I think is beyond debate, but simply about the term “Bayesian regret”.

The word “Bayesian”, of course, refers to Rev Thomas Bayes. He was many things, including a utilitarian philosopher; but the adjective “Bayesian” is generally understood to refer to the statistical approach deriving from his fundamental theorem on conditional probabilities (and, in its modern form, on conditional distributions). Baysianism involves taking a prior probability or distribution, conditioning it on some event (usually an observation), and obtaining a posterior probability or distribution. But in Smith’s “Bayesian Regret”, there is no conditioning going on; there is only a model (that is, distribution) of voter utility and behavior, and a consequent expected utility.

Now, it’s true, the term “Bayesian Regret” has been used in game theory. But as far as I can tell the beginning of such use is not until Woodroofe 2004, who actually said “Bayes regret” instead. Note that this is not the same concept as used by Smith; Woodrofe (and later literature in this vein, such as Bubeck & Sellke 2019, who do say “Bayesian” rather than “Bayes”) was talking about the regret of an explicitly Bayesian strategy, not the simple utilitarian regret of an arbitrary strategy as Smith was.

(Perhaps worthy of mention here is Tomás 1999, an article centered around contrasting a Bayesian model of behavior and a regret model of behavior in explaining equilibria in a coordination game. This article uses both “Bayesian” and “regret” many times, but never connects them as a single concept.)

It seems possible to me that the phrase “Bayesian regret” had been said by some game theorist before 2000, so I’m ready to believe anything Smith might say about whether he invented it himself or whether he used an existing term. I’m simply arguing here that it is a misnomer.

But of course, as I mentioned above, the concept is important. In fact, I’d say it’s fundamental to the project of voting method reform. So we need a term.

As people on this list probably know, I have invented another term for this concept: “Voter satisfaction efficiency”, or VSE. I understand that this term lacks the explicit callback to the broad game-theory literature on “regret”. However, I think it’s better-suited to a reform movement; clearly referring to a rigorously-defined numeric measure but far more understandable at first hearing.

I therefore encourage this community to use the term “VSE”. Smith is still the foundational figure in applying this concept systematically, and the numbers in his 2000 paper should still be understood as examples of VSE. My later VSE calculations still owe this large intellectual debt to Smith. This is not about whose models are better; this is merely about using one correct and easy-to-understand term for an important concept.

Bibliography:

Bordley, R. F. A Pragmatic Method for Evaluating Election Schemes through Simulation. American Political Science Review 77 , 123–141 (1983).

Bubeck, S. & Sellke, M. First-Order Bayesian Regret Analysis of Thompson Sampling. arXiv:1902.00681 [cs, stat] (2019).

Merrill, S. A Comparison of Efficiency of Multicandidate Electoral Systems. American Journal of Political Science 28 , 23 (1984).

Smith, W. D. Range Voting . (2000).

Tomás, J. - REGRET THEORY AND THE PROVISION OF BINARY PUBLIC GOODS. EXPERIMENTAL ANALYSIS. (1999).

Woodroofe, M. An asymptotic minimax determination of the initial sample size in a two-stage sequential procedure . A Festschrift for Herman Rubin 228–236 (Institute of Mathematical Statistics, 2004). doi:10.1214/lnms/1196285393.

1 Like

I found an older possible reference for “Bayesian Regret” in game theory: Hannan, J. (1957). Approximation to Bayes risk in repeated play. In Contributions to the Theory of Games, vol. 3. Annals of Mathematics Studies 39 97–139. Princeton Univ. Press, Princeton, NJ. I’m only able to access this through Google Books right now, so I can see that it has plenty of discussion of both Bayesian strategies (that is, based on conditioning and posteriors — unlike in Smith 2000), and of regret (in a expected utility sense). I’m not able to see if it ever uses the phrase “Bayesian Regret”. However, there is a 2006 NYT article that claims that “James Hanna” (misspelled author’s name) used the term “Bayesian regret” in that article. So it seems likely he did.

Anyway, none of this changes my main point. The term BR is a valid one in game theory, but it is not the same thing that Smith was talking about in voting theory.

(Kolata, Gina (2006-02-05). “Pity the Scientist Who Discovers the Discovered”. The New York Times . ISSN 0362-4331.)

And “VSE” is a rename of Social Utility Efficiency