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. This course will be in slot 11 (Tue, Fri, 3:30 - 5 PM), Venue: LA 001
2. First meeting of the course is on Tuesday, August 1, 2023, at 3:30 PM, in the regular classroom for this course (LA 001).
3. Get started: enroll yourself on Piazza. Moodle will NOT be used for class discussions.
4. All class-related announcements will be made on Piazza. If you are not enrolled there, you may miss the announcements.
5. First meeting slides.
6. 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.
7. Course registration policy (Aug 1, 2023): Currently, the course registration is open only for CSE PG students (Mtech, MS, PhD, DD final year). The older registrations of CSE Btech students are kept, but new registrations are not allowed. Anyone else not meeting this criteria will be removed (even if ASC allows to register now -- it is a bug), and the teaching staff will not be responsible for any consequences.
8. Quiz 1 will be on Tue, Sep 5, 2023. Time: 3:30 - 4:55 PM. More details about the exam will be posted on Piazza closer to the date.
9. Midsem will be on the Institute scheduled date-space-time (between 16 - 24 September, 2023). More details about the exam will be posted on Piazza closer to the date.
10. Quiz 2 will be on Fri, Oct 27, 2023. Time: 3:30 - 4:55 PM. All details are posted on Piazza.
11. Endsem will be on the Institute scheduled date-space-time (between 16 - 26 November, 2023). More details about the exam will be posted on Piazza closer to the date.

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: Ramsundar Anandanarayanan (ramsundar@cse.iitb.ac.in), Harshvardhan Agarwal (200050050@iitb.ac.in), Onkar Borade (200050022@iitb.ac.in), Rounak Dalmia (200050119@iitb.ac.in), Kartik Gokhale (200100083@iitb.ac.in) (more will be updated as assigned)
• Classroom: LA 001
• Evaluation:
  1. Two quizzes -- 20% weightage for each
  2. One midsem and one endsem exam -- 30% weightage for each
  3. 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

The slides of each week which correspond to this edition of the course will be shared at the end of the week (this is a policy of this course). You are encouraged to take your own notes regardless of the shared slides, as it can contain more information that are relevant for you than the slides. For this reason, the slides would not be shared in the middle of the week so that you take notes on your own and check that at the end of the week. The modules represent the content and videos of a previous offering. 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. The handouts are the same slides without the overlays, but it may jeopardize the animations to a certain extent.

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]
[Consolidated Weekly Slides (Handout)]

• 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]
[Consolidated Weekly Slides (Handout)]

• 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]
[Consolidated Weekly Slides (Handout)]

• Module 13: Mixed Strategies
  Mixed strategies: probability distribution over the set of strategies. Utility at a mixed strategy. Reading: MSZ chapter 5. [Boardwork] [Boardwork (NB version)]
  Videolecture

  NB version

• Module 14: Mixed Strategy Nash Equilibrium
  Relation between PSNE and MSNE. Example of MSNE. Reading: MSZ chapter 5. [Boardwork] [Boardwork (NB version)]
  Videolecture

  NB version

• Module 15: Find MSNE
  How to find an MSNE? Support of a mixed strategy. Characteristics of MSNE and its implications. Reading: MSZ chapter 5. [Boardwork] [Boardwork (NB version)]
  Videolecture

  NB version

• Module 16: MSNE Characterization Theorem Proof
  Observations and proof for the characterization of MSNE. Reading: MSZ chapter 5. [Boardwork] [Boardwork (NB version)]
  Videolecture

  NB version

• Module 17: Algorithm to find MSNE
  MSNE characterization theorem to algorithm. Existence of MSNE: Nash theorem (1951). Reading: MSZ chapter 5. [Boardwork] [Boardwork (NB version)] [Proof of Nash theorem]
  Videolecture

  NB version

Week 04

[Consolidated Weekly Slides]
[Consolidated Weekly Slides (Handout)]

• 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]
[Consolidated Weekly Slides (Handout)]

• 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]
[Consolidated Weekly Slides (Handout)]

• 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]
[Consolidated Weekly Slides (Handout)]

• 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]
[Consolidated Weekly Slides (Handout)]

• 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

• Module 38: The Gibbard Satterthwaite Theorem
  An SCF f is strategyproof (SP) iff it is Monotone (MONO). If an SCF f is Onto and MONO then it is PE. An SCF f is SP+PE iff f is SP+UN. An SCF f is SP+UN iff f is SP+Onto. Gibbard-Satterthwaite (GS) Theorem. [Boardwork] [Boardwork (NB version)]
  Videolecture

  NB version

• Module 39: Proof of GS Theorem
  Examples of the cases when the GS theorem does not hold. Proof for GS theorem for two agents. [Boardwork] [Boardwork (NB version)]
  Videolecture

  NB version

• Module 40: Domain Restriction
  Understanding the domain restriction with the example of single-peaked preferences. [Boardwork] [Boardwork (NB version)]
  Videolecture

  NB version

• Module 41: Median Voting Rule
  Every median voter SCF is strategyproof. Anonymous (ANON) SCFs. [Boardwork] [Boardwork (NB version)]
  Videolecture

  NB version

• Module 42: Median Voter Theorem - Part 1
  Median voter theorem: A strategyproof SCF f is Onto and ANON iff f is Median voter rule. Proof of the median voter theorem when the median peak is a phantom peak. [Boardwork] [Boardwork (NB version)]
  Videolecture

  NB version

• Module 43: Median Voter Theorem - Part 2
  Proof of the median voter theorem when the median peak is a non-phantom/agent peak. [Boardwork] [Boardwork (NB version)]
  Videolecture

  NB version

Week 09

[Consolidated Weekly Slides]
[Consolidated Weekly Slides (Handout)]

• 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]
[Consolidated Weekly Slides (Handout)]

• 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]
[Consolidated Weekly Slides (Handout)]

• 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]
[Consolidated Weekly Slides (Handout)]

• 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