CS 6001 / CS 405 — Game Theory and Algorithmic Mechanism Design

01 Goal of the Course

This course deals with topics at the interface of Economics and Computer Science, with a focus on applications of game theory in social decision making — how online advertising slots are allocated among competing advertisers, how mobile telephony spectrum is distributed among competing service providers so that certain "good" and "fair" properties are satisfied, and so on. Problems of a similar flavor exist in crowdsourcing, internet routing, fair division of goods, matching of students to advisors, facility location, social networks, and many more.

To understand these applications and improve them, technology needs to partner with the economic principles that drive them — this course develops those principles. Even though the course is mainly focused on mechanism design (inverse game theory), it does not assume any prior background in game theory; the basic concepts are developed in the initial phase of the course. The later part looks at how to put this knowledge into designing games with specified objectives, across several application domains.

There are no specialized prerequisites. Familiarity with formal mathematical reasoning, a fair amount of probability theory, basic calculus, and the basics of computational complexity will help. Experience with programming is useful too — one learns the concepts of an algorithm better by coding it.

Detailed plan of the course

02 Announcements

CS 405 is the UG version of CS 6001. The course content is the same. See the Evaluation section below for how grading differs between the two.
All times mentioned on this page are in Indian Standard Time (IST).
This course will be in slot 11 (Tue–Fri, 3:30 - 4:55 PM), Venue: [venue TBD].
First meeting of the course is on July 28, 2026, in the regular classroom for this course.
Get started: enroll yourself on Piazza (link in the Q&A section below). Moodle will not be used for class discussions.
All class-related announcements will be made on Piazza. If you are not enrolled there, you may miss them.
No audit grades will be given for this course. You are welcome to sit in, attend lectures, and ask questions on Piazza.
Course registration policy: CS 6001 is only for PG students; the UG elective is listed as CS 405. UG students should register only for CS 405, not CS 6001. Pre-registration is enforced for CS 405.
Every week, lecture slides and lecture notes for both lectures of that week will be posted in the Weekly Materials section below, usually within a few days of the lecture.
Each lecture has two short in-class quizzes (via Google Forms), used to encourage attendance and active participation. Quiz links are shared live in class and on Piazza only — they will never be posted on this page. See the Evaluation section for how these are weighted.
Quiz 1 (CS 405 only) will be on Aug 25, 2026, during regular lecture hours. More details closer to the date, on Piazza.
Midsem will be on the Institute-scheduled date/time (Sep 12–20, 2026). Details on Piazza closer to the date.
Quiz 2 (CS 405 only) will be on Oct 23, 2026, during regular lecture hours. More details on Piazza.
Endsem will be on the Institute-scheduled date/time (Nov 9–21, 2026). Details on Piazza closer to the date.
Course project (CS 6001 only): project suggestions will be posted on [evolving project list link TBD]; you're also free to propose your own idea within the scope of this course. Proposal format, group size, and deadline: [details TBD].

03 Logistics

Instructor: Swaprava Nath (office hours: by appointment — email with [CS6001] or [CS405], as appropriate, in the subject)
Primary TAs: Ramsundar Anandanarayanan (anandramsundar@cse.iitb.ac.in), Drashthi Doshi (drashthi@cse.iitb.ac.in), Sayantika Mandal (22D0379@iitb.ac.in), Aditi Singh (23b1053@iitb.ac.in), Ishita (23b0921@iitb.ac.in), Pulkit Gupta (24b1025@iitb.ac.in)
Classroom: [room TBD]
Slot: Slot 11 (Tue–Fri, 3:30 - 4:55 PM)
Calendar: Course calendar

Exam format

All exams are offline, proctored, in the lecture hall, pen-and-paper, closed book (unless otherwise mentioned). Grading is via Mulyankan — please sign up there as well.

04 Evaluation

The two versions of the course, CS 405 (UG) and CS 6001 (PG), share identical content and in-class quizzes, but differ in how the "quiz" component of the grade is composed. CS 405 has no course project — please don't ask for one.

In-class quiz policy (applies to both CS 405 and CS 6001): Every lecture includes two short in-class quizzes, administered live via Google Forms. Across the semester's 23 lectures, that's 46 quizzes in total, each of equal weightage. Only your best 40 quiz scores count towards your grade, together contributing a combined 15% to your final grade (so each counted quiz is worth 15/40 = 0.375% individually). Dropping the worst 6 rewards regular attendance and engagement without penalizing the occasional missed or off day. Quiz questions are designed so that only students present in that specific lecture can answer them; quiz links are never posted publicly, only shared live in class and on Piazza.

CS 405 (UG)

In-class quizzes (best 40 of 46)	15%
Quiz 1 (scheduled)	15%
Quiz 2 (scheduled)	15%
Midsem	25%
Endsem	30%
Total	100%

CS 6001 (PG)

In-class quizzes (best 40 of 46)	15%
Course project (replaces Quiz 1 + Quiz 2)	30%
Midsem	25%
Endsem	30%
Total	100%

