University Homepage School Homepage School Contacts School Search

CS4 Algorithmic Game Theory and Applications

This is an Msc course (and 4th year) that runs in Semester 1, on Mondays and Thursdays at 3:10pm, both in Appleton Tower, Lecture Theatre 4. The lecturer is Kousha Etessami. There are no official tutorials associated with this class.

• 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).
    K. Leyton-Brown and Y. Shoham, "Essentials of Game Theory", 2008 . (A short book, available electronically from the Edinburgh University Library.)

  • 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 for definitions:
    Sergiu Hart, "Games in Extensive and Strategic Form", Chapter 2 of Handbook of Game Theory, Vol I.

    Supplementary texbook reading for lectures 2 and 3 (not required reading):
    [Shoham/Leyton-Brown, Multi-Agent Systems (MAS) book, 2009, Chapter 3].

  • Lecture 3: Nash's Theorem

    Light 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 references:
    G. Owen, Game Theory, 1982.
    Chapter 2, on "2-person zero-sum Games".
    V. Chvatal, Linear Programming, 1983.
    Chapter 15, on "Matrix Games".
    

  • 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 references:
    Pages 235-245 of:
    A. Mas-Colell, M. D. Whinston, and J. Green, Microeconomic Theory, 1995.
    
    In [Shoham/Leyton-Brown MAS book] see [sections 3.4.3-3.4.4].

  • 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.

    In [Shoham/Leyton-Brown MAS book] see [Chapter 4].

  • 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.

    In [Shoham/Leyton-Brown MAS book] see [Chapter 5].

  • Lecture 11: Games of Perfect Information

  • 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 and Mean-Payoff Games

  • Lecture 14: Simulation, Bisimulation, and other Ehrenfeucht-Fraisse Games. (Not covered in Fall 2012.)

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

    Supplementary references:

    M. Puterman Markov Decision Processes: discrete stochastic dynamic programming, Wiley, 1994.
    J. Filar and K. Vrieze, Competitive Markov Decision Processes, Springer, 1997.

  • Lecture 16: Selfish Network Routing, Congestion Games, and the Price of Anarchy.

    Supplementary reference reading:
    Algorithmic Game Theory, editors N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Cambridge U. Press, 2007.
    (See chapters 18 and 19.)
    
    In [Shoham/Leyton-Brown MAS book] see [Chapter 6, section 6.4].

  • Lecture 17: A first look at Auctions and Mechanism Design: auctions as games, Bayesian games, and Vickrey auctions.

    Supplementary Reference reading for the next few lectures:
    Algorithmic Game Theory, editors N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Cambridge U. Press, 2007.
    (See chapters 9,11,12 13, and 28.)
    
    In [Shoham/Leyton-Brown MAS book] see [Chapters 10 and 11].

  • Lecture 18: Auctions and Mechanism Design II: a little social choice theory, the VCG mechanism, and Market Equilibria

    Supplementary reference reading for this and the previous lecture:
    Algorithmic Game Theory, editors N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Cambridge U. Press, 2007.
    (See chapters 9,11,12 13, and 28.)
    
    In [Shoham/Leyton-Brown MAS book] see [Chapters 10 and 11].

    For general background on market equilibria (and Microeconomic Theory in general), as well as on Mechanism design, see the excellent reference text:
    A. Mas-Colell, M. D. Whinston, and J. Green, Microeconomic Theory, 1995.

  • Lecture 19: Auctions and Mechanism Design III: Matching Markets, unit-demand auctions, and VCG;
    and a formal framework for Mechanism Design

    Supplementary reference reading for this and the previous two lectures:
    Algorithmic Game Theory, editors N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Cambridge U. Press, 2007.
    (See chapters 9,11,12 13, and 28.) In [Shoham/Leyton-Brown MAS book] see [Chapters 10 and 11].

    For general background on market equilibria (and Microeconomic Theory in general), as well as on Mechanism design, see the excellent reference text:
    A. Mas-Colell, M. D. Whinston, and J. Green, Microeconomic Theory, 1995.

    For background on matching markets (and multi-item unit-demand auctions), see the lovely book:
    A. Roth and M. Sotomayor, Two-Sided Matching: A study in Game-Theoretic Modeling and Analysis, 1990.

• Coursework:
  • Homework 1 (Fall, 2012)
  • Homework 2 (Fall, 2012)
• 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.