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 Syllabus

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

• Bayesian Decision-Making settings:
  1. Richard Weber’s course notes: Optimization and Control
  2. Kamesh Munagala’s notes on Optimization Under Uncertainty
• Non-Bayesian Decision-Making:
  1. Bobby Kleinberg’s course notes for Learning, Games and Electronic Markets
  2. Alex Slivkins’ book Introduction to Multi-Armed Bandits
• For Mechanism and Market Design:
  1. Mechanism Design: A Linear Programming Approach by Rakesh Vohra
  2. Mechanism Design and Approximation by Jason Hartline

Scribing:

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

• Template files
• Signup sheet

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.

• For Markov chains, see my 6500 notes: Intro to MCs (for basic definitions, stationary distributions and the Ergodic theorem), and MC mixing (for MC convergence, and also coupling)

• 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).

Lectures

• Introduction: [slides]
  • The Parisi and Coppersmith-Sorkin conjectures
    • [Sid’s notes]
    • An easy proof of the $\zeta(2)$ limit in the random assignment problem by Johan Wästlund

Unit 1: Introduction to Decision-Making under Uncertainty

• Lecture 1: Markov Decision-Processes, state-action frequency LP, HJB equations

  • [Sid’s notes]
    
    

• Lecture 2: LPs for infinite horizon MDPs, mechanism design basics

  • Mechanism design basics by Tim Roughgarden
  • [Sid’s notes]
    
    

• 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

• Lecture 5: The von Neumann Minimax Theorem, Yao’s Lemma, Intro to Optimal Stopping

  • [Sid notes-Minimax Theorem]

• Lecture 6: Optimal Stopping, Monotone stopping rules, Bruss’ Odds algorithm, sequential hypothesis testing

  • [Sid notes-Optimal Stopping]

• Lecture 7: Value function-policy dual pairs: bang-bang control, LQR and linear policies, convexity and threshold policies

  • [Sid notes-Dual VF-Policy pairs]

• Lecture 8: Multi-armed bandits and the Gittins Index, the prevailing-cost technique

  • [Sid notes-Index Policies]

  • [Slides] by Bobby Kleinberg

• Lecture 9: Indexability via polymatroids and the achievable region

  • [Notes] by Dave Goldberg

• Lecture 10: Approximate DP via dual balancing, Pandora’s box, prophet inequalities

  • [Sid notes-Dual Balancing]
    

Unit 3: Mechanism Design

Unit 4: Non-Bayesian Online Decision-Making