Online platforms and marketplaces are ubiquitous in most aspects of our lives. At their core, these platforms are engines for solving two types of problems:
We will survey the main paradigms for these problems – how to formulate them; what are common algorithmic tools for solving them; how to analyze the performance and limits of these algorithms; how to compare different models of knowledge in terms of their effect on decision-making. Our approach will be primarily theoretical, focusing on mathematical techniques for designing and analyzing algorithms with formal guarantees. However the problems we consider have significant practical motivation, and we will see lots of examples throughout the course.
Lectures: TR 9.40.10am-10.55am, Phillips 307
Piazza Link ORIE 6180 Fall 21 (Please join even if you are not registered, but plan on auditing)
There is no single textbook for the course; I will post my notes, as well as the scribed notes, for all the topics we cover. A lot of what we discuss will be drawn from papers/tutorials, which will be linked on the website. However, you may find some of the following references helpful (note these are all either online, or open access via the Cornell network/passkey; my sincerest thanks to these amazing folks for this!):
Each student should scribe 2-3 lectures, in groups of 2; worth 30% of grade.
Knowledge of basic probability and algorithms/optimization (at the level of ORIE 6500 and ORIE 6300/CS 6821) – in particular, you should be comfortable with (or willing to read up) LP duality, basic convex optimization, Markov chains, coupling, concentration inequalities. Prior exposure to game theory would be helpful, but is not necessary. Send me a mail if you are concerned about having the appropriate prerequisites.
For linear programming, see David Williamson’s excellent notes for ORIE 6300 (in particular, useful to revise the lectures on intro to LPs, standard forms and duality, Farkas’ lemma and strong duality, optimality conditions, sensitivity).
Lecture 1: Markov Decision-Processes, state-action frequency LP, HJB equations
Lecture 2: LPs for infinite horizon MDPs, mechanism design basics
Lecture 3: LP formulation for mechanism design, revelation principle, IC/IR constraints
Lecture 4: LP for BIC mechanism design, Intro to non-Bayesian decision-making
Lecture 5: The von Neumann Minimax Theorem, Yao’s Lemma, Intro to Optimal Stopping
Lecture 6: Optimal Stopping, Monotone stopping rules, Bruss’ Odds algorithm, sequential hypothesis testing
Lecture 7: Value function-policy dual pairs: bang-bang control, LQR and linear policies, convexity and threshold policies
Lecture 8: Multi-armed bandits and the Gittins Index, the prevailing-cost technique
Lecture 9: Indexability via polymatroids and the achievable region
Lecture 10: Approximate DP via dual balancing, Pandora’s box, prophet inequalities