CS 6501: Topics in Learning and Game Theory (Spring 2021)
Basic InformationClass Location: Virtual on Zoom
Class Time: Tuesdays and Thursdays, 2:00 pm to 3:15pm
Instructor: Haifeng Xu
- Email: hx4ad AT virginia.edu
- Office hours: Tuesday 3:15 pm - 4:15 pm (rightly after class), Zoom
- Jibang Wu,       Email: jw7jb AT virginia.edu;      Office hour: Weds 2 – 3 pm, Zoom
- Fan Yao,           Email: fy4bc AT virginia.edu;      Office hour: Fridays 3 – 4 pm, Zoom
- Feb 23: Project instruction is out. Please read it carefully and try to form a team from now and discuss your potential project topics. A short (at most one-page) proposal is due to Gradescope by 03/15.
- Feb 13: Homework 1 is out. Please start it early. We also provide a HW template just in case you need one.
- Nov 11: Course website is up!
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:
- First Half: Machine Learning for Game Theory
- (week 1) Linear programming and duality
- (week 2-3) Intro to game theory, zero-sum games
- (week 3-4) No regret learning and its convergence to equilibrium
- (week 5-6) Intro to learning theory
- (week 6-7) Intro to auctions and mechanism design
- (week 8-9) learning optimal auctions from samples
- Second Half: Game Theory for Machine Learning
- (week 10) Mechanism design for information elicitation: scoring rules and prediction markets
- (week 11) Peer prediction and Bayesian truth serum
- (week 12) Selling information
- (week 13-14) Learning from strategic data sources
- (week 15) Fairness tradeoffs in prediction
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|
|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
- Constantinos Daskalakis and Vasilis Syrgkanis: Algorithmic Game Theory and Data Science, MIT, Spring 2019
- Ilias Diakonikolas and Shaddin Dughmi: Topics in Learning and Game Theory, USC, Fall 2017
- Yiling Chen: Prediction, Learning and Games, Harvard, Spring 2016
- Michael Kearns and Aaron Roth: No Regrets in Game Theory and Machine Learning , UPenn, Spring 2013
- Maria Florina Balcan: Learning, Game Theory, and Optimization , CMU, Fall 2010
- Robert Kleinberg: Learning, Games, and Electronic Markets, Cornell, Spring 2007
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 needsWe 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:
- Power-based personal violence will not be tolerated.
- Everyone has a responsibility to do their part to maintain a safe community on Grounds.
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