The I.I.D. Prophet Inequality with Limited Flexibility

References

• [1] Abolhassani M, Ehsani S, Esfandiari H, Hajiaghayi M, Kleinberg R, Lucier B (2017) Beating 1-1/e for ordered prophets. Proc. 49th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 61–71.Google Scholar
• [2] Adelman D (2007) Dynamic bid prices in revenue management. Oper. Res. 55(4):647–661.Link, Google Scholar
• [3] Agarwal D, Chen BC, Elango P (2009) Spatio-temporal models for estimating click-through rate. Proc. 18th Internat. Conf. World Wide Web (Association for Computing Machinery, New York), 21–30.Google Scholar
• [4] Alaei S (2014) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM J. Comput. 43(2):930–972.Crossref, Google Scholar
• [5] Alaei S, Makhdoumi A, Malekian A, Niazadeh R (2022) Descending price auctions with bounded number of price levels and batched prophet inequality. Proc. 23rd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 246–246.Google Scholar
• [6] Allaart PC (2007) Prophet inequalities for iid random variables with random arrival times. Sequential Anal. 26(4):403–413.Crossref, Google Scholar
• [7] Azar PD, Kleinberg R, Weinberg SM (2014) Prophet inequalities with limited information. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1358–1377.Google Scholar
• [8] Babaioff M, Immorlica N, Kempe D, Kleinberg R (2007) A knapsack secretary problem with applications. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (Springer, Berlin), 16–28.Crossref, Google Scholar
• [9] Baker W, Chopra M, Nee A, Sinha S (2019) Pricing: The next frontier of value creation in private equity. https://www.mckinsey.com/business-functions/growth-marketing-and-sales/our-insights/pricing-the-next-frontier-of-value-creation-in-private-equity.Google Scholar
• [10] 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
• [11] Bubna A, Chiplunkar A (2023) Prophet inequality: Order selection beats random order. Proc. 24th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 302–336.Google Scholar
• [12] Buchbinder N, Jain K, Singh M (2014) Secretary problems via linear programming. Math. Oper. Res. 39(1):190–206.Link, Google Scholar
• [13] Chan THH, 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 (Society for Industrial and Applied Mathematics, Philadelphia), 1169–1188.Google Scholar
• [14] Chawla S, Devanur N, Lykouris T (2024) Static pricing for multi-unit prophet inequalities. Oper. Res. 72(4):1388–1399.Link, Google Scholar
• [15] Chawla S, Hartline JD, Malec DL, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Proc. 42nd ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 311–320.Google Scholar
• [16] Correa J, Saona R, Ziliotto B (2021) Prophet secretary through blind strategies. Math. Programming 190(1):483–521.Crossref, Google Scholar
• [17] Correa J, Dütting P, Fischer F, Schewior K (2019) Prophet inequalities for iid random variables from an unknown distribution. Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 3–17.Google Scholar
• [18] Correa J, Foncea P, Pizarro D, Verdugo V (2019) From pricing to prophets, and back! Oper. Res. Lett. 47(1):25–29.Crossref, Google Scholar
• [19] 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
• [20] Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2021) Posted price mechanisms and optimal threshold strategies for random arrivals. Math. Oper. Res. 46(4):1452–1478.Link, Google Scholar
• [21] 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
• [22] 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
• [23] Ehsani S, Hajiaghayi M, Kesselheim T, Singla S (2018) Prophet secretary for combinatorial auctions and matroids. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 700–714.Google Scholar
• [24] Feldman M, Svensson O, Zenklusen R (2016) Online contention resolution schemes. Proc. 27th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1014–1033.Google Scholar
• [25] Folland GB (1999) Real Analysis: Modern Techniques and Their Applications, vol. 40 (John Wiley & Sons, Hoboken, NJ).Google Scholar
• [26] Garbarino E, Lee OF (2003) Dynamic pricing in internet retail: Effects on consumer trust. Psych. Marketing 20(6):495–513.Crossref, Google Scholar
• [27] Goyal V, Udwani R (2023) Online matching with stochastic rewards: Optimal competitive ratio via path-based formulation. Oper. Res. 71(2):563–580.Link, Google Scholar
• [28] Hajiaghayi MT, Kleinberg R, Sandholm T (2007) Automated online mechanism design and prophet inequalities. Proc. 22nd Natl. Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 58–65.Google Scholar
• [29] Hill TP, Kertz RP (1981) Ratio comparisons of supremum and stop rule expectations. Z Wahrscheinlichkeitstheorie Verw. Gebiete 56(2):283–285.Crossref, Google Scholar
• [30] 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
• [31] Hill TP, Kertz RP (1992) A survey of prophet inequalities in optimal stopping theory. Contemporary Math. 125(1):191–207.Crossref, Google Scholar
• [32] Iserles A (2009) A First Course in the Numerical Analysis of Differential Equations (Cambridge University Press, Cambridge, UK).Google Scholar
• [33] Jiang J, Ma W, Zhang J (2022) Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. Proc. 2022 Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1221–1246.Google Scholar
• [34] Jiang J, Ma W, Zhang J (2023) Tightness without counterexamples: A new approach and new results for prophet inequalities. Proc. 24th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 909–909.Google Scholar
• [35] Kannan PK, Kopalle PK (2001) Dynamic pricing on the internet: Importance and implications for consumer behavior. Internat. J. Electronic Commerce 5(3):63–83.Crossref, Google Scholar
• [36] 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
• [37] Kesselheim T, Tönnis A, Radke K, Vöcking B (2014) Primal beats dual on online packing LPs in the random-order model. Proc. 46th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 303–312.Google Scholar
• [38] Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. Proc. 44th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 123–136.Google Scholar
• [39] Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. 83(4):745–747.Crossref, Google Scholar
• [40] Lee E, Singla S (2018) Optimal online contention resolution schemes via ex-ante prophet inequalities. Proc. 26th Annual Eur. Sympos. Algorithms (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany).Google Scholar
• [41] Li B, Wu X, Wu Y (2022) Prophet inequality on i.i.d. distributions: Beating 1-1/e with a single query. Preprint, submitted May 11, https://arxiv.org/abs/2205.05519.Google Scholar
• [42] 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. (Association for Computing Machinery, New York), 692–692.Google Scholar
• [43] Lucier B (2017) An economic view of prophet inequalities. SIGecom Exchanges 16(1):24–47.Crossref, Google Scholar
• [44] Mehta A, Saberi A, Vazirani U, Vazirani V (2007) AdWords and generalized online matching. J. ACM 54(5):22–es.Crossref, Google Scholar
• [45] Peng B, Tang ZG (2022) Order selection prophet inequality: From threshold optimization to arrival time design. 2022 IEEE 63rd Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 171–178.Google Scholar
• [46] Perez-Salazar S, Singh M, Toriello A (2024) Robust online selection with uncertain offer acceptance. Math. Oper Res., ePub ahead of print August 29, https://doi.org/10.1287/moor.2023.0210.Link, Google Scholar
• [47] Phillips R (2012) Why are prices set the way they are? Ozer O, Phillips R, eds. The Oxford Handbook of Pricing Management (Oxford University Press, Oxford, UK), 13–44.Crossref, Google Scholar
• [48] Rotemberg JJ (2011) Fair pricing. J. Eur. Econom. Assoc. 9(5):952–981.Crossref, Google Scholar
• [49] Rubinstein A, Singla S (2017) Combinatorial prophet inequalities. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1671–1687.Google Scholar
• [50] Rubinstein A, Wang JZ, Weinberg SM (2020) Optimal single-choice prophet inequalities from samples. Vidick T, ed. Proc. 11th Innovations Theoretical Comput. Sci. Conf. (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 60:1–60:10.Google Scholar
• [51] 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
• [52] Talluri KT, Van Ryzin G (2004) The Theory and Practice of Revenue Management, vol. 1 (Springer, New York).Crossref, Google Scholar