AGTA - Course Materials | Open Course Materials

Lecture 1 - 12 January 2026
Slides: What is Game Theory?
No required reading.
Some reference texts for the entire course (see slides of lecture 1 for a more comprehensive list):

M. Maschler, E. Solan, and S. Zamir, Game Theory , Cambridge U. Press, 2013.
(Available online from the University Library.)
N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Algorithmic Game Theory, Cambridge U. Press, 2007.
(Available online from the University library.)
Y. Shoham and K. Leyton-Brown, "Multi-agent Systems: algorithmic, game-theoretic, and logical foundations", 2009. (MAS)
(Available online from the University library.)
T. Roughgarden. Twenty Lectures on Algorithmic Game Theory, Cambridge U. Press, 2016.
(Available online from the University library.)

Lecture 2 & Lecture 3 - 15th and 19th of January 2026
Slides for Lecture 2: Mixed Strategies, Expected Payoffs, and Nash Equilibrium.
Slides for Lecture 3: Nash's Theorem.

Reading for Lectures 2 and 3:
The classic: John Nash, ``Non-cooperative Games'', Annals of Mathematics, 1951. (Only read pages 286--288.)

Supplementary (not required) textbook reading for Lectures 2 and 3:
[Shoham&Leyton-Brown, Multi-Agent Systems (MAS) book, 2009, Chapter 3]
(This book is available digitally from the Edinburgh University Library.)

Light supplementary reading (not required):
Chapter 15: "Application to Biology: Evolutionarily Stable Strategies" (only pages 93--99) in the book : Philip D. Straffin, "Game Theory and Strategy", AMS, 1993. (This book is available digitally from the University of Edinburgh Library.)

Lecture 4 - 22 January 2026
Slides: 2-Player Zero-Sum Games and the Minimax Theorem

Supplementary reading (not required):
T.E.S. Raghavan, "Zero-Sum Two-Person Games", Chapter 20 (only read pages 736--739) in
Handbook of Game Theory, Volume 2, Edited by R. J. Aumann and S. Hart, Elsevier, 1994.
(This handbook is available digitally from the University of Edinburgh Library.)

Lecture 5 - 26 January 2026
Slides: Introduction to Linear Programming

Reading for the next several lectures, either:

V. Chvatal, Linear Programming, Freeman & Co., 1983.
(Chapters 1-5 only; an electronic copy of these is available to AGTA students via the AGTA LEARN page under "Additional Course Materials")
Or, alternatively, another excellent textbook on linear programming is:
J. Matousek and B. Gaertner, Understanding and Using Linear Programming, Springer, 2006.
(This book is available digitally from the University Library.)

Lecture 6 - 29 January (& 2 February) 2026
Slides: The Simplex Algorithm

Reading: continue with Chvatal, or with Matousek&Gaertner.

Lecture 7 - 2 February (& 5 February) 2026
Slides: LP Duality

Reading: continue with Chvatal, or with Matousek&Gaertner.

Lecture 8 - 5 February (& 9 February) 2026
Slides: Computing solutions for general finite strategic games, Part 1: Dominance and Iterated Strategy Elimination

Supplementary reference:
Pages 235--245 of: A. Mas-Colell, M. D. Whinston, and J. Green, Microeconomic Theory, OUP, 1995.
(Also, e.g., [Maschler,Solan-Zamir, GT book, section 4.5] or [Shoham/Leyton-Brown MAS book, sections 3.4.3 & 3.4.4].)

Lecture 9 - 9 February & 12 February 2026
Slides: Computing solutions for general finite strategic games, Part 2: Nash Equilibria

Supplementary references (all of these are available digitally from the University of Edinburgh Library):

R. D. McKelvey and A. McLennan. "Computation of equilibria in Finite Games", Chapter 2, in Handbook of Computational Economics, volume 1, 1996.

B. von Stengel. "Computing equilibria for two-person games", Chapter 45, in Handbook of Game Theory, volume 3, 2002.

[Shoham & Leyton-Brown MAS book, Chapter 4: "Computing solution concepts for normal-form games".]

Lecture 10 - 23 February 2026
Slides: Games in Extensive Form

