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.

**“Game Theory”**— Michael Maschler, Eilon Solan, Shmuel Zamir (few copies of this book are available in the library)**“Multiagent Systems“**— Y. Shoham and K. Leyton Brown, Cambridge University Press,**“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 bittorrent animation |

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