Details

Time & location

Lectures: Tu, Th 13:00 - 14:20, E7 4433

Teaching team

Instructor

Prof. Seyed Majid Zahedi

Book appointments here

Description

This course is an introduction to the mathematical and computational foundations of modern multi-agent systems, with a focus on game theory, artificial intelligence, and machine learning. The course provides analytical tools to analyze and model multi-agent systems in which an agent's welfare is a function of not only their own actions, but also those of others. Tentative topics include normal-form games, extensive-form games, repeated games, stochastic games, Bayesian games, computation of solution concepts, and learning in multi-agent systems.

Prereq

There are no formal prerequisites, and it is assumed that most students in the class will be unfamiliar with game theory, mechanism design, and multi-agent systems. Since some of the material is quite mathematically formal, students are expected to have introductory knowledge in probability theory (ECE203 or equivalents), computational complexity (ECE208 or equivalents), and algorithms (ECE250 or equivalents).

Antireq

Students will not be allowed to take this course if they have completed (or are currently taking) ECON412, CO456, CO759 (Algorithmic Game Theory), CS886 (Multi-agent Systems), and MSCI724 (Game Theory and Recent App)

Readings

Main textbook

• Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations (freely available online)

Optional references

• Algorithmic Game Theory (freely available online)
• Twenty Lectures on Algorithmic Game Theory (freely available online)
• The Theory of Learning in Games
• Game Theory
• A Course in Game Theory (freely available online)

Evaluation

The course has two different grading schemes are as follows.

• Undergraduate: 5% quizzes; 20% assignments; 25% (survey) project; 50% final exam
• Graduate: 5% quizzes; 20% assignment; 45% (research) project; 30% final exam

Quizzes, assignments, and the final exam are the same for both schemes but have different percentage breakdowns in each scheme. The project, however, has different requirements in each scheme (see "Policies" for more details). Undergraduate students have the option of choosing the graduate grading scheme when they submit their project proposal. We reserve the right to make changes to the exact percentage breakdowns above.

Contingency proviso

We are facing unusual and challenging times. The course outline presents the instructor’s intentions for course assessments, their weights, and due dates in Winter 2025. As best as possible, we will keep to the specified assessments, weights, and dates. To provide contingency for unforeseen circumstances, the instructor reserves the right to modify course topics and/or assessments and/or weight and/or deadlines with due and fair notice to students. In the event of such challenges, the instructor will work with the Department/Faculty to find reasonable and fair solutions that respect rights and workloads of students, staff, and faculty.

Main Topics (tentative)

The course tentatively covers the following topics:

• Introduction to multi-agent systems

  Overview of game theory and mechanism design, rationality and self-interest, utility theorem, risk attitudes

• Normal-form games

  Pure and mixed-strategy Nash equilibrium, iterative elimination of dominated strategies, price of anarchy, correlated equilibrium, computing solution concepts of normal-form games

• Extensive-form games

  Perfect and imperfect-information games, finite and infinite-horizon games, subgame-perfect equilibrium, backward induction, one-shot deviation principle

• Beyond normal and extensive-form games

  Repeated games, stochastic games, Bayesian games, congestion games, trigger strategies, folk theorems, Bayes-Nash equilibrium, auctions, optimal auctions, revenue-equivalence theorem, incentive compatibility, VCG mechanisms

• Learning in multi-agent systems

  Multi-agent reinforcement learning, fictitious play, Bayesian learning, regret-minimization learning

Announcements

Schedule (tentative)

Week	Day	Lecture	Reading	Event
1	Tu 01/07	Introduction Slides: PDF
	Th 01/09	Preferences and utilities Slides: PDF	MAS Ch3.1 and Appx A	Makeup session
2	Tu 01/14	Games in normal form Slides: PDF	MAS Ch3.2-3.4
	Th 01/16
3	Tu 01/21
	Th 01/23
4	Tu 01/28	Computing solution concepts of normal-form games Slides: PDF Codes: ZIP	MAS Ch4 and Appx B Optional: A course on ILP CVXPY website
	Th 02/30			Makeup session Proposal deadline
5	Tu 02/04	Games in extended form Slides: PDF	MAS Ch5
	Th 02/06
6	Tu 02/11
	Th 02/13	Repeated games Slides: PDF	MAS Ch6.1	A1 deadline
7	Tu 02/18	Reading week
	Th 02/20
8	Tu 02/25
	Th 02/27			Makeup session
9	Tu 03/04	Stochastic games Slides: PDF	MAS Ch6.2
	Th 03/06
10	Tu 03/11	Bayesian games Slides: PDF	MAS Ch6.3-6.4 and Ch8.1-8.2	A2 deadline
	Th 03/13	NO class - ECE Capstone Design Symposium
11	Tu 03/18
	Th 03/20			Makeup session
12	Tu 03/25
	Th 03/27	Learning in games Slides: PDF	MAS Ch7	A3 deadline
13	Tu 04/01
	Th 04/03			Project deadline

Assignments

Resources

Slides

GitHub repository

Sample exams

Waterloo ECEE750

• W'24 Final: exam (PDF)
• W'23 Final: exam (PDF)

Waterloo ECEE700

• W'19 Midterm: exam (PDF)
• W'18 Midterm: exam (PDF)

