CS 6002: Selected Areas of Mechanism Design

Goal of the course

This course is based on selected topics in mechanism design. These topics include stable matching, fair allocation, cooperative games, selfish routing, games on networks, potential games. This is a research-oriented course, hence students are expected to read and present cutting-edge research topics in this area, and also develop writing skills towards a formal technical report.

A course like CS 6001 is a prerequisite for this course. In general, I will assume familiarity with formal mathematical reasoning, a fair amount of probability theory, basic calculus, the basics of computational complexity. I believe that one learns the concepts of an algorithm better when one codes that algorithm. Therefore, experience in programming will be useful.

Detailed plan of the course.

Announcements

  1. First meeting of the course is on Monday, January 2, 2023, at 2 PM, in CC 103 (note the unusual venue).
  2. Get started: enroll yourself on Piazza. Moodle will NOT be used for class discussions.
  3. All class-related announcements will be made on Piazza. If you are not enrolled there, you may miss the announcements.
  4. The first 9-10 weeks will be lecture-based and the remaining 2-3 weeks will be project presentations. A tentative list of probable projects are provided and you may form groups and start working on them. The project related meetings will start happening only after the first month of teaching and based on need. The group can email the instructor and schedule a time for a project meeting.
  5. First meeting slides.
  6. Audit grades will be given for this course only if you fairly complete (on or above 30% score in the 45% component) the project component of this course (part 2). However, you're welcome to sit-in, attend the lectures and problem-solving sessions, and ask questions on Piazza.

Logistics

  • Instructor: Swaprava Nath (office hours: Friday 2:30-3:30 PM at CC 209, mail at swaprava AT cse DOT iitb DOT ac DOT in with [CS6002] in the subject before coming)
  • Teaching assistants: Hyderi Narjis Asad (narjisasad@cse.iitb.ac.in), Aditya Pande (22m2108@iitb.ac.in)
  • Classroom: CC 101 (New CSE Building)
  • Evaluation:
    1. One quiz -- 15% weightage
    2. One midsem -- 40% weightage
    3. No final exam
    4. One group miniproject (group of 3 preferably): evaluation will be based on presentation (15%) and final report (30%)
    5. Make your own groups. Divide tasks into: (a) contribution to technical results -- partitioned into theory and experiments, (b) writing up the report, (c) preparing the presentation. Each of these tasks may be contributed by multiple members, but the contributions must be mentioned clearly along these 3 categories at the end of the report. Note that, based on these declaration, marks can be different for different members of the same group.
    6. All exams are offline, proctored, in-classroom, pen and paper, closed book (unless otherwise mentioned). Grading is done using Gradescope.
  • Attendance policy: If you are in IITB and not sick, then it is recommended that you should attend the classes. This is more important since there is no videolecture or online version of this course.
  • Practice problems: Stable matching exercises (chapter 22, MSZ). More coming soon on Piazza.
  • Course calendar

Reference texts

The following books could be useful.

  1. [MSZ] "Game Theory" — Michael Maschler, Eilon Solan, Shmuel Zamir, Cambridge University Press.
  2. [SLB] "Multiagent Systems" — Y. Shoham and K. Leyton Brown, Cambridge University Press.
  3. [COMSOC] Handbook of computational social choice.
  4. [Mishra] Lecture notes on mechanism design by Debasis Mishra.
  5. [Myer] "Game Theory -- analysis of conflict" -- Roger B. Myerson book.

Lectures

Some project themes

Here some project ideas are given in a cluster. You are free to propose any other project staying within the purview of CS 6001 and 6002. Projects will be evaluated based on the innovation, and if you have independently come up with the project idea, it will be weighed more. Multiple teams can work on different projects under the same theme. It is mandatory to announce with a synopsis of your project on Piazza between January 20-31 (but not before that, use this time to read/ideate on the projects) which project (and theme) your team is working on. Only one post per team (mentioning the team members) is enough. This is to make sure that multiple teams do not start working on the same project.

The themes contain a list of papers that belongs to the same theme. However, they can be different in their approaches. The expectation from the project will be that you read one paper in detail, do a literature survey around it (using the method in the workflow in this page), and attempt to make extensions (either theoretical or practical) on it.

Expand all papers | Collapse all papers

Regrading requests

The regrading procedures in this course are intended to correct serious errors in grading. It is not intended as an opportunity to argue about each judgment call made by the graders. We will only consider a regrading request if there is a significant error in grading, and if you sincerely feel that your exam was unfairly graded, we will look it over carefully. Having said that, if there is an attempt to use this feature to raise an unnecessary regrading request, then based on the severity of the attempt, a penalty will be placed which can go as high as deducting 50% of the marks for that question (irrespective of what marks you got in that question). We are not trying to scare off students whose exams were graded incorrectly, but we are trying to avoid frivolous requests.

What Merits a Regrade: The following are the usual circumstances that may lead to an increase in points:

  • Your answer is really the same as the one on the answer key, but the grader didn’t realize it.
  • Your answer is different from the one provided on the answer key, but your answer is also correct.

What Doesn’t Merit a Regrade: The following are not valid reasons for regrades:

  • “Most of what I wrote is correct, so I think I deserve more partial credit.” Partial credit is given equally for all students who write a particular answer, so it would not be fair to give you more points for this without adding points to all students who wrote the same answer.
  • “I wrote so much, and the grader didn’t notice that the correct answer is buried somewhere within this long paragraph.” You will lose points if the correct answer is accompanied by incorrect information or by so much irrelevant information that it gives the impression that you were just writing down everything you could think of on this topic. To get full credit you must demonstrate the ability to pull out the relevant info and to exclude irrelevant info.
  • “I’m just 1 point away from an A, so I thought it was worth scrounging around to find an extra point somewhere.” Lobbying for grades is considered inappropriate by the institute rules, so your case may be reported to appropriate authorities.

Virtual Q and A

We will be using Piazza for class discussion. The system is highly catered to getting help fast and efficiently from classmates, the TA, and myself. Rather than emailing questions to the teaching staff, I encourage you to post your questions on Piazza.

world map hits counter