IDEAS home Printed from https://ideas.repec.org/p/hrv/faseco/3204826.html
   My bibliography  Save this paper

Conditional Universal Consistency

Author

Listed:
  • Fudenberg, Drew
  • Levine, David

Abstract

Players choose an action before learning an outcome chosen according to an unknown and history-dependent stochastic rule. Procedures that categorize outcomes, and use a randomized variation on fictitious play within each category are studied. These procedures are “conditionally consistent:†they yield almost as high a time-average payoff as if the player knew the conditional distributions of actions given categories. Moreover, given any alternative procedure, there is a conditionally consistent procedure whose performance is no more than epsilon worse regardless of the discount factor. We also discuss cycles, and argue that the time-average of play should resemble a correlated equilibrium.

Suggested Citation

  • Fudenberg, Drew & Levine, David, 1999. "Conditional Universal Consistency," Scholarly Articles 3204826, Harvard University Department of Economics.
  • Handle: RePEc:hrv:faseco:3204826
    as

    Download full text from publisher

    File URL: http://dash.harvard.edu/bitstream/handle/1/3204826/fudenberg_conditional.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Fudenberg Drew & Kreps David M., 1993. "Learning Mixed Equilibria," Games and Economic Behavior, Elsevier, vol. 5(3), pages 320-367, July.
    2. Fudenberg, Drew & Levine, David, 1998. "Learning in games," European Economic Review, Elsevier, vol. 42(3-5), pages 631-639, May.
    3. Jordan J. S., 1993. "Three Problems in Learning Mixed-Strategy Nash Equilibria," Games and Economic Behavior, Elsevier, vol. 5(3), pages 368-386, July.
    4. Sonsino, Doron, 1997. "Learning to Learn, Pattern Recognition, and Nash Equilibrium," Games and Economic Behavior, Elsevier, vol. 18(2), pages 286-331, February.
    5. Sanchirico, Chris William, 1996. "A Probabilistic Model of Learning in Games," Econometrica, Econometric Society, vol. 64(6), pages 1375-1393, November.
    6. Foster, Dean P. & Vohra, Rakesh, 1999. "Regret in the On-Line Decision Problem," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 7-35, October.
    7. Fudenberg, Drew & Levine, David K, 1993. "Self-Confirming Equilibrium," Econometrica, Econometric Society, vol. 61(3), pages 523-545, May.
    8. Fudenberg, Drew & Levine, David K., 1999. "An Easier Way to Calibrate," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 131-137, October.
    9. Sergiu Hart & Andreu Mas-Colell, 2013. "A Simple Adaptive Procedure Leading To Correlated Equilibrium," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 2, pages 17-46, World Scientific Publishing Co. Pte. Ltd..
    10. T.H. Chung, 2010. "Approximate Methods for Sequential Decision Making Using Expert Advice," Levine's Working Paper Archive 564, David K. Levine.
    11. P. Auer & N. Cesa-Bianchi & Y. Freund & R. Schapire, 2010. "Gambling in a rigged casino: The adversarial multi-armed bandit problem," Levine's Working Paper Archive 462, David K. Levine.
    12. Kalai, Ehud & Lehrer, Ehud & Smorodinsky, Rann, 1999. "Calibrated Forecasting and Merging," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 151-169, October.
    13. D. Blackwell, 2010. "Controlled Random Walks," Levine's Working Paper Archive 465, David K. Levine.
    14. Foster, Dean P. & Vohra, Rakesh V., 1997. "Calibrated Learning and Correlated Equilibrium," Games and Economic Behavior, Elsevier, vol. 21(1-2), pages 40-55, October.
    15. N. Megiddo, 2010. "On Repeated Games with Incomplete Information Played with Non-Bayesian Players," Levine's Working Paper Archive 480, David K. Levine.
    16. Y. Freund & R. Schapire, 2010. "A Decision Theoretic Generalization of On-Line Learning and an Application to Boosting," Levine's Working Paper Archive 570, David K. Levine.
    17. Nimrod Megiddo, 1979. "On Repeated Games with Incomplete Information Played by Non-Bayesian Players," Discussion Papers 373, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    18. Aoyagi, Masaki, 1996. "Evolution of Beliefs and the Nash Equilibrium of Normal Form Games," Journal of Economic Theory, Elsevier, vol. 70(2), pages 444-469, August.
    19. M. Feder & N. Mehrav & M. Gutman, 2010. "Universal Prediction of Individual Sequences," Levine's Working Paper Archive 567, David K. Levine.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Sergiu Hart & Andreu Mas-Colell, 2013. "A General Class Of Adaptive Strategies," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 3, pages 47-76, World Scientific Publishing Co. Pte. Ltd..
    2. Mannor, Shie & Shimkin, Nahum, 2008. "Regret minimization in repeated matrix games with variable stage duration," Games and Economic Behavior, Elsevier, vol. 63(1), pages 227-258, May.
    3. Michel Benaïm & Josef Hofbauer & Sylvain Sorin, 2006. "Stochastic Approximations and Differential Inclusions, Part II: Applications," Mathematics of Operations Research, INFORMS, vol. 31(4), pages 673-695, November.
    4. Eric Friedman & Scott Shenker & Amy Greenwald, 1998. "Learning in Networks Contexts: Experimental Results from Simulations," Departmental Working Papers 199825, Rutgers University, Department of Economics.
    5. Foster, Dean P. & Young, H. Peyton, 2003. "Learning, hypothesis testing, and Nash equilibrium," Games and Economic Behavior, Elsevier, vol. 45(1), pages 73-96, October.
    6. H. Peyton Young, 2007. "The Possible and the Impossible in Multi-Agent Learning," Economics Series Working Papers 304, University of Oxford, Department of Economics.
    7. Sergiu Hart & Andreu Mas-Colell, 2013. "A Simple Adaptive Procedure Leading To Correlated Equilibrium," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 2, pages 17-46, World Scientific Publishing Co. Pte. Ltd..
    8. Kalai, Ehud & Lehrer, Ehud & Smorodinsky, Rann, 1999. "Calibrated Forecasting and Merging," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 151-169, October.
    9. Fudenberg, Drew & Takahashi, Satoru, 2011. "Heterogeneous beliefs and local information in stochastic fictitious play," Games and Economic Behavior, Elsevier, vol. 71(1), pages 100-120, January.
    10. Germano, Fabrizio & Lugosi, Gabor, 2007. "Global Nash convergence of Foster and Young's regret testing," Games and Economic Behavior, Elsevier, vol. 60(1), pages 135-154, July.
    11. Nicolò Cesa-Bianchi & Gábor Lugosi & Gilles Stoltz, 2006. "Regret Minimization Under Partial Monitoring," Mathematics of Operations Research, INFORMS, vol. 31(3), pages 562-580, August.
    12. Olszewski, Wojciech, 2015. "Calibration and Expert Testing," Handbook of Game Theory with Economic Applications,, Elsevier.
    13. Dean P Foster & Peyton Young, 2006. "Regret Testing Leads to Nash Equilibrium," Levine's Working Paper Archive 784828000000000676, David K. Levine.
    14. Foster, Dean P. & Vohra, Rakesh, 1999. "Regret in the On-Line Decision Problem," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 7-35, October.
    15. Sergiu Hart & Andreu Mas-Colell, 2013. "Stochastic Uncoupled Dynamics And Nash Equilibrium," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 8, pages 165-189, World Scientific Publishing Co. Pte. Ltd..
    16. Benaïm, Michel & Hofbauer, Josef & Hopkins, Ed, 2009. "Learning in games with unstable equilibria," Journal of Economic Theory, Elsevier, vol. 144(4), pages 1694-1709, July.
    17. Ehud Lehrer & Eilon Solan, 2007. "Learning to play partially-specified equilibrium," Levine's Working Paper Archive 122247000000001436, David K. Levine.
    18. Karl Schlag & Andriy Zapechelnyuk, 2009. "Decision Making in Uncertain and Changing Environments," Discussion Papers 19, Kyiv School of Economics.
    19. Eddie Dekel & Yossi Feinberg, 2006. "Non-Bayesian Testing of a Stochastic Prediction," Review of Economic Studies, Oxford University Press, vol. 73(4), pages 893-906.
    20. Daron Acemoglu & Asuman Ozdaglar, 2011. "Opinion Dynamics and Learning in Social Networks," Dynamic Games and Applications, Springer, vol. 1(1), pages 3-49, March.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:hrv:faseco:3204826. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: . General contact details of provider: https://edirc.repec.org/data/deharus.html .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Office for Scholarly Communication (email available below). General contact details of provider: https://edirc.repec.org/data/deharus.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.