AGTA - Course Materials

Note:
Game Theory is covered in both the CS-oriented textbooks and more classic textbooks in economics. Our main reference will be the CS textbooks, but for a deeper discussion, sometimes it might be useful to take a look into the books from economics also.

Week 1: 13-17 January 2025

Lecture 1 - 13 January 2025
Topics: What is Game Theory? Introduction to (normal form) games and strategies. Pure strategies and mixed strategies.

Slides:
Lecture 1 - Introduction to the course (pdf)
Lecture 1 - Introduction to the course (key) 

References:
Multiagent Systems by Shoham and Leyton-Brown, Chapter 3.2.2.

Alternative reading:
A Course in Game Theory by Osborne and Rubinstein, Chapters 2.1.1, 2.1.2 (available online from the University library).
Game Theory by Fudenberg and Tirole, Chapter 1.1.1. (available online from the University library). 

Lecture 2 - 16 January 2025
Topics: Solution Concepts: Dominant Strategy Equilibrium, Elimination of Strictly Dominated Strategies, pure and mixed Nash equilibrium.

Slides:
Lecture 2 - Games and Solution Concepts (pdf)
Lecture 2 - Games and Solution Concepts (key)

References:
Multiagent Systems by Shoham and Leyton-Brown, Chapters 3.2.3, 3.2.4, 3.3.2, and 3.4.3.
Algorithmic Game Theory by Nisan, Roughgarden, Tardos, and Vazirani, Chapters 1.1, 1.2, 1.3.1,. 1.3.3, and 1.3.4. 

Alternative reading:
A Course in Game Theory by Osborne and Rubinstein, Chapters 2.1, 2.2, 2.3, 3.1., 3.2, and 4.2. (available online from the University library).
Game Theory by Fudenberg and Tirole, Chapters 1, 2.1. (available online from the University library). 

Week 2: 20-24 January 2025

Lecture 3 - 20 January 2025
Topics: Mixed Nash Equilibria, Support Enumeration, 2-Player Zero-Sum Games, the Minimax Theorem.

Slides:
Lecture 3 - Nash Equilibrium and Zero-Sum Games (pdf)
Lecture 3 - Nash Equilibrium and Zero-Sum Games (key)

References:
Multiagent Systems by Shoham and Leyton-Brown, Chapters 3.2.3, 3.4.1, 4.2.3. 
Algorithmic Game Theory by Nisan, Roughgarden, Tardos, and Vazirani, Chapter 3.2.
Twenty Lectures on Algorithmic Game Theory by Roughgarden, Chapter 18.3.  

Alternative reading:
A Course in Game Theory by Osborne and Rubinstein, Chapter 3.1. (available online from the University library).
Linear Programming: Foundations and Extensions by Vanderbei, Chapter 11.

Lecture 4 - 23 January 2025
Topics: Introduction to Linear Programming.

Slides: 
Lecture 4 - Introduction to Linear Programming (pdf)
Lecture 4 - Introduction to Linear Programming (key)

References:
Linear Programming: Foundations and Extensions by Vanderbei, Chapter 1.
Understanding and Using Linear Programming by Matoušek and Gärtner, Chapter 1, Chapter 2.1., Chapter 3.1.

Additional reading:
Linear Programming by Chvatal, 1983 (available in paper copies via the University library).

Week 3: 27-31 January 2025

Lecture 5 - 27 January 2025
Topics: The Simplex Method, Degeneracy

Slides:
Lecture 5 - The Simplex Method (pdf)
Lecture 5 - The Simplex Method (key)

References:
Linear Programming: Foundations and Extensions by Vanderbei, Chapters 2 and 3.

Lecture 6 - 30 January 2025
Topics: LP-Duality and the Minimax Theorem

Slides:
Lecture 6 - LP-Duality and the Minimax Theorem (pdf)
Lecture 6 - LP-Duality and the Minimax Theorem (key)

References:
Linear Programming: Foundations and Extensions by Vanderbei, Chapter 11.
Multiagent Systems by Shoham and Leyton-Brown, Chapter 4.1. 

Week 4: 3-7 February 2025

Lecture 7 - 3 February 2025
Topics: The Lemke-Howson Algorithm and Computational Complexity of Computing a Nash Equilibrium

Slides:
Lecture 7 - The Lemke-Howson Algorithm and Computational Complexity (pdf)
Lecture 7 - The Lemke-Howson Algorithm and Computational Complexity (key)

References:
Multiagent Systems by Shoham and Leyton-Brown, Chapters 4.2.1., 4.2.2. 

Lecture 8 - 6 February 2025
Topics: A proof of Nash's Theorem, Approximate equilibria, Computational Complexity of Computing a Nash Equilibrium

Slides:
Lecture 8 - Nash Equilibrium Existence and Complexity (pdf)
Lecture 8 - Nash Equilibrium Existence and Complexity (key)

References:
Multiagent Systems by Shoham and Leyton-Brown, Chapter 3.3.4.
Twenty Lectures on Algorithmic Game Theory by Roughgarden, Chapters 20.4, 20.5.1 (more informal exposition). 
Algorithmic Game Theory by Nisan, Roughgarden, Tardos, and Vazirani, Chapters 2.2, 2.4. 

