Special Topics in Theoretical Computer Science - Bayesian Online Selection

Course code	COL863
Instructor	Ashish Chiplunkar (ashishc@...)
Classes	~~Block III, Room 342~~ SIT building, room 001; Monday and Wednesday 11:00 - 12:00, Thursday 12:00 - 13:00 (Slot H)

Overview

Suppose you wish to sell an item to one of several potential buyers. The buyers approach you one at a time, offer you a price, after which you need to either accept their offer and sell the item, or reject them and move to the next buyer. How do you strategize to maximize your revenue? The course concerns modelling and analysis of problems with this flavor, and design of algorithms for solving them.

The following talks by Prof. Matt Weinberg should serve as a gentle introduction to the course.

Eligibility and Prerequisites

All the institute-prescribed prerequisites for 800 level courses will apply. Additionally, a strong foundation in probability, linear algebra, and calculus is desirable.

Content (tentative; subject to minor changes)

Pre-requisite check: probability, independence, Bayes' rule, random variables, expectation, distribution, density, and cumulative distribution functions, stochastic dominance
Single-choice prophet inequality: optimum algorithms, fixed threshold algorithms, competitive ratio bounds -- in the adversarial and random arrival models
Digression: calculus of variations, Euler-Lagrange equation
IID prophet inequality
Multi-choice prophet inequality
Digression: matroids and their properties
Matroid prophet inequality -- in the adversarial and random arrival models
Digression: linear programs and LP duality
Ex-ante relaxation, contention resolution schemes, and equivalence of contention resolution schemes and prophet inequlities against the ex-ante relaxation
Approximate stochastic dominance, and equivalence of approximate stochastic dominance and competitive guarantees
Digression: mechanism design and Myerson's lemma
Approximate welfare and revenue maximization using prophet inequalities

Reference Material

No textbooks; we will refer to the following papers.

Useful Platforms

Microsoft Teams for announcements, discussion forum, lecture material
Gradescope for exam feedback

Grading

30 marks	easy short surprise Quizzes, best 6 of 8, no compesation for missed quizzes
30 marks	Reading Project -- read (sections of) 1-2 papers, write report, and present the result
40 marks	End-semester Exam

Passing criterion: >= 30 marks
Audit pass criterion: >= 30 marks in reading project + end-semester exam

Paper reading projects

Paper reading projects will involving choosing a paper (or two related papers), reading and understanding them, writing a report explaining the results in your own words, and presenting them to the class. Original contributions such as proving a new result, writing better proofs, validating results through experiments, etc. will get bonus credit. The following is an indicative list of papers that can be studied. Students are free to choose papers outside this list for their project, provided the papers are related to the content of the course. This will need the instructor's approval.

Attendance Policy

Grade will be completely determined by the marks obtained in the components listed in the Grading section. Mathematically, grade and attendance will be conditionally independent given marks. (However, rest assured that unconditionally, grade and attendance will be heavily correlated!)

The only exception to the above rule is if you fall into the E grade range. In this case, if your attendance is less than 75%, your E grade changes to F.