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

• Week 1-4: Information Elicitation I
  • scoring rules
  • connection to machine learning
  • elicitation complexity
  • multi-agent: wagering and SRMs
• Week 5: Algorithmic game theory
• game theory
• mechanism design
• Week 6: Online learning
  • basic settings
• Week 7-9: Game-theoretic probability
  • foundations
  • e values . algorithmic randomness
• Week 10-14: Open topics, paper presentations, project updates
• Week 15-16: Project presentations

Course work and grading

The grading breakdown is tentatively as follows.

• 10% Attendance / participation. Participation is based on in-class discussions.

• 30% Mini-reviews, peer feedback, and problems. When a research paper is assigned, students will submit a mini-review, described below. These will be due no later than 11pm the night before class. This deadline is important, since you will then be asked to leave feedback for another student, due 10 minutes before class. The point of these regular assignments is to give you practice (a) reading research papers, (b) thinking critically about them, and (c) strengthening your ability to form new research questions. They also form the basis for the class discussion. In addition to these regular assignments, there may also be two or three short problem sets to test understanding of the core material---though if possible we will work on some of these problems in class.

• 20% Presentations. Students are required to give at least one presentation to the class on a paper of their choice (and approved by the instructor), and lead the discussion.

• 40% Final project. The second half of the class will be centered around research projects, on which students will work in small groups on topics of their choice (subject to approval).

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:

• Summary: 1 paragrph describing the subject, motivation, results, and techniques in the paper, in your own words.
• Critique: 1-3 paragraphs or equivalent bullet points on the merits of the paper as well as issues you see. For example:
  • What did you like about the paper?
  • What did you dislike about the paper, and/or what could be improved?
  • Were all assumptions reasonable?
  • Were there any questions left open you felt the authors should have addressed?
  • How significant do you think the findings are?
• Extensions: 1 paragraph describing how one could fix the major issues you raised, and/or what interesting extensions or directions one could take from the paper.

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:

• Motivation, setting, relevant previous work. [1-2 minutes]
• Overview of main results. [1-2 minutes]
• In-depth proof sketch of one of the main results (check with me about which result to focus on). You should be able to walk through the key steps of the proof so that everyone walks away understanding exactly why the result holds, but not necessarily detailed enough that they could sit down and prove it. [10-15 minutes]
• Comments on future or subsequent work. [1-2 minutes]

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:

• Mini-proposal: The goal for this assignment is to give you a chance to run your project idea(s) by me to make sure it/they will fit, before you write the full 2-page proposal (below). To this end, you should give whatever details you think would be relevant. At a bare minimum though, give a paragraph or two sketching the topic, motivation, previous work, questions, and techniques (again, see below). And if you have a few potential project ideas, do the same for each.

• Proposal: Submit a 1-to-2-page document as a group listing the group members, the topic, its motivation and relevant existing work (with citations), explicit questions that you will pursue, techniques that you think will be relevant, and a rough timeline/plan for the research. While the focus of this class is theoretical, more applied research projects may be appropriate. If you are not sure whether your topic will be acceptable, please ask me in office hours. If your proposal is not accepted I will ask you to revise or submit another.

• Status report: Roughly mid-way through the project period, groups will give short [15-20 minute] presentations describing their progress. This is partly for you to receive feedback and ask for suggestions (especially if you are stuck), but also to ensure that you do not leave the project to the last minute. All students involved in the project should speak.

• Final presentation: Same as the status report, but roughly 30 minutes.

• Final write-up: The most important deliverable is the write-up, which should describe your findings in the style of a scientific publication, either in a journal (e.g. JMLR, Annals of Statistics, or similar) or conference (e.g. COLT) format. Take the write-up seriously, and write it as if you were actually submitting it for publication. (Indeed, some groups may end up doing so.) This means you should have a proper abstract, introduction, related work, and citations throughout, and any reader of the target journal audience should be able to follow easily. There will not be strict requirements on the length, but you should aim for a length comparable to a COLT submission (which comes to 12 pages in that format, plus references and an appendix).

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

Powered by hyde.