Policies

In-person sessions

Emergency remote-teaching contingency

Live sessions will be held on MS Teams during scheduled course times. To allow students to ask questions and participate freely, live sessions will not be recorded.

Assessments

Quiz policy

There will be an unspecified number of pop-up quizzes during the class. Each student is allowed to miss up to 10% of the total quizzes without providing any justification.

Assignment policy

There will be 3 assignments each with roughly 5 problems. Solutions will be graded on both accuracy and presentation. A correct solution that is poorly presented may not receive full marks.

Late submissions will be accepted with 15% penalty per day for only two days after the due date (the same policy is applied to project proposals and final reports).

Students can discuss the class material with other students. Students also can discuss with others about how to formulate assignment problems. However, students must write down their solutions by themselves. In particular, students may not take notes while they discuss assignments with others.

Any suspected plagiarism or infractions of this honor code will be reported to the appropriate Associate Dean.

Emergency remote-final-examination contingency

In the event of an emergency, the final exam will be a take-home exam.

Auditing

All students are welcome to audit the course unofficially without any requirements. However, for the audit to be officially recorded on their transcript, students must enroll in the course on Quest as an audit, attend the lectures, take the final exam, and achieve a minimum score of 30%.

Projects

Undergrad survey project

For the survey project, students will review existing literature (at least three major papers) in a subarea of multi-agent systems and possibly explore open research questions in that subarea. There will be 2 milestones during the term: proposal (15%) and final written report (85%).

Proposal for undergrads

In the project proposal, students should explain the subarea that will be surveyed and the significance of the research papers in the subarea. If necessary, the course instructor can help with finding topics. Each proposal should include all the following.

• Introduction: Introduce and motivate the subarea
• Related work: Overview the state-of-the-art by citing significant research papers

Undergraduate students can choose the graduate grading scheme when they submit their proposals. Those who decide to go with the graduate grading scheme have to follow the proposal format outlined below for grad students.

Final report for undergrads

In the final report, each student is expected to submit a written survey paper. The survey paper, as the name suggests, should provide a comprehensive survey of research papers in the proposed subarea. The paper should provide a critical assessment of the work that has been done in the subarea listing strengths and weaknesses of the existing work. The paper should also include an overview of some of the open research problems in the subarea. If applicable, brief comparisons between (or categorization of) the presented research papers should also be provided. The source for descriptions of existing research work is normally a collection of research papers presented at respected international conferences and in well-known international journals.

The paper should follow the same format described below for grad students. Without references, each survey report should not be less than 7 and not more than 18 pages.

Grad research project

For graduate students, an important part of this course is the research project. For the research project, students can work on the research project alone or in a team of at most three students; of course, teams are expected to work on more significant projects.

The goal of the research project is to try to do something novel, rather than merely a survey of existing work. Projects may be theoretical, experimental (based on simulations), experimental (based on real-world data), a useful software artifact, or any combination thereof. Creativity is encouraged. The only real constraint for the project is that it has to have something to do with the material covered in the course. Students are encouraged to talk to the course instructor if you are not sure about whether something is an appropriate project.

The final product is a writeup (in the form of a short research paper). Some projects may well lead to publishable papers (perhaps with some additional work). There will be 3 milestones during the course: proposal (15%), oral progress report (optional), and final written report (85%).

Proposal for grads

In the project proposal, students should explain the topic of their project, what types of results they hope to obtain, and what some of the technical issues are that you will need to address. For graduate students, the course project could be related to their own ongoing research as long as it also has clear connections with the course material. If necessary, the course instructor can help with finding topics. Each proposal should include all the following.

• Introduction: Introduce and motivate the project
• Problem statement: Describe the purpose and the objective(s) of the project
• Methodology: Describe methods and tools that will be deployed to tackle the problem
• Related work: Overview the state-of-the-art by citing related research papers, ideally published recently in top-tier conferences or journals

Progress report for grads

Intermediate oral project progress report is optional. This report should explain what results each group has obtained already, what (if any) difficulties the group has encountered, and what the group plans to do to complete the project. Ideally, at this point, each group should already have some good results, so that it can spend the rest of the time on answering questions generated by the results, as well as preparing the writeup.

Final report for grads

Each group will have to prepare and submit a final project report by the end of the term using the ACM Master Article Template. For Microsoft Word, students should use the interim layout.docx, and for Latex they should use the sample-sigconf.tex file in the samples folder. Submitted reports with any other format/style will not be accepted.

Each report has to include (at least) the following sections: abstract, introduction, methodology, experimental results (if applicable), related work, conclusion, and references. Without references, each report should not be less than 5 and not more than 11 pages.

Other policies

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.

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.

Discipline policy

A student is expected to know what constitutes academic integrity to avoid committing an academic offense, 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 offense, or who needs help in learning how to avoid offenses (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 offenses and types of penalties, students should refer to Policy 71, Student Discipline. For typical penalties, check Guidelines for the Assessment of Penalties.

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.

Automatic system to detect plagiarism

Moss (Measure Of Software Similarity) will be used to screen each project in this course. Students' submissions are stored on a U.S. server, therefore students will be given an alternative if they are concerned about their privacy and/or security. Students will be given due notice about arrangements and alternatives for the use of Moss in this course.