Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design
Authors:
- 1 October 2022
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 171-178
Abstract
In the classical prophet inequality, a gambler faces a sequence of items, whose values are drawn independently from known distributions. Upon the arrival of each item, its value is realized and the gambler either accepts it and the game ends, or irrevocably rejects it and continues to the next item. The goal is to maximize the value of the selected item and compete against the expected maximum value of all items. A tight competitive ratio of $\frac{1}{2}$ is established in the classical setting and various relaxations have been proposed to surpass the barrier, including the i.i.d. model, the order selection model, and the random order model. In this paper, we advance the study of the order selection prophet inequality, in which the gambler is given the extra power for selecting the arrival order of the items. Our main result is a 0.725-competitive algorithm, that substantially improves the state-of-the-art 0.669 ratio by Correa, Saona and Ziliotto (Math. Program. 2021), achieved in the harder random order model. Recently, Agrawal, Sethuraman and Zhang (EC 2020) proved that the task of selecting the optimal order is NP-hard. Despite this fact, we introduce a novel algorithm design framework that translates the discrete order selection problem into a continuous arrival time design problem. From this perspective, we can focus on the arrival time design without worrying about the threshold optimization afterwards. As a side result, we achieve the optimal 0.745 competitive ratio by applying our algorithm to the i.i.d. model.
Keywords
All Related Versions
Funding Information
- Shanghai Municipal Education Commission
- Shanghai University of Finance and Economics
This publication has 19 references indexed in Scilit:
- Recent developments in prophet inequalitiesACM SIGecom Exchanges, 2019
- From pricing to prophets, and back!Operations Research Letters, 2019
- Prophet Secretary2018
- An economic view of prophet inequalitiesACM SIGecom Exchanges, 2017
- Beating 1-1/e for ordered prophets2017
- Prophet SecretarySIAM Journal on Discrete Mathematics, 2017
- Approximation Schemes for Sequential Posted Pricing in Multi-unit Auctions2010
- A survey of prophet inequalities in optimal stopping theory1992
- Comparison of Threshold Stop Rules and Maximum for Independent Nonnegative Random VariablesThe Annals of Probability, 1984
- Semiamarts and finite valuesBulletin of the American Mathematical Society, 1977