Models of Strategic Behavior
CPSC 532L; Term 2, 2022–23

Overview

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.

Logistics

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

UBC Location: 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

Important Information about Taking this Class

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.

Course Outline

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.

 

Deliverables & Grading

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

 

Course Element Worth
Participation10 %
Three Assignments24 %
Midterm16 %
Peer Grading of Proposal Presentations10 %
Proposal Presentation15 %
Proposal Document25 %

 

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.

Schedule
DateTopicNotes
January 6Zoom office hours for any Alberta students
with logistical questions; No UBC class
Alberta first day of class
January 11Introduction and OverviewUBC first day of class
January 13Utility and Foundations
January 18Game Representations
January 20Game Representations II
January 25Canonical Game-Theoretic Domains
January 27Formalizing & Solving Normal-Form Games:
Pareto & Nash
February 1Formalizing & Solving Normal-Form Games:
Maxmin, Dominance, Rationalizability
Assignment 1: pick and justify a domain/problem
February 3Formalizing & Solving Extensive-Form Games
February 8Formalizing & Solving Imperfect-Information Extensive-Form Games
February 10Repeated Games
February 15Bayesian Games
February 17Mechanism Design & Auctions
February 22Reading week
February 24Reading weekAssignment 2: refine the games about your domain, compute and argue for solution concepts
March 1Play each others' games
March 3Behavioral Game Theory
March 8Machine Learning for BGT
March 10BGT: Extensive, Bayesian, Regret
March 15BGT: Risk Aversion and Loss Aversion 
March 17Midterm 
March 22Giving Effective PresentationsAssignment 3: fit ML models to the data from March 1
March 24Giving Effective Presentations
March 29Example Presentations
March 31Student Proposal Presentations (3 groups)
April 5Student Proposal Presentations (3 groups)
April 7Student Proposal Presentations (4 groups)
April 22Makeup Midterm (tentative date)
April 27Projects DueProject Instructions