Matroid prophet inequalities

Robert Kleinberg, Seth Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

82 Scopus citations

Abstract

Consider a gambler who observes a sequence of independent, non-negative random numbers and is allowed to stop the sequence at any time, claiming a 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 at least half as much reward, in expectation, as a "prophet" who knows the sampled values of each random variable and can choose the largest one. We generalize this result to the setting in which the gambler and the prophet are allowed to make more than one selection, subject to a matroid constraint. We show that the gambler can still achieve at least half as much reward as the prophet; this result is the best possible, since it is known that the ratio cannot be improved even in the original prophet inequality, which corresponds to the special case of rank-one matroids. Generalizing the result still further, we show that under an intersection of p matroid constraints, the prophet's reward exceeds the gambler's by a factor of at most O(p), and this factor is also tight. Beyond their interest as theorems about pure online algoritms or optimal stopping rules, these results also have applications to mechanism design. Our results imply improved bounds on the ability of sequential posted-price mechanisms to approximate optimal mechanisms in both single-parameter and multi-parameter Bayesian settings. In particular, our results imply the first efficiently computable constant-factor approximations to the Bayesian optimal revenue in certain multi-parameter settings.

Original languageEnglish (US)
Title of host publicationSTOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing
Pages123-135
Number of pages13
DOIs
StatePublished - 2012
Externally publishedYes
Event44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States
Duration: May 19 2012May 22 2012

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other44th Annual ACM Symposium on Theory of Computing, STOC '12
CountryUnited States
CityNew York, NY
Period5/19/125/22/12

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • bayesian mechanism design
  • matroids
  • online optimization
  • optimal stopping
  • prophet inequalities

Fingerprint Dive into the research topics of 'Matroid prophet inequalities'. Together they form a unique fingerprint.

  • Cite this

    Kleinberg, R., & Weinberg, S. M. (2012). Matroid prophet inequalities. In STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing (pp. 123-135). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2213977.2213991