Draft:Bayesian regret

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Symbol opinion vote.svg Comment: Draft looks promising at this point. As I am not an admin, I cannot see the deleted version of the article. This new draft does needs to be substantially different. Draft needs more reliable sourcing as there was talk of WP:OR during discussion of deleted article on subject. Antonioatrylia (talk) 21:36, 7 August 2017 (UTC)

Bayesian regret is a term from game theory meaning the average difference between the average utility of a strategy and the ideal utility. To be precise in some context, it requires two further definitions: the domain of the average and the ideal for comparison. A similar concept is "voter satisfaction efficiency" (aka "expected voter satisfaction", or "social utility efficiency"), which is the same number divided by the ideal utility.

In voting systems theory[edit]

Refers to the average difference in social utility between the chosen candidate and the best candidate. It is only measurable if it is possible to know the voters' true numerical utility for each candidate - that is, in monte carlo simulations of virtual elections. The term Bayesian is somewhat a misnomer, really meaning only "average probabilistic"; there is no standard or objective way to create distributions of voters and candidates.

The Bayesian regret concept was recognized as useful (and used) for comparing single-winner voting systems by Bordley and Merrill, and it also was invented independently (?) by R.J.Weber. Bordley attributed it (and the whole idea of the usefulness of "social" utility, that is, summed over all people in the population) to John Harsanyi in 1955. Note that some of these authors instead used the name "social utility efficiency" which is the same thing as Bayesian Regret up to a linear transformation. However, those earlier studies are superseded by Smith, as they included a narrower range of voting systems.

Such simulations depend heavily on assumptions. The one assumption which particularly gets in the way of comparing voting systems is how many voters will vote tactically under each voting system. Thus, the simulation will at best only give a "best" regret number (if all voters vote honestly) and a "worst" (all voters voting tactically in a situation dominated by two preexisting parties) for every system in every set of scenarios. The real utility presumably lies in between these extremes.

Smith's simulation, over a variety of scenarios, showed that Range voting had the lowest regrets for either fully-honest or fully-tactical voters. Voting systems whose regret score with honest voting fell between these numbers (and thus might be better by this measure if they led to less strategy) include Borda count and various forms of Condorcet voting. Voting systems whose best score fell at or below the worst score for Range Voting were IRV, Plurality voting, Approval voting and various random-ballot options included for completion.

In economics[edit]

This term has been used to compare a random buy-and-hold strategy to professional traders' records. This same concept has received numerous different names, as the New York Times notes:

"In 1957, for example, a statistician named James Hanna called his theorem Bayesian Regret. He had been preceded by David Blackwell, also a statistician, who called his theorem Controlled Random Walks. Other, later papers had titles like 'On Pseudo Games', 'How to Play an Unknown Game', 'Universal Coding' and 'Universal Portfolios'".[1]

In machine learning[edit]

Refers to the average difference between an algorithm's performance and ideal performance, for instance on a classification task. Note that ideal performance is not perfect since the "true" classifications may be somewhat intermixed in all perceivable dimensions. See Multicategory Ã-Learning by Yufeng Liu and Xiaotong Shen


  1. ^ Kolata, Gina (2006-02-05). "Pity the Scientist Who Discovers the Discovered". The New York Times. ISSN 0362-4331. Retrieved 2017-02-27. 
  • Range Voting (PDF) by Warren D. Smith. After the mathematical advocacy of Range Voting, there is a good monte-carlo comparison of voting systems in virtual elections, which, despite a rudimentary approach to strategy and polling, gives interesting best-case (honest) and worst-case (overstrategic) social utilities for various systems.
  • Robert F. Bordley: A pragmatic method for evaluating election schemes through simulation, Amer. Polit. Sci. Rev. 77 (1983) 123-141.
  • Samuel Merrill: Making multicandidate elections more democratic, Princeton Univ. Press 1988.
  • Samuel Merrill: A comparison of the efficiency of multicandidate electoral systesm, Amer. J. Polit. Sci. 28,1 (1984) 23-48.