MPCS 53810 Topics in Algorithmic Game Theory (Spring 2026)

Section 1
Instructor(s) Agarwal, Ishan (ishanagarwal)
Location None
Meeting Times
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 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 small 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

B+ or higher in MPCS 50103 Discrete Math (Immersion Math) OR a passing score on the Mathematics Placement exam.
B+ or higher in MPCS 55001 Algorithms or MPCS 55003 Intermediate Algorithms

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 does not conflict with any other classes this quarter.

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