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

Goal of the course

This course deals with topics at the interface of Economics and Computer Science. The focus will be more on the applications of game theory in social decision making. For example, how online advertising slots are allocated among competing advertisers or how the mobile telephony spectrum is distributed among the competing service providers such that certain “good” and “fair” properties are satisfied. Problems of similar flavor exist in many more applications like crowdsourcing, internet routing, fair division of goods, matching of students to advisors, facility location, social networks and many more. To understand these applications and to improve them, technology needs to partner with economic principles that drive them. This course is aimed to develop those economic principles. Even though the course is mainly focused on mechanism design (inverse game theory), it does not assume any background on game theory. The basic concepts will be developed in the initial phase of the course. The later part will see how to put this knowledge into designing games with specified objectives and several application domains of these ideas.

There are no specialized prerequisites for this course. 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. CS 405 is the UG version of CS 6001. The course content remains the same. CS 405 will have only exam-based evaluations: 2 quizzes, midsem, and endsem. In CS 6001, the two quizzes are replaced by a course project (group of size at most 2).
  2. This course will be in slot 5 (Wed, Fri, 9:30 - 10:55 AM), Venue: TBD
  3. First meeting of the course is on Wednesday, July 31, 2024, at 9:30 AM, in the regular classroom for this course.
  4. Get started: enroll yourself on Piazza. Moodle will NOT be used for class discussions.
  5. All class-related announcements will be made on Piazza. If you are not enrolled there, you may miss the announcements.
  6. First meeting slides.
  7. No audit grades will be given for this course. However, you're welcome to sit-in, attend the lectures and problem-solving sessions, and ask questions on Piazza.
  8. Course registration policy: CS 6001 is only for PG students, and UG elective course is listed as CS 405. UG students are advised to register only for CS 405 and not CS 6001. Pre-registration is enforced for CS 405. For pre-registration details, read this.
  9. Quiz 1 will be on Wed, Aug 28, 2024. Time: 9:30 - 10:55 AM. More details about the exam will be posted on Piazza closer to the date.
  10. Midsem will be on the Institute scheduled date-space-time (between 14 - 22 September, 2024). More details about the exam will be posted on Piazza closer to the date.
  11. Quiz 2 will be on Fri, Oct 25, 2024. Time: 9:30 - 10:55 AM. All details are posted on Piazza.
  12. Endsem will be on the Institute scheduled date-space-time (between 11 - 23 November, 2024). More details about the exam will be posted on Piazza closer to the date.
  13. Projects for CS 6001: some project suggestions are posted here. However, you are free to choose any project idea that is within the scope of this course. Make a two-page PDF with the problem statement, goal of your project, existing literature, and intended results in 4 clearly marked paragraphs (in addition to the title of the project and the group members). Send the proposal on Piazza as a private post to all the instructors. Projects are supposed to be done in groups of two. Send only one proposal for the group. The deadline of project proposal submission is September 13, 5:00 PM. Project discussions will start right after the midsem week. Please see Piazza for follow-ups.

Logistics

  • Instructor: Swaprava Nath (office hours: by appointment, mail at swaprava AT cse DOT iitb DOT ac DOT in with [CS6001] or [CS405], as appropriate, in the subject)
  • Teaching assistants: Ramsundar Anandanarayanan (ramsundar@cse.iitb.ac.in), Drashthi Doshi (drashthi@cse.iitb.ac.in), Isha Arora (210050070@iitb.ac.in), Karan Godara (210050082@iitb.ac.in), Ameya Vikrama Singh (210070007@iitb.ac.in), Sayantika Mandal (22D0379@iitb.ac.in) (more will be updated as assigned)
  • Classroom: TBD
  • Evaluation:
    1. CS 405: Two quizzes -- 20% weightage for each, no project
    2. CS 6001: One course project -- 30% weightage, no quizzes
    3. One midsem and one endsem exam -- 30% weightage for each (for CS 405), 35% weightage for each (for CS 6001)
    4. All exams are offline, proctored, in-lecture-hall, pen and paper, closed book (unless otherwise mentioned). Grading is done using Gradescope. Please sign up on this as well.
  • Course calendar

