Predict and Match: Prophet Inequalities with Uncertain Supply

Journal Article (Journal Article)

We consider the problem of selling perishable items to a stream of buyers in order to maximize social welfare. A seller starts with a set of identical items, and each arriving buyer wants any one item, and has a valuation drawn i.i.d. from a known distribution. Each item, however, disappears after an a priori unknown amount of time that we term the horizon for that item. The seller knows the (possibly different) distribution of the horizon for each item, but not its realization till the item actually disappears. As with the classic prophet inequalities, the goal is to design an online pricing scheme that competes with the prophet that knows the horizon and extracts full social surplus (or welfare).

Full Text

Duke Authors

Cited Authors

  • Alijani, R; Banerjee, S; Gollapudi, S; Munagala, K; Wang, K

Published Date

  • July 8, 2020

Published In

Volume / Issue

  • 48 / 1

Start / End Page

  • 13 - 14

International Standard Serial Number (ISSN)

  • 0163-5999

Digital Object Identifier (DOI)

  • 10.1145/3393691.3394212

Citation Source

  • Scopus