Game Theory with Engineering Applications


T&F 16:00 - 17:20
PHY 145
Seyed Majid Zahedi
Office hour: W 16:00 - 17:00, DC 2524
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.
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.
Coursework will include the following components:
  • Participation/Quizzes: 10%
  • Assignments: 20%
  • Midterm: 30% (Nov 12th, during class hours)
  • Project: 40%
There is no required textbook or official textbook for the course. There are, however, several texts that can serve as auxiliary or reference texts:
Main Topics
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
  • Mechanism design
    Optimal auctions, revenue-equivalence theorem, revelation principle, incentive compatibility, VCG mechanisms, mechanisms without money, Fisher market, Arrow–Debreu Model, Eisenberg–Gale Convex Program
  • Learning in games
    Fictitious play, Bayesian learning, regret minimization learning, minimax Q-learning
  • Applications
    Routing games, network formation games, selfish load balancing, resource allocation mechanisms, pricing in communications networks, incentives in peer-to-peer systems, strategies in electricity markets


Nov 6
The third assignment is due on Friday, November 15th.
Oct 22
The final project report is due on Tuesday, December 10th.
Oct 13
The second assignment is due on Friday, October 25th.
Oct 10
Proposals (10% of the final project's grade) are due on Monday, October 21st.
Sept 28
The first assignment is due on Tuesday, October 8th.
Sept 24
Midterm will be on Tuesday, November 12th, during class hours.
Sept 11
Office hour time has changed to Wednesdays, from 4pm to 5pm!
Aug 23
There will be no class on Friday, September 6th. The first lecture will be on Tuesday, September 10th.
Aug 23
Please sign up for the course on Piazza.

Lecture Notes

Lecture 1
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


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


Can I audit the class?
You are welcome to audit the class, but your assignments, midterm, and project will not be reviewed/graded.
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.
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.