6.853: Algorithmic Game Theory and Data Science

How do you setup an auction to optimize revenue? How do you price cloud resources to optimize efficiency? More broadly, how do you solve an optimization problem when your inputs are supplied by strategic agents with a keen interest on your solution, and who may therefore misreport their inputs to manipulate the result? How do you inform all these answers when you have access to data?

This class, situated at the intersection of Algorithms, Game Theory and Machine Learning, will present an analytical and computational framework to approach optimization and inference problems of this form. In doing so, we will also look at the foundations of Game Theory, Learning Theory and Econometrics.

Course Information

• Instructors: Constantinos Daskalakis, Vasilis Syrgkanis
  Office Hours: TBA
• TAs: Devendra Shelar, Govind Ramnarayan
• Useful Links: Stellar webpage, Piazza webpage
• Lecture: Tuesdays and Thursdays 2:30-4:00, 54-100 (both are subject to change).
• Textbooks:
  1. Parts of the course will follow the book Algorithmic Game Theory, by Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani (eds.), Cambridge University Press, September 2007.
  2. For extensive introduction to online learning and online convex optimization: Online Learning and Online Convex Optimization, by Shai Shalev-Shwartz, Foundations and Trends in Machine Learning
  3. For extensive introduction to mechanism design, revenue maximization and Myerson's theory: Mechanism Design and Approximation, by Jason Hartline
  4. For extensive introduction to PAC Learning: Understanding Machine Learning: From Theory to Algorithms, by Shai Shalev-Shwartz, Cambridge University Press, 2014
• Lecture Notes: Lecture notes and/or presentations will be provided.
• Prerequisites: A course in algorithms (6.046 or equivalent), probability (6.041 or equivalent), and discrete mathematics (6.042 or equivalent).
• Assessment: 65% problem sets (each problem (not problem set) counts equally), project 35%

Course Outline

There is a significant dynamic component to the course, as topics drop in and out, or get longer or shorter treatment, depending on audience interest/reaction/resistence. We consider this a feature. Given this, here is a rough outline of the course material:

Chapter 1. Game Theory and Online Learning Theory

1. Games, equilibria, minimax theorem, LP duality.
2. Online learning, online convex optimization, minimax theorem from no-regret learning.
3. Nash's theorem, complexity of Nash equilibria, PPAD.
4. Online learning and general games: correlated equilibrium via no-regret learning, quality of no-regret outcomes (price of anarchy)

Chapter 2. Mechanism Design and Statistical Learning Theory

1. Mechanism design: truthfulness, revelation principle, Myerson's lemma, Vickrey auction, Myerson's optimal auction
2. Simple vs Optimal auctions: single-sample mechanism, prophet inequality
3. Intro to Statistical Learning Theory: Rademacher complexity, Growth number
4. Statistical Learning Theory and Mechanism Design: learning optimal auctions from samples
5. Online learning of mechanisms

Chapter 3. Econometrics and Computer Science

1. Intro to estimation and inference
2. Econometrics in Games
3. Econometrics in Auctions: Revenue inference and A/B testing in auctions, Welfare guarantees from data
4. Econometrics for no-regret learners
5. Causal inference and machine learning

Homework

1. Problem Set 1: 3/15 (due: 3/4)
2. Problem Set 2: 3/8 (due: 3/23)
3. Problem Set 3: 3/23 (due: 4/10)
4. Problem Set 4: 4/11 (due: 4/25)
5. Problem Set 5: 5/2 (due: 5/10)

Projects

A list of project proposals will soon be posted on Stellar.

1. Project Proposal: due 4/3
2. Final Project: due 5/10

Lectures

Schedule subject to change

1. Lecture 2. Games, equilibria, minimax theorem, LP duality. [Lecture 2]
2. Lecture 3. Online learning, follow the regularized leader [Lecture 3]
3. Lecture 4. Online convex optimization, minimax theorem from no-regret learning [Lecture 4]
4. Lecture 5. Nash's theorem for general games [Lecture 5]
5. Lecture 6. Online learning and general games: correlated equilibrium via no-regret learning [Lecture 6]
6. Lecture 7: Complexity of Nash equilibria, PPAD
7. Lectures 8, 9: Mechanism design: truthfulness, revelation principle, VCG [Lecture 8] [Lecture 9]
8. Lectures 10, 11: Revenue maximization: Myerson's lemma, Myerson's optimal auction [Lecture 10] [Lecture 11]
9. Lecture 12: Simple vs Optimal auctions: single-sample mechanism, prophet inequality [Lecture 12]
10. Lecture 13: Simple vs Optimal auctions: Non-truthful auctions, price of anarchy [Lecture 13]
11. Lecture 14, 15: Intro to Statistical Learning Theory: Rademacher complexity, Growth number [Lecture 14] [Lecture 15]
12. Lecture 16, 17: Statistical Learning Theory and Mechanism Design: learning optimal auctions from samples [Lecture 16] [Lecture 17]
13. Lecture 18: Online learning of mechanisms
14. Lecture 19, 20, 21: Intro to Estimation: learning CDFs and density functions
15. Lecture 22, 23: Econometrics in Auctions: estimation of value distributions, revenue inference, welfare inference
16. Lecture 24, 25: Causal inference and machine learning: policy learning, heterogeneous treatment effect estimation

Online Resources

Previous incarnation of this class:

• Algorithmic Game Theory and Data Science, Spring 2017

Relevant workshops at recent conferences:

• First Workshop on Algorithmic Game Theory and Data Science, 2015
• Second Workshop on Algorithmic Game Theory and Data Science, 2016
• Third Workshop on Algorithmic Game Theory and Data Science, 2017
• NIPS17 Workshop on Learning in the Presence of Strategic Behavior
• NeurIPS 2018 smooth games and optimization workshop