Week 5: 10-14 February 2025

Lecture 9 - 10 February 2025
Topics: Extensive Form Games, Perfect and Imperfect Information Games

Slides:
Lecture 9 - Extensive Form Games (pdf)
Lecture 9 - Extensive Form Games (key)

References:
Multiagent Systems by Shoham and Leyton-Brown, Chapters 5.1, 5.2.1.
 

Lecture 10 - 13 February 2025
Topics: Imperfect Information Games, Perfect Recall, Markov Decision Processes, Stochastic Games

Slides:
Lecture 10 - Imperfect Information Games and More General Games (pdf)
Lecture 10 - Imperfect Information Games and More General Games (key)

References:
Multiagent Systems by Shoham and Leyton-Brown, Chapters 5.2.1, 5.2.2.

Further reading:
Markov Decision Processes: Discrete Stochastic Dynamic Programming by Puterman, Chapter 1, Chapter 2.1.
Competitive Markov Decision Processes by Filar and Vrieze (a book about stochastic games).

Week 6: 24-28 February 2025

Lecture 11 - 24 February 2025
Topics: Congestion Games, Potential Games

Slides:
Lecture 11 - Congestion Games (pdf)
Lecture 11 - Congestion Games (key)

References:
Multiagent Systems by Shoham and Leyton-Brown, Chapters 6.4.1 - 6.4.4.
Algorithmic Game Theory by Nisan, Roughgarden, Tardos, and Vazirani, Chapters 18.2.2, 18.3.2, 19.3.2, 19.3.4.

Lecture 12 - 27 February 2025
Topics: Price of Anarchy, Price of Stability, Bounds for linear congestion games, The potential method.

Slides:
Lecture 12 - Inefficiency of Equilibria (pdf)
Lecture 12 - Inefficiency of Equilibria (key) 

References:
Twenty Lectures on Algorithmic Game Theory by Roughgarden, Chapter 12.4, 12.5.
Algorithmic Game Theory by Nisan, Roughgarden, Tardos, and Vazirani, Chapters 17.1, 18.4.2, 19.3.3.

Week 7: 3-7 March 2025

Lecture 13 - 3 March 2025
Topics: Introduction to Mechanism Design, Social Choice Theory, The Gibbard-Satterthwaite Theorem

Slides:
Lecture 13 - Social Choice Theory (pdf)
Lecture 13 - Social Choice Theory (key) 

References:
Multiagent Systems by Shoham and Leyton-Brown, Chapter 9.4.
Algorithmic Game Theory by Nisan, Roughgarden, Tardos, and Vazirani, Chapter 9.2.

Note: The course textbooks present the proof of the Gibbard-Sattertwaite Theorem as a corollary of Arrow's Theorem, which we didn't mention in class. In the lectures, we saw a more direct proof (sketch) of the theorem, see "Further reading" below.

Further Reading: 

Alternative Proofs of the Gibbard-Satterthwaite theorem:

The Gibbard-Sattertwaite theorem: a simple proof by J. P. Benoît. The proof uses the same instances we used in the classroom but 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 14 - 6 March 2025
Topics: Single-peaked Preferences, Approximate Mechanism Design (without money), Truthful Facility Location

Slides:
Lecture 14 - Approximate Mechanism Design (pdf)
Lecture 14 - Approximate Mechanism Design (key) 

References:
Algorithmic Game Theory by Nisan, Roughgarden, Tardos, and Vazirani, Chapter 10.2.

Further Reading:
Approximate Mechanism Design without Money by A. D. Procaccia and M. Tennenholtz. ACM Transactions on Economics and Computation (TEAC), Volume 1, Issue 4, 2013 (journal version). 

Week 8: 10-15 March 2025

Lecture 15 - 10 March 2025
Topics: Mechanism Design without Money, Auctions, The VCG Mechanism, Weak Monotonicity

Slides:
Lecture 15 - Mechanism Design with Money and the VCG Mechanism (pdf)
Lecture 15 - Mechanism Design with Money and the VCG Mechanism (key) 

References:
Multiagent Systems by Shoham and Leyton-Brown, Chapter 10.3, 10.4.
Algorithmic Game Theory by Nisan, Roughgarden, Tardos, and Vazirani, Chapter 9.3, 9.5.2, 11.2.1.
Twenty Lectures on Algorithmic Game Theory by Roughgarden, Chapter 7.

Lecture 16 - 13 March 2025
Topics: Single-parameter Domains, Myerson's Characterization, The Revelation Principle

Slides:
Lecture 16 - Single Parameter Domains (pdf)
Lecture 16 - Single Parameter Domains (key)

References:
Algorithmic Game Theory by Nisan, Roughgarden, Tardos, and Vazirani, Chapters 9.4.3., 9.5.4, 9.5.6.
Twenty Lectures on Algorithmic Game Theory by Roughgarden, Chapters 3, 4.3.