Tight Guarantees for Multiunit Prophet Inequalities and Online Stochastic Knapsack

References

• Alaei S (2011) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. Proc. IEEE 52nd Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 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, MohammadTaghi H, Liaghat V (2012) Online prophet-inequality matching with applications to ad allocation. Proc. 13th ACM Conf. Electronic Commerce (ACM, New York), 18–35.Google Scholar
• Alaei S, MohammadTaghi H, Liaghat V (2013) The online stochastic generalized assignment problem. Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques (Springer, Berlin), 11–25.Google Scholar
• Alaei S, Makhdoumi A, Malekian A (2021) Revenue maximization under unknown private values with non-obligatory inspection. Proc. 22nd ACM Conf. Econom. Comput. (ACM, New York), 27–28.Google Scholar
• Alaei S, Makhdoumi A, Malekian A, Niazadeh R (2022) Descending price auctions with bounded number of price levels and batched prophet inequality. Preprint, submitted March 2, https://arxiv.org/abs/2203.01384.Google Scholar
• Arnosti N, Ma W (2023) Tight guarantees for static threshold policies in the prophet secretary problem. Oper. Res. 71(5):1777–1788.Link, 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
• Butcher JC, Goodwin N (2008) Numerical Methods for Ordinary Differential Equations, vol. 2 (Wiley Online Library, New York).Crossref, Google Scholar
• Chawla S, Devanur N, Lykouris T (2023) Static pricing for multi-unit prophet inequalities. Oper. Res., ePub ahead of print November 1, https://doi.org/10.1287/opre.2023.0031.Link, Google Scholar
• Chawla S, Hartline JD, Malec DL, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Proc. 42nd ACM Sympos. Theory Comput. (ACM, New York), 311–320.Google Scholar
• Chekuri C, Vondrák J, Zenklusen R (2014) Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43(6):1831–1879.Crossref, Google Scholar
• Chen X, Ma W, Simchi-Levi D, Xin L (2024) Assortment planning for recommendations at checkout under inventory constraints. Math. Oper. Res. 49(1):297–325.Link, Google Scholar
• Cominetti R, Correa J, Rothvoss T, San Martin J (2010) Optimal selection of customers for a last-minute offer. Oper. Res. 58(4-part-1):878–888.Link, Google Scholar
• Correa J, Saona R, Ziliotto B (2021) Prophet secretary through blind strategies. Math. Programming 190(1):483–521.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. Econom. Comput. (ACM, New York), 169–186.Google Scholar
• Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2019) Recent developments in prophet inequalities. ACM SIGecom Exchanges 17(1):61–70.Crossref, Google Scholar
• Dantzig GB, Thapa MN (2006) Linear Programming 2: Theory and Extensions (Springer Science & Business Media, Boston).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
• Esfandiari H, MohammadTaghi H, Liaghat V, Monemizadeh M (2017) Prophet secretary. SIAM J. Discrete Math. 31(3):1685–1701.Crossref, 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
• Feng Y, Niazadeh R, Saberi A (2022) Near-optimal Bayesian online assortment of reusable resources. Proc. 23rd ACM Conf. Econom. Comput. (ACM, New York), 964–965.Google Scholar
• Gallego G, Li A, Truong V-A, Wang X (2015) Online resource allocation with customer choice. Preprint, submitted November 25, https://arxiv.org/abs/1511.01837.Google Scholar
• Garey MR, Graham RL, Ullman JD (1972) Worst-case analysis of memory allocation algorithms. Proc. 4th Annual ACM Sympos. Theory Comput. (ACM, New York), 143–150.Google Scholar
• Goyal V, Iyengar G, Udwani R (2020) Asymptotically optimal competitive ratio for online allocation of reusable resources. Preprint, submitted February 6, https://arxiv.org/abs/2002.02430.Google Scholar
• Hajiaghayi MT, Kleinberg R, Sandholm T (2007) Automated Online Mechanism Design and Prophet Inequalities, vol. 7 (AAAI, Palo Alto, CA), 58–65.Google Scholar
• Han X, Kawase Y, Makino K (2015) Randomized algorithms for online knapsack problems. Theoretical Comput. Sci. 562:395–405.Crossref, Google Scholar
• Hill TP, Kertz RP (1982) Comparisons of stop rule and supremum expectations of iid random variables. Ann. Probability 10(2):336–345.Crossref, Google Scholar
• Jasin S, Sinha A (2015) An LP-based correlated rounding scheme for multi-item ecommerce order fulfillment. Oper. Res. 63(6):1336–1351.Link, 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. Discrete Algorithms (SIAM, Philadelphia), 1221–1246.Google Scholar
• Jiang J, Ma W, Zhang J (2023) Tightness without counterexamples: A new approach and new results for prophet inequalities. Proc. 24th ACM Conf. Electronic Commerce (ACM, New York), 909.Google Scholar
• Kleinberg R, Weinberg SM (2019) Matroid prophet inequalities and applications to multi-dimensional mechanism design. Games Econom. Behav. 113:97–115.Crossref, Google Scholar
• Kleywegt AJ, Papastavrou JD (1998) The dynamic and stochastic knapsack problem. Oper. Res. 46(1):17–35.Link, 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. Preprint, submitted June 25, https://arxiv.org/abs/1806.09251.Google Scholar
• Ma W, Simchi-Levi D, Zhao J (2019) The competitive ratio of threshold policies for online unit-density knapsack problems. Preprint, submitted July 20, https://arxiv.org/abs/1907.08735.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
• Papastavrou JD, Rajagopalan S, Kleywegt AJ (1996) The dynamic and stochastic knapsack problem with deadlines. Management Sci. 42(12):1706–1718.Link, Google Scholar
• Stein C, Truong V-A, Wang X (2020) Advance service reservations with heterogeneous customers. Management Sci. 66(7):2929–2950.Link, Google Scholar
• Wang X, Truong V-A, Bank D (2018) Online advance admission scheduling for services with customer preferences. Preprint, submitted May 26, https://arxiv.org/abs/1805.10412.Google Scholar
• Yan Q (2011) Mechanism design via correlation gap. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 710–719.Google Scholar