Supplementary reference reading:
Sergiu Hart, "Games in Extensive and Strategic Form", Chapter 2 of Handbook
of Game Theory, volume 1, Elsevier, 1992. (Available digitally from the University library.)

[Maschler, Solan, & Zamir Game Theory book, Chapters 3 and 6.]

[Shoham & Leyton-Brown MAS book, Chapter 5: "Games with sequential actions"].

Lecture 11 - 26 February 2026
Slides: Games of Perfect Information, and Games on Graphs

Supplemental reference reading (not required):

Jan Mycielski, "Games with Perfect Information", Chapter 3 of Handbook
of Game Theory, volume 1, Elsevier, 1992. (Available digitally from the University library.)

E. Grädel, W. Thomas, and T. Wilke (editors), Automata, Logics, and Infinite Games, Springer, 2002. (Available digitally from the University Library.)

N. Fijalkow (editor), Games on Graphs: from Logic and Automata to Algorithms (forthcoming book), Cambridge University Press, 2026. Current draft available here.

Lecture 12 - 2 March 2026
Slides:
Congestion Games (key)
Congestion Games (pdf)
Congestion Games (pdf, condensed slides)

Supplemental reference reading:

[Shoham & Leyton-Brown MAS book, Chapters 6.4.1 - 6.4.4].
[Nisan, Roughgarden, Tardos, & Vazirani AGT book, Chapters 18.2.2, 18.3.2, 19.3.2, 19.3.4].

Slides corrections:
- Fixed notation in the definition of congestion games.
- Updated notation in the definition of exact potential games.
- Fixed the proof of Rosenthal’s theorem to use a potential minimiser, since we are in a setting with costs.
- Update the termination argument to refer to costs rather than utilities.

Lecture 13 - 5 March 2026
Slides:
Inefficiency of Equilibria (key)
Inefficiency of Equilibria (pdf)
Inefficiency of Equilibria (pdf, condensed slides)

Supplemental reference reading:

Roughgarden, "Twenty Lectures on Algorithmic Game Theory", 2016, Chapter 12.4, 12.5. (Available digitally from the University Library).
[Nisan, Roughgarden, Tardos, & Vazirani AGT book, Chapters 17.1, 18.4.2, 19.3.3].

Lecture 14 - 9 March 2026
Slides:
Introduction to Mechanism Design: Social Choice Theory (key)
Introduction to Mechanism Design: Social Choice Theory (pdf)
Introduction to Mechanism Design: Social Choice Theory (pdf, condensed slides)

Supplemental reference reading:

[Shoham & Leyton-Brown MAS book, Chapter 9.4].
[Nisan, Roughgarden, Tardos, & Vazirani AGT book, Chapter 9.2].

Slides corrections:
- Fixed the definition of truthfulness to incorporate the fact that the chosen candidate may be the same before and after the misreport of the voter.
- Changed all occurrences of "a" to "$\alpha$", where required.
- Fixed a statement in the "Standard Truthfulness Argument" slide.

Supplemental reference reading (not required):

Alternative Proofs of the Gibbard-Satterthwaite theorem:

The Gibbard-Sattertwaite theorem: a simple proof by J. P. Benoît. The proof does not explicitly use monotonicity. It also uses unanimity, which is a weaker property than Pareto optimality.
The Proof of the Gibbard-Sattertwaite theorem revisited by L-S. Svensson and A. Reffgen. The proof first proves the theorem for two voters and then uses induction to obtain the proof for n voters.
A topological proof of the Gibbard-Satterthwaite theorem by Y. Baryshnikov and J. Root. The proof uses the topology of social choice functions.
A Computer-Aided Proof to Gibbard-Satterthwaite Theorem by P. Tang. The proof uses induction but employs a computer (and properties of truthfulness) for the induction step.

A general textbook on computational social choice:

Handbook of Computational Social Choice by Brandt, Conitzer, Endriss, Moulin, and Procaccia. The Gibbard-Satterthwaite theorem is covered in Chapter 2.8.

Lecture 15 - 12 March 2026
Slides:
Approximate Mechanism Design (key)
Approximate Mechanism Design (pdf)
Approximate Mechanism Design (pdf, condensed slides)

Supplemental reference reading:

[Nisan, Roughgarden, Tardos, & Vazirani AGT book, Chapter 10.2].

Search

Navigation