Models of Strategic Behavior
CPSC 532L; Term 2, 2022–23
Right now, this page mostly follows the previous offering of the course. I'll be updating it as we get closer to Winter, 2023. Overall, I'm planning to deemphasize behavioral game theory relative to the previous offering and to cover more material from my Coursera courses (1, 2) and textbooks (1, 2).
Course Description: This course will focus on models for predicting human strategic behavior. At the beginning of the course, groups of students will identify a strategic setting (e.g., from their own research areas) which they will study throughout the course. We will learn about how to analyze strategic settings from the perspective both of classical game theory and of machine learning, and students will apply such analysis (both mathematical and computational) to their chosen domains. The last part of the course will focus on student presentations of mock thesis proposals on their chosen topics.
Co-Instructors: The course will be remotely co-taught by Prof. Kevin Leyton-Brown and Prof. James R. Wright of the University of Alberta. Classes will be held over Zoom to permit full interaction with U of A students. Students will be free to do group work with other UBC and/or U of A students, as they prefer.
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
Alberta Instructor: James R. Wright
Alberta Instructor's Office Location: ATH 3-57
Alberta Instructor's Office Hours: TBA
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.
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.
|Three Assignments||24 %|
|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.
|January 6||Zoom office hours for any Alberta students |
with logistical questions; No UBC class
|Alberta first day of class|
|January 11||Introduction and Overview||UBC first day of class|
|January 13||Utility and Foundations|
|January 18||Game Representations|
|January 20||Game Representations II|
|January 25||Canonical Game-Theoretic Domains|
|January 27||Formalizing & Solving Normal-Form Games: |
Pareto & Nash
|February 1||Formalizing & Solving Normal-Form Games: |
Maxmin, Dominance, Rationalizability
|Assignment 1: pick and justify a domain/problem|
|February 3||Formalizing & Solving Extensive-Form Games|
|February 8||Formalizing & Solving Imperfect-Information Extensive-Form Games|
|February 10||Repeated Games|
|February 15||Bayesian Games|
|February 17||Mechanism Design & Auctions|
|February 22||Reading week|
|February 24||Reading week||Assignment 2: refine the games about your domain, compute and argue for solution concepts|
|March 1||Play each others' games|
|March 3||Behavioral Game Theory|
|March 8||Machine Learning for BGT|
|March 10||BGT: Extensive, Bayesian, Regret|
|March 15||BGT: Risk Aversion and Loss Aversion|
|March 22||Giving Effective Presentations||Assignment 3: fit ML models to the data from March 1|
|March 24||Giving Effective Presentations|
|March 29||Example Presentations|
|March 31||Student Proposal Presentations (3 groups)|
|April 5||Student Proposal Presentations (3 groups)|
|April 7||Student Proposal Presentations (4 groups)|
|April 22||Makeup Midterm (tentative date)|
|April 27||Projects Due||Project Instructions|