×

Prophet inequalities for independent and identically distributed random variables from an unknown distribution. (English) Zbl 1493.62492

Summary: A central object of study in optimal stopping theory is the single-choice prophet inequality for independent and identically distributed random variables: given a sequence of random variables \(X_1 , \ldots , X_n\) drawn independently from the same distribution, the goal is to choose a stopping time \(\tau\) such that for the maximum value of \(\alpha\) and for all distributions, \( \mathbb{E} [ X_\tau ] \geq \alpha \cdot \mathbb{E} [ \max_t X_t ]\). What makes this problem challenging is that the decision whether \(\tau = t\) may only depend on the values of the random variables \(X_1 , \ldots , X_t\) and on the distribution \(F\). For a long time, the best known bound for the problem had been \(\alpha \geq 1 - 1 / e \approx 0.632\), but recently a tight bound of \(\alpha \approx 0.745\) was obtained. The case where \(F\) is unknown, such that the decision whether \(\tau = t\) may depend only on the values of the random variables \(X_1 , \ldots , X_t\), is equally well motivated but has received much less attention. A straightforward guarantee for this case of \(\alpha \geq 1 / e \approx 0.368\) can be derived from the well-known optimal solution to the secretary problem, where an arbitrary set of values arrive in random order and the goal is to maximize the probability of selecting the largest value. We show that this bound is in fact tight. We then investigate the case where the stopping time may additionally depend on a limited number of samples from \(F\), and we show that, even with \(o(n)\) samples, \( \alpha \leq 1 / e\). On the other hand, \(n\) samples allow for a significant improvement, whereas \(O ( n^2 )\) samples are equivalent to knowledge of the distribution: specifically, with \(n\) samples, \( \alpha \geq 1 - 1 / e \approx 0.632\) and \(\alpha \leq \ln ( 2 ) \approx 0.693\), and with \(O ( n^2 )\) samples, \( \alpha \geq 0.745 - \varepsilon\) for any \(\varepsilon > 0\).

MSC:

62L15 Optimal stopping in statistics
60G40 Stopping times; optimal stopping problems; gambling theory
68W27 Online algorithms; streaming algorithms
91B26 Auctions, bargaining, bidding and selling, and other market models

References:

