We propose a new and simple adaptive procedure for playing a game: "regret-matching." In this procedure, players depart from their current play with probabilities that are proportional to measures of regret for not having used other strategies in the past. It is shown that our adaptive procedure guarantees that, with probability one, the empirical distributions of play converge to the set of correlated equilibria of the game. To compute these regret measures, a player needs to know his payoff function and the history of play. We also offer a variation where every player knows only his own realized payoff history (but not his payoff function).
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
page. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
Length: Date of creation: 24 Mar 1997 Date of revision:
24 Mar 1997 Handle: RePEc:wpa:wuwpga:9703006
Note: January 1997. Revised: October 1997. Paper + 3 figures (postscript). Also available at URL below Contact details of provider: Web page: http://129.3.20.41
For technical questions regarding this item, or to correct its listing, contact: (EconWPA).
Find related papers by JEL classification: C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games D83 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Search, Learning, and Information
References listed on IDEAS Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
Roger B. Myerson, 1995.
"Dual Reduction and Elementary Games,"
Discussion Papers
1133, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
[Downloadable!]
Other versions:
Mertens, J.-F., 1986.
"Repeated games,"
CORE Discussion Papers
1986024, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
Cited by: (explanations, Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.) This item has more than 25 citations. To prevent cluttering this page, these citations are listed on a separate page.