Algorithmic Economics and Machine Learning
When: MW 4:00-5:15pm
Where: ECCR 118
Professor: Rafael Frongillo
Office hours: Wednesdays 3pm outside CSEL (ECCS wing of Engineering Center, 1st floor)
Syllabus, Assignments, Grades: Moodle (key: AGT)
Traditional algorithm design takes the view that your program will run on its own machine, separated from the rest of the world behind a nice sturdy brick wall. Particularly with the onset of the internet, modern algorithmic design has needed to cope with what happens when this wall breaks down. As an example, early versions of protocols like TCP-IP were subject to attacks of various kinds, which often suited the attacker by allowing arbitrarily high bandwidth at the expense of other users. In a nutshell, algorithms were now subject to selfish behavior, and they needed to be designed to successfully navigate this new game theoretic world. Algorithmic game theory, or more broadly, algorithmic economics was born.
In this class, we will explore topics in algorithmic economics and algorithmic game theory, highlighting connections and applications to theoretical machine learning. The class will alternate between lectures to give adequate background and student presentations on related research papers or additional material. Topics will include algorithmic mechanism design, social choice, online learning, information elicitation, empirical risk minimization, prediction markets, crowdsourcing mechanisms, and differential privacy.
This is a research-oriented class. Rather than the typical approach of moving linearly through a body of material, we will instead focus on some core concepts, and then discuss other concepts as needed for the research papers being presented or the final research projects which will dominate the latter half of the course. As such, the nominal goal of the course is to prepare students to do research in algorithmic economics and theoretical machine learning, or related areas. That said, students who simply wish to learn about the topic can choose a final project with less of a research focus.
Prerequisites: I would suggest a solid background in algorithms, and ``mathematical maturity'' (meaning a grasp of proof writing and balancing intuition with formal arguments).
- Week 1-3: Information Elicitation I
- proper scoring rules
- property elicitation and ML
- Week 4-5: Algorithmic game theory
- game theory
- mechanism design
- social choice and voting
- selfish routing and price of anarchy
- Week 6-7: Online learning
- basic settings
- Week 8: Information elicitation II
- peer prediction
- crowdsourcing mechanisms
- prediction markets
- Week 9: Differential privacy
- basic mechanisms
- continual observation technique
- Week 10-14: Open topics, paper presentations, project updates
- Week 15-16: Project presentations
Information elicitation tutorial
Algorithmic Game Theory, edited by Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani -- also in Moodle
Algorithmic game theory primer by Tim Roughgarden
LaTeX resources and guides: one, two, three, four
Behold: the comic.
Thanks for a great class everyone!