- 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)
“Game Theory and Mechanism Design” — Y. Narahari, World Scientific and IISc Press, paperback.
“Multiagent Systems“ — Y. Shoham and K. Leyton Brown, Cambridge University Press,
[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 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. [scribed notes]
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. [scribed notes]
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. [scribed notes]
Lecture 30: Mechanism design 16: Internet advertisements — sponsored search auctions, comparison of VCG and generalized second price (GSP) mechanisms, desirable properties of VCG. [scribed notes]
Lecture 31: Mechanism design 17: limitations of VCG, generalization of VCG — affine maximizer allocation rules, implementability, Roberts’ theorem. [scribed notes]
Lecture 32: Mechanism design 18: domain restriction — single object allocation, relevant results from convex analysis. [scribed notes]
Lecture 33: Mechanism design 19: monotonicity of allocation rule, Myerson’s characterization for single object auction. [scribed notes]
Lecture 34: Mechanism design 20: properties of DSIC mechanisms in single object allocation domain: revenue equivalence, individual rationality, budget balance, examples. [scribed notes]
Lecture 35: Mechanism design 21: revenue maximization question, Bayesian incentive compatibility, interim individual rationality, characterization, single agent problem. [scribed notes]
Lecture 36: Mechanism design 22: monotone hazard rate, optimal auction for single agent, generalization for multiple agents. [scribed notes]
Lecture 37: Mechanism design 23: optimal mechanism for multiple agents, payment rule, examples. [scribed notes]
Lecture 38: Mechanism design 24: other results in mechanism design — efficiency and budget balance, Green-Laffont impossibility, interim individual rationality, Myerson-Satterthwaite result, mechanism design space. [scribed notes]
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.