CS 6501: Topics in Learning and Game Theory (Spring 2021)

Basic Information

Class Location: Virtual on Zoom
Class Time: Tuesdays and Thursdays, 2:00 pm to 3:15pm
Instructor: Haifeng Xu
TAs: 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 applications of machine learning or prediction, we have to obtain data from self-interested agents whose objectives are not aligned with the system 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 two directions. En route, we will also develop necessary basics of game theory, learning theory, mechanism design, and information elicitation.

Topics covered in this course, and tentative syllabus:

This is primarily a theory course, and lecture-based. That said, we will focus on mathematical foundations with rigorous proofs but 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.

Schedule and Reading Materials (updated after each lecture)

Lecture Description and Slides Readings
1 (Feb 2) Introduction [slides] Kleinberg/Leighton paper
2 (Feb 4) Basics of LPs [slides] Chapter 2.1, 2.2, 4.3 of Convex Optimization by Boyd and Vandenberghe
3 (Feb 9) LP duality [slides] Lecture notes 5 and 6 of an optimization course by Trevisan
4 (Feb 11) Intro to Game Theory (I) [slides] Section 3.1, 3.2, 3.3 of an game theory book by Shoham and Leyton-Brown
5 (Feb 16) Intro to Game Theory (II) [slides] Equilibrium analysis of GANs by Arora et al.
6 (Feb 18) Intro to Online Learning [slides]
7 (Feb 23) Multiplicative Weight [slides] A survey paper on MWU and its applications by Arora et al.
8 (Feb 25) Swap Regret [slides] A note by Balcan on converting regret to swap regret
9 (Mar 2) Multi-Armed Bandits [slides] Section 2 and 3 of the Book by Bubeck and Cesa-Bianch on Bandits
10 (Mar 4) Mechanism Design Intro [slides] Lecture 1 and 2 of a Book by Roughgarden on Algorithmic Game Theory
(Mar 9) Spring break day -- no lecture
11 (Mar 11) Optimal Auction I [slides]
12 (Mar 16) Optimal Auction II [slides] Lecture 3, 4, 5 of a Book by Roughgarden on Algorithmic Game Theory
13 (Mar 18) Sample Auctions [slides] Revenue Maximization with a Single Sample
14 (Mar 23) Simple Auctions [slides] Notes from a similar course by Daskalakis and Syrgkanis
15 (Mar 25) Intro to Prediction Markets [slides]
16 (Mar 30) Scoring Rules [slides] Notes from a similar course by Waggoner
17 (Apr 1) PMs and Scoring Rules [slides] The original paper including all presented results
18 (Apr 6) Peer Prediction [slides] Bayesian Truth Serum paper
19 (Apr 8) Bayesian Persuasion [slides] The original Bayesian Persuasion paper
20 (Apr 13) Sell Information [slides] The Selling Information Through Consulting paper
(Apr 15) Spring break day -- no lecture
21 (Apr 20) Strategic Learning I [slides] Classification from Selected Samples paper
22 (Apr 22) Strategic Learning II [slides] Classification from Transformed Samples paper
23 (Apr 27) Strategic Learning III [slides] How Can ML Induce Right Efforts paper
24 (Apr 29) Tradeoffs of Fariness [slides] Inherent Trade-Offs in the Fair Determination
25 (May 4) Project Presentation Presentation Schedule and the Scoring Sheet
26 (May 6) Project Presentation Presentation Schedule and the Scoring Sheet

Homework

Due date Homework Note
03/05 Homework 1 Here is a HW solution template in case you need one

Requirements and Grading

Homework assignments will count for 60% of the grade. There will be 4-5 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 40% 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, get a deep understanding of the area and then write an overview report. 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.


Some Related Courses





Other Related Statements

Honor code (Adapted from Honor Syllabus Example Statement of UVa)

I trust every student in this course to fully comply with all of the provisions of the University’s Honor Code. By enrolling in this course, you have agreed to abide by and uphold the Honor System of the University of Virginia, as well as the policies specific to this course. All suspected violations will be forwarded to the Honor Committee, and you may, at my discretion, receive an immediate zero on that assignment regardless of any action taken by the Honor Committee.

Please let me know if you have any questions regarding the course honor policy. If you believe you may have committed an Honor Offense, you may wish to file a Conscientious Retraction by calling the Honor Offices at (434) 924-7602. For your retraction to be considered valid, it must, among other things, be filed with the Honor Committee before you are aware that the act in question has come under suspicion by anyone. More information can be found at here.

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 Student Disability Access Center 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: sdac.studenthealth.virginia.edu. If you have already been approved for accommodations through SDAC, please send me your accommodation letter and meet with me so we can develop an implementation plan together.

Discrimination and power-based violence

The University of Virginia is dedicated to providing a safe and equitable learning environment for all students. To that end, it is vital that you know two values that I and the University hold as critically important:

If you or someone you know has been affected by power-based personal violence, more information can be found on the UVA Sexual Violence website that describes reporting options and resources available - https://eocr.virginia.edu/

As your professor and as a human, I care about you and your well-being and stand ready to provide support and resources as I can. As a faculty member, I am required by University policy and federal law to report what you tell me to the University’s Title IX Coordinator. The Title IX Coordinator’s job is to ensure that the reporting student receives the resources and support that they need, while also reviewing the information presented to determine whether further action is necessary to ensure survivor safety and the safety of the University community. If you wish to report something that you have seen, you can do so at the Just Report It portal. The worst possible situation would be for you or your friend to remain silent when there are so many here willing and able to help.

Religious accommodations

It is the University’s long-standing policy and practice to reasonably accommodate students so that they do not experience an adverse academic consequence when sincerely held religious beliefs or observances conflict with academic requirements.

Students who wish to request academic accommodation for a religious observance should submit their request in writing directly to me via Email as far in advance as possible. Students who have questions or concerns about academic accommodations for religious observance or religious beliefs may contact the University’s Office for Equal Opportunity and Civil Rights (EOCR) at UVAEOCR@virginia.edu or 434-924-3200.

Section 5.2 - 5.4 are adapted from a SEAS-wide example