Algorithms, Game Theory, and Applications-2025-Elective

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.

[B4] Computational Geometry : Algorithms and Applications by Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars.

[B5] Twenty Lectures on Algorithmic Game Theory by Tim Roughgarden.

[B6] Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

[P1] "Optimal strategies for the one-round discrete Voronoi game on a line" by Aritra Banik, Bhaswar B. Bhattacharya, and Sandip Das. Journal of Combinatorial Optimization 26.4 (2013): 655-669.

[P2] "Geometric stable roommates" by Esther M. Arkin, Sang Won Bae, Alon Efrat, Kazuya Okamoto, Joseph S.B. Mitchell, Valentin Polishchuk. Information Processing Letters 109.4 (2009): 219-224.

[V1] Lecture on Uncertainty in Financial Markets by Dripto Bakshi.

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

Page updated

Google Sites

Report abuse