Game Theory and Algorithms

Instructor David Pritchard
Language English

This doctoral course offers a broad introduction to game theory (models of competition, cooperation and multi-party decision-making) from an algorithmic perspective. We begin from scratch and cover interesting results in several game-theoretic models. Some results give insight into real-life situations (e.g., finite vs infinitely repeated games), some are useful in practice (e.g., auctions) and others show what kind of properties in a model are reasonable/unreasonable or possible/incompatible (e.g., voting models). 


The meetings take place twice a week. Most meetings will be lectures but approximately twice per month there will be an exercise session, where we review solutions to exercises given in lecture. At the end of the term, each student will give a ~40 minute presentation on a topic of their choice related to the material covered in the course.
Time and location (starting Feb 22):
  • 10:15-12:00 Tuesdays in MA A1 10    (except CM 010 for Mar 22)
  • 10:15-12:00 Thursdays in MA A3 30

News: Lecture will be cancelled on the last day of class (May 31). In place of this, the last exercise session will be made optional and moved to the morning of Monday May 23, 10:15-12:00 in MA A3 31.

You do not need a textbook for the course: we will cover the material in lecture and post notes as each lecture takes place.
The course code is MATH-764. This is a 4-credit doctoral course.

Course Contents

Strategic Games

  • 2/22 (1) Prisoner’s dilemma, dominated actions, iterated elimination
  • 2/24 (2) Best responses, Nash equilibria, examples, oligopoly
  • 3/1 (3) Weakly dominant strategies, auctions, elections
  • 3/3 Exercises 1
  • 3/8 (4) Mixed strategies, mixed equilibria, and Nash’s theorem
  • 3/10 (5, scan only) Efficient algorithm for Nash Equilibria in 2-player zero-sum games (LP Duality)
  • 3/15 (6, and scan) Algorithm for Nash Equilibria in 2-player games (Lemke-Howson)
  • 3/17 (7) Topological proof of Nash’s theorem, and PPAD-hardness (neat: Sperner’s applet)
  • 3/22 Exercises 2

Extensive Games 

  • 3/24 (8, and scan) Introduction, subgame-perfect equilibria (thanks to Dejan Novakovic for scribing!)
  • 3/29 (9) Repeated games and infinitely repeated games
  • 3/31 (10) Incomplete information, modelling mixed strategies, critiques of backwards induction
  • 4/5 Exercises 3


  • 4/7 (11, and scan) Cake-cutting; and the VCG mechanism (thanks to Andres Ruiz-Vargas for scribing!)
  • 4/12 (12) More about VCG; fractional VCG via approximation algorithms
  • 4/14 (13) Revenue maximization (for known bidder distributions)
  • 4/19 (14) Revenue maximization (for unknown bidder distributions)
  • See also the video “How to Think About Mechanism Design,” Tim Roughgarden
  • 4/21 Exercises 4

Social Choice / Elections 

  • In the news: May 5, the UK has a referendum on voting systems
  • 5/3 (15) Elections and Arrow’s Theorem
  • 5/5 (16) Elections on a Line and in Practice

Social Cost of Equilibria

  • 5/10 (17) Network Games and Quality of Equilibria
  • 5/12 (18) Routing Games and Potentials

Impartial Combinatorial Games

  • 5/17 (19) Algorithm for perfect play via the Sprague-Grundy theorem
  • 5/23 (Monday) Exercises 5. Optional! 10:15-12:00 AM in MA A3 31
  • 5/26 Chomp tournament and strategy-stealing proof

Student Presentations

  • 5/19 Jean-Benoît (regret minimization as a solution concept) reference
  • 5/19 Dejan (complexity in elections) references: 1 2 3
  • 5/24 Andres (selfish load balancing) from Nisan et al, Chapter 7 (Michael Kearns)
  • 5/24 Leo (graphical games) from Nisan et al, Chapter 20 (Berthold Vöcking)
  • 5/26 Christian (dueling algorithms) reference (Note from DP: data in graphs about algorithm performance is work of the presenter, not part of the original paper, do not reuse without permission.)


We will deal frequently with probability (e.g. expected values), algorithms, and proofs, so students should be comfortable with these concepts. In a few places we will use linear programming and students who have seen the simplex algorithm will be at an advantage when we discuss the Lemke-Howson algorithm. There is a little bit of calculus in the sections on auctions and network games. You can contact me if you want a better idea of whether the course suits your situation.

One well-written explanation of the simplex algorithm is Sections 2-5 of these lecture notes by Vempala

Contact Information

David Pritchard, [email protected], Office hours available upon appointment

Presentation Suggestions