Sample-Driven Optimal Stopping: From the Secretary Problem to the i.i.d. Prophet Inequality

References

• [1] Azar PD, Kleinberg R, Weinberg SM (2014) Prophet inequalities with limited information. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM), 1358–1377.Google Scholar
• [2] Babaioff M, Dinitz M, Gupta A, Immorlica N, Talwar K (2009) Secretary problems: weights and discounts. Proc. 20th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM), 1245–1254.Google Scholar
• [3] Babaioff M, Immorlica N, Kempe D, Kleinberg R (2007a) A knapsack secretary problem with applications. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: Proc. 10th Internat. Workshop, APPROX 2007, and 11th Internat. Workshop, RANDOM 2007 (Springer), 16–28.Google Scholar
• [4] Babaioff M, Immorlica N, Kempe D, Kleinberg R (2018) Matroid secretary problems. J. ACM. 65(6):1–26.Crossref, Google Scholar
• [5] Babaioff M, Immorlica N, Kleinberg R (2007b) Matroids, secretary problems, and online mechanisms. Proc. 18th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM), 434–443.Google Scholar
• [6] Bearden JN, Rapoport A, Murphy RO (2006) Sequential observation and selection with rank-dependent payoffs: An experimental study. Management Sci. 52(9):1437–1449.Link, Google Scholar
• [7] Bruss FT (2005) What is known about robbins’ problem? J. Appl. Probab. 42(1):108–120.Crossref, Google Scholar
• [8] Buchbinder N, Jain K, Singh M (2014) Secretary problems via linear programming. Math. Oper. Res. 39(1):190–206.Link, Google Scholar
• [9] Campbell G, Samuels SM (1981) Choosing the best of the current crop. Adv. Appl. Probab. 13(3):510–532.Crossref, Google Scholar
• [10] Chan TH, Chen F, Jiang SHC (2014) Revealing optimal thresholds for generalized secretary problem via continuous lp: impacts on online k-item auction and bipartite k-matching with random arrival order. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM), 1169–1188.Google Scholar
• [11] Chawla S, Hartline JD, Malec DL, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Proc. 42nd ACM Sympos. Theory Comput., 311–320.Google Scholar
• [12] Chow Y, Moriguti S, Robbins H, Samuels S (1964) Optimal selection based on relative rank (the “secretary problem”). Israel J. Math. 2(2):81–90.Crossref, Google Scholar
• [13] Cole R, Roughgarden T (2014) The sample complexity of revenue maximization. Proc. 46th Annual ACM Sympos. Theory Comput., 243–252.Google Scholar
• [14] Correa J, Cristi A, Feuilloley L, Oosterwijk T, Tsigonias-Dimitriadis A (2021a) The secretary problem with independent sampling. Proc. 2021 ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 2047–2058.Google Scholar
• [15] Correa J, Dütting P, Fischer F, Schewior K (2022) Prophet inequalities for iid random variables from an unknown distribution. Math. Oper. Res. 47(2):1287–1309.Link, Google Scholar
• [16] Correa J, Dütting P, Fischer F, Schewior K, Ziliotto B (2021b) Unknown iid prophets: Better bounds, streaming algorithms, and a new impossibility. 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) (Schloss Dagstuhl-Leibniz-Zentrum für Informatik).Google Scholar
• [17] Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2017) Posted price mechanisms for a random stream of customers. Proc. 2017 ACM Conf. Econom. Comput., 169–186.Google Scholar
• [18] Correa J, Saona R, Ziliotto B (2021d) Prophet secretary through blind strategies. Math. Program. 190(1–2):483–521.Crossref, Google Scholar
• [19] Dynkin EB (1963) The optimum choice of the instant for stopping a Markov process. Soviet Math. 4:627–629.Google Scholar
• [20] Ehsani S, Hajiaghayi M, Kesselheim T, Singla S (2018) Prophet secretary for combinatorial auctions and matroids. Proceedings of the twenty-ninth annual ACM-SIAM Symposium on Discrete Algorithms, 700–714 (SIAM).Google Scholar
• [21] Feldman M, Svensson O, Zenklusen R (2014) A simple o (log log (rank))-competitive algorithm for the matroid secretary problem. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM), 1189–1201.Google Scholar
• [22] Ferguson TS (1989) Who solved the secretary problem? Statist. Sci. 4(3):282–289.Crossref, Google Scholar
• [23] Gilbert JP, Mosteller F (1966) Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61:35–73.Crossref, Google Scholar
• [24] Guo C, Huang Z, Zhang X (2019) Settling the sample complexity of single-parameter revenue maximization. Proc. 51st Annual ACM SIGACT Sympos. Theory Comput., 662–673.Google Scholar
• [25] Gusein-Zade S (1966) The problem of choice and the sptimal stopping rule for a sequence of independent trials. Theory Probab. Appl. 11(3):472–476.Crossref, Google Scholar
• [26] Hajiaghayi MT, Kleinberg R, Sandholm T (2007) Automated online mechanism design and prophet inequalities. Proc. 22nd National Conf. Artificial intelligence-Volume 1, 58–65.Google Scholar
• [27] Hill TP, Kertz RP (1982) Comparisons of stop rule and supremum expectations of iid random variables. Ann. Probab. 10(2):336–345.Crossref, Google Scholar
• [28] Kaplan H, Naori D, Raz D (2020) Competitive analysis with a sample and the secretary problem. Proc. 14th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM), 2082–2095.Google Scholar
• [29] Kertz RP (1986) Stop rule and supremum expectations of iid random variables: a complete comparison by conjugate duality. J. Multivariate Anal. 19(1):88–112.Crossref, Google Scholar
• [30] Kesselheim T, Radke K, Tönnis A, Vöcking B (2013) An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. Algorithms–ESA 2013: Proc. 21st Annual Eur. Sympos. (Springer), 21:589–600.Google Scholar
• [31] Kesselheim T, Radke K, Tonnis A, Vocking B (2018) Primal beats dual on online packing lps in the random-order model. SIAM J. Comput. 47(5):1939–1964.Crossref, Google Scholar
• [32] Korula N, Pál M (2009) Algorithms for secretary problems on graphs and hypergraphs. Automata, Languages and Programming: Proc. 36th Internat. Coll., ICALP (Springer), 36(Part II):508–520.Google Scholar
• [33] Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. (N.S.). 83(4):745–747.Crossref, Google Scholar
• [34] Krengel U, Sucheston L (1978) On semiamarts, amarts, and processes with finite value. Adv. Probab. Related Topics 4:197–266.Google Scholar
• [35] Lachish O (2014) O(log log rank) competitive ratio for the matroid secretary problem. 2014 IEEE 55th Annual Sympos. Foundations of Comput. Sci., 326–335.Google Scholar
• [36] Lindley DV (1961) Dynamic programming and decision theory. J. R. Stat. Soc. Ser. C. Appl. Stat. 10(1):39–51.Crossref, Google Scholar
• [37] Liu A, Leme RP, Pál M, Schneider J, Sivan B (2021) Variable decomposition for prophet inequalities and optimal ordering. Proc. 22nd ACM Conf. Econom. Comput., 692–692.Google Scholar
• [38] Mucci AG (1973a) Differential equations and optimal choice problems. Ann. Statist. 1(1):104–113.Crossref, Google Scholar
• [39] Mucci AG (1973b) On a class of secretary problems. Ann. Probab. 1:417–427.Crossref, Google Scholar
• [40] Rubinstein A, Wang JZ, Weinberg SM (2020) Optimal single-choice prophet inequalities from samples. 11th Innovations Theoretical Comput. Sci. Conf., ITCS 2020 (Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing), 60.Google Scholar
• [41] Soto JA (2013) Matroid secretary problem in the random-assignment model. SIAM J. Comput. 42(1):178–211.Crossref, Google Scholar
• [42] Soto JA, Turkieltaub A, Verdugo V (2021) Strong algorithms for the ordinal matroid secretary problem. Math. Oper. Res. 46(2):642–673.Link, Google Scholar