CS 224M : Multi Agent Systems Spring 2013-14

Syllabus

• View grades here. (Requires log-in via Stanford NetID)
• CS224M on edX (video lectures)
• Discussion Forum on edX (short questions, homework-related questions, etc.)
• Google Form to submit questions (questions worthy of a discussion in-class). See the list of questions here.

Announcements

• The class is over! Have a great summer!
• NOTE: You must submit a hard copy of your final paper by 4pm on June 9. (There is a dropbox outside Gates 128.)
• There will be no bonus lecture as not enough students signed up.
  On June 9, Yoav will give a bonus lecture on combinatorial auctions at 2:15pm.
  If you are interested in coming, please email Eric. If 15 people or more respond, it's on.
  

• Homework 4 has been graded and solutions are posted.

• We posted on the forum some notes on definition of dictatorship and IIA.
  Please check these notes before you submit your HW4 solution.
• Also, in Q4 of HW4, you can use Arrow's theorem, but if you are disproving a statement, you must give us a counter-example (otherwise, you will only get a partial credit).

• On June 2 (last lecture), Haden and Eric will give short presentations on some GT research relevant to the course.
• On June 9, Yoav will give a bonus lecture on combinatorial auctions at 2:15pm.
  If you are interested in coming, please email Eric. If 15 people or more respond, it's on.
  (PS -- I attended it when I took this class, and it would be worth your time! -- Haden.)

• Haden's last office hours will be on Friday (May 30) from 2:30pm to 4:30pm at Gates 128. (It's a different time than the usual one due to a robotics seminar at Gates.)
• If your proposal was not approved, please follow up with Yoav directly.

• We added some clarifications to HW4 Q3 and Q4-b. Please check the updated version here.

