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

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

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

**Important:**Lecture-Scribe assignment.

### Scribing

*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