CS698W: Topics in Game Theory and Collective Choice

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 a bit of cooperative game theory 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):

  • Lecture-Scribe assignment is now available. Scribes will be updated at the beginning of the week.
  • Some projects ideas are shared. Check Piazza.
  • Problem set 1 is available (few additions/edits may be made later). Don’t send us solutions, these are for your practice only.
  • Midterm exam is on September 22, 2017, from 1-3 PM in KD 101. It will be a closed book/notes exam.
  • Midterm: questions, selected solutions.
  • No class on Oct 27, 2017 — Antaragni Friday!
  • Problem set 2 is available (few additions/edits may be made later). Don’t send us solutions, these are for your practice only.
  • Project submission template: tex, pdf. Details are available in the pdf — keep your report limited to 5 pages in that format. The deadline for submission of the reports is November 18 (the first day of end-sem exams).
  • Final exam is on November 22, 2017, from 9.59-11.59 AM in KD 101. It will be a closed book/notes exam.
  • Final: exam questions and one set of solutions.
  • Presentation schedule: [Presentations limited to 15 min + 5 min questions and discussions]
    Time: 2 – 3.30 PM on each day, Venue: KD 102.
    All groups must be present for the entire period from 2 — 3.30 PM.
    Nov 25 (Sat): Groups: (Gundeep, Divyanshu, Neeraj), (Gaurav, Amit, Mayank), (Dhawal, Anil, Ameya), (Sachin, Asim, Kunal)
    Nov 26 (Sun): Groups: (Sandipan, Aayush, Souradeep), (Garima, Gaurav, Sudhir), (Piyush, Prakhar, Kaustubh), (Ankit, Pranav, Dheeraj)

Course logistics:

Class times and venue: Tue Fri 12.00 – 13.00, Wed 14.00 – 15.00, KD 102
Instructor: Swaprava Nath (office hours: by appointment, mail at swaprava@cse.iitk.ac.in with [CS698W] 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 Final exam (both closed book), 1 group course-project (30% each) + scribing around 2 lectures (will follow roughly the procedure mentioned here) — 10%.
Reference texts: No specific one. The following two books could be helpful.
“Game Theory and Mechanism Design” — Y. Narahari, World Scientific and IISc Press, paperback.

Multiagent Systems — Y. Shoham and K. Leyton Brown, Cambridge University Press,

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

Important: Lecture-Scribe assignment.
All in one place: consolidated lecture notes.

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