web.stanford.edu Open in urlscan Pro
2607:f6d0:0:925a::ab43:d7c8  Public Scan

Form analysis
0 forms found in the DOM

Text Content

CS 224M : Multi Agent Systems
Spring 2013-14

--------------------------------------------------------------------------------


SYLLABUS

The syllabus is subject to change. Visit http://cs224m.stanford.edu/ to find the
latest syllabus.


--------------------------------------------------------------------------------

Course Links
 * 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

June 9, 2014
 * 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.
   

June 6, 2014
 * Homework 4 has been graded and solutions are posted.

May 30, 2014
 * 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).

May 28, 2014
 * 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.)

May 27, 2014
 * 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.

May 25, 2014
 * We added some clarifications to HW4 Q3 and Q4-b. Please check the updated
   version here.

May 23, 2014
 * 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.

May 19, 2014
 * 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.

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

May 13, 2014
 * 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).

May 5-9, 2014
 * 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.

May 3, 2014
 * 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.

May 2, 2014
 * 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.

Apr 29, 2014
 * 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.
   

Apr 15, 2014
 * 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.

Apr 14, 2014
 * 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.

Apr 12, 2014
 * 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.

Apr 10, 2014
 * 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).

Apr 9, 2014
 * 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.

Apr 7, 2014
 * 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).

Apr 5, 2014
 * 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.

Apr 1, 2014
 * 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.)

Mar 31, 2014
 * 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

Instructor: Yoav Shoham
 * Office Hours: Mondays 1pm - 2pm (starting April 7).
 * Location: Gates 140

TAs:
 * 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 release and due dates (NO late submissions are allowed.)
 * 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).

Midterm date and coverage
 * 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 due dates
 * 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.