Tightness Without Counterexamples: A New Approach and New Results for Prophet Inequalities

References

• [1] Adelman D (2007) Dynamic bid prices in revenue management. Oper. Res. 55(4):647–661.Link, Google Scholar
• [2] Alaei S (2014) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM J. Comput. 43(2):930–972.Crossref, Google Scholar
• [3] Alaei S, Hajiaghayi M, Liaghat V (2012) Online prophet-inequality matching with applications to ad allocation. Proc. 13th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 18–35.Google Scholar
• [4] Arlotto A, Gurvich I (2019) Uniformly bounded regret in the multisecretary problem. Stochastic Systems 9(3):231–260.Link, Google Scholar
• [5] Arnosti N, Ma W (2012) Tight guarantees for static threshold policies in the prophet secretary problem. Proc. 23rd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 242.Google Scholar
• [6] 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
• [7] Brustle J, Perez-Salazar S, Verdugo V (2024) Splitting guarantees for prophet inequalities via nonlinear systems. Preprint, submitted June 25, https://arxiv.org/abs/2406.17767.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] Chawla S, Devanur N, Lykouris T (2020) Static pricing for multi-unit prophet inequalities. Preprint, submitted July 15, https://arxiv.org/abs/2007.07990v1.Google Scholar
• [10] 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
• [11] Correa J, Saona R, Ziliotto B (2021) Prophet secretary through blind strategies. Math. Program. 190(1):483–521.Crossref, Google Scholar
• [12] 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. (Association for Computing Machinery, New York), 169–186.Google Scholar
• [13] Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2019) Recent developments in prophet inequalities. SIGecom Exchanges 17(1):61–70.Crossref, Google Scholar
• [14] De Farias DP, Van Roy B (2003) The linear programming approach to approximate dynamic programming. Oper. Res. 51(6):850–865.Link, Google Scholar
• [15] Duembgen L (2010) Bounding standard Gaussian tail probabilities. Preprint, submitted December 20, https://arxiv.org/abs/1012.2063.Google Scholar
• [16] Ehsani S, Hajiaghayi M, Kesselheim T, Singla S (2018) Prophet secretary for combinatorial auctions and matroids. Proc. Twenty-Ninth Annu. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 700–714.Google Scholar
• [17] Ezra T, Feldman M, Gravin N, Tang ZG (2022) Prophet matching with general arrivals. Math. Oper. Res. 47(2):878–898.Link, Google Scholar
• [18] 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
• [19] Fu H, Lu P, Tang ZG, Turkieltaub A, Wu H, Wu J, Zhang Q (2022) Oblivious online contention resolution schemes. Sympos. Simplicity Algorithms SOSA (SIAM, Philadelphia), 268–278.Google Scholar
• [20] Gallego G, Li A, Truong V-A, Wang X (2015) Online resource allocation with customer choice. Preprint, submitted November 5, https://arxiv.org/abs/1511.01837.Google Scholar
• [21] Hajiaghayi MT, Kleinberg R, Sandholm T (2007) Automated online mechanism design and prophet inequalities. AAAI’07 Proc. 22nd Natl. Conf. Artificial Intelligence, vol. 1 (AAAI Press, Cambridge, MA), 58–65.Google Scholar
• [22] Harremoës P (2016) Bounds on tail probabilities for negative binomial distributions. Kybernetika 52(6):943–966.Google Scholar
• [23] 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
• [24] Jiang J, Li X, Zhang J (2025) Online stochastic optimization with Wasserstein based nonstationarity. Management Sci., ePub ahead of print March 3, https://doi.org/10.1287/mnsc.2020.03850.Google Scholar
• [25] Jiang J, Ma W, Zhang J (2022) Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. Proc. 2022 Annu. ACM-SIAM Sympos. Discrete Algorithms SODA (SIAM, Philadelphia), 1221–1246.Google Scholar
• [26] Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. Proc. Forty-Fourth Annu. ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 123–136,Google Scholar
• [27] Krengel U, Sucheston L (1978) On semiamarts, amarts, and processes with finite value. Kuelbs J, ed. Probability on Banach Spaces, Advances in Probability and Related Topics, vol. 4 (Marcel Dekker, New York), 197–266.Google Scholar
• [28] Lee E, Singla S (2018) Optimal online contention resolution schemes via ex-ante prophet inequalities. Preprint, submitted June 25, https://arxiv.org/abs/1806.09251.Google Scholar
• [29] 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
• [30] Perez-Salazar S, Singh M, Toriello A (2022) The IID prophet inequality with limited flexibility. Preprint, submitted October 11, https://arxiv.org/abs/2210.05634v1.Google Scholar
• [31] 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
• [32] Shapiro A (2009) Semi-infinite programming, duality, discretization and optimality conditions. Optimization 58(2):133–161.Crossref, Google Scholar
• [33] Yan Q (2011) Mechanism design via correlation gap. Proc. Twenty-Second Annu. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 710–719.Google Scholar