Meeting Times: Tuesday, Thursday, 2:00 PM PST / 3:00 PM MST – 3:30 PM PST / 4:30 PM MST

First Class: Tuesday, January 11, 2022

Zoom Link:Has been sent to all registered students (including on waitlists). Please contact one of the instructors if you haven't received a link.

 

UBC Instructor: Kevin Leyton-Brown

UBC Instructor's Office Location: ICCS X565

UBC Instructor's Office Hours: Tuesdays and Thursdays 3:30–4:00 PM, or by appointment

UBC Web Pages: 532L; 532L waiting list; 530L; 530L waiting list

UBC Location (before February 7): Zoom; see above.

UBC Location (February 8 onwards): we'll decide if we prefer to remain online-only to facilitate interaction with James and the Alberta students. If the UBC contingent chooses to gather together in person, this will happen in ICICS/CS Building, room 246

 

Alberta Instructor: James R. Wright

Alberta Instructor's Office Location: ATH 3-57

Alberta Instructor's Office Hours: TBA

Alberta Web Pages: CMPUT 654; eClass

Alberta Location: CSC B-41

Prerequisites: The course has no formal prerequisites. As a graduate topics course, it will survey current research literature and expect students to be able to read, summarize, and form critical opinions of this material. Students may find it useful to have background in machine learning and in microeconomics and game theory; however, I expect that many students will not have all of this background. (Particularly, I recognize that most CS students may not have previous exposure to economics.) Data analysis and basic coding will be required. Additionally, an ability to speak, read and write fluently in English, and a willingness to participate actively in class discussions, is essential for success in the class.

 

Equity, Inclusion and Wellness: Please see the UBC CS Department's resources on this topic.

 

Academic Honesty: Plagiarism is a serious offence (see the UBC CS Department's statement) and will be dealt with harshly.  I consider plagiarism to be the unattributed use of an external source (e.g., another student, code or text from a web site, a book) in work for which a student takes credit, or the inappropriate use of an external source whether or not attribution is made. The seriousness of the offence depends on the extent to which the student relied upon the external source.  You must cite all external sources that you use, and write in your own words. Any text that you take verbatim from another source must be in quotation marks and followed by a citation.

 

Textbook: Material on game theory follows the book Essentials of Game Theory: A Concise, Multidisciplinary Introduction, K. Leyton-Brown, Y. Shoham, Morgan & Claypool Publishers, 2008. You should be able to get a free PDF copy of the book via the UBC or Alberta university library via this link. A more thorough treatment of the same material, plus many additional topics that may provide useful background for your project, appears in Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Y. Shoham, K. Leyton-Brown, Cambridge University Press, 2009. That book has a free PDF download.

UBC Course number: The course is cross-listed as CPSC 532L (Topics in Artificial Intelligence, part of the department's "Computational Intelligence" stream) and CPSC 530L (Topics in Information Processing, part of the department's "Interdisciplinary Studies" stream). Students are free to enroll in whichever course better suits their needs.

The course will consist of four major units.

 

Unit	Deliverables
1. Modeling Strategic Situations. We will begin by exploring what is meant by a "strategic situation": roughly, an environment in which multiple self-interested actors interact, and in which their satisfaction with the resulting state of the world is based on the decisions that both they and the other actor(s) chose. We will consider a variety of models of such interactions (simultaneous moves; sequential moves, with both perfect and imperfect information; Bayesian uncertainty; infinite repetitions of any of the above). We will also consider what makes a setting inappropriate for consideration as strategic: e.g., decision-theoretic settings exhibiting weak or no coupling between agents' payoffs.	Students will form small groups and identify a strategic domain that they will study together for the remainder of this course. We strongly encourage students to choose domains related to their existing research interests and/or expertise, and to form groups with students having similar interests.
2. Game Theoretic Analysis. This unit will survey the classical game theoretic question: "How should strategic agents behave?" We will learn various game theoretic answers to this question, such as best response, Nash equilibrium, dominant and dominated strategies, minimax strategies, and minimax regret strategies. We will learn how to apply these answers in a variety of game formalisms, including normal-form, extensive-form games with both perfect and imperfect information, Bayesian games, and repeated games.	Students will identify various games modeling aspects of their target domains and making use of different game formalisms. For each, they will identify game theoretic solution concepts, and will argue which is most appropriate for understanding the domain.
3. Modeling Strategic Behavior as a Machine Learning Problem. Unfortunately, humans often behave differently from the way game theory predicts. In this unit, we will consider an alternate approach to modeling human behavior in strategic settings, leveraging techniques from machine learning. We will consider a variety of candidate model families, including the Level-k, Cognitive Hierarchy, Quantal Response, and Quantal Level-k models from the behavioral game theory literature, and will also learn why traditional machine learning model families are often inappropriate for use in this setting. We will learn how to design experiments, obtain training data from human play of games, fit models to this training data, and detect and avoid overfitting these models.	Students will play each others' games from the previous unit and gather training data. They will use this data to fit different model families, and will argue which is most appropriate to their domain.
4. Project Presentations. The last unit will focus on research proposals for cutting-edge projects on modeling human behavior by combining methods from behavioral game theory and machine learning. We will begin with sample proposals from the instructors and TAs, and then will move on to proposals by groups of students in the class. You will have the opportunity to give and receive feedback on each others' proposals to inform the content of your final written submission.	At the end of the course, student groups will hand in a hypothetical thesis proposal putting forward a research program for modeling human strategic behavior in their chosen domain. Like a real thesis proposal, this will explain why the problem is important, survey related literature, present initial results, and describe promising avenues for further exploration.

 

Evaluation will consist of the following elements. We may adjust the exact grade breakdown as the course progresses.

 

Course Element	Worth
Participation	10 %
Three Assignments	24 %
Midterm	16 %
Peer Grading of Proposal Presentations	10 %
Proposal Presentation	15 %
Proposal Document	25 %

 

Grades will be divided among assignments in proportion to each assignment's total number of points. Proposal presentations and documents are group work, with the same grade assigned to each member of the group.

 

Late policy: Students will be given a 24-hour grace period for each assignment, where they can submit late without a grade penalty. After the grace period, late assignments will be penalized 20% per day. 

 

Final project presentation scheduling: We will create an initial schedule that assigns groups to presentation slots. Then, groups will be free to trade slots with each other if they can identify Pareto-improving changes. The initial schedule will begin with the smallest groups presenting first and the largest groups presenting last. Within a group size, we will schedule groups in descending order of the total amount of assignment grace period used by members of the group on the three assignments.