System architects are increasingly confronted with settings in which multiple self-interested parties interact. Examples include computer networks and electronic marketplaces. To interact optimally, each party must take into account the actions of other parties. Game theory has proven itself to be an effective and powerful tool for studying these interactions.
This course is an introduction to fundamental topics in game theory and their applications in engineered computing and communication systems. In addition to theoretical foundations and mathematical models, the course focuses on practical applications, including distributed control of communication networks, incentive-compatible resource allocation, pricing and investment decisions, and multi-agent systems.
Prerequisites
Basic knowledge of algorithms, complexity, probability, and optimization would be helpful, but it is not required. No prior knowledge of economics or game theory is required.
Grading
Coursework will include the following components:
Participation/Quizzes: 10%
Assignments: 20%
Midterm: 30% (Nov 12th, during class hours)
Project: 40%
Readings
There is no required textbook or official textbook for the course. There are, however, several texts that can serve as auxiliary or reference texts:
[MAS] Y. Shoham and K. Leyton-Brown, Multi-agent Systems (freely available online)
The course tentatively covers the following topics:
Introduction to game theory Overview of games theory and mechanism design, engineering examples, rationality, utility theorem, risk attitudes
Normal form games Strategic form games, strategic dominance, pure and mixed strategy Nash equilibrium, iterative elimination of dominated strategies, price of anarchy, correlated equilibrium, computing game-theoretic solution concepts
Extensive form games Perfect and imperfect information games, finite and infinite horizon games, subgame perfect equilibrium, backward induction, one-shot deviation principle
Repeated games Finitely and infinitely repeated games, trigger strategies, folk theorems
Games with incomplete information Bayesian games, Bayes-Nash equilibrium, auctions
Introduction
Date: 9/10
Download Slides: PPTX, PDF
Lecture 2
Preferences and Utilities
Date: 9/13
Download Slides: PPTX, PDF
Lecture 3
Games in Normal Form
Date: 9/13 - 9/27
Download Slides: PPTX, PDF
Lecture 4
Computing Solution Concepts of Normal Form Games
Date: 10/1 - 10/8
Download Slides: PPTX, PDF Download Python3 Codes: ZIP Additional Resources: A Course on ILP, CVXPY Website
Lecture 5
Games in Extensive Form
Date: 10/8 - 11/1 (Reading Week: 10/15 - 10/18)
Download Slides: PPTX, PDF
Lecture 6
Repeated Games
Date: 11/8 - 11/22 (Midterm: 11/12)
Download Slides: PPTX, PDF
Lecture 7
Games with Incomplete Information
Date: 11/22 - 11/26
Download Slides: PPTX, PDF
Assignments
Assignment 1
Due on Tuesday, October 8th (before the class)
Download: PDF
Assignment 2
Due on Friday, October 25th (before the class)
Download: PDF
Assignment 3
Due on Friday, November 15th (before the class)
Download: PDF
FAQ
General
Can I audit the class? You are welcome to audit the class, but your assignments, midterm, and project will not be reviewed/graded.
Assignments
What is the lateness policy? Late submissions will be accepted with a penalty of 25% per day for only two days after the due date.
What is the group work policy? You can discuss the class material with other students. However, all assignments must be done on your own. In particular, you cannot discuss with other students how to formulate an assignment, or help another student with their assignment, or share or discuss your own work. For that kind of assistance, see the instructor. Any suspected plagiarism or infractions of the honor code will be referred to the University of Waterloo process.
Can I submit my assignments electronically? Yes, but only if you type your solutions. Scanned handwritten documents will not be accepted.
Where do I submit my assignments to? Submit your assignments to the instructor before the class.
Project
What should the project be on? Ideally, the project would be defined to be related to your current research. You can take a game-theoretic approach to any of the research problems you are currently working on. If no such research problem exists, then you can consult the instructor to define a proper project.
Other Policies
What is the academic integrity policy? In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. Check the Office of Academic Integrity for more information.
What is the grievance policy? A student who believes that a decision affecting some aspect of his/her university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70, Student Petitions and Grievances, Section 4. When in doubt, please be certain to contact the department's administrative assistant who will provide further assistance.
What is the discipline policy? A student is expected to know what constitutes academic integrity to avoid committing an academic offence, and to take responsibility for his/her actions. Check the Office of Academic Integrity for more information. A student who is unsure whether an action constitutes an offence, or who needs help in learning how to avoid offences (e.g., plagiarism, cheating) or about"rules" for group work/collaboration should seek guidance from the course instructor, academic advisor, or the undergraduate associate dean. For information on categories of offences and types of penalties, students should refer to Policy 71, Student Discipline. For typical penalties, check Guidelines for the Assessment of Penalties.
What is the appeals policy? A decision made or penalty imposed under Policy 70, Student Petitions and Grievances (other than a petition) or Policy 71, Student Discipline may be appealed if there is a ground. A student who believes he/she has a ground for an appeal should refer to Policy 72, Student Appeals.