Matroid prophet inequalities

By Robert D. Kleinberg, S. Matthew Weinberg. Symposium on the Theory of Computing, 2012

301 citations recorded by the source corpus.

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.

Subfields: Economics and Econometrics, Management Science and Operations Research, Marketing

View Paper: https://www.semanticscholar.org/paper/9b2b14bd4865427aac6ddfb4f5a36f69f82e6315

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Economics and Econometrics

In Management Science and Operations Research

In Marketing

Citations in the corpus

Prophet Secretary (2015, background): “Proof : Suppose for the sake of contradiction that there exists an algorithm Alg for the minimization secretary problem which isC-competitive.”
Prophet Secretary: Surpassing the 1-1/e Barrier (2017, methodology): “Kleinberg and Weinberg [12] considered the Matroid Prophet Inequality problem, where the feasible subsets of random variables are independent sets of a given matroid.”
Prophet Inequalities with Limited Information (2013, methodology): “Recently there has been a renewed interest in prophet inequalities, generalizing the problem to settings where the prophet and gambler can choose any k out of the n presented items [1, 6], and more generally to settings where the prophet and gambler can choose any independent set in a matroid or mat”