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.)
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.]
Lecture 1: Introduction to the course with examples of game theory in practice. [slides] [badminton game video]
Lecture 2: Game theory 1: examples of games, preferences without utility representation, von-Neumann-Morgenstern utilities. [scribed notes]
Lecture 3: Game theory 2: vNM theorem, rationality and intelligence, common knowledge, dominant strategy, ideas of equilibrium. [scribed notes]
Lecture 4: Game theory 3: Pure and mixed strategy Nash equilibrium, best response interpretation, examples of mixed Nash in games, characterization theorem of MSNE. [scribed notes]
Lecture 5: Game theory 4: proof of characterization theorem, examples of its use to find MSNE, computation of MSNE — difficulty, Nash theorem. [scribed notes] [MSNE hardness paper]
Lecture 6: Game theory 5: Nash theorem and its proof. [scribed notes]
Lecture 7: Game theory 6: correlated equilibrium, comparison with MSNE, extensive form games — notation and examples. [scribed notes]
Lecture 8: Game theory 7: equilibrium refinement for perfect information EFG, subgame perfect Nash equilibrium (SPNE), computing SPNE — backward induction, expressive power of PIEFG — imperfect information EFG. [scribed notes]
Lecture 9: Game theory 8: IIEFG — richer representation of games, richer strategy space, mixed versus behavioral strategies, incomparability of mixed and behavioral strategies — games with perfect recall. [scribed notes]
Lecture 10: Game theory 9: outcome equivalence of mixed and behavioral strategies in games with perfect recall, equilibrium notion, “equilibrium notion tied to the belief of the players”, Bayesian belief, sequential rationality, perfect Bayesian equilibrium. [scribed notes]
Lecture 11: Game theory 10: classification of standard games, application domain: peer-to-peer file sharing. [scribed notes] [paper 1] [paper 2] [slides]
Lecture 12: Game theory 11: games with incomplete information — Bayesian games, types, common prior, ex-ante, ex-interim utilities, examples — bargaining, auction. [scribed notes]
Lecture 13: Game theory 12: Bayesian games — equilibrium concepts, Nash, Bayesian equilibria, equivalence, existence of Bayesian equilibrium. [scribed notes] [addendum]
Lecture 14: Game theory 12.5: examples of Bayesian equilibrium in first and second price auctions, Mechanism Design — examples and notation. [scribed notes]
Lecture 15: Mechanism design 1: social choice function, mechanisms and implementation via indirect and direct mechanisms, dominant strategy implementability and dominant strategy incentive compatibility, revelation principle for DSI SCFs. [scribed notes]
Lecture 16: Mechanism design 2: implementation in Bayesian equilibrium, Bayesian incentive compatibility, revelation principle for BIC, Arrovian social welfare functions, preference ordering, weak/strong Pareto. [scribed notes]
Lecture 17: Mechanism design 3: independence of irrelevant alternative, Arrow’s impossibility theorem and its proof, decisive group, field expansion lemma. [scribed notes]
Lecture 18: Mechanism design 4: group contraction lemma — finishing Arrow’s theorem, social welfare function to social choice function, voting rules. [scribed notes]
Lecture 19: Mechanism design 5: axioms for social choice function — Pareto efficiency, unanimity, onto-ness, monotonicity, strategyproofness, equivalence of SP and MONO, equivalence of PE, UN, and ONTO under SP. [scribed notes]
Lecture 20: Mechanism design 6: Gibbard-Satterthwaite theorem and its proof (for two voters), cases where GS theorem does not hold. [scribed notes] [Ref: Chapter 6 of the lecture notes by Debasis Mishra]
Lecture 21: Mechanism design 7: GS theorem and unrestricted domains, domain restrictions, single peaked preferences, example of non-dictatorial strategyproof SCFs, median voter SCF. [scribed notes]
Lecture 22: Mechanism design 8: properties of SCF in single-peaked domain, monotonicity, anonymity, Moulin’s characterization theorem with median voter rule. [scribed notes]
Lecture 23: Mechanism design 9: proof of Moulin’s characterization theorem with median voter rule. [scribed notes]
Lecture 24: Mechanism design 10: private good allocation — task sharing model, Pareto efficiency, Anonymity, strategyproofness, some candidate SCFs. [scribed notes]
Lecture 25: Mechanism design 11: uniform rule SCF, characterization of Pareto efficiency, anonymity, and strategyproofness using this rule, mechanism design with transfers and quasi-linear preferences. [hwnotes] [scribed notes (draft)]
Lecture 26: Mechanism design 12: examples of allocation and payment rules in quasi-linear domain, dominant strategy incentive compatibility and its impact on the payment functions. [scribed notes]
Lecture 27: Mechanism design 13: Pareto optimality of mechanisms in quasi-linear domain, relation with allocative efficiency, implementing AE rules — Groves class of payments, Clarke’s pivotal rule. [scribed notes]
Lecture 28: Mechanism design 14: illustration of VCG mechanism and its properties in single-object allocation, public good allocation, combinatorial allocation. [hwnotes] [scribed notes (draft)]
Lecture 29: Mechanism design 15: more properties of VCG mechanism in combinatorial good allocation, case study: Internet advertisements, kinds of ads, position auctions, agent valuations, click-through-rate, allocation rules. [hwnotes] [scribed notes (draft)]
Lecture 30: Mechanism design 16: Internet advertisements — sponsored search auctions, comparison of VCG and generalized second price (GSP) mechanisms, desirable properties of VCG. [hwnotes] [scribed notes (draft)]
Lecture 31: Mechanism design 17: limitations of VCG, generalization of VCG — affine maximizer allocation rules, implementability, Roberts’ theorem. [hwnotes] [scribed notes (draft)]
Important: Lecture-Scribe assignment.
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.
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.
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