Instructor: Bo Waggoner
Time: Mon/Wed/Fri 13:00 - 13:50
Room: HUMN 1B90
Course information and syllabus
News: Project guidelines page is here
This advanced graduate-level course will cover a number of topics at the interface of computer science and microeconomics, from a theoretical perspective. Examples of likely topics include online learning, mechanism design for approximate welfare and revenue maximization, information elicitation and aggregation, and/or computational social choice. The course will focus on reading papers and a final project.
Prerequisites: The course will have flexibility in allowing students to keep up at their own pace. Preprequisites encouraged, but not required, include multivariable calculus, linear algebra, probability, and analysis; and undergraduate algorithms and complexity theory. No economic prerequisites are assumed.
To sign up for our class on NB, please paste these two strings together in your browser:
https://nb.mit.edu/subscribe?key=OeSCswNgU5dl4eh5p
hmU981ksHM1GuDZ0veU7p1o1OFFLumFuL
| Mon, Jan 13 | Intro to game theory |
|
| Resources | Osborne and Rubinstein Ch 1, Ch 2 - 2.4, and Ch 3 - 3.2; vN+M utility theorem discussed in class; risk aversion |
|
| Wed, Jan 15 | Types of games - Bayesian, extensive form |
|
| Resources | Osborne and Rubinstein Ch 2.6-end, Ch 6 - 6.2 |
|
| Fri, Jan 17 | Computing equilibria - congestion games |
|
| Resources | ||
| Mon, Jan 20 | MLK Day - No class |
|
| Wed, Jan 22 | Computing equilibria - PPAD, Brouwer, etc |
|
| Resources | ||
| Fri, Jan 24 | Generic sampling algorithm for NASH |
|
| Reading | Lipton, Markakis, Mehta. Playing Large Games Using Simple Strategies. Electronic Commerce (EC), 2003. |
|
| Mon, Jan 27 | PPAD-hardness of NASH |
|
| Reading | Daskalakis, Goldberg, Papadimitriou. The Complexity of Computing a Nash Equilibrium. (circa 2006, simplified version). |
|
| Resources | ||
| Wed, Jan 29 | More on computational hardness, gadgets, circuits, etc |
|
| Fri, Jan 31 | Hardness of NASH under ETH-like assumptions |
|
| Reading | Aviad Rubinstein. Settling the Complexity of Computing Approximate Two-Player Nash Equilibria. Foundations of Computer Science (FOCS), 2016. |
|
| Mon, Feb 03 | Guest Presentation - Anson Kahng, Carnegie Mellon |
|
| Resources | ||
| Wed, Feb 05 | Online learning - Polynomial Weights |
|
| Resources | Penn lecture notes on Polynomial Weights (skip page 1); Arora, Hazan, Kale. The Multiplicative Weights Update Method:A Meta-Algorithm and Applications. Theory of Comp., 2012 (survey paper). |
|
| Fri, Feb 07 | Online Learning dynamics |
|
| Reading | Bailey, Gidel, Piliouras. Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent. Working paper, 2019. |
|
| Mon, Feb 10 | Zero-sum games |
|
| Reading | Freund, Shapire. Adaptive Game-Playing Using Multiplicative Weights. Games and Economic Behavior, 1999. |
|
| Resources | ||
| Wed, Feb 12 | Developments in solving zero-sum games |
|
| Fri, Feb 14 | Online learning for game-solving |
|
| Reading | Brown, Lerer, Gross, Sandholm. Deep Counterfactual Regret Minimization. International Conference on Machine Learning (ICML), 2019. |
|
| Mon, Feb 17 | Proper scoring rules |
|
| Reading | Brier. Verification of Forecasts Expressed in Terms of Probability. Monthly Weather Review, 1950. |
|
| Wed, Feb 19 | Characterization of Proper Scoring Rules |
|
| Resources | ||
| Fri, Feb 21 | Proper Scoring Rules continued |
|
| Reading | Savage. Elicitation of Personal Probabilities and Expectations. Journal of the American Statistical Association, 1971. |
|
| Resources | Gneiting, Raftery. Strictly Proper Scoring Rules, Prediction,and Estimation. Journal of the American Statistical Association, 2007. |
|
| Mon, Feb 24 | Prediction Markets |
|
| Reading | Hanson. Combinatorial Information Market Design. Information Systems Frontiers, 2003. |
|
| Resources | Wolfers, Zitzewitz. Prediction Markets. Journal of Economic Perspectives, 2004. |
|
| Wed, Feb 26 | Further discussion on prediction markets; convex analysis basics |
|
| Fri, Feb 28 | Computationally efficient prediction markets |
Project proposal due |
| Reading | Abernethy, Chen, Wortman Vaughan. Efficient Market Making via Convex Optimization, and a Connection to Online Learning. Transactions on Economics and Computation, 2013. |
|
| Mon, Mar 02 | Wagering mechanisms |
|
| Reading | Freeman, Pennock, Wortman Vaughan. An Equivalence Between Wagering and Fair-Division Mechanisms. AAAI, 2019. |
|
| Wed, Mar 04 | Further discussion on wagering mechanisms and/or fair division |
|
| Fri, Mar 06 | Information elicitation and online learning |
|
| Reading | Freeman, Pennock, Podimatra, Wortman Vaughan. No-Regret and Incentive-Compatible Online Learning. Working paper, 2019. |
|
| Resources | ||
| Mon, Mar 09 | Persuasion and online decisionmaking |
|
| Reading | Immorlica, Mao, Slivkins, Wu. Bayesian Exploration with Heterogeneous Agents. The Web Conference (WWW), 2019. |
|
| Wed, Mar 11 | Information elicitation without verification (a.k.a. peer prediction) |
|
| Resources | Miller, Resnick, Zeckhauser. Eliciting Informative Feedback: The Peer-Prediction Method. Management Science, 2005. |
|
| Fri, Mar 13 | Frontiers of peer prediction |
|
| Reading | Kong. Dominantly Truthful Multi-Task Peer Prediction with a Constant Number of Tasks. Symposium on Discrete Algorithms (SODA), 2020. |
|
| Mon, Mar 16 | Decision markets |
|
| Reading | Hanson "futarchy" post and: Teschner, Rothschild, Gimpel. Manipulation in Conditional Decision Markets. Group Decision and Negotiation, 2017. |
|
| Wed, Mar 18 | Prediction markets, governance, and/or blockchain |
|
| Fri, Mar 20 | Decentralized Prediction Markets |
Project progress report due |
| Reading | van Shreven, N. Goel, Faltings. Infochain: A Decentralized System for Truthful Information Elicitation. Working paper, 2019. |
|
| Mon, Mar 23 | Spring break - no class |
|
| Wed, Mar 25 | Spring break - no class |
|
| Fri, Mar 27 | Spring break - no class |
|
| Mon, Mar 30 | Mechanism design, "social welfare", and price of anarchy |
|
| Reading | Roughgarden, Syrgkanis, Tardos. The Price of Anarchy in Auctions. Journal of AI Research, 2017 (survey paper). Sections 1-2 |
|
| Resources | Mechanism Design and Approximation book by Hartline |
|
| Wed, Apr 01 | Smoothness arguments and price of anarchy |
|
| Resources | Roughgarden, Syrgkanis, Tardos. The Price of Anarchy in Auctions. Journal of AI Research, 2017 (survey paper). Sections 4-5 |
|
| Fri, Apr 03 | Mechanism design as group decisionmaking for welfare maximization |
Project progress report due |
| Reading | Fotakis, Tsipras, Tzamos, Zampetakis. Efficient Money Burning in General Domains. Theory of Computing Systems, 2016. |
|
| Resources | ||
| Mon, Apr 06 | Revenue maximization |
|
| Reading | ||
| Wed, Apr 08 | More on Myerson: revelation principle, truthfulness characterization |
|
| Resources | ||
| Fri, Apr 10 | Mechanism design and revenue |
|
| Reading | Kleinberg, Weinberg. Matroid Prophet Inequalities. Symposium on Theory of Computing (STOC), 2012. |
|
| Resources | ||
| Mon, Apr 13 | Competition improving revenue |
|
| Reading | Fu, Liaw, Randhawa. The Vickrey Auction with a Single Duplicate Bidder Approximates the Optimal Revenue. Economics and Computation (EC), 2019. |
|
| Wed, Apr 15 | Automated mechanism design, learning theory prereqs for Friday |
|
| Fri, Apr 17 | Learning auction rules and pseudodimension |
Project progress report due |
| Reading | Morgenstern, Roughgarden. Learning Simple Auctions. Conference on Learning Theory (COLT), 2016. And 9-min video presentation |
|
| Mon, Apr 20 | Learning auction rules, continued |
|
| Reading | Gonczarowski, Weinberg. The Sample Complexity of Up-to-ε Multi-Dimensional Revenue Maximization. Foundations of Computer Science (FOCS), 2018. |
|
| Wed, Apr 22 | Project presentations |
|
| Fri, Apr 24 | Project presentations |
|
| Mon, Apr 27 | Project presentations |
|
| Wed, Apr 29 | Project presentations |
|
Sat, May 02: Final project writeups due.