Models of Strategic Behaviour
(CPSC 532L, Term 2, Session 201, 2022-23)
Course Description: This course examines core economic and algorithmic models of strategic behavior and their applications, with a focus on game theoretic analysis of systems in which agents cannot be guaranteed to behave cooperatively. It will use a "flipped classroom" model in which lectures will be delivered online. Classes will emphasize student participation. The first class of a week will focus on reinforcing and applying material covered in the videos. The second class of a week will consist of student presentations on enrichment topics, which will be peer evaluated and discussed afterwards.
Meeting Times: Tuesday, Thursday, 2:00 - 3:30 PM
First Class: Tuesday, January 10, 2023
Location: ICCS 246
Instructor: Kevin Leyton-Brown
Instructor's Office Location: ICCS X565
Office Hours: Tuesday, Thursday, 3:30 - 4:00 PM, or by appointment
Course TA: Narun Raman
Course Topics: Overall, problems at the interface of economic theory and computer science. (No prior experience in economics is assumed.) Specific topic include: Games: normal-form; extensive-form; repeated; stochastic; coalitional; Bayesian. Computation of game-theoretic solution concepts. Social choice theory and mechanism design: key positive and negative results. Single- and multi-good auctions.
Prerequisites: There are no formal prerequisites, and it is assumed that most students in the class will be unfamiliar with game theory, mechanism design, auction theory, and the literature on multiagent systems. Since some of the material to be covered is quite formal mathematically, students do need to be able to construct and follow formal proofs. Relevant mathematical/CS background includes introductory knowledge of probability theory, computational complexity and combinatorial optimization. Much of the work associated with the course will revolve around reading papers and making a presentation to the class. As a result, students who have trouble reading, speaking or writing comfortably in English will find themselves at a disadvantage.
Academic Honesty: Plagiarism is a serious offense and will be dealt with harshly. I consider plagiarism to be the unattributed use of an external source (e.g., another student, a web site, a book, a large language model) 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 offense depends on the extent to which the student relied upon the external source. Assignments and midterms will include an honour code statement which you will be required to sign, specifying forms of collaboration and reference to non-course materials that are acceptable. For presentations, you must cite all external sources that you use, and the vast majority of the slides must be written in your own words. Any text that you take verbatim from another source must be in quotation marks and followed by a citation.
Flipped Classroom Structure: The course will follow the following
|Before first class||
Watch the week's videos. Hand in the previous week's assignment electronically.
We'll begin with a quiz on the material covered in videos. We'll swap quizzes and peer-grade, discussing concepts as we go. We'll have an opportunity for open discussion of the lecture material. Then I'll cover related material and we'll have a chance to apply what we've learned with challenge problems and games.
|Second class||Student presentations on enrichment topics. Each student has 20 minutes to present, followed by discussion of both the material and the presentation itself. Remaining time will be devoted to discussion of the previous week's assignment and help with/group work on the current week's assignment.|
We'll start out with the first class being a Tuesday and the second being a Thursday. The midterm will be on a Tuesday. After that, the first class of a week will be a Thursday and the second will be a Tuesday. We'll keep the last class as a slack day in case it turns out to be necessary to cancel a class during the term.
CPSC 532L is being held in person. You won't be able to succeed in the course if you aren't physically in Vancouver; the course emphasizes in-class attendance and participation.
Masks: As of July 1, 2022, masks are no longer required in UBC indoor spaces. You're welcome to wear a mask if it makes you more comfortable.
Vaccination: If you are not yet vaccinated against Covid-19, vaccines are available to you, free, and on campus. The higher the rate of vaccination in our community overall, the lower the chance of spreading this virus. You are an important part of the UBC community. Please arrange to get vaccinated if you have not already done so.
If you’re sick, it’s important that you stay home, no matter what you think you may be sick with (e.g., cold, flu, other). Do not come to class if you have Covid symptoms, have recently tested positive for Covid, or are required to quarantine. In this class, the marking scheme provides flexibility so that you can prioritize your health and still be able to succeed. However, this class has not been designed to make attendance optional; your grade will suffer if you consistently skip class! If you have a prolonged illness or another special circumstance, please get in touch with the instructor.
If you are sick on a final exam day, do not attend the exam. You must apply for deferred standing (an academic concession) through Science Advising no later than 48 hours after the missed final exam/assignment. Students who are granted deferred standing write the final exam/assignment at a later date. Learn more and find the application online. For additional information about academic concessions, see this UBC policy.
Warning: I reserve the right to make changes to the exact percentage breakdowns shown here. However, the following grading scheme should be approximately accurate, and indicates the components of the class upon which you will be graded.
|Course Element||Contribution to Your Grade|
|Quizzes (weekly; we'll keep your 9 best grades)||10 %|
|Assignments (weekly; we'll keep your 9 best grades)||20 %|
|Midterm||15 % (or 7 %)|
|Final||20 % (or 28 %, if better and final >= 80%)|
|Presentation||20 % (10% instructor; 10% peer)
|Peer Review of Other Students' Presentations||5 %|
|Participation in Discussions; Attendance||10 %|
Curving Grades and Peer Review: Final grades may be curved to give the overall distribution of grades a desired mean and standard deviation. Peer review is an important component of the class, and will be taken into account when evaluating presentations. Since this is an Algorithmic Game Theory course, a grading scheme has been constructed that does not provide students with any ability to influence their own grades by reviewing other students strategically. The curve for a given student x will be calculated disregarding x's presentation reviews of other students.
Assignments: The course will include weekly assignments, given out at the second class of the week (e.g., Thursday) and due an hour before the following week's first class (e.g., Tuesday). Assignments must be prepared using LaTeX and submitted electronically. They will include questions drawing on the week's lecture and also student-created questions based on the week's presentations (see below). Assignments will not be weighted equally: weighting will be proportional to the total number of available points. Late assignments will be penalized at 20\% per day. Assignments will receive a grade of zero after 1:00 PM on the second class after the due date. At the end of the term, we will drop your 2 worst assignments, to account for brief illness, scheduling conflicts with other courses, personal commitments, and other emergencies. No additional accommodations will be granted except under truly exceptional circumstances.
Each student will give a brief (20 minute) presentation on a topic that goes beyond a given week's core material. Each topic may be presented by at most one student, and each day may contain at most two presentations. A list of candidate topics is available here; feel free to propose other topics. In the second class of the term, we'll have an auction to assign students to topics from the first two weeks; we'll assign the rest of the topics after the drop date.
More specifically, we'll use a descending-price Japanese auction to procure 4 presenters for the first four classes, starting from 50% bonus credit and descending; all 4 selected presenters will get the amount of bonus credit the 5th-highest student was willing to accept. If we reach 0% with more than 4 presenters we'll randomize among the set of students who remain. Once the 4 presenters are chosen, we'll see if they can come to an agreement on who presents in which week, and otherwise will randomize. For the subsequent weeks, after the add-drop deadline we'll draw names from a hat in sequential order of week; at any point students whose names remain in the hat will be permitted to claim the week currently being decided instead of continuing to remain in the lottery. Within a given week, topics will be set on a first-come, first-served basis (two students cannot both present on the same topic.) After assignments are finalized, students are free to swap weeks with each other at any time if both agree.
Three quarters (15%) of the presentation grade will come from the presentation itself. Presentations should be 20
minutes long. Topics must be chosen from the assigned list or negotiated
with me. The goal is to give you the chance to research and dig deeper into
a topic that interests you. You're encouraged to include at least one
interactive activity or puzzle for students to solve during your presentation. Your presentation grade will come half from the instructor and half from peer grades. The grading
form used for (peer/) evaluation of presentations is available here. After each presentation is complete, we'll have a discussion about the presentation itself (what worked, what didn't) and the
subject matter it covered (clarifications, elaborations).
The remaining quarter (5%) of the presentation grade will come from an assignment question submitted by the presenter and forming part of the week's assignment. Each question should be similar in difficulty and structure to that of the other assignment questions (you'll see at least two before you have to make your own) and should be graded out of 10 points. Presenters will peer grade the responses to their own questions, which will be spot checked by the course TA; if this isn't done reliably, the student will forfeit the assignment question quarter of their participation grade. Otherwise, this portion of your grade will come 50% from an instructor assessment and 50% from a peer assessment (grading form to come).
- Y. Shoham and K. Leyton-Brown, Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Cambridge University Press, 2009.
Another good general text for exploring more advanced material in the research area, written largely from a CS theory perspective, is the following edited volume:
- N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani (Eds.), Algorithmic Game Theory, Cambridge University Press, 2007.
If you'd like to do additional reading on Game Theory, I recommend the following supplemental books:
- D. Fudenberg and Tirole, Game Theory, MIT Press, 1991;
- M. Osborne and A. Rubinstein, A Course in Game Theory, MIT Press, 1994.
- J. Nocedal and S. Wright, Numerical Optimization, Springer, 1984.
- V. Krishna, Auction Theory, Second Edition, Elsevier, 2009.
|Week||Dates||Topic (click for videos)||Presentations||Links|
|0||Jan 10, 12||Course overview||
Giving Effective Presentations
|1||Jan 17, 19||Normal-form games||Congestion games (tex)||Assg1|
|2||Jan 24, 26||Mixed Nash equilibrium||Aaron||Assg2|
|3||Jan 31, Feb 2||Alternate solution concepts||Shruthi, Ruiyu||Assg3|
|4||Feb 7, 9||Extensive-form games||no presentation||Assg4|
|5||Feb 14, 16||Repeated games||Brandon, Ward||Assg5|
|6||Mar 2, 7||Coalitional games||Sophie, Jackie||Assg6|
|7||Mar 9, 14||Social choice||Liron||Assg7|
|8||Mar 16, 21||Bayesian games||Jenny||Assg8|
|9||Mar 23, 28||Mechanism design||no presentation||Assg9|
|10||Mar 30, Apr 4||Efficient mechanisms||Prayus, Ben||Assg10|
|11||Apr 6, 11||Auctions||Michael||Assg11|
|12||Apr 13||Review Session|