In CS 6001, the two scheduled quizzes that make up 30% of the CS 405 grade are replaced entirely by a single course project (also worth 30%), done in groups; details in the Announcements above once posted. [Project group size, proposal deadline, and format to be finalized].

05 Weekly Materials

Each week has one consolidated slide deck covering both lectures, and two separate lecture-notes documents, one per lecture. Everything is posted here shortly after the lecture. Click a week to expand it.

06 Course Content

The topics below are organized by broad unit rather than tied to specific lecture numbers, since the week-by-week pacing is adjusted slightly each offering. See Weekly Materials for what was actually covered, week by week, this semester.

Part I — Foundations of Game Theory

Introduction — why game theory and mechanism design; rationality, intelligence, common knowledge

The Game of Chess — formal setup, strategies, von Neumann's theorem and its proof

Strategic (Normal) Form Games — definition, examples

Dominance — dominant/dominated strategies, iterated elimination

Nash Equilibrium — best response, pure strategy NE (PSNE)

Maxmin Strategies — security level, relation to PSNE

Matrix (Zero-Sum) Games — saddle points, maxmin/minmax relation

Mixed Strategies — mixed strategy NE (MSNE), characterization, algorithms, Nash's existence theorem

Correlated Equilibrium — definition, computation

Part II — Extensive Form and Bayesian Games

Perfect Information Extensive Form Games — formal definition, conversion to normal form

Subgame Perfection — SPNE, backward induction, the Centipede game

Imperfect Information EFGs — behavioral vs. mixed strategies, perfect recall, Kuhn's theorem

Equilibrium in IIEFGs — beliefs, sequential rationality, Perfect Bayesian Equilibrium

Case Study: P2P File Sharing — BitTorrent and strategic manipulation

Bayesian Games — definition, ex-ante/ex-interim utility, Bayesian equilibrium, first- and second-price auctions

Part III — Mechanism Design and Social Choice

Mechanism Design Basics — social choice functions, DSIC, the revelation principle

Arrow's Impossibility Theorem — social welfare functions, IIA, proof

Gibbard–Satterthwaite Theorem — strategyproofness and monotonicity, proof

Domain Restrictions — single-peaked preferences, the median voter rule and theorem

Task Sharing & the Uniform Rule — Sprumont's characterization

Part IV — Mechanism Design with Money

Quasi-Linear Preferences — allocation and payment rules, Groves payments, Pareto efficiency

The VCG Mechanism — combinatorial allocation, individual rationality, pros and cons

Internet Advertising — position auctions, click-through rates

Affine Maximizers & Roberts' Theorem — characterizing DSIC mechanisms

Single-Object Auctions — Myerson's lemma, monotonicity

Optimal Mechanism Design — revenue maximization, virtual valuations, monotone hazard rate

07 Reference Texts

[MSZ] M. Maschler, E. Solan, S. Zamir, Game Theory, Cambridge University Press. The primary reference for this course.
[SLB] Y. Shoham, K. Leyton-Brown, Multiagent Systems, Cambridge University Press.
[Nar] Y. Narahari, Game Theory and Mechanism Design, World Scientific and IISc Press.
[OR] M. J. Osborne, A. Rubinstein, A Course in Game Theory, MIT Press. Useful alternative treatment, especially for strategic-form notation.
[NRTV] N. Nisan, T. Roughgarden, É. Tardos, V. Vazirani (eds.), Algorithmic Game Theory, Cambridge University Press. Good for the computational side of the course.
[PS] D. Parkes, S. Seuken, Economics and Computation. Useful for the applications (e.g. P2P file sharing) modules.

[Link to an evolving supplementary-references document — to be added]

08 Regrading Requests

The regrading procedure is intended to correct serious errors in grading — not to argue about each judgment call made by a grader. We will only consider a regrading request if there is a significant error, and if you sincerely feel your exam was unfairly graded, we will look it over carefully. If this feature is used to raise unnecessary regrading requests, a penalty may be applied — up to 50% of the marks for that question, irrespective of what marks you originally received. We are not trying to scare off students whose exams were graded incorrectly; we are trying to avoid frivolous requests.

What merits a regrade

Your answer is really the same as the one on the answer key, but the grader didn't realize it.
Your answer differs from the one on the answer key, but your answer is also correct.

What doesn't merit a regrade

"Most of what I wrote is correct, so I think I deserve more partial credit." — Partial credit is applied equally to all students who wrote a particular answer; it would be unfair to give you more without doing the same for everyone else.
"I wrote so much, and the grader didn't notice the correct answer buried in the paragraph." — You lose points if the correct answer is surrounded by incorrect or irrelevant information. Full credit requires pulling out the relevant information and excluding the rest.
"I'm just 1 point away from a higher grade, so I thought it was worth finding an extra point somewhere." — Lobbying for grades is inappropriate per Institute rules; such cases may be reported to the appropriate authorities.

09 Virtual Q&A

We use Piazza for class discussion — it's built for getting help fast and efficiently from classmates, TAs, and the instructor. Please post questions there rather than emailing the teaching staff directly.