CS698A: Selected Areas of Mechanism Design

Outline: This course is based on selected topics in mechanism design and its relationship with areas like algorithms, optimization etc. These topics include cooperative games, stable matching, games on networks, potential games etc. This is a research-oriented course, hence students are expected to read and present cutting-edge research topics in this area, and also develop writing skills towards a formal technical report.

Pre-requisites: Familiarity with formal mathematical reasoning, probability theory, calculus, basics of computational complexity, and familiarity with computer programming. The course expects familiarity with game theoretic ideas and results – hence a course like CS698W or CS656 will be required.

First Course Handout (FCH): PDF

Announcement(s):

  • Lecture-Scribe assignment is now available. Scribes will be updated at the beginning of the week.
  • Problem set on bargaining (taken from Game Theory by Maschler et al.) — problems (15.) 10, 12, 13, 14, 16,17, 22, 23, 29.
  • Problem set on TU games (taken from Game Theory by Maschler et al.) — problems (16.) 6, 7, 11, 12, 20, 21, 23.
  • Problem set on Core (taken from Game Theory by Maschler et al.) — problems (17.) 3, 4, 7, 8, 10, 11, 12, 16, 17, 28, 52.
  • Some papers are suggested on Piazza for the project component of the course. They are indicative, however, you are free to choose project ideas of your own — see the course project section below.
  • Project proposal submission deadline: February 28 (4 days after the last midterm exam) — submit a one-page summary of the plan you are planning to pursue. You may use the project submission template below.
  • Project submission template: tex, pdf. Details are available in the pdf — keep your report limited to 10 pages in that format. The deadline for submission of the reports is April 21 (one day before the first day of end-sem exams).
  • Problem set on Shapley value and nucleolus (taken from Game Theory by Maschler et al.) — problems (18.) 7, 11, 12, 13, 14, 16, 28, and 20.23.
  • Midsem question paper. Solution to question 3.
  • The presentations start from March 16, 2018. The schedule will be updated soon. Here is a suggested guideline for the presentations.
  • Quiz on March 17, 2018, at 2 PM (venue: KD 102 – tentative)

Course logistics:

Class times and venue: Tuesday, Friday 14.00 – 15.15 hrs, KD 102
Instructor: Swaprava Nath (office hours: by appointment, mail at swaprava@cse.iitk.ac.in with [CS698A] in the subject)
TA: Rahul Jain (office hours: email at jain@cse.iitk.ac.in, Piazza is better to communicate though)
Evaluation: 1 midterm exam, 1 quiz (both closed book, weightages 40% and 10% respectively), and no endsem exam. The course project and presentation together amounts to 30%. Each student is supposed to scribe 2 lectures which weighs 20% (will follow roughly the procedure mentioned here for scribing).

Course policies are available in the FCH above.

Books & References

No specific textbook. The references and lecture notes of CS698W will be useful for the basics of game theory and mechanism design. Selected chapters from books and lecture notes that may be useful will be made available during the course. However the students may refer to the following books:

  • Martin Osborne and Ariel Rubinstein: A course in game theory
  • Y. Narahari: Game theory and mechanism design
  • Maschler, M., Solan, E., & Zamir, S. (2013). Game Theory. Cambridge: Cambridge University Press.
  • Jackson, Matthew O. Social and economic networks. Princeton university press, 2010.
  • Easley, David, and Jon Kleinberg. “Networks, Crowds, and Markets.” (2010).
  • Debasis Mishra
    Game Theory course notes: http://www.isid.ac.in/~dmishra/gm1doc/notes_2016.pdf
    Mechanism Design course notes: http://www.isid.ac.in/~dmishra/gmdoc/mdnotes.pdf
  • Papers from conferences, e.g., (but not limited to) EC, WINE, AAAI, IJCAI, AAMAS, and journals, e.g., Econometrica, Journal of Economic Theory, Games and Economic Behavior etc.

Lectures

[Will be updated as the classes go along. Disclaimer: these scribed lecture notes resulted from a compilation from multiple other sources, e.g., books and other lecture notes.]

