Prophet secretary
From MaRDI portal
(Redirected from Publication:5348218)
Prophet secretary (scientific article; zbMATH DE number 6760184)
Prophet secretary (scientific article; zbMATH DE number 6760184)
Abstract: Optimal stopping theory is a powerful tool for analyzing scenarios such as online auctions in which we generally require optimizing an objective function over the space of stopping rules for an allocation process under uncertainty. Perhaps the most classic problems of stopping theory are the prophet inequality problem and the secretary problem. The classical prophet inequality states that by choosing the same threshold OPT/2 for every step, one can achieve the tight competitive ratio of 0.5. On the other hand, for the basic secretary problem, the optimal strategy achieves the tight competitive ratio of 1/e. In this paper, we introduce Prophet Secretary, a natural combination of the prophet inequality and the secretary problems. An example motivation for our problem is as follows. Consider a seller that has an item to sell on the market to a set of arriving customers. The seller knows the types of customers that may be interested in the item and he has a price distribution for each type: the price offered by a customer of a type is anticipated to be drawn from the corresponding distribution. However, the customers arrive in a random order. Upon the arrival of a customer, the seller makes an irrevocable decision whether to sell the item at the offered price. We address the question of finding a strategy for selling the item at a high price. We show that by using a uniform threshold one cannot break the 0.5 barrier. However, we show that i) using n distinct non-adaptive thresholds one can obtain a competitive ratio that goes to (1-1/e) as n grows; and ii) no online algorithm can achieve a competitive ratio better than 0.75. Our results improve the (asymptotic) approximation guarantee of single-item sequential posted pricing mechanisms from 0.5 to (1-1/e) when the order of agents (customers) is chosen randomly.
Recommendations
Cites work
- A Knapsack Secretary Problem with Applications
- A multiple-choice secretary algorithm with applications to online auctions
- A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
- Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers
- scientific article; zbMATH DE number 6783427 (Why is no real title available?)
- scientific article; zbMATH DE number 3383344 (Why is no real title available?)
- Improved algorithms and analysis for secretary problems and generalizations
- Improved competitive ratios for submodular secretary problems (extended abstract)
- Matroid prophet inequalities
- Matroids, secretary problems, and online mechanisms
- Multi-parameter mechanism design and sequential posted pricing
- Optimal Auction Design
- Optimal choice and assignment of the best \(m\) of \(n\) randomly arriving items
- Polymatroid Prophet Inequalities
- Prophet Inequalities with Limited Information
- Prophet-type inequalities for multi-choice optimal stopping
- Ratio prophet inequalities when the mortal has several choices
- Semiamarts and finite values
- Submodular secretary problem and extensions
- The d choice secretary problem
- The online stochastic generalized assignment problem
- The Optimal Choice of a Subset of a Population
- The Secretary Problem and Its Extensions: A Review
- The submodular secretary problem goes linear
Cited in
(37)- Progressive stopping heuristics that excel in individual and competitive sequential search
- Prophet secretary for \(k\)-knapsack and \(l\)-matroid intersection via continuous exchange property
- The secretary problem with distributions
- Finding the second-best candidate under the Mallows model
- Prophet inequalities vs. approximating optimum online
- Prophet secretary through blind strategies
- Optimal on-line allocation rules with verification
- Prophet inequality with competing agents
- Prophet secretary
- Prophet secretary for combinatorial auctions and matroids
- Beating \(1-\frac{1}{e}\) for ordered prophets
- Optimal online contention resolution schemes via ex-ante prophet inequalities
- Posted price mechanisms and optimal threshold strategies for random arrivals
- Prophet inequalities for independent and identically distributed random variables from an unknown distribution
- Uniformly bounded regret in the multisecretary problem
- Tight revenue gaps among simple mechanisms
- Prophet secretary through blind strategies
- Stochastic input models for online computing
- Optimal and Efficient Auctions for the Gradual Procurement of Strategic Service Provider Agents
- 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 secretary problem with predictions
- The importance of knowing the arrival order in combinatorial Bayesian settings
- Prophet inequalities via the expected competitive ratio
- Competition and recall in selection problems
- On submodular prophet inequalities and correlation gap
- Prophet secretary for combinatorial auctions and matroids
- Order-competitive ratio
- The outer limits of contention resolution on matroids and connections to the secretary problem
- Oracle-augmented prophet inequalities
- Hiring strategies
- From contention resolution to matroid secretary and back
- Pairwise-independent contention resolution
- Matroid Bayesian online selection
- Pairwise-independent contention resolution
- Random order vertex arrival contention resolution schemes for matching, with applications
- Beating competitive ratio 4 for graphic matroid secretary
This page was built for publication: Prophet secretary
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5348218)
