OPIM 319, Spring 2006:
Advanced Decision Systems:
Agents, Games & Evolution

OPIM 319, "Agents, Games & Evolution," explores applications and fundamentals of strategic behavior.

Strategic, or game-theoretic, topics arise throughout the social sciences. The topics include---and we shall study---trust, cooperation, market-related phenomena (including price equilibria and distribution of wealth), norms, conventions, commitment, coalition formation, and negotiation. They also include such applied matters as design of logistics systems, auctions, and markets generally (for example, markets for electric power generation).

In addressing these topics we focus on the practical problem of finding effective strategies for agents in strategic situations (or games). Our method of exploration will be experimental: we review and discuss experiments on the behavior of agents in strategic (or game-theoretic) situations.

In focusing on the design and behavior of artificial agents in strategic (or game-theoretic) situations, we will be especially concerned with strategic contexts of commercial import, such as markets, bargaining, and repeated play. We shall dwell on effective agent learning techniques, including evolutionary methods and reinforcement learning. A main theme in the course is the inherent difficulty, even unknowability, of the problem of strategy acquisition.

We will rely mainly on computational experiments (or simulations), in distinction to analytic mathematical methods, for studying strategy formation and strategic behavior (either by individuals or by groups). Much of the class work will be devoted to discussing and interpreting computational experiments that have been reported in the literature, or that can be undertaken with tools provided in class. In doing so, we draw upon the rapidly growing literature in agent-based modeling and agent-based simulation. Agent-Based Computational Economics (for example, http://www.econ.iastate.edu/tesfatsi/ace.htm) and Agent-Based Social Science (for example, http://www.brookings.edu/es/dynamics/papers/csed_wp41.htm) have come to denote active communities of research and application. We shall draw upon them.

Computer programming is neither required nor discouraged for the course. The instructor invites, and will support, projects using NetLogo (as well as other envirnments). Many of the computational demonstrations and experiments we will examine are available as NetLogo programs (http://ccl.northwestern.edu/netlogo/). Students are not, however, at all required to undertake programming exercises, in NetLogo or in any other environment.

Students completing the course can expect to come away with:

  1. Solid understanding of what is known and what is not known about the problem of designing procedures for strategic behavior,
  2. Familiarity with the principal methods, and results of applying those methods, for the modeling of human agents and design of artificial agents in strategic contexts, and
  3. Deepened appreciation for contexts of strategic interaction.

Class meets 3-4:30 p.m., Mondays and Wednesdays. Grading is based on class participation, assigned short essays undertaken during the term, a midterm quiz, and a term project. For further information, contact the principal instructor for the course, Professor Steven O. Kimbrough (kimbrough@wharton.upenn.edu).

See the class homepage http://opim-sun.wharton.upenn.edu/~sok/teaching/age/s06/ for further information.

Required Texts

Recommended

In addition, various other readings will be assigned. These will generally be handed out or made available online. In particular, we will read a number of chapters from Professor Kimbrough's draft manuscript, Agents, Games & Evolution, which is referred to below as the AGEbook.

Class Schedule

  1. January 9, 2006, Monday. Introduction and overview of the course.

    2. Strategic interaction. Illustrations of "games in the wild." Towards a natural history of games. Read: "Contexts of Strategic Interaction," chapter 1 of AGEbook. Recommended reading: ``A Natural History of Peace,'' by Robert M. Sapolsky, Foreign Affairs, January/February 2006, Vol 85, Number 1. Link.

  2. January 11, 2006, Wednesday. Four themes: social order; emergence and self-organization; complexity; and rationality.

    3. Read: "Micromotives and Macrobehavior," pp. 11-43 of Micromotives and Macrobehavior, Thomas C. Schelling, W.W. Norton & Co., New York, 1978.

    Note: Schelling just (10 October 2005) won a Nobel Prize for doing this sort of work. http://nobelprize.org/economics/laureates/2005/press.html.

    Also read chapter 2 of the AGEbook, "Four Themes," and "The Tragedy of the Commons," by Garrett Hardin, Science, vol. 162, no. 3859, Dec. 13, 1968, pp. 1243-1248. PDF.

    January 16, 2006, Monday. MLK day, no class.
  3. January 18, 2006, Wednesday. Elements of strategic analysis.

    4. Games in strategic form, games in extensive form. Focus on 2×2 games. Equilibrium. Mixed equilibrium. Solution concepts. Folk Theorem. Read: "Games in the Abstract" chapter of AGE. Recommended reading: Wikipedia article on game theory: http://en.wikipedia.org/wiki/Game_theory. Recommended reading: Ross, Don "Game Theory", The Stanford Encyclopedia of Philosophy (Winter 2005 Edition), Edward N. Zalta (ed.), forthcoming URL = http://plato.stanford.edu/archives/win2005/entries/game-theory/, if it's available, otherwise: http://plato.stanford.edu/entries/game-theory/.

    Read chapter 3 of the AGEbook.

    Assignment 1 handed out.

  4. January 23, 2006, Monday. Cooperation and its evolution.

    5. Read: The Evolution of Cooperation by Robert Axelrod, Basic Books, 1984, chapters 1-3, appendix B.

  5. January 25, 2006, Wednesday. Cooperation and its evolution.

    6. Read: The Evolution of Cooperation by Robert Axelrod, Basic Books, 1984, chapters 4-5.

  6. January 30, 2006, Monday. Cooperation and its evolution.

    7. Read: The Evolution of Cooperation by Robert Axelrod, Basic Books, 1984, chapters 6-9 (skim).

    Assignment 1 due.

  7. February 1, 2006, Wednesday. ESS: Evolutionarily Stable Strategy.

    8. Strategies that will be favored by evolution in repeated play of a game. Read: Wikipedia article on ESS: http://en.wikipedia.org/wiki/Evolutionarily_stable_strategy. Recommended reading: John Maynard Smith, "The Basic Model," chapter 2 (pp. 10-27) of Evolution and the Theory of Games, Cambridge University Press, 1982. Recommended reading: Alexander, J. McKenzie, "Evolutionary Game Theory", The Stanford Encyclopedia of Philosophy (Summer 2003 Edition), Edward N. Zalta (ed.), URL = http://plato.stanford.edu/archives/sum2003/entries/game-evolutionary/.

    Assignment 2 (short essay) handed out.

  8. February 6, 2006, Monday. Fairness and ultimatum games; commitment; reciprocity.

    9. Read: Brian Skyrms, Evolution of the Social Contract, chapters 1-2 ("Sex and Justice," pp. 1-21; "Commitment," pp. 22-44), Cambridge University Press, 1996.

  9. February 8, 2006, Wednesday. Beyond Prisoner's Dilemma: The Stag Hunt and other illuminating games.

    10. Read: Brian Skyrms, The Stag Hunt and the Evolution of Social Structure, "Preface" (pp. xi-xiv) and chapter 1, "The Stag Hunt" (pp. 1-14), Cambridge University Press, 2004.

    Assignment 3 (short essay) handed out.

  10. February 13, 2006, Monday. Beyond Prisoner's Dilemma: The Stag Hunt and other illuminating games.

    11. Read: Brian Skyrms, The Stag Hunt and the Evolution of Social Structure, chapter 2, "Bargaining with Neighbors" (pp. 17-30) and chapter 3, "Stag Hunt with Neighbors" (pp. 31-44), Cambridge University Press, 2004.

  11. February 15, 2006, Wednesday. Beyond Prisoner's Dilemma: The Stag Hunt and other illuminating games.

    12. Read: Brian Skyrms, The Stag Hunt and the Evolution of Social Structure, chapter 4, "Evolution of Inference" (pp. 45-64) and chapter 5, "Cheap Talk" (pp. 65-82), Cambridge University Press, 2004.

  12. February 20, 2006, Monday. Beyond Prisoner's Dilemma: The Stag Hunt and other illuminating games.

    13. Read: Brian Skyrms, The Stag Hunt and the Evolution of Social Structure, chapter 6, "Choosing Partners" (pp. 87-104) and chapter 7, "Coevolution of Structure and Strategy" (pp. 105-124), Cambridge University Press, 2004.

  13. February 22, 2006, Wednesday. Trust.

    14. Read: Garrett Hardin, "The Tragedy of the Commons," Science 162:1243-8, 1968. Read: Steven O. Kimbrough, "Foraging for Trust: Exploring Rationality and the Stag Hunt Game," in Trust Management: Third International Conference, iTrust 2005, Paris, France, May 23-26, 2005. Proceedings, P. Hermann, Valérie Issarny and Simon Shiu, eds., Springer-Verlag GmbH, Berlin, Germany, LNCS: Lecture Notes in Computer Science, 3477 / 2005, pp. 1-16, 2005. Read: Jon Elster, "Introduction: the two problems of social order," chapter 1 in The Cement of Society: A study of social order, Cambridge University Press, 1989, pp. 1-16.

  14. February 27, 2006, Monday. Trust (continued).

    15. Computational explorations of trust.

  15. March 1, 2006, Wednesday. Mid-term quiz.
    16. March 6 & 8, 2006, Monday & Wednesday, no class. Spring break.
  16. March 13, 2006, Monday. Cellular automata models.

    17. The Game of Life, among others. Read: "What Is Life?" in Winning Ways for Your Mathematical Plays, volume 2: Games in Particular, by Elwyn R. Berlekamp, John H. Conway and Richard K. Guy, Academic Press, 1982.

  17. March 15, 2006, Wednesday. Growing artificial societies.

    18. Read: Growing Artificial Societies: Social Science from the Bottom Up, by Joshua Epstein and Robert Axtell, MIT Press, 1996, chapters 1-2.

  18. March 20, 2006, Monday. Growing artificial societies.

    19. Read: Growing Artificial Societies: Social Science from the Bottom Up, by Joshua Epstein and Robert Axtell, MIT Press, 1996, chapters 3-4.

  19. March 22, 2006, Wednesday. Growing artificial societies.

    20. Read: Growing Artificial Societies: Social Science from the Bottom Up, by Joshua Epstein and Robert Axtell, MIT Press, 1996, chapters 5-6.

  20. March 27, 2006, Monday. Further explorations on the gridscape.

    21. Computational demonstrations and experiments. Recommended readings: chapters from AGE.

  21. March 29, 2006, Wednesday. Games, complexity, computability.

    22. Instructor handouts. Recommended reading: Patrick Grim, "Undecidability in the Spatialized Prisoner's Dilemma: Some Philosophical Implications" at http://www.sunysb.edu/philosophy/faculty/pgrim/SPATIALP.HTM

  22. April 3, 2006, Monday. Applications: Stock markets.

    23. Read: Dhananjay K. Gode and Shyam Sunder, "Allocative Efficiency of Markets with Zero-Intelligence Traders: Market as a Partial Substitute for Individual Rationality," Journal of Political Economy, 101, no. 1, pp. 119-137, 1993. File: gode-sunder-1993.pdf in misc. readings/ folder on webCafe.

    Also read: J. Doyne Farmer and Andrew W. Lo, "Frontiers of finance: Evolution and efficient markets," Proceedings of the National Academy of Science, 96), pp. 9991-9992, August 1999. File: farmer-lo-1999.pdf in misc. readings/ folder on webCafe.

    Recommended: Dhananjay K. Gode and Shyam Sunder, "What Makes Markets Allocationally Efficient?", The Quarterly Journal of Economics, 112, no. 2, May, 1997, pp. 603-630. File: gode-sunder-1997.pdf in misc. readings/ folder on webCafe.

    Recommended: J. Doyne Farmer, Paolo Patelli, and Ilija I. Zovko, "The Predictive Power of Zero Intelligence in Financial Markets". File: farmer-etal-zi-2003.pdf in misc. readings/ folder on webCafe.

    If time permits: Presentation of information regarding BehaviorSpace in NetLogo.

  23. April 5, 2006, Wednesday. Applications: Matching problems.

    24. Read: D. Gale and L. S. Shapley, 1962. "College Admissions and the Stability of Marriage," The American Mathematical Monthly, 69, no. 1, pp. 9-15. Lawrence Bodin and Aaron Panken, 2003. "High Tech for a Higher Authority: The Place of Graduating Rabbis from Hebrew Union College--Jewish Institute of Religion," Interfaces, 33, no. 3, May-June, pp. 1-11.

  24. April 10, 2006, Monday. Applications: Markets for electric power generation.

    25. Instructor handouts. Cournot duopoly models. Read: Steven O. Kimbrough, Ming Lu, and Frederic Murphy, 2004. "Learning and Tacit Collusion by Artificial Agents in Cournot Duopoly Games," in Steven O. Kimbrough and D. J. Wu, eds., Formal Modelling in Electronic Commerce, Springer, pp. 477-492.

  25. April 12, 2006, Wednesday. Evolutionary algorithms.

    26. Evolutionary computing. Genetic algorithms. Replicator dynamics. Genetic programming.

  26. April 17, 2006, Monday. Evolutionary alogorithms.

    27. Evolutionary computing. Learning classifier systems. Models of individual learning in strategic contexts.

  27. April 19, 2006, Wednesday. Last class.

    28. Summing up. Rationality redux.

Provisional syllabus, version $Id: syllabus-f05-age.html,v 1.1 2005/10/31 23:01:55 sok Exp $