Algorithmic Economics

When: TTh 11:00-12:15pm
Where: ECCR 1B55 and Zoom (password is the 4-digit course number)
Professor: Rafael Frongillo
Webpage: https://www.cs.colorado.edu/~raf/teaching/6314-s22.html
Syllabus: below
Assignments, grades: Canvas
Schedule, suggested papers, signups: Spreadsheet
Lecture notes, etc: Google drive


Syllabus

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. See below for a partial list of topics.

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

Tentative Schedule

Course work and grading

The grading breakdown is tentatively as follows.

Mini-reviews

When a "mini-review" of a paper is assigned, you should spend a good 1-2 hours (depending on length and density) to read the paper; don't just skim it. (Skipping a few proofs can be okay.) Then submit the following in Canvas in plain text:

All-in-all your mini-review should be at least 3 paragraphs.

Peer feedback

The morning before class, read through the mini-review you were assigned, and respond to it in a few sentences (or more). Do you think the summary is accurate? Is the review fair? Are there any particularly good points made? Take note of the latter and bring them up during the discussion.

Problem sets

I may assign small problem sets, to make sure everyone is following. You may submit these as very legible hand-written or in LaTeX. If you don't know LaTeX, you will probably need it for your project anyway! I'd recommend Overleaf in that case.

Guidelines for paper presentations

When you present a paper to the class, you should prepare slides that go over the paper in detail, aiming for about 20 minutes. Try to cover the following:

You should email me your slides at least 3 days before your presentation so that I can give you feedback.

Final Project

For your final project, you are welcome to work alone or in groups of 2 (maybe 3 if we have enough students). The purpose of the project is to engage in research related to the topics covered in class. This could mean exploring a connection with your existing research, tackling one of the open problems discussed in class, or coming up with your own topic or question (related to class of course). The final product of the project will be a report written in the style of a scientific paper which describes the findings (see below).

The following components comprise your final project grade:

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