Course Outline : The course consists of 4 lecture hours per week. The lectures will be focused on developing algorithms and data structures to the problems in resource allocation and auction design. A basic syllabus will be followed as outlined in the school website.
A (soft) prerequisite for the course is exposure to data structures, algorithms and their time complexities.
Course Instructor : Dr. Arun Kumar Das, SCIS
Teaching Assistants: Sandipan Seth, Arun V.
Venue: LHC1-R3
Timings : Tuesday 4 PM - 6 PM, Wednesday 5 PM - 6 PM, Thursday 12 PM - 1 PM
Grading policy : Minor (Mid Sem) - 40%, Major (End Sem) - 60%
Reference Materials : [B1] Algorithmic Game Theory by Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani.
[B2] Algorithm Design by John Kleinberg & Eva Tardos.
[B3] Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani.
[B5] Twenty Lectures on Algorithmic Game Theory by Tim Roughgarden.
[B7] Reinforcement Learning: An Introduction by Richard S. Sutton and Andrew G. Barto.
[V1] Lecture on Uncertainty in Financial Markets by Dripto Bakshi.
[V2] Lecture on Uncertainty in Financial Markets by Dripto Bakshi.
[V3] Lecture on Uncertainty in Financial Markets by Dripto Bakshi.
[V4] Lecture on Perceptron Learning Algorithm by Kapser Green Larsen.
Lecture 1 (20/08/2025) : Course outline and Introduction. Prisoner's Dilemma: theory and practice [B1, Ch. 1.1.1].
Lecture 2 (21/08/2025) : Contention Resolution : Probability and Randomization [B2, Ch. 13.1].
Lecture 3 (26/08/2025) : Competitive Facility Location, One round Voronoi Game [P1] on Real Line. Median Finding, Selection sort, Quick sort.
Lecture 4 (28/08/2025) : Expectation of random variables [B2, Ch. 13.3], analysis of the expected running time of randomized median finding and quick sort [B2, Ch. 13.5].
Lecture 5 (02/09/2025) : Lower bound of comparison based sorting [B6, Ch. 8.1], Finding median in deterministic linear time [B6, Ch. 9.3].
Lecture 6 (03/09/2025) : Uncertainty in financial markets : Idea of hedging and arbitrage [V1].
Lecture 7 (04/09/2025) : Constrained optimization: Introduction to Linear Programming [B3, Ch. 7.1].
Assignment 1 (05/09/2025) : First assignment announced!. Deadline 19/09/2025.
Lecture 8 (09/09/2025) : Convex hulls [B4, Ch. 1; B6, Ch. 33.3].
Lecture 9 (10/09/2025) : Line segments intersection: idea [B6, Ch. 2].
Lecture 10 (11/09/2025) : Line segments intersection: execution [B6, Ch. 2].
Lecture 11 (16/09/2025) : Introduction to Network flow: Ford-Fulkerson algorithm [B2, Ch. 7.1].
Lecture 12 (17/09/2025) : Max flow and Min Cuts [B2, Ch. 7.2].
Lecture 13 (18/09/2025) : Min Cuts in undirected graphs [B2, Ch. 13.2].
Lecture 14 (23/09/2025) : Stable Matching problem [B2, Ch. 1].
Lecture 15 (24/09/2025) : Bipartite Matching : application of network flow [B2, Ch. 7.5].
Lecture 16 (25/09/2025) : Existence of perfect bipartite matching [B2, Ch. 7.5].
Lecture 17 (30/09/2025) : Geometric Stable Roommates [P2], Finding the closest pair of points [B2, Ch. 5.4].
Lecture 18 (01/10/2025) : Game Theory: Example on Prisoners' Dilemma [B1, Ch. 1.1.1], Tragedy of the commons [B1, Ch. 1.1.2].
Lecture 19 (08/10/2025) : Coordination Games: battle of sexes, routing congestion [B1, Ch.1.1.3]
Minor (14/10/2025) : Minor 1 examination!
Assignment 2 (15/10/2025) : Second assignment announced!. Deadline 31/10/2025.
Lecture 20 (15/10/2025) : Standard form games and compact representation [B1, Ch. 1.2].
Lecture 21 (16/10/2025) : Pure Nash Equilibrium, Zero sum games, Saddle points.
Lecture 22 (21/10/2025) : Mixed Nash equilibrium, Nash Theorem [B1, Ch. 1.3], Braess’s Paradox [B5, Ch. 1].
Lecture 23 (22/10/2025) : Auctions: First price auctions, Second price auctions, sponsored search auctions [B5, Ch. 2].
Lecture 24 (23/10/2025) : Myerson’s Lemma [B5, Ch. 3].
Project preparation week (28/10/2025-30/10/2025) : Submission deadline is 12/11/2025.
Lecture 25 (04/11/2025) : Uncertainty in financial markets : call and put options, put-call parity [V2,V3].
Lecture 26 (06/11/2025) : Predicting from data: perceptron learning algorithm [V4].
Lecture 27 (11/11/2025) : Proof sketch of Myerson’s Lemma, Applying the payment formula to sponsored search auctions [B5, Ch. 3].
Lecture 28 (12/11/2025) : Predicting from data: Deep Neural Networks [V5].
Lecture 29 (13/11/2025) : Learning from rewards: an idea of reinforcement learning [B7, Ch. 1.5].
Project evaluation (15/11/2025) : Presentation of the assignment projects!
Major (06/12/2025) : End semester/Major examination!