Static Pricing for Multi-unit Prophet Inequalities

References

• Agrawal S, Devanur NR (2019) Bandits with global convex constraints and objective. Oper. Res. 67(5):1486–1502.Link, 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
• Arnosti N, Ma W (2022) Tight guarantees for static threshold policies in the prophet secretary problem. Oper. Res., ePub ahead of print December 29, https://doi.org/10.1287/opre.2022.2419.Google Scholar
• Babaioff M, Dughmi S, Kleinberg RD, Slivkins A (2015) Dynamic pricing with limited supply. ACM Trans. Econom. Comput. 3(1):4:1–4:26.Google Scholar
• Badanidiyuru A, Kleinberg R, Slivkins A (2018) Bandits with knapsacks. J. ACM 65(3):13.Crossref, Google Scholar
• Balseiro SR, Brown DB, Chen C (2021) Dynamic pricing of relocating resources in large networks. Management Sci. 67(7):4075–4094.Link, Google Scholar
• Banerjee S, Freund D, Lykouris T (2022) Pricing and optimization in shared vehicle systems: An approximation framework. Oper. Res. 70(3):1783–1805.Link, Google Scholar
• Chawla S, Miller JB, Teng Y (2019) Pricing for online resource allocation: Intervals and paths. Proc. Thirtieth Annual ACM-SIAM Sympos. Discrete Algorithms SODA 2019 (SIAM, Philadelphia), 1962–1981.Google Scholar
• Chawla S, Devanur NR, Holroyd AE, Karlin AR, Martin JB, Sivan B (2017) Stability of service under time-of-use pricing. Proc. 49th Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 184–197.Google Scholar
• Dütting P, Kleinberg R (2015) Polymatroid prophet inequalities. Algorithms—ESA 2015—23rd Annual Eur. Sympos. Proc. Lecture Notes Comput. Sci., vol. 9294 (Springer, Berlin, Heidelberg), 437–449.Google Scholar
• 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
• Feldman M, Gravin N, Lucier B (2014) Combinatorial auctions via posted prices. Proc. Twenty-Sixth Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 123–135.Google Scholar
• Hajiaghayi MT, Kleinberg R, Sandholm T (2007) Automated online mechanism design and prophet inequalities. Proc. 22nd National Conf. Artificial Intelligence AAAI’07, vol. 1 (AAAI Press, Palo Alto, CA), 58–65.Google Scholar
• Hamza K (1995) The smallest uniform upper bound on the distance between the mean and the median of the binomial and Poisson distributions. Statist. Probab. Lett. 23(1):21–25.Crossref, Google Scholar
• Hoeffding W (1956) On the distribution of the number of successes in independent trials. Ann. Math. Statist. 27(3):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. Discrete Algorithms (SODA) (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. Leyton-Brown K, Hartline JD, Samuelson L, eds. Proc. 24th ACM Conf. Econom. Comput. EC 2023 (ACM, New York), 909.Google Scholar
• Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. Proc. Forty-Fourth Annual ACM Sympos. Theory Comput. (ACM, New York), 123–136.Google Scholar
• Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. 83(4):745–747.Crossref, Google Scholar
• Lucier B (2017) An economic view of prophet inequalities. ACM SIGecom Exchanges 16(1):24–47.Crossref, Google Scholar
• Rubinstein A, Singla S (2017) Combinatorial prophet inequalities. Proc. Twenty-Eighth Annual ACM-SIAM Sympos. Discrete Algorithms SODA 2017 (SIAM, Philadelphia), 1671–1687.Google Scholar
• 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