{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T13:53:03Z","timestamp":1763041983722,"version":"3.45.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>In this article, we introduce an over-time variant of the well-known prophet inequality with i.i.d. random variables. Instead of stopping with one realized value at some point in the process, we decide for each step how long we select the value. Then we cannot select another value until this period is over. The goal is to maximize the expectation of the sum of selected values. We describe the structure of the optimal stopping rule and give upper and lower bounds on the prophet inequality. In online algorithms terminology, this corresponds to bounds on the competitive ratio of an online algorithm.<\/jats:p>\n                  <jats:p>\n                    We give a surprisingly simple algorithm with a single threshold that results in a prophet inequality of \u2248 0.396 for all input lengths\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    . Additionally, as our main result, we present a more advanced algorithm resulting in a prophet inequality of \u2248 0.598 when the number of steps tends to infinity. We complement our results by an upper bound that shows that the best possible prophet inequality is at most 1\/\u03c6 \u2248 0.618, where \u03c6 denotes the golden ratio.\n                  <\/jats:p>","DOI":"10.1145\/3766547","type":"journal-article","created":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T06:28:24Z","timestamp":1757140104000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Prophet Inequalities over Time"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5997-6636","authenticated-orcid":false,"given":"Andreas","family":"Abels","sequence":"first","affiliation":[{"name":"HHU D\u00fcsseldorf","place":["D\u00fcsseldorf, Germany"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8195-8226","authenticated-orcid":false,"given":"Elias","family":"Pitschmann","sequence":"additional","affiliation":[{"name":"University of Bremen","place":["Bremen, Germany"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7776-3426","authenticated-orcid":false,"given":"Daniel","family":"Schmand","sequence":"additional","affiliation":[{"name":"University of Bremen","place":["Bremen, Germany"]}]}],"member":"320","published-online":{"date-parts":[[2025,11,13]]},"reference":[{"key":"e_1_3_1_2_2","first-page":"311","volume-title":"Proceedings of the 42nd Symposium on Theory of Computing","author":"Chawla S.","year":"2010","unstructured":"S. Chawla, J. Hartline, D. Malec, and B. Sivan. 2010. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the 42nd Symposium on Theory of Computing. 311\u2013320."},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585151"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2023.1363"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.1167"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085137"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3670865.3673625"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2019.0993"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1323850"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","unstructured":"Paul D\u00fctting Thomas Kesselheim and Brendan Lucier. 2024. An \\(O(\\log \\log m)\\) Prophet inequality for subadditive combinatorial auctions.SIAM Journal on Computing 53 6 (2024) FOCS20-239-FOCS20-275. DOI:10.1137\/20M1382799","DOI":"10.1137\/20M1382799"},{"key":"e_1_3_1_11_2","first-page":"437","volume-title":"Proceedings of the 23rd Annual European Symposium on Algorithms","volume":"9294","author":"D\u00fctting P.","year":"2015","unstructured":"P. D\u00fctting and R. Kleinberg. 2015. Polymatroid prophet inequalities. In Proceedings of the 23rd Annual European Symposium on Algorithms, Vol. 9294. 437\u2013449."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1029394"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3530893"},{"key":"e_1_3_1_14_2","first-page":"123","volume-title":"Proceedings of the 26th Symposium on Discrete Algorithms","author":"Feldman M.","year":"2015","unstructured":"M. Feldman, N. Gravin, and B. Lucier. 2015. Combinatorial auctions via posted prices. In Proceedings of the 26th Symposium on Discrete Algorithms. 123\u2013135."},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3490486.3538320"},{"key":"e_1_3_1_16_2","first-page":"631","volume-title":"Proceedings of the 23rd Annual European Symposium on Algorithms","volume":"9294","author":"Fiat A.","year":"2015","unstructured":"A. Fiat, I. Gorelik, H. Kaplan, and S. Novgorodov. 2015. The temp secretary problem. In Proceedings of the 23rd Annual European Symposium on Algorithms, Vol. 9294. 631\u2013642."},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1966.10502008"},{"key":"e_1_3_1_18_2","first-page":"58","volume-title":"Proceedings of the 22nd AAAI Conference on Artificial Intelligence","author":"Hajiaghayi M.","year":"2007","unstructured":"M. Hajiaghayi, R. Kleinberg, and T. Sandholm. 2007. Automated online mechanism design and prophet inequalities. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence. 58\u201365."},{"issue":"2","key":"e_1_3_1_19_2","first-page":"336","article-title":"Comparisons of stop rule and supremum expectations of i.i.d. random variables","volume":"10","author":"Hill T. P.","year":"1982","unstructured":"T. P. Hill and R. P. Kertz. 1982. Comparisons of stop rule and supremum expectations of i.i.d. random variables. Annals of Probability 10, 2 (1982), 336\u2013345.","journal-title":"Annals of Probability"},{"issue":"1","key":"e_1_3_1_20_2","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0047-259X(86)90095-3","article-title":"Stop rule and supremum expectations of i.i.d. random variables: A complete comparison by conjugate duality","volume":"19","author":"Kertz R. P.","year":"1986","unstructured":"R. P. Kertz. 1986. Stop rule and supremum expectations of i.i.d. random variables: A complete comparison by conjugate duality. Journal of Multivariate Analysis 19, 1 (1986), 123\u2013136.","journal-title":"Journal of Multivariate Analysis"},{"key":"e_1_3_1_21_2","first-page":"54:1\u201354:17","volume-title":"Proceedings of the 24th Annual European Symposium on Algorithms","volume":"57","author":"Kesselheim T.","year":"2016","unstructured":"T. Kesselheim and A. T\u00f6nnis. 2016. Think eternally: Improved algorithms for the temp secretary problem and extensions. In Proceedings of the 24th Annual European Symposium on Algorithms, Vol. 57. 54:1\u201354:17."},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.11.002"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"e_1_3_1_24_2","first-page":"197","article-title":"On semiamarts, amarts, and processes with finite value","volume":"4","author":"Krengel U.","year":"1978","unstructured":"U. Krengel and L. Sucheston. 1978. On semiamarts, amarts, and processes with finite value. Advances in Applied Probability 4 (1978), 197\u2013266.","journal-title":"Advances in Applied Probability"},{"key":"e_1_3_1_25_2","volume-title":"Proceedings of the 20th Conference on Web and Internet Economics","author":"Perez-Salazar S.","year":"2024","unstructured":"S. Perez-Salazar and V. Verdugo. 2024. Optimal guarantees for online selection over time. In Proceedings of the 20th Conference on Web and Internet Economics."},{"issue":"4","key":"e_1_3_1_26_2","first-page":"1213","article-title":"Comparisons of threshold stop rule and maximum for independent nonnegative random variables","volume":"12","author":"Samuel-Cahn E.","year":"1983","unstructured":"E. Samuel-Cahn. 1983. Comparisons of threshold stop rule and maximum for independent nonnegative random variables. Annals of Probability 12, 4 (1983), 1213\u20131216.","journal-title":"Annals of Probability"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3766547","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T13:47:19Z","timestamp":1763041639000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3766547"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,13]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1145\/3766547"],"URL":"https:\/\/doi.org\/10.1145\/3766547","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2025,11,13]]},"assertion":[{"value":"2024-09-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-22","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}