CS 5408: Game Theory for Computing - Fall 2022

Legend for Reading Assignments


Label Reference / Book
M Game Theory: Analysis of Conflict, by Roger B. Myerson
S-LB Multiagent Systems, by Yoav Shoham and Kevin Leyton-Brown
EK Networks, Crowds and Markets, by David Easley and Jon Kleinberg
NRTV Algorithmic Game Theory, Edited by Noam Nisam, Tim Roughgarden, Eva Tardos and Vijay V. Vazirani
VN-M Theory of Games and Economic Behavior, by John Von Neumann and Oskar Morgenstern
Z P. Zafra, Linear Programming and Two‐Person Zero‐Sum Games, in Wiley Encyclopedia of Operations Research and Management Science (eds J. J. Cochran et al.), 2011.

Jupyter Notebooks

All Jupyter Notebooks used in lectures can be found here.

Tentative Schedule


Lecture # Date Topic and Slides Subtopics Reading Assignment
1 Aug 23 T0: Introduction Introduction, Applications, Course Prerequisites and Expectations
2 Aug 25 T1: Decision Theory Choice Experiments, Lotteries, St. Petersburg's Paradox, Preference Relations M: Chapters 1.1-1.4
3 Aug 30 Preference Axioms, Expected Utility Maximization, Violations, Bounded Rationality M: Chapters 1.5-1.7
4 Sep 1 Allias Paradox, Prospect Theory, Domination M: Chapters 1.8
5 Sep 6 T2: Basic Models and Solution Concepts Introduction to Games, Representation: Normal-form, Extensive-form M: Chapters 2.1-2.2
6 Sep 8 Information Sets: Imperfect Information, Nature's Randomness, Incomplete Information
7 Sep 13 Transformation from Extensive-form to Normal-form Representation, Iter. Elimination of Dominated Strategies M: Chapters 2-3-2.5
8 Sep 15 Zero-sum Games, Minimax Equilibrium S-LB: Chapters 3.4.1, VN-M: Chapters 3-6
9 Sep 20 Nash Equilibrium, Potential Games, Congestion Games M: Chapters 3.2-3.3, S-LB: Chapters 6.4
10 Sep 22 Congestion Games, Linear Programming S-LB: Chapter 6.4, S-LB: Appendix B, Z
11 Sept 27 No Class Career Fair Day
12 Sep 29 T2: Basic Models and Solution Concepts (cont.) Linear Programming to Solve Two-Player Zero-Sum Games S-LB: Chapters 4.1, Z
13 Oct 4 Equilibria in Bayesian Normal-Form Games S-LB: Chapter 6.3
14 Oct 6 No Class Fall Break
15 Oct 11 T3: Coalitional Games Transferable Utilities and Strategic Coalitions S-LB: Chapter 12.1
16 Oct 13 EXAM 1 (Topics 1 and 2)
17 Oct 18 T3: Coalitional Games Fair Distribution and Shapley Value S-LB: Chapter 12.2.1
18 Oct 20 Team Stability and Core S-LB: Chapter 12.2.2
19 Oct 25 T4: Dynamic Games
Handout: Signaling Games		 Stackelberg Games, Subgame Perfect Equilibrium S-LB: Chapters 5.1, 5.2
20 Oct 27 Equilibria in Imperfect Extensive-Form Games, Sequential Equilibrium S-LB: Chapter 5.2
21 Nov 1 Bayesian Perfect Equilibrium S-LB: Chapter 5.2
22 Nov 3 Repeated Games S-LB: Chapter 6.1
23 Nov 8 T5: Mechanism Design Social Choice, Revelation Principle, Truthfulness S-LB: Chapters 9.1, 9.2, 10.1, 10.2
24 Nov 10 Voting Mechanisms and Their Applications S-LB: Chapter 9.3, EK: Chapter 23
25 Nov 15 VCG Mechanisms, Auctions and Their Applications S-LB: Chapters 10.3, 10.4, EK: Chapters 9, 15
26 Nov 17 T6: Advanced Solution Concepts Games with Contracts, Correlated Equilibrium S-LB: Chapter 4.6
27 Nov 22 No Class Thanksgiving Break
28 Nov 24 No Class Thanksgiving Break
29 Nov 29 Topics 3-5 EXAM 2
30 Dec 1 T6: Advanced Solution Concepts epsilon-Nash Equilibia, Trembling-Hand Perfect Equilibria S-LB: Chapter 4.6
31 Dec 6 Evolutionarily Stable Strategies EK: Chapter 7
32 Dec 8 Evolutionarily Stable Strategies (cont...) EK: Chapter 7