Matroid prophet inequalities and applications to multi-dimensional mechanism design

Robert Kleinberg, S. Matthew Weinberg

Research output: Contribution to journalArticlepeer-review

29 Scopus citations


Consider a gambler who observes a sequence of independent random numbers and is allowed to stop at any time, claiming reward equal to the most recent observation. The famous prophet inequality of Krengel, Sucheston, and Garling asserts that a gambler who knows the distribution of each random variable can achieve half as much reward, in expectation, as a “prophet” who knows the sampled values and can choose the largest one. We generalize this result to settings in which the gambler and the prophet are allowed to make multiple selections, subject to a matroid constraint, showing that the gambler can still achieve half as much reward as the prophet. Our results imply improved bounds on the ability of sequential posted-price mechanisms to approximate optimal mechanisms in single-parameter and multi-parameter Bayesian settings. In particular, we provide the first efficiently computable constant-factor approximations to the Bayesian optimal revenue in certain multi-parameter settings.

Original languageEnglish (US)
Pages (from-to)97-115
Number of pages19
JournalGames and Economic Behavior
StatePublished - Jan 2019
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Finance
  • Economics and Econometrics


  • Auction theory
  • Multi-dimensional mechanism design
  • Online optimization
  • Revenue
  • Stochastic optimization


Dive into the research topics of 'Matroid prophet inequalities and applications to multi-dimensional mechanism design'. Together they form a unique fingerprint.

Cite this