From Theory

Contents 1 Info 2 Lecture notes 3 Assignments 4 Syllabus 5 Acknowledgements

Info

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.

• Algorithmic Game Theory, edited by Nisan et al.
• A Course in Game Theory, by Osborne and Rubinstein.

Adam's Office hours: Thursday after class. Just meet me in the lecture room, and we can talk there.

• TA: Atish Das Sarma, [Email: atish@cc.gatech.edu].
  • TA office hours: Thursday 3pm-4pm, Room 2124 KACB

Lecture notes

• 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 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.

Assignments

• 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 atish@cc.gatech.edu (See rules above.)
• No assignments over spring break. :)
• GTCS Assignment 4 Due 4/15/08.
• GTCS FINAL Assignment Due 5/2/08.

Syllabus

• 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
  • Computation
• Correlated equilibrium
  

  

  Robert Aumann
  • Definition and existence
  • Computation
• 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

• Efficiency
  • Price of Anarchy
• Cooperative game theory
  • Bargaining
    • Nash, Kalai-Smorodinsky, and Egalitarian solutions
  • Shapley value
  • Core
• Bounded rationality
• Cryptography and game theory

Acknowledgements

Funding is partly provided by NSF award SES-0734780.