# CS 8803 - Game Theory and Computer Science. Spring 2008

From Theory

## Contents |

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

## 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
- 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*

- Price of
- Cooperative game theory
- Bargaining
- Nash, Kalai-Smorodinsky, and Egalitarian solutions

- Shapley value
- Core

- Bargaining
- Bounded rationality
- Cryptography and game theory

# Acknowledgements

Funding is partly provided by NSF award SES-0734780.