CS 8803 - Game Theory and Computer Science. Spring 2008
Time: Tuesdays and Thursdays 9:35-10:55am
Location: College of Computing, room 53
Instructor: Adam Tauman Kalai
Grading: 50% Homework (Students may work alone or in groups of size at most 3. In either case, each student must submit his or her own work. In the case of a group, please write the names of the collaborators on the assignment.) , 30% Final, 20% Midterm. The final and midterm should be done independently. See the Georgia Tech honor code.
References: Some of the material for the class will be taken from the following books, but they are not required.
Adam's Office hours: Thursday after class. Just meet me in the lecture room, and we can talk there.
- TA: Atish Das Sarma, [Email: email@example.com].
- TA office hours: Thursday 3pm-4pm, Room 2124 KACB
- GTCS Lecture 1/8/08 Intro and zero-sum normal-form games.
- GTCS Lecture 1/10/08 A proof of the min-max theorem via the repeated n-decision game and the weighted majority theorem.
- GTCS Lecture 1/15/08 A proof of the weighted majority theorem. See also this survey, On-Line Algorithms in Machine Learning by Avrim Blum.
- GTCS Lecture 1/17/08 Convex-concave games and Multi-armed bandits.
- GTCS Lecture 1/22/08 Summary: the complexity of solving/playing normal-form zero-sum games. Adversarial routing game. Game representation. Extensive-form games. Dominance.
- GTCS Lecture 1/22/08 Structured decision-making algorithm. Iterated elimination of dominated strategies.
- GTCS Lecture 1/29/08 More on iterated elimination of dominated strategies. Utility theory.
- GTCS Lecture 1/31/08 Finish utility theory. Nash equilibrium.
- 2/4/08 Interesting game theory/CS lecture in ARC colloquium series on Monday at 3pm.
- GTCS Lecture 2/5/08 (Approximate) epsilon-equilibria and finding them. NP-Hardness of finding best Nash equilibrium in <math>n \times n</math> games.
- GTCS Lecture 2/7/08 Hardness of finding NE and Refinements: Subgame-perfect equilibrium and trembling-hand perfect equilibrium.
- GTCS Lecture 2/12/08. Potential games and congestion games. See the excellent notes of Yishay Mansour.
- GTCS Lecture 2/14/08. Finish showing equivalence of potential/congestion games. Start price of anarchy.
- GTCS Lecture 2/19/08. Continue price of anarchy.
- GTCS Lecture 2/21/08. Price of stability and the Network formation game, More refinements: Strict Nash equilibrium, Evolutionarily Stable Strategy (ESS), and Persistent Nash equilibrium.
- GTCS Lecture 2/26/08. Evolutionarily Stable Strategy (ESS) and Correlated Equilibrium.
- GTCS Lecture 2/28/08. Swap regret and Computing correlated equilibrium.
- GTCS Lecture 3/4/08. Finish Computing correlated equilibrium.
- GTCS Lecture 3/6/08. Repeated games and the folk theorem.
- GTCS Lecture 3/11/08. Prove the folk theorem.
- GTCS Lecture 3/13/08. Bargaining
- GTCS Lecture 3/25/08. Incomplete information.
- GTCS Lecture 3/27/08. Finish incomplete information.
- GTCS Lecture 4/1/08. Common Knowledge, start auctions.
- GTCS Lecture 4/3/08. Continue auctions.
- GTCS Lecture 4/8/08. Finish auctions.
- GTCS Lecture 4/10/08. Guest Lecture: Yair Tauman Coalitional Form, The Core, 0-1 Games, The Shapley Value, Uniqueness of the Shapley Value
- GTCS Lecture 4/15/08. Rational learning.
- GTCS Lecture 4/17/08. Market Equilibrium.
- GTCS Lecture 4/22/08. Bounded rationality.
- GTCS Lecture 4/24/08. Large Games.
- GTCS Assignment 1 Due 1/31/08. (See rules above.)
- GTCS Assignment 2 Due 2/14/08. (See rules above.)
- Midterm (take home) Due 2/28/08. Must do on your own.
- GTCS Assignment 3 Due 3/14/08. May turn in to TA in Class on Thursday (3/13/08) or by email to firstname.lastname@example.org (See rules above.)
- No assignments over spring break. :)
- GTCS Assignment 4 Due 4/15/08.
- GTCS FINAL Assignment Due 5/2/08.
- Definition of a normal-form game (with mixed strategies) and some further notation
- Two-person zero-sum game (or constant-sum game)
- The min-max theorem
- The repeated n-decision game and the weighted-majority algorithm
- A proof of the min-max theorem using the weighted majority theorem
- A proof of the weighted majority theorem
- Multi-armed bandits
- Worst-case analysis and zero-sum game
- Game representation
- Zero-sum games of incomplete information
- Computing equlibrium in large zero-sum games
- Nash equilibrium
- Definition and existence
- Correlated equilibrium
- Definition and existence
- Repeated games
- Utility functions and discounting
- Folk theorem
- Games of incomplete information
- Bayesian equilibrium
- Rational Learning
- Special types of games
- Potential games
- Market games
- Grahpical games
- Auctions/Mechansim design
- Price of Anarchy
- Cooperative game theory
- Nash, Kalai-Smorodinsky, and Egalitarian solutions
- Shapley value
- Bounded rationality
- Cryptography and game theory
Funding is partly provided by NSF award SES-0734780.