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.]

Date Topics References Slides/Notes
Jul 30 Introduction Any of the references, introductory chapter Slides, [handout]
Aug 2 Strategy, Rationality, Common Knowledge Chap 1, Sec 4.5 of MSZ Slides, [handout] Exercise 1.3 of MSZ
Aug 6 Maxmin Strategies, Nash Equilibrium Chap 4, MSZ Slides, [handout]
Aug 9 Elimination of dominated strategies, Two player zero sum games Chap 4, MSZ Slides, [handout]
Aug 13 Mixed strategies Chap 5, MSZ Slides, [handout]
Aug 16 Existence of MSNE Chap 5, MSZ Slides, [handout]
proof of the Nash theorem
Aug 20 Correlated equilibria, Extensive form games Chaps 8, 3, MSZ Slides, [handout]
Aug 23 PIEFG, IIEFG Chap 3 MSZ / Chap 5 SLB Slides, [handout]
Aug 27 Behavioral strategies, equivalence Chap 6 MSZ Slides, [handout]
Aug 30 Kuhn’s theorem, sequential rationality, perfect Bayesian equilibrium Chap 6, 7 MSZ Slides, [handout]
Sep 6 Applications of repeated games: p2p file sharing, incomplete information games Chap 9.4, MSZ p2p slides
Sep 8 Harsanyi representation of Bayesian games Chap 9.4, MSZ
Sep 10 Introduction to mechanism design, revelation principle Chap 14, YN scribed lecnotes above
Sep 13 Social welfare function, Arrow’s impossibility result Chap 14, YN scribed lecnotes above
Sep 24 Proof of Arrow’s result — Field Expansion and Group Contraction Lemmata scribed lecnotes above
Sep 27 Social Choice Function, Voting domain, Strategyproofness and other axioms scribed lecnotes above
Oct 1 Gibbard Satterthwaite theorem setup scribed lecnotes above
Oct 4 GS theorem proof scribed lecnotes above
Oct 8 Domain restriction, single peaked preferences, non-dictatorial solutions scribed lecnotes above
Oct 11 Moulin’s characterization, other domain restrictions — task allocation domain Lec 24-25 scribed lecnotes above
Oct 22 Introduction to mechanisms in quasi-linear domain Lec 25-26 scribed lecnotes above
Nov 1 Pareto optimality, VCG mechanism Lec 27-28 scribed lecnotes above
Nov 4 VCG in combinatorial auction, Application in Internet advertising Lec 28-29 scribed lecnotes above
Nov 5 Other mechanisms of internet advertising: GSP and its limitation, limitations of VCG Lec 30-31 scribed lecnotes above
Nov 8 Roberts’ theorem, mechanism design for selling a single object, Myerson theorem Lec 32-33 scribed lecnotes above
Nov 12 Myerson payment, individual rationality, Bayesian incentive compatibility, single agent problem Lec 34-35 scribed lecnotes above
Nov 15 Revenue optimal mechanism for single, multiple agents, the properties and examples, the domain and mechanism space Lec 36-37 scribed 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

Advertisements