{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T07:28:26Z","timestamp":1770276506430,"version":"3.49.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,5,27]],"date-time":"2020-05-27T00:00:00Z","timestamp":1590537600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007515","name":"National Science Foundation","doi-asserted-by":"publisher","award":["ECCS-1847393, DMS-1839346, CCF-1408784, CCF-1637397, IIS-1447554"],"award-info":[{"award-number":["ECCS-1847393, DMS-1839346, CCF-1408784, CCF-1637397, IIS-1447554"]}],"id":[{"id":"10.13039\/100007515","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010198","name":"Army Research Laboratory","doi-asserted-by":"publisher","award":["W911NF-17-1-0094"],"award-info":[{"award-number":["W911NF-17-1-0094"]}],"id":[{"id":"10.13039\/100010198","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007297","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-19-1-2268"],"award-info":[{"award-number":["N00014-19-1-2268"]}],"id":[{"id":"10.13039\/100007297","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2020,5,27]]},"abstract":"<jats:p>We consider the problem of selling perishable items to a stream of buyers in order to maximize social welfare. A seller starts with a set of identical items, and each arriving buyer wants any one item, and has a valuation drawn i.i.d. from a known distribution. Each item, however, disappears after an a priori unknown amount of time that we term the horizon for that item. The seller knows the (possibly different) distribution of the horizon for each item, but not its realization till the item actually disappears. As with the classic prophet inequalities, the goal is to design an online pricing scheme that competes with the prophet that knows the horizon and extracts full social surplus (or welfare). Our main results are for the setting where items have independent horizon distributions satisfying the monotone-hazard-rate (MHR) condition. Here, for any number of items, we achieve a constant-competitive bound via a conceptually simple policy that balances the rate at which buyers are accepted with the rate at which items are removed from the system. We implement this policy via a novel technique of matching via probabilistically simulating departures of the items at future times. Moreover, for a single item and MHR horizon distribution with mean, we show a tight result: There is a fixed pricing scheme that has competitive ratio at most 2 - 1\/\u03bc, and this is the best achievable in this class. We further show that our results are best possible. First, we show that the competitive ratio is unbounded without the MHR assumption even for one item. Further, even when the horizon distributions are i.i.d. MHR and the number of items becomes large, the competitive ratio of any policy is lower bounded by a constant greater than 1, which is in sharp contrast to the setting with identical deterministic horizons.<\/jats:p>","DOI":"10.1145\/3379470","type":"journal-article","created":{"date-parts":[[2020,5,28]],"date-time":"2020-05-28T04:29:21Z","timestamp":1590640161000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Predict and Match"],"prefix":"10.1145","volume":"4","author":[{"given":"Reza","family":"Alijani","sequence":"first","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siddhartha","family":"Banerjee","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sreenivas","family":"Gollapudi","sequence":"additional","affiliation":[{"name":"Google Research, San Francisco Bay Area, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kamesh","family":"Munagala","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kangning","family":"Wang","sequence":"additional","affiliation":[{"name":"Duke University, DURHAM, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,5,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055479"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/120878422"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229018"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219182"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9511-8"},{"key":"e_1_2_1_6_1","first-page":"311","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing","author":"Chawla S.","year":"2010","unstructured":"Chawla , S. , Hartline , J. D. , Malec , D. L. , and Sivan , B . Multi-parameter mechanism design and sequential posted pricing . In Proceedings of the 42nd ACM Symposium on Theory of Computing ( 2010 ), ACM, pp. 311 -- 320 . Chawla, S., Hartline, J. D., Malec, D. L., and Sivan, B. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the 42nd ACM Symposium on Theory of Computing (2010), ACM, pp. 311--320."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_23"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.118"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085137"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.56"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.46"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1029394"},{"key":"e_1_2_1_13_1","first-page":"123","volume-title":"Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Feldman M.","year":"2014","unstructured":"Feldman , M. , Gravin , N. , and Lucier , B . Combinatorial auctions via posted prices . In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms ( 2014 ), SIAM, pp. 123 -- 135 . Feldman, M., Gravin, N., and Lucier, B. Combinatorial auctions via posted prices. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (2014), SIAM, pp. 123--135."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250807"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1870103.1870106"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.48"},{"key":"e_1_2_1_17_1","first-page":"58","volume-title":"Proceedings of the 22nd AAAI Conference on Artificial Intelligence","author":"Hajiaghayi M. T.","year":"2007","unstructured":"Hajiaghayi , M. T. , Kleinberg , R. D. , and Sandholm , T . Automated online mechanism design and prophet inequalities . In Proceedings of the 22nd AAAI Conference on Artificial Intelligence ( 2007 ), pp. 58 -- 65 . Hajiaghayi, M. T., Kleinberg, R. D., and Sandholm, T. Automated online mechanism design and prophet inequalities. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (2007), pp. 58--65."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993861"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176990548"},{"key":"e_1_2_1_20_1","volume-title":"Prophet-type inequalities for multi-choice optimal stopping. Stochastic Processes and their Applications 24, 1","author":"Kennedy D.","year":"1987","unstructured":"Kennedy , D. Prophet-type inequalities for multi-choice optimal stopping. Stochastic Processes and their Applications 24, 1 ( 1987 ), 77--88. Kennedy, D. Prophet-type inequalities for multi-choice optimal stopping. Stochastic Processes and their Applications 24, 1 (1987), 77--88."},{"key":"e_1_2_1_21_1","volume-title":"Stop rule and supremum expectations of iid random variables: a complete comparison by conjugate duality. Journal of multivariate analysis 19, 1","author":"Kertz R. P.","year":"1986","unstructured":"Kertz , R. P. Stop rule and supremum expectations of iid random variables: a complete comparison by conjugate duality. Journal of multivariate analysis 19, 1 ( 1986 ), 88--112. Kertz, R. P. Stop rule and supremum expectations of iid random variables: a complete comparison by conjugate duality. Journal of multivariate analysis 19, 1 (1986), 88--112."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213991"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"e_1_2_1_24_1","volume-title":"On semiamarts, amarts, and processes with finite value. Probability on Banach spaces 4","author":"Krengel U.","year":"1978","unstructured":"Krengel , U. , and Sucheston , L . On semiamarts, amarts, and processes with finite value. Probability on Banach spaces 4 ( 1978 ), 197--266. Krengel, U., and Sucheston, L. On semiamarts, amarts, and processes with finite value. Probability on Banach spaces 4 (1978), 197--266."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.110"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993150"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1996.10476696"},{"key":"e_1_2_1_28_1","volume-title":"Prophet inequality with correlated arrival probabilities, with application to two sided matchings. arXiv preprint arXiv:1901.02552","author":"Truong V.-A.","year":"2019","unstructured":"Truong , V.-A. , and Wang , X . Prophet inequality with correlated arrival probabilities, with application to two sided matchings. arXiv preprint arXiv:1901.02552 ( 2019 ). Truong, V.-A., and Wang, X. Prophet inequality with correlated arrival probabilities, with application to two sided matchings. arXiv preprint arXiv:1901.02552 (2019)."}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3379470","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3379470","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3379470","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:22Z","timestamp":1750197742000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3379470"}},"subtitle":["Prophet Inequalities with Uncertain Supply"],"short-title":[],"issued":{"date-parts":[[2020,5,27]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,5,27]]}},"alternative-id":["10.1145\/3379470"],"URL":"https:\/\/doi.org\/10.1145\/3379470","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,27]]},"assertion":[{"value":"2020-05-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}