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)
Webpage: https://www.cs.colorado.edu/~raf/teaching/7000-s17.html
Syllabus, Assignments, Grades: Moodle (key: AGT)

Overview

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).

Schedule

Resources

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

Parting Words

Behold: the comic.

Thanks for a great class everyone!