Prophet Secretary Against the Online Optimal

References

• [1] Agrawal S, Sethuraman J, Zhang X (2020) On optimal ordering in the optimal stopping problem. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 187–188.Google Scholar
• [2] Alaei S (2011) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. Proc. 52nd IEEE Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 512–521.Google Scholar
• [3] Anari N, Niazadeh R, Saberi A, Shameli A (2019) Nearly optimal pricing algorithms for production constrained and laminar Bayesian selection. Proc. 20th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 91–92.Google Scholar
• [4] Arsenis M, Drosis O, Kleinberg R (2021) Constrained-order prophet inequalities. Proc. 2021 ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2034–2046.Google Scholar
• [5] Azar Y, Chiplunkar A, Kaplan H (2018) Prophet secretary: Surpassing the 1-1/e barrier. Proc. 19th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 303–318.Google Scholar
• [6] Berger B, Ezra T, Feldman M, Fusco F (2023) Pandora’s problem with combinatorial cost. Proc. 24th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 273–292.Google Scholar
• [7] Beyhaghi H, Cai L (2022) Pandora’s problem with nonobligatory inspection: Optimal structure and a PTAS. Proc. 55th Annual ACM Sympos. Theory Comput. Conf. (Association for Computing Machinery, New York), 803–818.Google Scholar
• [8] Beyhaghi H, Kleinberg R (2019) Pandora’s problem with nonobligatory inspection. Proc. 20th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 131–132.Google Scholar
• [9] Boodaghians S, Fusco F, Lazos P, Leonardi S (2020) Pandora’s box problem with order constraints. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 439–458.Google Scholar
• [10] Braun A, Kesselheim T, Pollner T, Saberi A (2024) Approximating optimum online for capacitated resource allocation. Proc. 25th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 278. Google Scholar
• [11] Braverman M, Derakhshan M, Molina Lovett A (2022) Max-weight online stochastic matching: Improved approximations against the online benchmark. Proc. 23rd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 967–985.Google Scholar
• [12] Braverman M, Derakhshan M, Pollner T, Saberi A, Wajc D (2024) New philosopher inequalities for online Bayesian matching, via pivotal sampling. Proc. 36th ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 3029–3068.Google Scholar
• [13] Bubna A, Chiplunkar A (2022) Prophet inequality: Order selection beats random order. Proc 24th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 302–336.Google Scholar
• [14] Chakraborty T, Even-Dar E, Guha S, Mansour Y, Muthukrishnan S (2010) Approximation schemes for sequential posted pricing in multi-unit auctions. Saberi A, ed. Proc. Sixth Internat. Conf. Internet Network Econom. (Springer, Berlin), 158–169.Google Scholar
• [15] Chawla S, Gergatsouli E, McMahan J, Tzamos C (2023) Approximating Pandora’s box with correlations. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 2023 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 26:1–26:24.Google Scholar
• [16] 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
• [17] Chawla S, Gergatsouli E, Teng Y, Tzamos C, Zhang R (2020) Pandora’s box with correlations: Learning and approximation. Proc. 61st IEEE Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers Computer Society, Washington, DC), 1214–1225.Google Scholar
• [18] Chen L, Sun N, Tang ZG (2024) Setting targets is all you need: Improved order competitive ratio for online selection. Proc. 25th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 263–277.Google Scholar
• [19] Correa J, Cristi A (2023) A constant factor prophet inequality for online combinatorial auctions. Proc. 55th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 686–697.Google Scholar
• [20] Correa JR, Saona R, Ziliotto B (2019a) Prophet secretary through blind strategies. Proc. 30th ACM-SIAM Symposium Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1946–1961.Google Scholar
• [21] Correa JR, Dütting P, Fischer FA, Schewior K (2019b) Prophet inequalities for I.I.D. random variables from an unknown distribution. Proc. 20th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 3–17.Google Scholar
• [22] Correa JR, Foncea P, Pizarro D, Verdugo V (2019c) From pricing to prophets, and back! Oper. Res. Lett. 47(1):25–29.Crossref, Google Scholar
• [23] Correa JR, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2017) Posted price mechanisms for a random stream of customers. Proc. 18th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 169–186.Google Scholar
• [24] Correa JR, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2018) Recent developments in prophet inequalities. ACM SIGecom Exchanges 17(1):61–70.Crossref, Google Scholar
• [25] DeHaan I, Pashkovich K (2024) Matroid Bayesian online selection. Schäfer G, Ventre C, eds. International Symposium on Algorithmic Game Theory (Springer, Berlin), 405–422.Crossref, Google Scholar
• [26] Doval L (2018) Whether or not to open Pandora’s box. J. Econom. Theory 175:127–158. Crossref, Google Scholar
• [27] Dütting P, Kleinberg R (2015) Polymatroid prophet inequalities. Bansal N, Finocchi I, eds. Proc. 23rd Annual Eur. Sympos. Algorithms, Lecture Notes in Computer Science, vol. 9294 (Springer, Berlin), 437–449.Google Scholar
• [28] Dütting P, Kesselheim T, Lucier B (2020) An O(log log m) prophet inequality for subadditive combinatorial auctions. Proc. 61st IEEE Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers Computer Society, Washington, DC), 306–317.Google Scholar
• [29] Dütting P, Feldman M, Kesselheim T, Lucier B (2017) Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs. Proc. 58th IEEE Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers Computer Society, Washington, DC), 540–551.Google Scholar
• [30] 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
• [31] Esfandiari H, Hajiaghayi M, Liaghat V, Monemizadeh M (2015) Prophet secretary. Proc. 23rd Eur. Sympos. Algorithms (European Association for Theoretical Computer Science), 496–508.Google Scholar
• [32] Esfandiari H, HajiAghayi M, Lucier B, Mitzenmacher M (2019) Online Pandora’s boxes and bandits. Proc. AAAI Conf. Artificial Intelligence, vol. 33 (AAAI Press, Washington, DC), 1885–1892.Google Scholar
• [33] Ezra T, Feldman M, Tang ZG (2024) Choosing behind the veil: Tight bounds for identity-blind online algorithms. Proc. 25th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 136–158.Google Scholar
• [34] Ezra T, Feldman M, Gravin N, Tang ZG (2020) Online stochastic max-weight matching: Prophet inequality for vertex and edge arrival models. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 769–787.Google Scholar
• [35] Ezra T, Feldman M, Gravin N, Tang ZG (2023) Who is next in line? On the significance of knowing the arrival order in Bayesian online settings. Proc. 2023 Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 3759–3776.Google Scholar
• [36] Feldman M, Gravin N, Lucier B (2015) Combinatorial auctions via posted prices. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 123–135.Google Scholar
• [37] Feldman M, Svensson O, Zenklusen R (2016) Online contention resolution schemes. Proc. 27th ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1014–1033.Google Scholar
• [38] Fu H, Li J, Liu D (2022) Pandora box problem with nonobligatory inspection: Hardness and improved approximation algorithms. Proc. 55th Annual ACM Sympos. Theory Comput. Conf. (Association for Computing Machinery, New York), 789–802. Google Scholar
• [39] Fu H, Li J, Xu P (2018) A PTAS for a class of stochastic dynamic programs. Proc. 45th Internat. Colloquium Automata Languages Programming (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 56:1–56:14.Google Scholar
• [40] Giambartolomei G, Mallmann-Trenn F, Saona R (2023) Prophet inequalities: Separating random order from order selection. Preprint, submitted April 8, https://arxiv.org/abs/2304.04024.Google Scholar
• [41] Gravin N, Wang H (2019) Prophet inequality for bipartite matching: Merits of being simple and non adaptive. Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 93–109.Google Scholar
• [42] Guha S, Munagala K, Sarkar S (2008) Information acquisition and exploitation in multichannel wireless networks. Preprint, submitted April 10, https://arxiv.org/abs/0804.1724.Google Scholar
• [43] Hajiaghayi MT, Kleinberg RD, Sandholm T (2007) Automated online mechanism design and prophet inequalities. Proc. 22nd AAAI Conf. Artificial Intelligence (AAAI Press, Washington, DC), 58–65.Google Scholar
• [44] 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
• [45] Hill TP, Kertz RP (1992) A survey of prophet inequalities in optimal stopping theory. Contemp. Math. 125(1):191–207.Crossref, Google Scholar
• [46] Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. Proc. 44th Annual ACM Sympos. Theory Comput. Conf. (Association for Computing Machinery, New York), 123–136.Google Scholar
• [47] Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. 83(4):745–747.Crossref, Google Scholar
• [48] Krengel U, Sucheston L (1978) On semiamarts, amarts, and processes with finite value. Advances in Probability and Related Topics, vol. 4 (Marcel Dekker, Inc., New York), 197–266.Google Scholar
• [49] 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.Google Scholar
• [50] Lucier B (2017) An economic view of prophet inequalities. ACM SIGecom Exchanges 16(1):24–47.Crossref, Google Scholar
• [51] Naor J, Srinivasan A, Wajc D (2023) Online dependent rounding schemes. Proc. 36th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 3116–3154.Google Scholar
• [52] Niazadeh R, Saberi A, Shameli A (2018) Prophet inequalities vs. approximating optimum online. Proc. 14th Conf. Web Internet Econom. (Springer, Berlin), 356–374. Google Scholar
• [53] Papadimitriou C, Pollner T, Saberi A, Wajc D (2021) Online stochastic max-weight bipartite matching: Beyond prophet inequalities. Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 763–764.Google Scholar
• [54] Papadimitriou CH (1985) Games against nature. J. Comput. System Sci. 31(2):288–301.Crossref, Google Scholar
• [55] Peng B, Tang ZG (2022) Order selection prophet inequality: From threshold optimization to arrival time design. Proc. 63rd IEEE Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 171–178.Google Scholar
• [56] Saberi A, Wajc D (2021) The greedy algorithm is not optimal for on-line edge coloring. Proc. 48th Internat. Colloquium Automata Languages Programming (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 109:1–109:18.Google Scholar
• [57] 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
• [58] Segev D, Singla S (2021) Efficient approximation schemes for stochastic probing and prophet problems. Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 793–794.Google Scholar
• [59] Weitzman ML (1979) Optimal search for the best alternative. Econometrica 47(3):641–654.Crossref, Google Scholar