• If you have not picked up your midterm yet, you can pick it up during the following hours:
• May 30 (1pm-3pm) (Haden's office hours)
• June 2 (in-class -- this is our last class)
• June 2 (4pm - 6pm) (Eric's office hours)
• After 6pm, June 2, we will place all midterms in a dropbox outside Gates 128.
  (If you want us to keep it in our office, just email us.)
• Note that we will NOT accept any re-grade requests on HW/midterm after June 2 6pm.
• Also note that there will be no re-grade of HW4 submissions due to the course schedule.
• There is no class on May 26.

• Final Paper: See here for infomration. We will make an official announcement after the midterm.
• Midterm has been graded (stats available on the forum). You can check your grades here.
• MIDTERM SOLUTION
• Practie midterm and previous midterms are posted as of May 11.
• Solutions to practice midterm and previous midterms are posted as of May 12.

• Homework 3 has been graded. Solutions are posted (see 'Important Dates' section).
• For stats (median/average), see the discussion forum.

• Midterm coverage has been finalized. See the midterm section for details.
• Homework 4 is released. Due date is May 27, but we will grant a 1-week extension with no penalty (if submitted before 4pm June 3).

• Haden and Eric will be out of town between May 3 - May 10 (and therefore no office hours).
• Our third TA (Sathish) will hold special office hours on May 6th during 12pm-2pm.
  Location: Basement of Huang building. Email Sathish about the exact location if you can't find him.

• A clarification on Q2 of HW 3: 'Latency' has the same meaning as 'Cost' defined in the book, and this should cause no ambiguity.
• You need to justify your answers for Q2 and Q3 in HW 3. We updated the problem statement to reflect this.

• We finished grading homework 2. Solutions can be found under the 'Important Dates' section.
• Here's some example problems on Selfish routing (from last years recitation).[ PDF ]
  The slides are self-explanatory.
  Disclaimer: The slides may contain a typo or error, so please report on the discussion forum if you find any.

• Homework 3 is released.
• Here is a practice problem on Bayesian Games (PDF) from previous years homework. (Solutions)
  Since we do not have homework problems on Bayesian Games this year, use this as an exercise problem in preparation for midterm.
  We will upload a solution to this later, but feel free to discuss on the forum.
  

• Homework 2 is released.
• Homework 1 solutions can be found under "Important Dates" section.
  Feel free to discuss and comment on solutions of HW1.
• Homework 1 has been graded. You can pick it up from the box outside Gates 128.

• Office Hours: As announced in class today, Haden will hold office hours on Fridays 1pm-3pm starting this week.
• A clarification on the wording of Q4-(b) and (c): The minmax values are defined as the (expected) payoff if the player best-responds to the minmax strategy of the other player against her (see Definition 3.4.2.). In case this was not clear, we updated our wording in the problem set.

• Minor changes to the coverage of reading material:
  For Week 3, we are removing sub-sections 5.2.3 and 5.2.4 from the reading list; we noted this in the original syllabus, but we are just making it more explicit.
  For Week 4, there is one video ("Learning in Repeated Games") that covers Ch 7.2 of the book.
  Note that we do not have lecture videos for Week 6.
  For Week 7, we are making Ch 9.5 optional.
  For Week 9, we are making Ch 10.4.7 and 10.5 optional.
  All these changes have been reflected into the schedule at the bottom of this page.

• If you visit the edX Course Info, you can now download "All Lecture Slides" by clicking on the link under "Course Handouts" (on the right panel).

• In Week 2 material, there are two lecture videos on "Maxmin Strategies", one Basic and one Advanced.
  They are essentially the same except the Basic one skips a few slides, and thus we are making the Basic one optional.
  The edX Courseware has been updated accordingly.

• In Homework 1: Assume that epsilon is positive in Question 1-(g). This should be clear from the context. We have updated the pdf file as well.
• We have changed the coverage of textbook material for week 1 and week 2.
  For week 1, we have removed 3.3.4 (it is optional now).
  For week 2, we added 4.1 and 4.2.1. See the bottom of this page for the updated schedule.
• Eric's office hours have been changed to Mondays 4pm-6pm starting next week (at Gates 128).
  For this week, Eric will hold office hours 11am-1pm tomorrow on April 8 (at Gates 128).

• We are aware that some lecture videos of Week 2 through Week 10 do not appear. The edX tech team is currently fixing it, and the videos will be ready soon.
  As of 2:30pm Apr 5, all videos sohuld be available on the edX platform (except for Week 6 which has no lecture videos). If you do not see a video for any sub-section, please let us know by posting on the forum which week and which sub-section is missing.

• Homework 1 has been released!
• Haden's first office hours on April 9 will run from 1pm-3pm (It's re-scheduled due to a seminar that starts at 3pm.)

• The syllabus has been updated. You can now watch videos on edX (see below).
• We have announcned a schedule for homework assignments.
• A tentative coverage of midterm is announced. We will finalize it a week prior to the exam date.
• Eric's office hours have been changed to Fridays 2pm-4pm (from 1pm-3pm).

The Flipped Classroom

We will run a flipped classroom: You are responsible for watching video lectures and reading the textbook on your own.
When we meet on Mondays, the first half of the class will consist of reviewing the main concepts (that you are supposed to have learned), and invite your questions and discussion; occasionally we may have an invited guest speaker. For the second half of the class, the TAs will take over and do some recitation (for example, solving an exercise problem and answering questions related to homework).

You should register for the course on edX here: https://class.stanford.edu/courses/Engineering/CS224M/Spring2014/about.
You are advised to follow our suggested schedule (see the bottom of this page), but you are welcome to watch videos ahead of our schedule.
We will collect questions in advance from you via the form here: http://goo.gl/U3Ahx5.
You can also view the questions asked by other students (to avoid duplicate questions): http://goo.gl/9iNOJo.
You can ask any questions through the form, and we will try to address them when we meet on Mondays.

Time and Location

Mondays 2:15-4:05pm in 420-041 (Jordan Hall)

Textbook

All lecture slides are available on edX (see below). Additional required reading material will be the textbook by Professor Shoham, co-authored with Kevin Leyton-Brown: Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations (Cambridge University Press, 2009). A slightly rough version is available here.

Quizzes and Lab Exercises

Some lectures will have short quizzes which will help you understand the material. They are intended to make sure you understand the basic definitions, but don't call for the same level of thinking as the problem sets or the midterm. We encourage you to take all quizzes, but they will not count towards your grade.

You will have the opportunity to participate in some periodic online 'lab exercises' which will allow you to play some of the games that we discuss in the lectures. Links to specific games will be provided at the end of some lecture videos. Like the quizzes, these will not be graded. We will usually ask you to complete these before the corresponding material is covered in lecture, so that you have a chance to experience some of the games before we provide a formal game theoretic analysis of them.

Grading Policies

We will have 4 homework assignments and in-class midterm on 5/19 Monday (tentative).
We will not grade based on attendance.

Homework = 50% | Midterm = 50% | Final Paper* (see below)

We will only accept hard-copies (no scanned copy or email) for homework solutions.
Homework solutions are due by Tuesdays 4pm at Gates 128 (there will be a box). NO late submissions are allowed as we will release the solution at the deadline.
While we do our best to make questions unambiguous, some questions may still remain unclear.
Please ask on the Discussion forum on edX if you are confused.

(*) Your Final Paper is graded on the A/B/C basis, which could change your letter grade up to a full grade up or down.
Roughly speaking, getting an A on your final paper could increase your final letter grade up to a full grade (analogous for a C).

Instructors and Office Hours

• Office Hours: Mondays 1pm - 2pm (starting April 7).
• Location: Gates 140

• Haden Hooyeon Lee
• Office Hours: 1:00pm - 3:00pm on April 9 (Wed).
  Fridays 1:00pm - 3:00pm
  No office hours on May 9 (out of town).
• Location: Gates 128. (If the fishbowl (Gates 120) is not occupied by another group, I will be there.)
  (May 30th will be the last office hours of Haden's, and it will run from 2:30pm until 4:30pm. )
• Eric Huang
• Office Hours: 11:00am - 1:00pm on April 8 (One-time).
  Mondays 4:00pm - 6:00pm.
  No office hours on May 5 (out of town).
• Location: Gates 128.
  (June 2nd will be the last office hours of Eric's)
• Sathish Ramanathan Nagappan
• Office Hours: No regular office hours.

Important Dates

• Homework 1 will be released on Apr 01 and due by 4pm on Apr 15. [Solutions]
• Homework 2 will be released on Apr 15 and due by 4pm on Apr 29. [Solutions]
• Homework 3 will be released on Apr 29 and due by 4pm on May 13. [Solutions]
• Homework 4 will be released on May 13 and due by 4pm on May 27. [Solutions]
  You are given a 1-week extension on HW4 with no penalty (if submitted before 4pm June 3).

• Date: In-class midterm on May 19th.
• Coverage: Week 1 - Week 6 material (all lecture videos and textbook readings) as well as homework assignments 1 through 3.
  Except for:
  • LP formulations discussed in the book. (We will not ask you to formulate LP problems, for instance.)
  • Chapter 6.1.3 (automata).
  • Chapter 6.2.3 (computing equilibria in stochastic games).
  • Chapter 7.5, 7.6, and 7.7.
• Open book policy: Open-book and open-note (including your laptops and tablet devices that may have your notes and/or e-book).
  Lecture slides and notes (from other schools) that you found online can be used as well.
  However, please do NOT access the Internet during the midterm (including, but not limited to, chatting on-line, searching on-line, etc.).
  That will be a violation of the honor code.
• Use of software: You are NOT allowed to use software or solvers (such as Matlab, Mathematica, CVX, etc.) other than basic calculators and e-book reader.
• Practice miderm
• Midterm 1 [ Solutions ] (Spring 2012)
• Midterm 2 [ Solutions ] (Spring 2013)
• Practice midterm [ Solutions ] (Used in recitation, Spring 2013) -- this practice midterm re-uses many problems of midterm #1 above, so we advise you to focus on midterm #1 and #2 above.

• Final paper topic proposal due by 4pm on 5/23 Fri (NO LATE SUBMISSION ALLOWED)
• Final paper topic approval due by 4pm on 5/30 Fri (NO LATE SUBMISSION ALLOWED)
• Final paper submission due by 4pm on 6/09 Mon (NO LATE SUBMISSION ALLOWED)
• How to submit proposal: If you visit HERE (same link as the grading center), you should be able to see a link to the submission form. If not, email Haden.
• NOTE: You MUST submit a hard copy of your final paper by 6/09 4pm. No electronic submission is allowed.
• For more information, please refer to the forum post HERE.

Honor Code

We encourage students to form study groups and discuss the lecture videos (including in-video questions). We also encourage you to get together with friends to watch the videos together as a group. However, the answers that you submit for the problem sets and midterm should be your own work; students are encouraged to discuss concepts and problems, but are NOT allowed to share their answers to problem sets and midterm. We ask that you do not share your solutions to any of the problem sets and midterm with any other students. This includes any sort of sharing, whether face-to-face, by email, uploading onto public sites, etc. Doing so will drastically detract from the learning experience of your fellow students, and any attempt to do so will be considered a clear honor code violation.

Lecture Schedules and Weekly Contents (subject to change)

Dates	Content (subject to change)	Released	Due Dates
3/31 (Mon)	Week 1: Introduction and Normal Form Games Normal Form Definitions, Dominant Strategies, Pareto Optimality, Mixed Strategies, and Nash Equilibrium Videos: All videos under Week 1 on edX. (~94 minutes) Readings: Ch 3.1-3.3 (3.3.4 is optional.)	HW 1
4/7 (Mon)	Week 2: Solution Concepts and Computation in Game Theory Maxmin Strategy, Minimax Regret, Iterative Removal of Dominated Strategies, Computing Nash Equilibrium, Complexity of Nash Equilibrium, and Compact Representation Videos: All videos under Week 2 on edX (there are two 'optional' vidoes). (~70 minutes excluding optional vidoes) Readings: Ch 3.4, Ch 4.1 and Ch 4.2.1. (Rest of Ch 4 is optional.)
4/14 (Mon)	Week 3: Extensive Form Games Extensive Form Definitions, Centipede Game, Backward Inductions, Imperfect Information, and Subgame Perfect Equilibrium Videos: All videos under Week 3 on edX. (~99 minutes) Readings: Ch 5 (5.2.3 and 5.2.4 are optional). NOTE: Sequence form and sequential equilibrium will be good to know, but will not appear in the homework or exam. Ch 6.5 is optional (but we recommend you read it as it contains intereting examples).	HW 2	Homework 1 due (Apr 15)
4/21 (Mon)	Week 4: Repeated Games Finitely Repeated Games, Infinitely Repeated Games, Stochastic Games, Learning in Repeated Games, Folk Theorems Videos: All videos under Week 4 on edX. (~84 minutes) Readings: Ch 6.1-6.2; Also Ch 7.2 (Fictitious play).
4/28 (Mon)	Week 5: Coalitional Games and Bayesian Games Coalitional Game Theory, Shapley Value, Core, and Bayesian Games Videos: All videos under Week 5 on edX. (~93 minutes) Readings: Ch 12.1-2, Ch 6.3	HW 3	Homework 2 due (Apr 29)
5/5 (Mon)	Week 6: Multi-Agent Learning (and Congestion Games) Rational Learning, Reinforcement Learning, Replicator Dynamics and Evolutionarily Stable Strategies, and Congestion Games Videos: No videos. (In Week 4, you watched "Learning in Repeated Games" that covers Fictitious play in Ch 7.2 of the book.) Readings: Ch 7, Ch 6.4
5/12 (Mon)	Week 7: Social Choice Social Choice, Computational Social Choice and Voting Manipulation Videos: All videos under Week 7 on edX. (~77 minutes) Readings: Ch 9 (Ch 9.5 is optional)	HW 4	Homework 3 due (May 13)
5/19 (Mon) In-class: MIDTERM	MIDTERM Week 8: Mechanism Design Intro to Mechanism Design, Implementation, Revelation Principle, Quasilinear Preferences, and Mechanism Design as an Optimization Problem Videos: All videos under Week 8 on edX. (~69 minutes) Readings: Ch 10.1-10.3		Final Paper Proposal due (May 23)
5/26 (Mon) No classes, Memorial day	Week 9 : The VCG Mechanisms Groves Mechanisms, VCG Mechanisms, and more Videos: All videos under Week 9 on edX. (~81 minutes) Readings: Ch 10.4 (Ch 10.4.7 is optional.) (optional: 10.5-10.7)		Homework 4 due (May 27) Final Paper Approval due (May 30)
6/2 (Mon)	Week 10: Auctions First Price Auctions, Auction Formats, Beyond Single Unit Auctions, Bidding Languages, and the Winner Determination Problem Videos: All videos under Week 10 on edX. (~110 minutes) Readings: Ch 11.1-11.2 (optional: 11.3-11.4)
6/9 (Mon)	Finals week Final Paper due by 4pm June 9.