|
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. |
|
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. |
|
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. |
|
Classes will be held Classes begin on January 21st. |
|
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.
|
|
|
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. | |
Mixed Strategies, Nash's Theorem, and Zero-sum Games. | |
Characterizing MNE. Computing equilibria in zero-sum games via LP duality. | |
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). | |
Complete the Lemke-Howson algorithm. A proof of Nash's Theorem via Brouwer's fixed-point theorem.
|
|
|
|