Tight Guarantees for Static Threshold Policies in the Prophet Secretary Problem

References

• Agrawal S, Sethuraman J, Zhang X (2020) On optimal ordering in the optimal stopping problem. Proc. 21st ACM Conf. on Econom. and Comput. (Association for Computing Machinery, New York), 187–188.Google Scholar
• Alaei S (2011) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. Proc. IEEE 52nd Annual Sympos. on Foundations of Comput. Sci. (IEEE, New York), 512–521.Google Scholar
• Alaei S (2014) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM J. Comput. 43(2):930–972.Crossref, Google Scholar
• Alaei S, Taghi Hajiaghayi M, Liaghat V (2012) Online prophet-inequality matching with applications to ad allocation. Proc. ACM Conf. on Econom. and Comput. (Association for Computing Machinery, New York), 18–35.Google Scholar
• Arlotto A, Gurvich I (2019) Uniformly bounded regret in the multisecretary problem. Stochastic Systems 9(3):231–260.Link, Google Scholar
• Arnosti N, Ma W (2022) Tight guarantees for static threshold policies in the prophet secretary problem. Proc. 23rd ACM Conf. Econom. Comput. (EC ‘22) (Association for Computing Machinery, New York), 242.Google Scholar
• Azar Y, Chiplunkar A, Kaplan H (2018) Prophet secretary: Surpassing the 1-1/e barrier. Procc. ACM Conf. on Econom. and Comput. (Association for Computing Machinery, New York), 303–318.Google Scholar
• Azar PD, Kleinberg R, Weinberg SM (2014) Prophet inequalities with limited information. Proc. 25th Annual ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 1358–1377.Google Scholar
• Babaioff M, Immorlica N, Kleinberg R (2007a) Matroids, secretary problems, and online mechanisms. Proc. Sympos. on Discrete Algorithms, 434–443.Google Scholar
• Babaioff M, Immorlica N, Kempe D, Kleinberg R (2007b) A knapsack secretary problem with applications. Approximation, randomization, and combinatorial optimization. Algorithms and Techniques (Springer, Berlin), 16–28.Google Scholar
• Beyhaghi H, Golrezaei N, Leme RP, Pál M, Sivan B (2021) Improved revenue bounds for posted-price and second-price mechanisms. Oper. Res. 69(6):1805–1822.Link, Google Scholar
• Bray R (2019) Does the multisecretary problem always have bounded regret? Preprint, submitted December 19, https://dx.doi.org/10.2139/ssrn.3497056.Google Scholar
• Cayley A (1875) Mathematical questions with their solutions. Edu. Times 23:18–19.Google Scholar
• Chawla S, Devanur NR, Lykouris T (2021) Static pricing for multi-unit prophet inequalities. Feldman M, Fu H, Talgam-Cohen I, eds. Proc. Web Internet Econom.—17th Internat. Conf, (WINE) 2021, Potsdam, Germany, (Springer, Berlin), 545–546.Google Scholar
• Cominetti R, Correa JR, Rothvoß T, Martín JS (2010) Optimal selection of customers for a last-minute offer. Oper. Res. 58(4-part-1):878–888.Google Scholar
• Correa J, Pizarro D, Verdugo V (2021a) Optimal revenue guarantees for pricing in large markets. Proc. Internat. Sympos. on Algorithmic Game Theory (Springer, Berlin), 221–235.Google Scholar
• Correa J, Saona R, Ziliotto B (2021b) Prophet secretary through blind strategies. Math. Programming 190(1):483–521.Crossref, Google Scholar
• Correa J, Dütting P, Fischer F, Schewior K (2019a) Prophet inequalities for iid random variables from an unknown distribution. Proc. ACM Conf. on Econom. and Comput. (Association for Computing Machinery, New York), 3–17.Google Scholar
• Correa J, Foncea P, Pizarro D, Verdugo V (2019b) From pricing to prophets, and back! Oper. Res. Lett. 47(1):25–29.Crossref, Google Scholar
• Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2017) Posted price mechanisms for a random stream of customers. Proc. ACM Conf. on Econom. and Comput. (Association for Computing Machinery, New York), 169–186.Google Scholar
• Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2018) Recent developments in prophet inequalities. ACM Sigecom Exchanges 17(1):61–70.Crossref, Google Scholar
• Dütting P, Fischer F, Klimm M (2016) Revenue gaps for static and dynamic posted pricing of homogeneous goods. Preprint, submitted July 24, https://arxiv.org/abs/1607.07105.Google Scholar
• Dutting 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
• Dynkin EB (1963) The optimum choice of the instant for stopping a Markov process. Soviet Math. 4:627–629.Google Scholar
• Ehsani S, Hajiaghayi M, Kesselheim T, Singla S (2018) Prophet secretary for combinatorial auctions and matroids. Proc. 29th Annual ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 700–714.Google Scholar
• Esfandiari H, Hajiaghayi M, Liaghat V, Monemizadeh M (2017) Prophet secretary. SIAM J. Discrete Math. 31(3):1685–1701.Crossref, Google Scholar
• Ezra T, Feldman M, Gravin N, Tang, ZG (2022a) General graphs are easier than bipartite graphs: Tight bounds for secretary matching. Proc. 23rd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 1148–1177.Google Scholar
• Ezra T, Feldman M, Gravin N, Tang ZG (2022b) Prophet matching with general arrivals. Math. Oper. Res. 47(2):878–898.Google Scholar
• Feldman M, Svensson O, Zenklusen R (2021) Online contention resolution schemes with applications to Bayesian selection problems. SIAM J. Comput. 50(2):255–300.Crossref, Google Scholar
• Ferguson TS (1989) Who solved the secretary problem? Statist. Sci. 4(3):282–289.Crossref, Google Scholar
• Gallego G, Li A, Truong VA, Wang X (2015) Online resource allocation with customer choice. Preprint, submitted November 5, https://arxiv.org/abs/1511.01837.Google Scholar
• Gilbert JP, Mosteller F (1966) Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61(313):35–73.Crossref, Google Scholar
• Hajiaghayi MT, Kleinberg R, Sandholm T (2007) Automated online mechanism design and prophet inequalities. Proc. 22nd National Conf. on Artificial Intelligence (AAAI, Palo Alto, CA), 58–65.Google Scholar
• Hill T (1983) Prophet inequalities and order selection in optimal stopping problems. Proc. Amer. Math. Soc. 88(1):131–137.Crossref, Google Scholar
• Hill TP, Hordijk A (1985) Selection of order of observation in optimal stopping problems. J. Appl. Probability 22(1):177–184.Crossref, Google Scholar
• Hill T, Kertz RP (1982) Comparisons of stop rule and supremum expectations of iid random variables. Ann. Probability 10(2):336–345.Crossref, Google Scholar
• Hill TP, Kertz RP (1992) A survey of prophet inequalities in optimal stopping theory. Contemporary Math. 125:191–207.Crossref, Google Scholar
• Hoeffding W (1956) On the distribution of the number of successes in independent trials. Ann. Math. Statist. 27:713–721.Crossref, Google Scholar
• Jiang J, Ma W, Zhang J (2022) Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. Proc. Annual ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 1221–1246.Google Scholar
• Kleinberg R (2005) A multiple-choice secretary algorithm with applications to online auctions. Proc. ACM Sympos. on Discrete Algorithms.Google Scholar
• Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. Proc. 44th Annual ACM Sympos. on Theory of Comput. (Association for Computing Machinery, New York), 123–136.Google Scholar
• Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. (New Ser.) 83(4):745–747.Crossref, Google Scholar
• Krengel U, Sucheston L (1978) On semiamarts, amarts, and processes with finite value. Probability Banach Spaces 4:197–266.Google Scholar
• Lee E, Singla S (2018) Optimal online contention resolution schemes via ex-ante prophet inequalities. Azar Y, Bast H, Herman G, eds. 26th Annual Eur. Sympos. Algorithms (ESA 2018), vol. 112, Leibniz International Proceedings in Informatics (LIPIcs) (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 57:1–57:14.Google Scholar
• Lieber R (2021) How to get the coronavirus vaccine in New York city. New York Times (March 22), https://www.nytimes.com/article/nyc-vaccine-shot.html.Google Scholar
• Lucier B (2017) An economic view of prophet inequalities. ACM SIGecom Exchanges 16(1):24–47.Crossref, Google Scholar
• Rubinstein A (2016) Beyond matroids: Secretary problem and prophet inequality with general constraints. Proc. 48th Annual ACM Sympos. on Theory of Comput. (Association for Computing Machinery, New York), 324–332.Google Scholar
• Rubinstein D (2021) After unused vaccines are thrown in trash, Cuomo loosens rules. New York Times (January 10), https://www.nytimes.com/2021/01/10/nyregion/new-york-vaccine-guidelines.html.Google Scholar
• Rubinstein A, Wang JZ, Weinberg SM (2020) Optimal single-choice prophet inequalities from samples. Proc. 11th Innovations in Theoretical Comput. Sci. Conf.Google Scholar
• Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 12(4):1213–1216.Google Scholar
• Yan Q (2011) Mechanism design via correlation gap. Proc. 22nd Annual ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 710–719.Google Scholar