University Homepage School Homepage School Contacts School Search

CS4 Algorithmic Game Theory and Applications

This is a 4th year and Msc course that runs in Semester 1, on Mondays and Thursdays at 3.00pm in Forrest Hill room 3.D01 (central campus). The course descriptor is here.

The lecturer is Kousha Etessami. There are no official tutorials associated with this class, but we might arrange to meet informally on some weeks for question and answer sessions, etc.

• Lectures
  • Lecture 1: What is Game Theory?

    No required reading.
    Supplementary reading:
    T. L. Turocy and B. von Stengel, "Game Theory" (a survey), 2002. (from Encyclopedia of Information Systems).

  • Lecture 2: Mixed Strategies, Expected Payoffs, and Nash Equilibrium.

    Reading for Lectures 2 and 3:
    ( Read only pages 286-288)
    The classic: John Nash, "Non-cooperative Games", Annals of Mathematics, 1951.

    Reference reading:
    Sergiu Hart, "Games in Extensive and Strategic Form", Chapter 2 of Handbook of Game Theory, Vol I.

  • Lecture 3: Nash's Theorem

    Reading:
    "Application to Biology: Evolutionarily Stable Strategies",
    from P. Straffin (1993), chap. 15, pp. 93-99.
    

  • Lecture 4: 2-Player Zero-Sum Games, and The Minimax Theorem

    Supplementary Reading:
    G. Owen, Game Theory, 1982.
    Chapter 2, on "2-person zero-sum Games".
    (Chapter 3 discusses LP, but the reference Chvatal below is far preferable.)
    On reserve in the JCMB library.

  • Lecture 5: Introduction to Linear Programming

    Reading for the next several lectures:
    our reference for Linear Programming will be:
    V. Chvatal, Linear Programming, 1983. (Chapters 1-5)
    On reserve in the JCMB library.

  • Lecture 6: The Simplex Algorithm

    Reading: continuing with Chvatal, Chapters 1-5.

  • Lecture 7: LP Duality

    Reading: continuing with Chvatal, Chapters 1-5.
    supplementary reference: chapter 3 of Owen.
    

  • Lecture 8: Computing Solutions for General Finite Strategic Games, Part I: Dominance and iterated strategy elimination

    Supplementary reference:
    Pages 235-245 of:
    A. Mas-Colell, M. D. Whinston, and J. Green, "Microeconomic Theory", 1995.

  • Lecture 9: Computing Solutions for General Finite Strategic Games, Part II: Nash Equilibria

    Supplementary references:
    R. D. McKelvey and A. McLennan Computation of Equilibria in Finite Games , from Handbook of Computational Economics, vol. I, 1996.
    B. Von Stengel, Computing equilibria for two-person games , chapter 45 from Handbook of Game Theory, vol. 3, 2002.

  • Lecture 10: Games in Extensive Form

    Reference reading for this and next lecture (same reference as Lec. 2):
    Sergiu Hart, "Games in Extensive and Strategic Form", Chapter 2 of Handbook of Game Theory, Vol I.

  • Lecture 11: Games of Perfect Information

  • Lecture 11.5: Guest Lecture by Sandra Quickert: Borel Games and Borel Determinacy

  • Lecture 12: Games on Graphs

    Supplementary reference:
    E. Grädel, W. Thomas, and Th. Wilke (editors), Automata, Logics, and Infinite Games, Springer-Verlag, LNCS volume 2500, 2002.

  • Lecture 13: Parity Games

  • Lecture 14: Simulation, Bisimulation, and other Ehrenfeucht-Fraisse Games.

  • Lecture 15: A brief taster of Markov Decision Processes and Stochastic Games

  • Lecture 16: A brief glimpse beyond: mechanism design and auctions, network routing games and price of anarchy, etc.

    Reference reading:
    Algorithmic Game Theory, editors N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Cambridge U. Press, 2007.

• Coursework:
  • Homework 1 (Fall, 2009)
  • Homework 2 (Fall, 2009)
• Resources:

  There are endlessly many resources on the web about Game Theory that you can get happily lost in. I'll hopefully get around to putting some useful links here.

Kousha Etessami, kousha@inf.ed.ac.uk.