MPCS 53810 Topics in Algorithmic Game Theory (Spring 2026)

Section 1
Instructor(s) Agarwal, Ishan (ishanagarwal)
Location None
Meeting Times Wednesday 5:30pm - 8:30pm
Fulfills Core Theory Elective

Syllabus

Syllabus PDF: Please look at the attached syllabus (Winter 2025 version) for full details about the class. There may be small changes in this iteration of the class.


Premise of the class:


What is Algorithmic Game Theory?

‘Intersection of game theory and computer science’: analyzing/ designing algorithms or mechanisms in strategic environments (where agents are strategic about what inputs they give the algorithm; they may lie for their own benefit!)

  1. Analysis: given the currently implemented algorithms (mechanisms), analyze participating agents’ incentives/ behaviour.

  2. Design: design algorithms (mechanisms) that align participants incentives with ‘overall welfare’ and also have good algorithmic properties. Algorithmic mechanism design.

Learning goals:

  1. Be able to use fundamental game theoretic concepts to analyze how a ‘system’/‘mechanism’ can incentivize participants to behave a certain way.

  2. Learn how to think about/ manage what the ‘system’ (mechanism) you are designing incentivizes participants to do. Aligning individual incentives with the ‘overall good’. Examples: Classical/ more modern mechanisms.

  3. Gain exposure to the wide interplay between game theory and other computer-science topics: online algorithms, learning, optimization, cryptography, networks, routing, etc.

  4. Build widely useful skills: critical thinking and analysis/ independently reviewing literature, doing a project, and presenting your work and ideas to others.

Coursework:

  1. In class ‘games’ and their analysis/ other activities.

  2. 4 written homeworks.

  3. 2 mini projects.

  4. A final project and associated write-up + presentation.

Some possible topics/ applications:
  1. Prisoner’s dilemma
     
  2. Second price/ Google ad auctions

  3. Evolutionary game theory

  4. Voting and social dynamics

  5. Matchings: kidney exchange, Uber

  6. Game theory on the blockchain

Some more broad topics: equilibria, social welfare, fairness, competition, bargaining, online decision making, learning and game theory, mechanisms with and without money, economies and markets, reputation systems, incentives in peer to peer networks….many many other possibilities.

Things to be aware of:

1) Prerequisites: discrete math + basic algorithms + a tiny bit of calculus/ 'continuous' math. Don’t need to know any game theory.

2) This is a theory class: you should be comfortable with formal and mathematical writing/ reasoning.

3) Probably a smaller class: lots of discussions/ class participation.

4) Mini-projects/ final project. (Project could be mathematical/ theory focussed, or a case study or numerical/ qualitative experiments.)

5) You will read papers/ do simulations/ case studies/ present your work.

6) Specifications grading: not exam focussed, qualitative evaluation/ resubmissions/ continuous feedback. Based on understanding and applying the course materials + developing other skills (projects/ presentations).


To Learn More:

While we will not necessarilly completely follow just one textbook. However Tim Roughgarden's : Twenty Lectures on Algorithmic Game Theory is an excellent book that we will use. 

You can look at Chapter 1 of an early draft that is freely available online here. While the set of topics we cover will be different from the exact set  of material in this book, Chapter 1 (it's just ~ 5 pages long), should give you some sense of the flavour of the course and the kind of things we will care about and study in this class.


Contact:

If you are interested in the class and have any questions, or are unsure about meeting the prerequisites, please feel free to email me.
Email: ishanagarwal@uchicago.edu

Course Prerequisites

Must have complete MPCS 51036, 51040, 51042, 51046, 51100, CAPP 30122, MACS 30122, or have a Core Waiver for Programming.

B+ or better in MPCS 55001 Algorithms, a waiver for Algorithms based on CMSC coursework, or a pass on the Algorithms placement exam. This class can count as a Core Theory class for students with a waiver for Algorithms based on CMSC coursework or passing the Algorithms placement exam. This class can also count as a 6th Core class for 12-course students.

Other Prerequisites

Familiarity with discrete math, basic algorithms, and calculus. Prior knowledge of game theory is not required.

Students should be comfortable with formal and mathematical writing/reasoning.

This course requires competency in Unix and Linux. If you attended the MPCS Unix Bootcamp you covered the required material. If you did not, please review the UChicago CS Student Resource Guide here: https://uchicago-cs.github.io/student-resource-guide/.

Course request information for non-MPCS students: https://masters.cs.uchicago.edu/student-resources/non-mpcs-student-course-requests/

Overlapping Classes

This class is scheduled at a time that conflicts with these other classes:

  • MPCS 52030-1 -- Operating Systems
  • MPCS 53001-1 -- Databases
  • MPCS 51235-1 -- Advanced User Interface and User Experience Design
  • MPCS 51260-1 -- Human-Computer Interaction
  • MPCS 51238-2 -- Design, Build, Ship

Eligible Programs

MS in Computational Analysis in Public Policy (Year 2) Bx/MS in Computer Science (Option 1: Research-Oriented) Bx/MS in Computer Science (Option 2: Professionally-oriented - CS Majors) Bx/MS in Computer Science (Option 3: Profesionally-oriented - Non-CS Majors) Masters Program in Computer Science