Algorithmic Game Theory
Course outline
Game theory studies mathematical models of the interaction of multiple agents, where each agent is rational. In a highly connected world where large populations commonly interact, game theory finds applications both in the analysis and design of systems.

This is an introductory course, and our goal in this course is to understand the fundamentals of game theory, particularly focusing on algorithmic aspects. We will introduce a number of widely-studied games, and analyse equilibria and related problems in their context. Topics that I plan to cover include:

games and their representation; equilibria and notions of stability; zero-sum games; bimatrix games; potential games; learning dynamics and convergence to equilibria; games on networks; price of stability and price of anarchy; auctions and mechanism design; contract theory.

Evaluation
Your grade will be based on your performance in homeworks (60-70%), either a final exam, paper presentation, or project (30-40%), and class participation (2-5%).

All students, including those auditing, will have to do all the requirements of the course, including homeworks and projects.

Prerequisites
While most of the course will be self-contained, some lectures will require a basic course in algorithms, linear programming, and complexity theory. You should know how to write concise and correct mathematical proofs.
Details
Classes will be held Tue/Thu 11:30 - 1 Mon 9:30 - 11 and Tue 11:30 - 1 in A-238.

Classes begin on January 21st.

Reference material
Although most of what we cover is available in the reference materials below, we won't be following any particular book or set of notes too closely. I will be uploading lecture notes following the lecture.

Lectures
Jan 21: Lecture Notes
Rationality, Prisoner's Dilemma and dominant / dominated strategies. Game notation. IRDS game and Iterated Removal of Dominated Strategies. The Canteen game and pure strategy Nash equilibria.

References: Slides by Tayfun Sonmez until slide 20, for a good description of dominance and the classical games we talked about.

Jan 23: Lecture Notes (1) and (2)
Mixed Strategies, Nash's Theorem, and Zero-sum Games.

A very brief primer on linear programming.

Jan 30: Lecture Notes
Characterizing MNE. Computing equilibria in zero-sum games via LP duality.

A very brief refresher on computational geometry.

Feb 3:
Computing equilibria in general bimatrix games. An exponential-time algorithm, and the Lemke-Howson algorithm.

Reference: Chapter 2 from the AGT book (which also has the example above).

Feb 5:
Complete the Lemke-Howson algorithm. A proof of Nash's Theorem via Brouwer's fixed-point theorem.

Assignments