CMSC 35401: Topics in Machine Learning

The Interplay of Learning and Game Theory (Autumn 2022)

Basic Information

Class Location: K 102 (the class is fully in person unless noted otherwise)
Class Time: Tuesdays and Thursdays, 2:00pm to 3:20pm
Instructor: Haifeng Xu
TA: Minbiao Han
Course Material: There will not be any official textbook, but the slides and links to reading materials will be posted on the course schedule after each lecture.

Announcements


Course Description

Welcome! This is a graduate level course covering topics at the interface between machine learning and game theory. In many economic or game-theoretic applications, the problem either lacks sufficient data or is too complex. In such cases, machine learning theory helps to design more realistic or practical algorithms. Conversely, in many application of machine learning or prediction, the algorithms have to obtain data from self-interested agents whose objectives are not aligned with the algorithm designer. In those settings, the algorithms have to take into account these agents' strategic behaviors. These problems form an intriguing interplay between machine learning and game theory, and have attracted a lot of recent research attention. This course will discuss several recent research directions in this space. Our goal is to cover (some selected) basic results in the following four directions. Alone the way, we will also cover necessary basics to game theory, learning theory, mechanism design, prediction and information aggregation.

Topics covered in this course, and tentative syllabus:

This is primarily a theory course, and lecture-based. That said, we will focus on proofs and will not write code. Prerequisites include linear algebra, probability and algorithms. Familiarity to optimization is a plus but not necessary. Note that no background on game theory or learning theory is required.

Tentative Schedule and Readings (slides will be posted after each lecture)

Week Lectures Readings
1 (Sep 27) Introduction [slides] Kleinberg/Leighton paper
2 (Sep 29) Basics of LPs [slides] Chapter 2.1, 2.2, 4.3 of Convex Optimization by Boyd and Vandenberghe
3 (Oct 4) LP duality [slides] Lecture notes 5 and 6 of an optimization course by Trevisan
4 (Oct 6) Intro to Game Theory (I) [slides] Section 3.1, 3.2, 3.3 of an game theory book by Shoham and Leyton-Brown
5 (Oct 11) Intro to Game Theory (II) [slides] Equilibrium analysis of GANs by Arora et al.
6 (Oct 13) Intro to Online Learning [slides]
7 (Oct 18) Multiplicative Weight [slides] A survey paper on MWU and its applications by Arora et al.
8 (Oct 20) Swap Regret [slides] A note by Balcan on converting regret to swap regret
9 (Oct 25) Multi-Armed Bandits [slides] Section 2 and 3 of the Book by Bubeck and Cesa-Bianch on Bandits
10 (Oct 27) Prediction Markets (PMs) [slides] Notes from a similar course by Waggoner
11 (Nov 1) PMs and Scoring Rules [slides] The original paper including all presented results
12 (Nov 3) Peer Prediction [slides] Bayesian Truth Serum paper
13 (Nov 8) Bayesian Persuasion [slides] The original Bayesian Persuasion paper
14 (Nov 10) Pricing of Information [slides] The Optimal Pricing of Information paper
15 (Nov 15) Strategic Learning I [slides] PAC-learning for Strategic Classification paper
16 (Nov 17) Strategic Learning II [slides] How Can ML Induce Right Efforts paper
(Nov 22) Thanksgiving, No Lecture
(Nov 24) Thanksgiving, No Lecture
17 (Nov 29) Tradeoffs of Fairness [slides] Inherent Trade-Offs in the Fair Determination
(Dec 1) Project presentations [schedule]

Homework

Due date Homework Note
10/18 Homework 1 Here is a HW solution template in case you need one
11/03 Homework 2 Good luck!
proposal due 11/03 Projection Instructions Email us if need any help
12/06 Homework 3 Good luck!

Requirements and Grading

Homework assignments will count for 50% of the grade. There will be 3 assignments, roughly 3 weeks apart each. The homework will be proof-based, and are intended to be very challenging. Collaboration and discussion among students is allowed, even encouraged. However, students must write up the solutions independently. The remaining 50% of the grade is allocated to a final project. Students can team up for the project and each team should consist of 2 to 4 people. The project can: (1) study a research problem relevant to the course (ideally, also related to your own research) and write a report about your research findings; or (2) survey a related research topic by reading papers in that area and write an overview report of the area. More detailed instructions will come later.

There is no midterm or final for the course.

Late Homework Policy : Each student is allowed one late homework for at most two days from the due date. You may choose whichever homework to use this chance (or not use it). No additional late homework will be accepted.



Students with disabilities or learning needs

We thrive to create a learning experience that is as accessible as possible. If you anticipate any issues related to the format, materials, or requirements of this course, please meet with me outside of class so we can explore potential options. Students with disabilities may also wish to work with the UChicago Student Disability Services to discuss a range of options to removing barriers in this course, including official accommodations. Please visit their website for information on this process and to apply for services online: disabilities.uchicago.edu. If you have already been approved for accommodations through SDS, please send me your accommodation letter, and meet with me if needed, so we can develop an implementation plan together.