CS 6001: 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. First meeting of the course is on Friday, July 29, 2022, at 2 PM, in F C Kohli Auditorium (note the unusual venue).
  2. Get started: enroll yourself on (1) Piazza, (2) NB (see details below). 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. First meeting slides.
  5. 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 or NB.
  6. Exam setup details for SAFE have been posted on this piazza note.
  7. Quiz 1 will be on Tue, Aug 30, 2022. Time: 4:15 - 4:45 PM. All details are posted in the same note above.
  8. Midsem will be on Mon, Sep 19, 2022. Time: 6:30 - 8:30 PM. All details are posted on Piazza.
  9. Quiz 2 will be on Tue, Nov 1, 2022. Time: 4:00 - 4:45 PM. All details are posted on Piazza.

Logistics

  • Instructor: Swaprava Nath (office hours: by appointment, mail at swaprava AT cse DOT iitb DOT ac DOT in with [CS6001] in the subject)
  • Teaching assistants: Hyderi Narjis Asad (narjisasad@cse.iitb.ac.in), Khajjayam Gowtham (gowtham@cse.iitb.ac.in), Abhishek Kumar (213050076@iitb.ac.in), Ashish Pandey (213050007@iitb.ac.in), Rishabh Kumar (184050005@iitb.ac.in), Sarfaraz Equbal (204050008@iitb.ac.in)
  • Classroom: CC 103 (New CSE Building)
  • Evaluation:
    1. Two quizzes -- 15% weightage for each
    2. One midsem and one endsem exam -- 35% weightage for each
    3. All exams are offline, proctored, in-lecture-hall, pen and paper, closed book (unless otherwise mentioned). Grading is done using SAFE or Gradescope.
  • 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.

Videolectures

Dear students and viewers,
In an attempt to make the videolectures better for self-learning, we need inputs from you. If you find errors or feel that there could be more details / clarifications in any of the videolecture modules, please enter your comments / inputs in this form. Your contribution will be gratefully acknowledged in a future version of these videolectures if you enter your name as well.
Similarly, for the course materials, we have created NB versions, where you can annotate and ask questions. Please use this tool to the fullest. The entire set of course materials, i.e., the boardwork, lecture notes, and the videolectures, is available on NB. Please subscribe via this link.
-- Instructor.

The entire playlist of lecture videos is now available.

Expand all videos | Collapse all videos

Before you start

  • Module 00: Prelude
    A 4-minute introduction. No specific reading for this module.
    Videolecture

Week 01

  • 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 01 Q&A on Piazza
Week 02

  • 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 02 Q&A on Piazza
Week 03

Week 04

  • 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 04 Q&A on Piazza
Week 05

  • 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 05 Q&A on Piazza
Week 06

  • 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 06 Q&A on Piazza
Week 07

  • 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

  • Module 37: The Social Choice Setup
    Scoring rules, Condorcent consistency. Properties of scoring rules: Pareto domination, Pareto efficient (PE), Unanimity (UN), Ontoness, Manipulability, Monotonicity. [Boardwork] [Boardwork (NB version)]
    Videolecture

    NB version

  • Week 07 Q&A on Piazza
Week 08

Week 09

  • 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 09 Q&A on Piazza
Week 10

  • 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 10 Q&A on Piazza
Week 11

  • 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 11 Q&A on Piazza
Week 12

  • 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

  • Week 12 Q&A on Piazza

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