CS711: Introduction to Game Theory and Mechanism Design (Fall 2018)

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 class. I will assume familiarity with formal mathematical reasoning, some 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: PDF
Here is the course timetable (for figuring out clashes with other courses etc.)

Announcement(s):

  • Register yourself (students and TAs) on Piazza via the link given in the virtual classroom section at the end.
  • The first problem set is out. These are only for your practice. Please do not send the teaching staff their solutions. You are encouraged to discuss on Piazza or offline to solve these problems, and occasionally the TAs will step in answering questions on Piazza. To ask a question to the TAs on Piazza, please mention how you have attempted to solve the question first and where you are stuck.
  • Assignment 1, a solution (your submitted solution could be different, and it will be checked accordingly).
  • Midsem question paper, a solution (your submitted solution could be different, and it will be checked accordingly).
  • The second problem set is out. These are only for your practice. Please do not send the teaching staff their solutions. You are encouraged to discuss on Piazza or offline to solve these problems, and occasionally the TAs will step in answering questions on Piazza. To ask a question to the TAs on Piazza, please mention how you have attempted to solve the question first and where you are stuck.
  • Assignment 2, a solution (your submitted solution could be different, and it will be checked accordingly).
  • Endsem question paper, a solution (your submitted solution could be different, and it will be checked accordingly).

Course logistics:

Class times and venue: Mon Thu, 14.00-15.15, RM 101
Instructor: Swaprava Nath (office hours: by appointment, mail at swaprava AT cse DOT iitk DOT ac DOT in with [CS711] in the subject)
TA: Garima Shakya (office hours: email at garima AT cse DOT iitk DOT ac DOT in, Piazza is better to communicate though), Souradeep Chandra (souradeepc AT cse DOT iitk DOT ac DOT in), Gujarathi Dhaval Sukhanand (gdhaval AT cse DOT iitk DOT ac DOT in)
Evaluation:
1 Midterm exam and 1 Endterm exam (both closed book with weight 35% each)
2 take-home assignments (15% each)
The solutions of the assignments must be typeset in Latex and emailed. Here is the template for submitting the assignments.  Here and here are good introductions to LaTeX.
Reference texts: No specific one. The following books could be helpful.
  1. “Game Theory” — Michael Maschler, Eilon Solan, Shmuel Zamir (few copies of this book are available in the library)
  2. Multiagent Systems — Y. Shoham and K. Leyton Brown, Cambridge University Press,
  3. “Game Theory and Mechanism Design” — Y. Narahari, World Scientific and IISc Press, paperback.

Scribed lecture notes from a past incarnation of this course can be found here.

Lectures

[Will be updated as the classes go along. Disclaimer: the slides/lecture notes resulted from a compilation of multiple other resources.]

DateTopicsReferencesSlides/Notes
Jul 30IntroductionAny of the references, introductory chapterSlides, [handout]
Aug 2Strategy, Rationality, Common KnowledgeChap 1, Sec 4.5 of MSZSlides, [handout] Exercise 1.3 of MSZ
Aug 6Maxmin Strategies, Nash EquilibriumChap 4, MSZSlides, [handout]
Aug 9Elimination of dominated strategies, Two player zero sum gamesChap 4, MSZSlides, [handout]
Aug 13Mixed strategiesChap 5, MSZSlides, [handout]
Aug 16Existence of MSNEChap 5, MSZSlides, [handout]
proof of the Nash theorem
Aug 20Correlated equilibria, Extensive form gamesChaps 8, 3, MSZSlides, [handout]
Aug 23PIEFG, IIEFGChap 3 MSZ / Chap 5 SLBSlides, [handout]
Aug 27Behavioral strategies, equivalenceChap 6 MSZSlides, [handout]
Aug 30Kuhn’s theorem, sequential rationality, perfect Bayesian equilibriumChap 6, 7 MSZSlides, [handout]
Sep 6Applications of repeated games: p2p file sharing, incomplete information gamesChap 9.4, MSZp2p slides
bittorrent animation
Sep 8Harsanyi representation of Bayesian gamesChap 9.4, MSZ
Sep 10Introduction to mechanism design, revelation principleChap 14, YNscribed lecnotes above
Sep 13Social welfare function, Arrow’s impossibility resultChap 14, YNscribed lecnotes above
Sep 24Proof of Arrow’s result — Field Expansion and Group Contraction Lemmatascribed lecnotes above
Sep 27Social Choice Function, Voting domain, Strategyproofness and other axiomsscribed lecnotes above
Oct 1Gibbard Satterthwaite theorem setupscribed lecnotes above
Oct 4GS theorem proofscribed lecnotes above
Oct 8Domain restriction, single peaked preferences, non-dictatorial solutionsscribed lecnotes above
Oct 11Moulin’s characterization, other domain restrictions — task allocation domainLec 24-25scribed lecnotes above
Oct 22Introduction to mechanisms in quasi-linear domainLec 25-26scribed lecnotes above
Nov 1Pareto optimality, VCG mechanismLec 27-28scribed lecnotes above
Nov 4VCG in combinatorial auction, Application in Internet advertisingLec 28-29scribed lecnotes above
Nov 5Other mechanisms of internet advertising: GSP and its limitation, limitations of VCGLec 30-31scribed lecnotes above
Nov 8Roberts’ theorem, mechanism design for selling a single object, Myerson theoremLec 32-33scribed lecnotes above
Nov 12Myerson payment, individual rationality, Bayesian incentive compatibility, single agent problemLec 34-35scribed lecnotes above
Nov 15Revenue optimal mechanism for single, multiple agents, the properties and examples, the domain and mechanism spaceLec 36-37scribed lecnotes above

Virtual Classroom

We will be using Piazza for class discussion. The system is highly catered to getting you 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.

Enrolment link (students and TAs, please register yourself here)
Class link

web site traffic statistics