Lecture 1: Introduction to the course with examples of game theory and mechanism design. [hwnotes] [scribed notes (draft)] [scribed notes]
Lecture 2: Introduction to cooperative game theory, correlated equilibrium, axiomatic bargaining. [hwnotes] [scribed notes (draft)] [scribed notes]
Lecture 3: Axioms for bargaining, Nash bargaining theorem. [hwnotes] [scribed notes (draft)] [scribed notes]
Lecture 4: Proof of Nash bargaining theorem. Extension for more than two players, limitations, Transferable Utility (TU) games. [hwnotes] [scribed notes (draft)] [scribed notes]
Lecture 5: Solution concepts of TU games, the core, examples of cores, balanced collection of coalitions, balanced weights, the Bondareva-Shapley theorem. [hwnotes] [scribed notes (draft)] [scribed notes]
Lecture 6: Proof of the Bondareva-Shapley theorem, examples of game classes with non-empty cores — market games, totally balanced games. [hwnotes] [scribed notes (draft)] [scribed notes] [linear programming duality intro]

Lecture 7: Consistency of set solution concepts of TU games– the Davis-Maschler reduced game property, applications to core, convex games with equivalent definition, non-emptiness of core of convex games. [hwnotes] [scribed notes (draft)] [scribed notes]
Lecture 8: Single-valued solution concept, Shapley axioms, Shapley value. [hwnotes] [scribed notes (draft)] [scribed notes]
Lecture 9: Proof of Shapley theorem, examples and applications, Shapley-Shubik power index, case study, Shapley value for convex games, consistency property — Hart-Mas-colell reduced game. [hwnotes] [scribed notes (draft)] [scribed notes]
Lecture 10: Refinements of the core, nucleolus, its computation, compact representation of coalitional games, weighted graph games. [hwnotes] [scribed notes (draft)] [scribed notes]
Lecture 11: Social choice and Gibbard-Satterthwaite result, one-sided matching, serial dictatorship, top-trading cycle mechanism. [hwnotes] [scribed notes (draft)] [scribed notes]
Lecture 12: Analysis of top-trading cycle mechanism, stability, core, individual rationality, characterization of TTC, generalized TTC. [hwnotes] [scribed notes (draft)] [scribed notes]
Lecture 13: Two sided matching, pairwise blocking and group blocking, stability, deferred acceptance algorithm, stability of DA algorithm. [hwnotes] [scribed notes (draft)] [scribed notes] [advisor-student matching app]
Lecture 14: Optimality of DA algorithm, further structures of the men and women-proposing versions of the algorithm. [hwnotes] [scribed notes (draft)] [scribed notes]
Lecture 15: Strategic aspects of DA algorithm, strategic network formation, Jackson-Wolinsky network formation model, pairwise stability, efficiency, structures of efficient and stable networks. [hwnotes] [scribed notes (draft)] [scribed notes]

Important: Lecture-Scribe assignment.

Scribing

Here is the template for scribing the lectures.  Here and here are good introductions to LaTeX. Please email me the scribed lecture notes within 2 days of the class (first week scribes get one week’s time) — I’ll immediately put them on the course page as ‘draft’. Later when I review the notes, you may need to update the notes and resubmit. Less the update that is needed, better is the credit — so consider to do the first draft carefully.

Course Project

Since this is a research-focused course, the course project is extremely important for developing new ideas and transforming them into workable solutions. It is seen that in doing a project, where a learner is required to either code a system or prove a result independently, s/he learns very intricate details of an idea or concept. A course project can be (a) completely a theoretical development, (b) completely a real-world application development, or (c) a mix of the previous two. All topics has to have a significant game-theoretic/mechanism design component — however there is no restriction on what the application area may be. It is a good idea to keep looking for ideas when different topics are discussed in the class — and if you have an idea that may be converted into a project, come and talk to me. Deadline for submitting the project proposals will be announced later.

Virtual Classroom

This semester 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

Advertisements