Strategic Multi-Agent Artificial Intelligence

A Course in the International Summer School, IIT Bombay, 2025

Goal of the course

This course is based on selected topics in AI, game theory, mechanism design, social choice. The focus is to introduce an uninitiated audience to the world of strategic decision making in a formal mathematical setup. The course also shows the rational decisions paradigm of Artificial Intelligence that deals with these topics. Examples from real life are provided where these ideas are applicable. The course requires no prerequisites except a basic understanding of probability, linear algebra, and calculus.

This course is built upon selected topics and lectures from CS 6001 / CS 405, CS 6002, and CS 217. References are provided for further study of the topics.

Announcements

  1. The course happens in LC 101, from June 23-27, 2025. A detailed plan is here.
  2. Get started: enroll yourself on Piazza for class discussions, asking doubts to TAs, and connecting solving queries.
  3. All class-related announcements will be made on Piazza. If you are not enrolled there, you may miss the announcements.

Logistics

  • Instructor: Swaprava Nath (office hours: mail at swaprava AT cse DOT iitb DOT ac DOT in with [summer school] in the subject before coming)
  • Teaching assistant: Drashthi Doshi (drashthi@cse.iitb.ac.in)
  • Classroom: LC 101 (old lecture hall complex)
  • Evaluation:
    1. One take home assignment

Lectures

  • Day 01: AI and competitive games [opening slides] [slides]

    Part 1: Sequential move games, games with partial information, games with no information, subgame and subgame perfection. Reading: modules 20 and 21 of this course. Support reading: [RN] chapter 5 and [MSZ] chapter 3 (only relevant sections). [Scribed lecture notes] [More details: Lec 19 of CS 217]

    Part 2: Speedup techniques for solving sequential two player zero-sum games: depth-limited search, pruning. Examples in real-life. Simultaneous move two player zero-sum games, idea of an equilibrium. [Scribed lecture notes] [Alpha-Beta pruning example] [More details: Lec 20 of CS 217]

  • Day 02: Game theory and practice

    Part 1: General games with any finite number of players and utilities, normal form game representation, equilibria concepts: dominant strategy equilibrium, pure and mixed Nash equilibrium. Algorithm to find MSNE. [Scribed lecture notes] [More details: Lec 21 of CS 217]

    Part 2: Peer-to-peer sharing: desired terminology, file-sharing game, New protocol (BitTorrent). BitTorrent optimistic unchoking algorithm, attacks on BitTorrent, BitThief, Strategic piece revealer. Reading: Parkes and Seuken book chapter 5. [Boardwork] [More details: Module 28 of CS 405/6001]

  • Day 03: AI in democracy and stable matching

    Part 1: A general model for mechanism design. Social choice function. Direct and indirect mechanisms. Dominant strategy incentive compatibility (DSIC). [Boardwork], Scoring rules, Condorcent consistency. Properties of scoring rules: Pareto domination, Pareto efficient (PE), Unanimity (UN), Ontoness, Manipulability, Monotonicity. [Boardwork], An SCF f is strategyproof (SP) iff it is Monotone (MONO). If an SCF f is Onto and MONO then it is PE. An SCF f is SP+PE iff f is SP+UN. An SCF f is SP+UN iff f is SP+Onto. Gibbard-Satterthwaite (GS) Theorem. [Boardwork] [More details: Modules 33, 37, 38 of CS 405/6001]

    Part 2: Blocking pairs, Gale-Shapley deferred acceptance algorithm and its properties. Stability properties: pairwise and group blocking. Structure of stable matchings -- order over the stable matchings from the men and women sides. Reading: [Mishra] Chapter 8. [Deferred acceptance in balanced market animation] [Handwritten notes] [Scribed notes] [More details: Lec 4 of CS 6002]

  • Day 04: Auctions and Internet economics

    Part 1: Examples of allocation problems. Valuation and payment functions. Quasi-linear utility function. [Boardwork], Examples of allocation rules: Constant rule, dictatorial rule, utilitarian rule, affine maximizer rule, egalitarian rule. Examples of payment rules: No deficit, no subsidy, budget balanced. Domain strategy incentive compatibility in quasi-linear setting. Properties of payment rule that implements an allocation rule. [Boardwork], What is the expression for the VCG? Computing the outcome and VCG payment. [Boardwork] [More details: Modules 46, 47, 49 of CS 405/6001]

    Part 2: The essence of Internet advertising. Click through rate and a foundation for the next module. [Boardwork] [More details: Module 51 of CS 405/6001]

  • Day 05: Cake cutting and inheritance division

    Part 1: Allocation of a single divisible good, cake model: heterogeneous, divisible, non-identical preferred good, agent model: additive valuation, divisibility, normalization, fairness notions: proportionality, envy-freeness, Robertson-Webb query model for complexity, mechanisms: I-cut-you-choose (2 players), Dubins-Spanier algorithm (n players), Even-Paz algorithm (n players, recursive). Readings: [COMSOC] Chapter 13. [Handwritten notes] [Paper on divide and conquer PROP] [Scribed notes] [More details: Lec 7 of CS 6002]

    Part 2: Cake cutting envy-freeness question: Selfridge-Conway algorithm for EF allocation of a cake between three agents. [3 player EF cake cutting animation] Upper bound for n agents [Aziz and Mackenzie, FOCS 2016], lower bound for n agents [Procaccia, IJCAI 2009]. [Wikipedia article on envy-free cake cutting], [a general audience piece]. Fair allocation of indivisible goods, envy-freeness upto one good, round-robin algorithm for additive valuations. Reading (indivisible goods): survey by Amantidis et al. [Handwritten notes] [Scribed notes] [More details: Lec 8 of CS 6002]

Virtual Q and A

We will be using Piazza for class discussion. The system is highly catered to getting 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.

world map hits counter