Reference texts

The following books could be useful. There is an old, non-reviewed, scribed lecture note file that may be used. This note file roughly covers all the things that is taught in the course, but has not gone through usual review that is needed for scientific publications. Hence, it may not be fully error-free, so refer to the standard books for authentic reference. But it may still 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. [Nar] "Game Theory and Mechanism Design" — Y. Narahari, World Scientific and IISc Press, paperback.
Check out this document for additional references (particularly for mechanism design).

Weekly lectures

You are strongly recommended to take your own notes regardless of the shared slides, as it can contain more information that are relevant for you than the slides. The modules represent the content and videos of a previous offering. Though it is given all in one go, it is highly recommended that you synchronize with the course and read that much. While there is not much difference in the content, some of the contents have been reorganized and may not match exactly as the slides. The viewers and readers are requested to see the weekly slides for a more up-to-date synchronization with the offline lectures.

Expand all videos | Collapse all videos

Before you start

  • Module 00: Prelude
    A 4:37 minutes' introduction. No specific reading for this module.
    Videolecture

Week 01

[Consolidated Weekly Slides]

  • Module 01: Introduction to Game Theory
    The setup for game theory. Example of game theory: Neighbouring kingdom's dilemma. What do we mean by strategies, players, actions, rational and intelligent players? Objectives of game theory. Reading: any reference, introductory chapter. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 02: Introduction to Mechanism Design
    Understanding mechanism design with the example of a cake-cutting problem. Why should we design a game? Takeaways from the course. Reading: any reference, introductory chapter. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 03: The Game of Chess
    Example to illustrate game theory: game of chess. Players, strategies, outcomes in chess. Reading: MSZ chapter 1. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 04: Proof of the Chess Theorem
    Proof of the chess theorem by Von Neumann (1928). Reading: MSZ chapter 1. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 05: Normal Form Games
    Representation of games in normal form (NF). Rationality and intelligence. Common knowledge and its implications. How does common knowledge percolate? Reading: MSZ chapter 4. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

Week 02

[Consolidated Weekly Slides]

  • Module 06: Dominance
    Domination in NFGs: dominant strategy, dominated strategy, dominant strategy equilibrium. Reading: MSZ chapter 4. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 07: Nash Equilibrium
    Rationality and dominant strategies. Existence of dominant strategies. Nash equilibrium. Best response and pure strategy nash equilibrium (PSNE). Reading: MSZ chapter 4. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 08: Maxmin Strategies
    Risk aversion of players. Maxmin value. Maxmin and dominant strategies. Relationship of maxmin value with PSNE. Reading: MSZ chapter 4. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 09: Elimination of Dominated Strategies
    What happens to stability and security when some (dominated) strategies are eliminated (iterative elimination)? Does it change the maxmin value? No. Reading: MSZ chapter 4. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 10: Preservation of PSNE
    What happens to equilibrium after iterative elimination? Can a new equilibrium be generated? No. Reading: MSZ chapter 4. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 11: Matrix Games
    Two-player zero-sum game (matrix game). What are the PSNEs of these games? Saddle points. Reading: MSZ chapter 4. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 12: Relation between Maxmin and PSNE in Matrix Games
    A matrix game has a PSNE (saddle point) iff maxmin and minmax values are the same. Reading: MSZ chapter 4. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

Week 03

[Consolidated Weekly Slides]

Week 04

