The Secretary Problem with Independent Sampling

References

• Allart P, Islas J (2015) A sharp lower bound for choosing the maximum of an independent sequence. J. Appl. Probability 53:1041–1051.Crossref, Google Scholar
• Alpern S, Baston V (2017) The secretary problem with a selection committee: Do conformist committees hire better secretaries? Management Sci. 63(4):1184–1197.Link, Google Scholar
• Angelovski A, Güth W (2020) When to stop: A cardinal secretary search experiment. J. Math. Psych. 98:102425.Crossref, Google Scholar
• Azar P, Kleinberg R, Weinberg SM (2014) Prophet inequalities with limited information. Proc. Twenty-Fifth Annual ACM-SIAM Sympos. Discrete Algorithms (SODA ’14) (Society for Industrial and Applied Mathematics, Philadelphia), 1358–1377.Google Scholar
• Babaioff M, Immorlica N, Kempe D, Kleinberg R (2007) A knapsack secretary problem with applications. Charikar M, Jansen K, Reingold O, Rolim JDP, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2007, Lecture Notes in Computer Science, vol. 4627 (Springer, Berlin, Heidelberg).Google Scholar
• Baumann C, Singmann H, Gershman SJ, von Helversen B (2020) A linear threshold model for optimal stopping behavior. Proc. Natl. Acad. Sci. USA 117(23):12750–12755.Crossref, Google Scholar
• Beyhaghi H, Kleinberg R (2019) Pandora’s problem with nonobligatory inspection. Proc. 2019 ACM Conf. Econom. Comput. (EC ’19) (Association for Computing Machinery, New York), 131–132.Google Scholar
• Beyhaghi H, Golrezaei N, Paes Leme R, Pál M, Sivan B (2021) Improved revenue bounds for posted-price and second-price mechanisms. Oper. Res. 69(6):1805–1822.Google Scholar
• Bradac D, Gupta A, Singla S, Zuzic G (2020) Robust algorithms for the secretary problem. 11th Innovations Theoret. Comput. Sci. Conf. (ITCS 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 151 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 32:1–32:26.Google Scholar
• Bruss FT (1984) A unified approach to a class of best choice problems with an unknown number of options. Ann. Probability 12(3):882–889.Crossref, Google Scholar
• Bruss FT (2000) Sum the odds to one and stop. Ann. Probability 28(3):1384–1391.Crossref, Google Scholar
• Campbell G, Samuels S (1981) Choosing the best from the current crop. Adv. Appl. Probability 13(3):510–532.Crossref, Google Scholar
• Chan HT-H, Chen F, Jiang SH-C (2015) 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. 2015 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 1169–1188.Google Scholar
• Chawla S, Hartline J, Malec D, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Proc. Forty-Second ACM Sympos. Theory Comput. (STOC ’10) (Association for Computing Machinery, New York), 311–320.Google Scholar
• Chen Y, Goldberg D (2018) Beating the curse of dimensionality in options pricing and optimal stopping. Preprint, submitted July 6, https://arxiv.org/abs/1807.02227.Google Scholar
• Chen Y, Goldberg D (2019) A new approach to high-dimensional online decision-making.Google Scholar
• Chen Y, Farias VF, Trichakis N (2019) On the efficacy of static prices for revenue management in the face of strategic customers. Management Sci. 65(12):5535–5555.Link, Google Scholar
• Ciocan DF, Mišić VV (2020) Interpretable optimal stopping. Management Sci. 68(3):1616–1638.Link, Google Scholar
• Correa J, Cristi A, Epstein B, Soto J (2020) The two-sided game of googol and sample-based prophet inequalities. Proc. 2020 ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 2066–2081.Google Scholar
• Correa J, Cristi A, Epstein B, Soto J (2023) Sample-driven optimal stopping: From the secretary problem to the i.i.d. prophet inequality. Math. Oper. Res. 49(1):441–475.Link, Google Scholar
• Correa J, Dutting P, Fischer F, Schewior K (2019) Prophet inequalities for i.i.d. random variables from an unknown distribution. Proc. 2019 ACM Conf. Econom. Comput. (EC ’19) (Association for Computing Machinery, New York), 3–17.Google Scholar
• 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
• Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2021b) Posted price mechanisms and optimal threshold strategies for random arrivals. Math. Oper. Res. 46(4):1452–1478.Link, Google Scholar
• Cownden D, Steinsaltz D (2014) Effects of competition in a secretary problem. Oper. Res. 62(1):104–113.Link, Google Scholar
• Derakhshan M, Golrezaei N, Paes Leme R (2021) Linear program-based approximation for personalized reserve prices. Management Sci. 68(3):1849–1864.Link, Google Scholar
• Doval L (2018) Whether to open Pandora’s box. J. Econom. Theory 175:127–158.Crossref, Google Scholar
• Dütting P, Lattanzi S, Paes Leme R, Vassilvitskii S (2021) Secretaries with advice. Proc. 22nd ACM Conf. Econom. Comput. (EC ’21) (Association for Computing Machinery, New York), 409–429.Google Scholar
• Dynkin EB (1963) The optimum choice of the instant for stopping a Markov process. Soviet Math. Dokl. 4:627–629.Google Scholar
• Esfandiari H, Korula N, Mirrokni V (2018) Allocation with traffic spikes: Mixing adversarial and stochastic models. ACM Trans. Econom. Comput. 6(3–4):14.Google Scholar
• Esfandiari H, Hajiaghayi MT, Lucier B, Mitzenmacher M (2020) Prophets, secretaries, and maximizing the probability of choosing the best. Internat. Conf. Artificial Intelligence Statist. (PMLR, New York).Google Scholar
• Ferguson TS (1989) Who solved the secretary problem? Statist. Sci. 4(3):282–296.Crossref, Google Scholar
• Gilbert J, Mosteller F (1966) Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61:35–73.Crossref, Google Scholar
• Goldstein DG, McAfee PR, Suri S, Wright JR (2020) Learning when to stop searching. Management Sci. 66(3):1375–1394.Link, Google Scholar
• Golrezaei N, Jaillet P, Zhou Z (2022) Online resource allocation with samples. Available at SSRN.Google Scholar
• Goodfellow I, Bengio Y, Courville A (2016) Deep Learning (MIT Press, Cambridge, MA).Google Scholar
• Hill T, Kertz R (1982) Comparisons of stop rule and supremum expectations of i.i.d. random variables. Ann. Probability 10(2):336–345.Crossref, Google Scholar
• Hwang D, Jaillet P, Manshadi V (2021) Online resource allocation under partially predictable demand. Oper. Res. 69(3):895–915.Link, Google Scholar
• Immorlica N, Kleinberg RD, Mahdian M (2006) Secretary problems with competing employers. Spirakis P, Mavronicolas M, Kontogiannis S, eds. Internet and Network Economics. WINE 2006, Lecture Notes in Computer Science, vol. 4286 (Springer, Berlin, Heidelberg).Google Scholar
• Jaillet P, Soto JA, Zenklusen R (2013) Advances on matroid secretary problems: Free order model and laminar case. Goemans M, Correa J, eds. Integer Programming and Combinatorial Optimization. IPCO 2013, Lecture Notes in Computer Science, vol. 7801 (Springer, Berlin, Heidelberg).Google Scholar
• Kaplan H, Naori D, Raz D (2020) Competitive analysis with a sample and the secretary problem. Proc. 2020 ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 2082–2095.Google Scholar
• Kesselheim T, Molinaro M (2020) Knapsack secretary with bursty adversary. 47th Internat. Colloquium Automata Languages Programming (ICALP 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 168 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 72:1–72:15.Google Scholar
• Kesselheim T, Radke K, Tönnis A, Vöcking B (2013) An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. Bodlaender HL, Italiano GF, eds. Algorithms - ESA 2013. ESA 2013, Lecture Notes in Computer Science, vol. 8125 (Springer, Berlin, Heidelberg).Google Scholar
• Kleinberg R (2005) A multiple-choice secretary algorithm with applications to online auctions. Proc. Sixteenth Annual ACM-SIAM Sympos. Discrete Algorithms (SODA ’05) (Society for Industrial and Applied Mathematics, Philadelphia), 630–631.Google Scholar
• Korula N, Pál M (2009) Algorithms for secretary problems on graphs and hypergraphs. Albers S, Marchetti-Spaccamela A, Matias Y, Nikoletseas S, Thomas W, eds. Automata, Languages and Programming. ICALP 2009, Lecture Notes in Computer Science, vol. 5556 (Springer, Berlin, Heidelberg).Google Scholar
• Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. (New Series) 83:745–747.Crossref, Google Scholar
• Krengel U, Sucheston L (1978) On semiamarts, amarts, and processes with finite value. Adv. Probability 4:197–266.Google Scholar
• Lindley DV (1961) Dynamic programming and decision theory. J. Roy. Statist. Soc. Ser. C Appl. Statist. 10:39–51.Google Scholar
• Lykouris T, Vassilvitskii S (2021) Competitive caching with machine learned advice. J. ACM 68(4):1–25.Crossref, Google Scholar
• Ma W, Simchi-Levi D, Zhao J (2021) Dynamic pricing (and assortment) under a static calendar. Management Sci. 67(4):2292–2313.Link, Google Scholar
• Ma T, Tang B, Wang Y (2016) The simulated greedy algorithm for several submodular matroid secretary problems. Theory Comput. Systems 58:681–706.Crossref, Google Scholar
• Mahdian M, Nazerzadeh H, Saberi A (2012) Online optimization with uncertain information. ACM Trans. Algorithms 8(1):1–29.Crossref, Google Scholar
• Moran S, Snir M, Manber U (1985) Applications of Ramsey’s theorem to decision tree complexity. J. ACM 32(4):938–949.Crossref, Google Scholar
• Nuti P (2022) The secretary problem with distributions. Integer Programming and Combinatorial Optimization, 23rd International Conference, IPCO 2022, Eindhoven, The Netherlands, June 27–29, 2022, Proceedings (Springer-Verlag, Berlin, Heidelberg), 429–439.Google Scholar
• Nuti P, Vondrák J (2023) Secretary problems: The power of a single sample. Proc. 2023 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 2015–2029.Google Scholar
• Rubinstein A, Wang JZ, Weinberg SM (2020) Optimal single-choice prophet inequalities from samples. 11th Innovations Theoret. Comput. Sci. Conf. (ITCS 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 151 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 60:1–60:10.Google Scholar
• Samuels S (1982) Exact solutions for the full information best choice problem. Technical report number 82-17, Department of Statistics, Purdue University, West Lafayette, IN.Google Scholar
• Samuels S (1991) Secretary problems. Ghosh B, Sen P, eds. Handbook of Sequential Analysis (CRC Press, Boca Raton, FL), 381–405.Google Scholar
• Seale DA, Rapoport A (1997) Sequential decision making with relative ranks: An experimental investigation of the “secretary problem”. Organ. Behav. Human Decision Processes 69(3):221–236.Crossref, Google Scholar
• Soto J, Turkieltaub A, Verdugo V (2021) Strong algorithms for the ordinal matroid secretary problem. Math. Oper. Res. 46(2):642–673.Link, Google Scholar
• Weitzman M (1979) Optimal search for the best alternative. Econometrica 47(3):641–654.Crossref, Google Scholar
• Zwick R, Rapoport A, King Chung Lo A, Muthukrishnan AV (2003) Consumer sequential search: Not enough or too much? Marketing Sci. 22(4):503–519.Link, Google Scholar