Prior independent mechanisms via prophet inequalities with limited information

Pablo D. Azar, Robert Kleinberg, S. Matthew Weinberg

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


Prophet inequalities have recently become a fundamental tool in the design of sequential and multi-dimensional mechanisms in Bayesian settings. However, existing mechanisms—as well as the underlying prophet inequalities behind their analysis—require sophisticated information about the distribution from which inputs are drawn. Our goal in this work is to design prior-independent sequential and multi-dimensional mechanisms. To this end, we first design prophet inequalities that require knowing only a single sample from the input distribution. These results come in two forms: the first is via a reduction from single-sample prophet inequalities to secretary algorithms. The second is via novel single-sample prophet inequalities for k-uniform matroids. Leveraging our new prophet inequalities, we construct the first prior-independent sequential mechanisms where the seller does not know the order in which buyers arrive, and buyers may have asymmetric value distributions. We also construct the first prior-independent multi-dimensional mechanism where buyers may have asymmetric value distributions.

Original languageEnglish (US)
Pages (from-to)511-532
Number of pages22
JournalGames and Economic Behavior
StatePublished - Nov 2019

All Science Journal Classification (ASJC) codes

  • Finance
  • Economics and Econometrics


  • Bargaining Theory
  • Game Theory


Dive into the research topics of 'Prior independent mechanisms via prophet inequalities with limited information'. Together they form a unique fingerprint.

Cite this