|
|
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; computational social choice and fairness. |
|
|
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 Mon/Wed 2-3:30 pm in A-201.
Classes begin on August 17th. |
|
|
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. | |
| Computing equilibria in zero-sum games via LP duality. | |
| Symmetric games and the Lemke-Howson algorithm. An example.
Reference: Chapter 2 from the AGT book (which also has the example above). | |
| A proof of Nash's Theorem.
| |
| A proof of Brouwer's Fixed-Point Theorem and Sperner's Lemma.
| |
| The complexity of finding a Nash equilibrium.
| |
| Fictitious play and coarse correlated equilibria.
| |
| Algorithms for no external regret, and correlated equilibria.
| |
| An algorithm for no internal regret. Best response dynamics, network congestion games, and potential games.
| |
| PLS, PLS-completeness, and complexity of pure Nash equilibrium computation.
| |
| Price of Anarchy and Price of Stability 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.
| |
| Smooth games, and PoA and PoS in 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.
| |
| Mechanism design. Condorcet's paradox and Arrow's impossibility theorem.
References: AGT book, Chapter 9 until section 9.2.4.
| |
| Social choice functions, and the Gibbard-Satterthwaite theorem. Cardinal mechanisms with money, and Vickrey's second price auction.
References: AGT book, Chapter 9 until Section 9.3.1.
| |
| Cardinal mechanisms with money more formally, DSIC mechanisms, the Revelation Principle. Single parameter domains and Myerson's Lemma.
References: Tim Roughgarden's notes for lecture 3.
| |
| Proof of Myerson's Lemma. Sponsored search auctions, multi-unit auctions, and knapsack auctions.
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.
References: Tim Roughgarden's notes for lecture 6
| |
| Multi-parameter mechanism design.
References: Tim Roughgarden's notes for lecture 7
| |
| Maximal-in-range mechanisms.
References: The paper "Mechanisms for multi-unit auctions" by Dobzinski and Nisan, available here , particularly Section 3.2.
| |
| Truthful mechanisms without money: housing allocation and kidney exchange.
References: Tim Roughgarden's notes for lecture 9 and lecture 10
| |
| Stable matching.
References: Tim Roughgarden's notes for lecture 10
| |
| Fair division of indivisible goods. | |
|
|
|
| |