MPCS 53810 Topics in Algorithmic Game Theory (Summer 2024)

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

Syllabus

Detailed Syllabus of this class is attached. Look at this for full details about the class. There may be small changes in the next 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:

Tentatively:

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

  2. 4 homeworks.

  3. 2-3 mini projects (out of several options).

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

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

  3. Voting and social dynamics

  4. Matchings: kidney exchange, Uber

  5. 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 + maybe 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) Many 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 may be somewhat different than the exact 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
Core Programming

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.

Please contact the instructor if you do not meet all the formal prerequisites but still wish to take the class.
Email: ishanagarwal@uchicago.edu

Overlapping Classes

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

  • MPCS 52011-1 -- Introduction to Computer Systems

Eligible Programs

Masters Program in Computer Science MS in Computational Analysis in Public Policy (Year 1) MS in Computational Analysis in Public Policy (Year 2) MA in Computational Social Science (Year 1) MA in Computational Social Science (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) MS in Molecular Engineering Undergraduate - CS Minor Undergraduate - CS Major