Online Decision-Making and Market Design

Course Description

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:

  • Online decision-making: Settings involving multiple decisions over time, with uncertainty about future events, and where actions affect current and future outcomes.
  • Market design: Settings involving multiple decision-making agents, with uncertainty about agents’ types, and where agents’ actions affect each other as well as overall outcomes.

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.

Course Information

  • Lectures: TR 9.40.10am-10.55am, Phillips 307

  • Instructor: Sid Banerjee, 229 Rhodes Hall, email

  • Piazza Link ORIE 6180 Fall 21 (Please join even if you are not registered, but plan on auditing)

References

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!):

Scribing:

Each student should scribe 2-3 lectures, in groups of 2; worth 30% of grade.

Prerequisites (and some background material)

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.

Lectures

Unit 1: Introduction to Decision-Making under Uncertainty

  • 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

Unit 2: Bayesian Online Decision-Making

Unit 3: Mechanism Design

Unit 4: Non-Bayesian Online Decision-Making

Siddhartha Banerjee
Siddhartha Banerjee
Associate Professor

Sid Banerjee is an associate professor in the School of Operations Research at Cornell, working on topics at the intersection of data-driven decision-making, market design, and algorithms for large-scale networks.