Learning in Games

19 Feb 2012 10:27

---

See also Collective Cognition; Evolutionary Economics; Low-Regret Learning; Machine Learning, Statistical Inference and Induction; the Minority Game; Sequential Decisions Under Uncertainty; Universal Prediction Algorithms

Recommended:
• Jenna Bednar and Scott Page, "Can Game(s) Theory Explain Culture? The Emergence of Cultural Behavior Within Multiple Games", Rationality and Society 19 (2007): 65--97 [PDF preprint via Prof. Bednar]
• Lawrence E. Blume and David Easley
  • "If You're So Smart, Why Aren't You Rich? Belief Selection in Complete and Incomplete Markets," SFI Working Paper 01-06-031
  • "Optimality and Natural Selection in Markets," SFI Working Paper 98-09-0 82
• Tilman Börgers and Rajiv Sarin, "Learning Through Reinforcement and Replicator Dynamics", Journal of Economic Theory 77 (1997): 1--14
• Vivek S. Borkar, "Reinforcement Learning in Markovian Evolutionary Games", Advances in Complex Systems 5 (2002): 55--72
• Nicolo Cesa-Bianchi and Gabor Lugosi, Prediction, Learning, and Games [Mini-review]
• Christophe Chamley, Rational Herds: Economic Models of Social Learning
• Ido Erev and Alvin E. Roth, "Simple Reinforcement Learning Models and Reciprocation in the Prisoner's Dilemma Game", pp. 215--232 in Gigerenzer and selten (eds.), Bounded Rationality
• Dean P. Foster and H. Peyton Young, "Learning, hypothesis testing, and Nash equilibrium," Games and Economic Behavior 45 (2003): 73--96 [pdf]
• Herbert Gintis, Game Theory Evolving: A Problem-Centered Introduction to Modeling Strategic Interaction
• Joseph Y. Halpern, Rafael Pass, "Iterated Regret Minimization: A More Realistic Solution Concept", arxiv:0810.3023 [Somewhat astonishingly, does mention the huge literature on low-regret learning]
• Ariel Rubinstein, Modeling Bounded Rationality [Review: O docta simplicitas!]
• Timothy C. Salmon, "An Evaluation of Econometric Models of Adaptive Learning", Econometrica 69 (2001): 1597--1628
• Larry Samuelson (no relation of the Samuelson), Evolutionary Games and Equilibrium Selection
• José M. Vidal and Edmund H. Durfee, "Predicting the Expected Behavior of Agents That Learn About Agents: The CLRI Framework," cs.MA/0001008
• H. Peyton Young, Individual Strategy and Social Structure: An Evolutionary Theory of Institutions [Review: A Myopic (and Sometimes Blind) Eye on the Main Chance, or, the Origins of Custom]

To read:
• Jacob Abernethy, Alekh Agarwal, Peter L. Bartlett, Alexander Rakhlin, "A Stochastic View of Optimal Regret through Minimax Duality", arxiv:0903.5328
• James Bergin and Barton L. Lipman, 1996, "Evolution with State-Dependent Mutations," Econometrica 64 (1996): 943--956
• Andreas Blume, "A Learning-Efficiency Explanation of Structure in Language", Theory and Decision 57 (2004): 265--285
• Oliver Board, "Dynamic interactive epistemology", Games and Economic Behavior 49 (2004): 49--80
• Jacob W. Crandall and Michael A. Goodrich, "Learning to compete, coordinate, and cooperate in repeated games using reinforcement learning", Machine Learning 82 (2011): 281--314
• Emilio De Santis and Carlo Marinelli, "Stochastic games with infinitely many interacting agents", math.PR/0505608 [Sounds very cool: "study a class of infinite-horizon non-zero-sum non-cooperative stochastic games with infinitely many interacting agents using ideas of statistical mechanics.... in the general case of asymmetric interactions, the existence of a strategy that allows any player to eliminate losses after a finite random time. In the special case of symmetric interactions ... as time goes to infinity, the game converges to a Nash equilibrium. Moreover, assuming that all agents adopt the same strategy, using arguments related to those leading to perfect simulation algorithms, spatial mixing and ergodicity are proved ... ergodicity [implies] ``fixation'', i.e. that players will adopt a constant strategy after a finite time. ... related to zero-temperature Glauber dynamics on random graphs of possibly infinite volume."]
• Pradeep Dubey and Ori Haimanko, "Learning with Perfect Information", Games and Economic Behavior 46 (2004): 304--324
• Jim Engle-Warnick, William J. McCausland and John H. Miller, "The Ghost in the Machine: Inferring Machine-Based Strategies from Observed Behavior" [i.e., inferring stochastic transducers from data; hence the inclusion here]
• Anders Eriksson and Kristian Lindgren, "A simple model of cognitive processing in repeated games", q-bio.PE/0608015
• Fudenberg and Levine, The Theory of Learning in Games
• Douglas Gale and Hamid Sabourian, "Complexity and Competition", Econometrica 73 (2005): 739--769 ["Extensive-form market games typically have a large number of noncompetitive equilibria. In this paper, we argue that the complexity of noncompetitive behavior provides a justification for competitive equilibrium in the sense that if rational agents have an aversion to complexity (at the margin), then maximizing behavior will result in simple behavioral rules and hence in a competitive outcome. For this purpose, we use a class of extensive-form dynamic matching and bargaining games with a finite number of agents. In particular, we consider markets with heterogeneous buyers and sellers and deterministic, exogenous, sequential matching rules, although the results can be extended to other matching processes. If the complexity costs of implementing strategies enter players' preferences lexicographically with the standard payoff, then every equilibrium strategy profile induces a competitive outcome."]
• Val E. Lambson and Daniel A. Probst, "Learning by Matching Patterns", Games and Economic Behavior 46 (2004): 398--409
• Panayotis Mertikopoulos and Aris L. Moustakas, "The emergence of rational behavior in the presence of stochastic perturbations", Annals of Applied Probability 20 (2010): 1359--1388
• Jacek Miekisz
  • "Statistical mechanics of spatial evolutionary games", cond-mat/0210094
  • "Stochastic stability in spatial games", cond-mat/0409647 = Journal of Statistical Physics 117 (2004): 99--110
  • "Long-run behavior of games with many players", cond-mat/0409742
• Liviu Panait, Karl Tuyls, Sean Luke, "Theoretical Advantages of Lenient Learners: An Evolutionary Game Theoretic Perspective", Journal of Machine Learning Research 9 (2008): 423--457
• Mark Stegeman and Paul Rhode, "Stochastic Darwinian equilibria in small and large populations", Games and Economic Behavior 49 (2004): 171--214
• Arne Traulsen, Dirk Semmann, Ralf D. Sommerfeld, Hans-Juergen Krambeck, Manfred Milinski, "Human strategy updating in evolutionary games", arxiv:1001.3768
• Yevgeniy Vorobeychik, Michael P. Wellman and Satinder Singh, "Learning payoff functions in infinite games", Machine Learning 67 (2007): 145--168