[Consolidated Weekly Slides]

  • Module 18: Correlated Equilibrium
    Correlated strategy and equilibrium: definitions, example, and discussion. Reading: MSZ chapter 8. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 19: Computing Correlated Equilibrium
    The two sets of constraints are to be solved to compute the CE. Comparison of CE with the previous equilibrium notions. Summary so far in this course. Reading: MSZ chapter 8. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 20: Extensive Form Games
    Perfect information extensive form games (PIEFGs): Example of brother-sister chocolate division, formal definition. Understanding the transformation of PIEFG into NFG with an example. Reading: MSZ chapter 3. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 21: Subgame Perfection
    Equilibrium guarantees are weak in PIEFG. Subgame perfect Nash equilibrium (SPNE). Finding SPNE using backward induction. Reading: MSZ chapter 3. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 22: Limitations of SPNE
    The computation cost of SPNE. Advantages and disadvantages of SPNE. Centipede game. Reading: MSZ chapter 3. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

Week 05

[Consolidated Weekly Slides]

  • Module 23: Imperfect Information Extensive Form Games
    IIEFG: Games with imperfect information. Example and formal definition of IIEFG. Reading: MSZ chapter 3, SLB chapter 5. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 24: Strategies in IIEFGs
    Randomized strategies in IIEFG. Behavioral strategy. Relation between mixed and behavioral strategies: equivalence, can we have an equivalence? Utility equivalence. Reading: MSZ chapter 3, 6. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 25: Equivalence of Strategies in IIEFGs
    Why behavioral strategies are desirable? Does the equivalence always hold? The equivalence does not hold if the players are forgetful. Reading: MSZ chapter 6. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 26: Perfect Recall
    Forgetfulness of the players. Games with perfect recall: definition, example, the implication of perfect recall. Kuhn's theorem (1957). Reading: MSZ chapter 6. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

Week 06

[Consolidated Weekly Slides]

  • Module 27: Equilibrium in IIEFGs
    Equilibrium notions in IIEFGs. Example and formal definitions of belief, Bayesian beliefs, and sequential rationality. Perfect Bayesian Equilibrium (PBE). Reading: MSZ chapter 6. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 28: Game Theory in Practice -- P2P File Sharing
    Peer-to-peer sharing: desired terminology, file-sharing game, New protocol (BitTorrent). BitTorrent optimistic unchoking algorithm, attacks on BitTorrent, BitThief, Strategic piece revealer. Reading: Parkes and Seuken book chapter 5. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 29: Bayesian Games
    Bayesian game: definition, example, stages of a Bayesian game. Reading: MSZ chapter 9.4. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 30: Strategy, Utility in Bayesian Games
    Strategy, Relationship between ex-ante utility, ex-interim utility. Example: Two-player bargaining game, sealed bid auction. Reading: MSZ chapter 9.4. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 31: Equilibrium in Bayesian Games
    Equilibrium concepts in Bayesian games: Nash equilibrium (NE) and Bayesian equilibrium (BE), equivalence between the two concepts. Existence of BE. Reading: MSZ chapter 9.4. [Boardwork] [Addendum] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 32: Examples of Bayesian Equilibrium
    Bayesian equilibria in Bayesian games. Examples: first-price auction, second-price auction. Reading: MSZ chapter 9.4. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

Week 07