[1] [1] Abolhassani M, Ehsani S, Esfandiari H, Hajiaghayi MT, Kleinberg RD, Lucier B (2017) Beating 1−1/e for ordered prophets. Proc. 49th Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 61-71.Google Scholar · Zbl 1369.68349
[2] [2] Alaei S (2014) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM J. Comput. 43(2):930-972.Crossref, Google Scholar · Zbl 1307.91088 · doi:10.1137/120878422
[3] [3] Alijani R, Banerjee S, Gollapudi S, Munagala K, Wang K (2020) Predict and match: Prophet inequalities with uncertain supply. Proc. ACM Measurement Anal. Comput. Systems 4(1):1-23.Crossref, Google Scholar · doi:10.1145/3379470
[4] [4] Anari N, Niazadeh R, Saberi A, Shameli A (2019) Nearly optimal pricing algorithms for production constrained and laminar Bayesian selection. Proc. 20th ACM Conf. Econom. Comput. (ACM, New York), 91-92.Google Scholar
[5] [5] Azar Y, Chiplunkar A, Kaplan H (2018) Prophet secretary: Surpassing the 1−1/e barrier. Proc. 19th ACM Conf. Econom. Comput. (ACM, New York), 303-318.Google Scholar
[6] [6] Azar PD, Kleinberg R, Weinberg SM (2014) Prophet inequalities with limited information. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 1358-1377.Google Scholar · Zbl 1422.91162
[7] [7] Babaioff M, Blumrosen L, Dughmi S, Singer Y (2017) Posting prices with unknown distributions. ACM Trans. Econom. Comput. 5(2):13.Google Scholar
[8] [8] Berezovskiy BA, Gnedin AV (1984) The Best Choice Problem (in Russian) (Nauka, Moscow).Google Scholar · Zbl 0579.62066
[9] [9] Bergemann D, Schlag K (2008) Pricing without priors. J. Eur. Econom. Assoc. 6(2-3):560-569.Crossref, Google Scholar · doi:10.1162/JEEA.2008.6.2-3.560
[10] [10] Bergemann D, Schlag K (2011) Robust monopoly pricing. J. Econom. Theory 146(6):2527-2543.Crossref, Google Scholar · Zbl 1229.91124 · doi:10.1016/j.jet.2011.10.018
[11] [11] Chawla S, Miller JB, Teng Y (2019) Posted pricing for online resource allocation: Intervals and paths. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1962-1981.Google Scholar · Zbl 1435.91107
[12] [12] Chawla S, Hartline JD, Malec DL, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Proc. 42nd Annual ACM Sympos. Theory Comput. (ACM, New York), 311-320.Google Scholar · Zbl 1293.91078
[13] [13] Correa J, Saona R, Ziliotto B (2019) Prophet secretary through blind strategies. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1946-1961.Google Scholar · Zbl 1433.91071
[14] [14] Correa J, Cristi A, Epstein B, Soto JA (2020) The two-sided game of googol and sample-based prophet inequalities. Proc. 31st Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2066-2081.Google Scholar · Zbl 07304151
[15] [15] Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2017) Posted price mechanisms for a random stream of customers. Proc. 18th ACM Conf. Econom. Comput. (ACM, New York), 169-186.Google Scholar
[16] [16] den Boer AV (2015) Dynamic pricing and learning: Historical origins, current research, and new directions. Surveys Oper. Res. Management Sci. 20(1):1-18.Crossref, Google Scholar · doi:10.1016/j.sorms.2015.03.001
[17] [17] Dütting P, Kesselheim T (2019) Posted pricing and prophet inequalities with inaccurate priors. Proc. ACM Conf. Econom. Comput. (ACM, New York), 111-129.Google Scholar
[18] [18] Dütting P, Kleinberg RD (2015) Polymatroid prophet inequalities. Bansal N, Finocchi I, eds. Proc. 23rd Eur. Sympos. Algorithms (Springer, Berlin), 437-449.Google Scholar · Zbl 1466.68087
[19] [19] Dütting P, Kesselheim T, Lucier B (2020) An O(log log m) prophet inequality for subadditive combinatorial auctions. Proc. 61st Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 306-317.Google Scholar
[20] [20] Dütting P, Feldman M, Kesselheim T, Lucier B (2020) Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs. SIAM J. Comput. 49(3):540-582.Crossref, Google Scholar · Zbl 1454.91090 · doi:10.1137/20M1323850
[21] [21] Dvoretzky A, Kiefer J, Wolfowitz J (1956) Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. Ann. Math. Statist. 27(3):642-669.Crossref, Google Scholar · Zbl 0073.14603 · doi:10.1214/aoms/1177728174
[22] [22] Ehsani S, Hajiaghayi MT, Kesselheim T, Singla S (2018) Prophet secretary for combinatorial auctions and matroids. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 700-714.Google Scholar · Zbl 1403.60035
[23] [23] Esfandiari H, Hajiaghayi MT, Liaghat V, Monemizadeh M (2015) Prophet secretary. Bansal N, Finocchi I, eds. Proc. 23rd Eur. Sympos. Algorithms (Springer, Berlin), 496-508.Google Scholar · Zbl 1466.91131
[24] [24] Ezra T, Feldman M, Gravin N, Tang ZG (2020) Online stochastic max-weight matching: Prophet inequality for vertex and edge arrival models. Proc. 21st ACM Conf. Econom. Comput. (ACM, New York), 769-787.Google Scholar
[25] [25] Feldman M, Gravin N, Lucier B (2015) Combinatorial auctions via posted prices. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 123-135.Google Scholar · Zbl 1372.91049
[26] [26] Feldman M, Svensson O, Zenklusen R (2016) Online contention resolution schemes. Proc. 27th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1014-1033.Google Scholar · Zbl 1411.68203
[27] [27] Feng Y, Niazadeh R, Saberi A (2019) Linear programming based online policies for real-time assortment of reusable resources. Preprint, submitted July 17, https://dx.doi.org/10.2139/ssrn.3421227.Google Scholar
[28] [28] Ferguson TS (1989) Who solved the secretary problem? Statist. Sci. 4(3):282-289.Crossref, Google Scholar · Zbl 0955.01509 · doi:10.1214/ss/1177012493
[29] [29] Gilbert JP, Mosteller F (1966) Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61(313):35-73.Crossref, Google Scholar · doi:10.1080/01621459.1966.10502008
[30] [30] Goldenshluger A, Zeevi A (2021) Optimal stopping of a random sequence with unknown distribution. Math. Oper. Res., ePub ahead of print October 25, https://doi.org/10.1287/moor.2020.1109.Google Scholar
[31] [31] Gravin N, Wang H (2019) Prophet inequality for bipartite matching: Merits of being simple and non adaptive. Proc. 20th ACM Conf. Econom. Comput. (ACM, New York), 93-109.Google Scholar
[32] [32] Hajiaghayi MT, Kleinberg RD, Sandholm TW (2007) Automated mechanism design and prophet inequalities. Cohn A, ed. Proc. 22nd AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 58-65.Google Scholar
[33] [33] Hill TP, Kertz RP (1982) Comparisons of stop rule and supremum expectations of i.i.d. random variables. Ann. Probab. 10(2):336-345.Crossref, Google Scholar · Zbl 0483.60035 · doi:10.1214/aop/1176993861
[34] [34] Hill TP, Kertz RP (1992) A survey of prophet inequalities in optimal stopping theory. Contemporary Math. 125:191-207.Crossref, Google Scholar · Zbl 0794.60040 · doi:10.1090/conm/125/1160620
[35] [35] Kaplan H, Naori D, Raz D (2020) Competitive analysis with a sample and the secretary problem. Proc. 31st Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2082-2095.Google Scholar · Zbl 07304152
[36] [36] Kertz RP (1986) Stop rule and supremum expectations of i.i.d. random variables: A complete comparison by conjugate duality. J. Multivariate Anal. 19(1):88-112.Crossref, Google Scholar · Zbl 0598.60044 · doi:10.1016/0047-259X(86)90095-3
[37] [37] Kleinberg RD, Weinberg SM (2012) Matroid prophet inequalities. Proc. 44th Annual ACM Sympos. Theory Comput. (ACM, New York), 123-136.Google Scholar · Zbl 1286.60037
[38] [38] Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. (N.S.). 83(4):745-747.Crossref, Google Scholar · Zbl 0336.60032 · doi:10.1090/S0002-9904-1977-14378-4
[39] [39] Krengel U, Sucheston L (1978) On semiamarts, amarts, and processes with finite value. Probability on Banach Spaces (Dekker, New York), 197-266.Google Scholar
[40] [40] Ramsey FP (1930) On a problem of formal logic. Proc. London Math. Soc. (3) 30(1):264-286.Crossref, Google Scholar · JFM 55.0032.04 · doi:10.1112/plms/s2-30.1.264
[41] [41] Rubinstein A (2016) Beyond matroids: Secretary problem and prophet inequality with general constraints. Proc. 48th Annual ACM Sympos. Theory Comput. (ACM, New York), 324-332.Google Scholar · Zbl 1373.68457
[42] [42] Rubinstein A, Singla S (2017) Combinatorial prophet inequalities. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1671-1687.Google Scholar · Zbl 1417.91251
[43] [43] Rubinstein A, Wang JZ, Weinberg SM (2020) Optimal single-choice prophet inequalities from samples. Proc. 11th Sympos. Innovations Theoret. Comput. Sci., Seattle, January 12-14, 1-60.Google Scholar · Zbl 07650408
[44] [44] Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 12(4):1213-1216.Crossref, Google Scholar · Zbl 0549.60036 · doi:10.1214/aop/1176993150
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.