CS 181: Algorithmic Game Theory - Fall 2026

Overview

Welcome to CS 181: Algorithmic Game Theory! The instructor for this course is me, Professor Zlatin. The class meets on Mondays and Wednesdays from 11:00 - 12:15pm in Lincoln 1125. My office hours are on Tuesdays from 10:00 - 11:30am, Wednesdays 4:00 - 5:00pm, and by appointment in Edmunds 223. I am happy to talk about the class, CS theory or whatever is on your mind. The best way to reach me is by email. There will also be a course Slack channel. Check out the syllabus and course schedule below!

Syllabus

Course Description: Algorithmic Game Theory is an interdisciplinary field at the interface of Economics and Computer Science. In classical algorithm design, we treat the input as a fixed and accurate description of the problem at hand. What happens when that input is instead supplied by people (or agents) who have goals and incentives of their own? How might strategic behavior impact the performance of real-world systems that rely on these algorithms? Finally, can we design incentive-aware algorithms that elicit the behavior we seek from these strategic agents?

This course develops the foundations of AGT and its applications. We will cover topics such as: games and equilibria, auctions and mechanism design, matching markets, the price of anarchy, and fair division.

This class has CS 140 as a prerequisite. It is also focused on algorithm design and analysis, not implementation. Please send me an email if you are considering enrolling and have any questions.

Deliverables: Most weeks, I will put out a set of exercises accompanying the material for that week. These will be graded for completion/effort and correctness: half of the points are achieved by turning something in with a genuine effort. There will be around four larger assignments in the course - these will typically consist of around four problems which will augment the material we learn in class, and are done in groups of two. There will be two in-class exams which will serve as checkpoints for the first and second half of the course material respectively. Finally, there will a course project with associated milestones. The grading breakdown is as follows:

• Participation – 5%
• Exercises – 16%
• Assignments – 40%
• Checkpoints – 12% + 12%
• Final project and milestones – 15%

Course Project: The final project will consist of a deeper exploration of some aspect of algorithmic game theory, as well as a presentation of your findings. There are two main directions you can take. One is to choose some topic which we didn't get to cover in class (and there are many cool ones), learn about the motivation for the problem, the history, and methods for its solution. The second option is to select some computational task or applied problem of your own interest (or from a recent paper), implement it and evaluate it empirically while using known theoretical properties as a baseline. Students will work in teams of two.

Policies: Attendance is required, please let me know as early as possible if you cannot attend class. If you want to meet outside of office hours, write me an email or come to my office - if I am there I will answer your questions. Any feedback, concerns, or suggestions are more than welcome. You can email me, come to my office or submit feedback through this anonymous form . If you need accommodations, please contact the Disability Coordinator on your home campus. The process for Pomona students is available here. If you feel overloaded with the amount of work for this course, or are feeling burned out, I encourage you to contact me so that we can address the concerns together. You are probably not alone in feeling that way, and I am here to help.

Resources: We won't follow any particular textbook fully, but we will draw topics from the following:

• Twenty Lectures on Algorithmic Game Theory, by Tim Roughgarden (TR).
• Networks, Crowds and Markets, by David Easley and Jon Kleinberg (EK).
• Mechanism Design and Approximation, by Jason Hartline (JH).

Schedule

This is the course calendar, which will be populated over time with lecture notes and associated readings.^*

^* Much of this course has been adapted from Tim Roughgarden and especially Shikha Singh's course materials. Many thanks to them!

Exercises

These will be released over the course of the semester.

Assignments

These will be released over the course of the semester.