[Consolidated Weekly Slides]

  • Module 33: Introduction to Mechanism Design
    A general model for mechanism design. Social choice function. Direct and indirect mechanisms. Dominant strategy incentive compatibility (DSIC). [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 34: Revelation Principle
    Relationship between DSI and DSIC. Bayesian implementation (BI) of a social choice function. Relationship between BI and Bayesian incentive compatibility (BIC). [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 35: Arrow's Impossibility Result
    Linear or non-linear preference order and preference aggregation: social welfare function (SWF). Properties of SWF: Weak/strong Pareto, Independence of irrelevant alternatives (IIA), and Arrow's impossibility result. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 36: Proof of Arrow's Result
    Decisive and almost decisive set of agents. Field expansion lemma and group contraction lemma. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

Week 08

[Consolidated Weekly Slides]

Week 09

[Consolidated Weekly Slides]

  • Module 44: The Task Sharing Domain
    Single-peaked preferences over task share. Pareto efficiency in task-sharing setting. Some SCFs: Serial dictatorship, proportional. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 45: The Uniform Rule
    For the task-sharing setting, a deterministic SCF f is SP, PE, and ANON iff f is the Uniform rule. [Boardwork] [Boardwork (NB version)] [Sprumont's paper]
    Videolecture

    NB version

  • Module 46: Mechanism Design with Transfers
    Examples of allocation problems. Valuation and payment functions. Quasi-linear utility function. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 47: Examples of Quasi-linear Preferences
    Examples of allocation rules: Constant rule, dictatorial rule, utilitarian rule, affine maximizer rule, egalitarian rule. Examples of payment rules: No deficit, no subsidy, budget balanced. Domain strategy incentive compatibility in quasi-linear setting. Properties of payment rule that implements an allocation rule. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 48: Pareto Optimality and Groves Payments
    A mechanism (f,p) is PE iff it is allocatively efficient. Groves payment rule to implement allocatively efficient rule. Proving that Groves' mechanisms are DSIC. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

Week 10

[Consolidated Weekly Slides]

  • Module 49: Introduction to VCG Mechanism
    What is the expression for the VCG? Computing the outcome and VCG payment. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 50: VCG in Combinatorial Allocations
    Proving that the payment for an agent not getting any object is zero. Proving that for 'allocation of goods' VCG is always IR. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 51: Applications to Internet Advertising
    The essence of Internet advertising. Click through rate and a foundation for the next module. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 52: Slot Allocation and Payments in Position Auctions
    An allocation is efficient if the allocation is by rank by the expected revenue mechanism. Calculation of total expected payment. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 53: Pros and Cons of VCG Mechanism
    Pros: DSIC, no deficit if items are goods, never charges a losing agent, etc. Cons: privacy and transparency, susceptibility to collusion, not frugal, revenue monotonicity violated, not budget-balanced. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

Week 11

[Consolidated Weekly Slides]

  • Module 54: Affine Maximizers
    Generalization of VCG mechanism. Affine maximizer allocation rule. Independence of non-influential agents (INA). An AM rule satisfying INA is implementable in dominant strategies. Roberts theorem (1979) for characterization of the class of DSIC mechanisms in the quasi-linear domain. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 55: Single Object Allocation
    Mechanism design for selling single indivisible object: setup, allocation rule, valuation, second-price auction. Observations and some standard results from convex analysis. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 56: Myerson's Lemma
    Monotonicity and Myerson's lemma. An allocation rule in single object allocation is implementable in dominant strategies if it is non-decreasing. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 57: Illustration of Myerson's Lemma
    Examples of some single object allocation mechanisms. Ex-post individual rationality. Some non-Vickrey auctions. Deterministic mechanisms that redistribute the money. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 58: Optimal Mechanism Design
    How to maximize the revenue earned by the auctioneer. Bayesian Incentive compatibility (BIC). Independence and characterization of BIC mechanisms. Interim individually rational (IIR) mechanism. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

Week 12

[Consolidated Weekly Slides]

  • Module 59: Single Agent Optimal Mechanism Design
    Optimal mechanism design for a single agent. What is the structure of an optimal mechanism? Expected revenue. Monotone hazard rate (MHR). [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 60: Multiple Agent Optimal Mechanism Design
    Optimal mechanism (BIC, IIR, and maximizes revenue) design for multiple agents. Virtual valuation of a player. A 'regular' virtual valuation. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 61: Examples of Optimal Mechanisms
    Examples: two buyers, Symmetric bidders, Efficiency, and optimality. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Module 62: Endnotes and Summary
    The uniqueness of Groves mechanism for efficiency. No Groves mechanism is budget balanced. Weakening DSIC for positive results. In a bilateral trade, no mechanism can be simultaneously BIC, efficient, IIR, and budget balanced. Summary of the mechanisms with different combinations of properties discussed in this course. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

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.

  • Enrollment link (students and TAs, please register yourself here -- access code will be given on the first meeting of the course)
  • Class link

world map hits counter