|
|
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. | |
| Complete the Lemke-Howson algorithm. A proof of Nash's Theorem via Brouwer's fixed-point theorem.
| |
| An example of Lemke-Howson. A proof of Nash's Theorem via Brouwer's fixed-point theorem, done more formally.
| |
| Completing the proof of Nash's Theorem. The complexity of finding a Nash equilibrium.
Some additional resources:
| |
| Small-support equilibria: the paper, and my notes. | |
| Arriving at an equilibrium: Fictitious play and coarse correlated equilibria. | |
| Coarse-correlated equilibria and no-regret dynamics. | |
| Session 1: Connecting CCE and no-external-regret dynamics. Correlated equilibria and swap regret.
Session 2: Congestion games and best-response dynamics. | |
| PLS, PLS-completeness, and complexity of pure Nash equilibrium computation (my notes).
| |
| Efficiency and welfare in games. PoA and PoS in congestion games and global connection games.
| |
| PoA and PoS in facility location and valid utility games.
References: Sections 19.3 and 19.4 from the AGT book. Valid utility games are from this paper. Note: next class is on Wednesday, March 12th, 4 - 5:30 pm in A-238.
| |
| Smooth games and load balancing games.
References: For smooth games, Tim's notes lecture 14, particularly Sections 3 and 4. For selfish load-balancing games, Chapter 20 from the AGT book, and in particular Theorem 20.7. I would recommend reading the proof of existence of PNE (Proposition 20.3) as well.
| |
| Completed the proof for PoA of load-balancing games.
| |
| Mechanism design. Condorcet's paradox and Arrow's impossibility theorem. My notes.
References: AGT book, Chapter 9 until section 9.2.4.
| |
| The Gibbard-Satterthwaite impossibility theorem for social choice functions My notes.
References: AGT book, Chapter 9 until section 9.3.1.
| |
| Vickrey's second price auction. Cardinal mechanisms with money more formally, DSIC mechanisms, the Revelation Principle. Single parameter domains (notes) (we stopped after stating the theorem for implementable social choice functions).
References: Tim Roughgarden's notes for lecture 3.
| |
| Proof of Myerson's Lemma. Sponsored search auctions, multi-unit auctions, and knapsack auctions (notes).
References: Tim Roughgarden's notes for lecture 4. | |
| Revenue maximization in Bayesian auctions.
References: Tim Roughgarden's notes for lecture 5.
| |
| Simple near-optimal auctions (notes).
References: Tim Roughgarden's notes for lecture 6
| |
|
|
|
| |