Abstract: In the classic prophet inequality, samples from independent random variables arrive online. A gambler that knows the distributions must decide at each point in time whether to stop and pick the current sample or to continue and lose that sample forever. The goal of the gambler is to maximize the expected value of what she picks and the performance measure is the worst case ratio between the expected value the gambler gets and what a prophet, that sees all the realizations in advance, gets. In the late seventies, Krengel and Sucheston, and Gairing (1977) established that this worst case ratio is a universal constant equal to 1/2. In the last decade prophet inequalities has resurged as an important problem due to its connections to posted price mechanisms, frequently used in online sales. A very interesting variant is the Prophet Secretary problem, in which the only difference is that the samples arrive in a uniformly random order. For this variant several algorithms achieve a constant of 1-1/e and very recently this barrier was slightly improved. This paper analyzes strategies that set a nonincreasing sequence of thresholds to be applied at different times. The gambler stops the first time a sample surpasses the corresponding threshold. Specifically we consider a class of strategies called blind quantile strategies. They consist in fixing a function which is used to define a sequence of thresholds once the instance is revealed. Our main result shows that they can achieve a constant of 0.665, improving upon the best known result of Azar et al. (2018), and on Beyhaghi et al. (2018) (order selection). Our proof analyzes precisely the underlying stopping time distribution, relying on Schur-convexity theory. We further prove that blind strategies cannot achieve better than 0.675. Finally we prove that no algorithm for the gambler can achieve better than 0.732.
Recommendations
Cites work
- Beating \(1-\frac{1}{e}\) for ordered prophets
- Combinatorial auctions via posted prices
- Comparison of threshold stop rules and maximum for independent nonnegative random variables
- Comparisons of stop rule and supremum expectations of i.i.d. random variables
- Convex functions, partial orderings, and statistical applications
- From pricing to prophets, and back!
- scientific article; zbMATH DE number 7650408 (Why is no real title available?)
- Matroid prophet inequalities
- Matroid prophet inequalities and applications to multi-dimensional mechanism design
- Multi-parameter mechanism design and sequential posted pricing
- Optimal Auction Design
- Optimal auctions vs. anonymous pricing
- Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
- Prophet Inequalities with Limited Information
- Prophet secretary
- Prophet secretary for combinatorial auctions and matroids
- Semiamarts and finite values
- Stop rule and supremum expectations of i.i.d. random variables: A complete comparison by conjugate duality
Cited in
(14)- Prophet secretary
- scientific article; zbMATH DE number 67296 (Why is no real title available?)
- Prophet inequalities for independent and identically distributed random variables from an unknown distribution
- Prophet secretary through blind strategies
- Prophet secretary
- Sample-Driven Optimal Stopping: From the Secretary Problem to the i.i.d. Prophet Inequality
- Tight Guarantees for Static Threshold Policies in the Prophet Secretary Problem
- The importance of knowing the arrival order in combinatorial Bayesian settings
- Order-competitive ratio
- Prophet upper bounds for online matching and auctions
- Matroid Bayesian online selection
- Online combinatorial assignment in independence systems
- A computer-aided approach for approximate Nash equilibria
- Beating competitive ratio 4 for graphic matroid secretary
This page was built for publication: Prophet secretary through blind strategies
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2235156)
