{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T05:49:55Z","timestamp":1792734595265,"version":"4.5.0"},"reference-count":46,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["337122"],"award-info":[{"award-number":["337122"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["317\/17"],"award-info":[{"award-number":["317\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>We present a general framework for stochastic online maximization problems with combinatorial feasibility constraints. The framework establishes prophet inequalities by constructing price-based online approximation algorithms, a natural extension of threshold algorithms for settings beyond binary selection. Our analysis takes the form of an extension theorem: we derive sufficient conditions on prices when all weights are known in advance, then prove that the resulting approximation guarantees extend directly to stochastic settings. Our framework unifies and simplifies much of the existing literature on prophet inequalities and posted price mechanisms and is used to derive new and improved results for combinatorial markets (with and without complements), multidimensional matroids, and sparse packing problems. Finally, we highlight a surprising connection between the smoothness framework for bounding the price of anarchy of mechanisms and our framework, and show that many smooth mechanisms can be recast as posted price mechanisms with comparable performance guarantees.<\/jats:p>","DOI":"10.1137\/20m1323850","type":"journal-article","created":{"date-parts":[[2020,6,2]],"date-time":"2020-06-02T11:48:57Z","timestamp":1591098537000},"page":"540-582","source":"Crossref","is-referenced-by-count":68,"title":["Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs"],"prefix":"10.1137","volume":"49","author":[{"given":"Paul","family":"D\u00fctting","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michal","family":"Feldman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Kesselheim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Brendan","family":"Lucier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,6,2]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"M. Abolhassani, S. Ehsani, H. Esfandiari, M. T. Hajiaghayi, R. Kleinberg, and B. Lucier,\n                      Beating 1-1\/e for ordered prophets\n                      , in Proceedings of the 49th ACM Symposium on Theory of Computing, 2017, pp. 61-71.","DOI":"10.1145\/3055399.3055479"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"I. Abraham, M. Babaioff, S. Dughmi, and T. Roughgarden,\n                      Combinatorial auctions with restricted complements\n                      , in Proceedings of the 13th ACM Conference on Electronic Commerce, 2012, pp. 3-16.","DOI":"10.1145\/2229012.2229016"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/120878422"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"S. Alaei, M. Hajiaghayi, and V. Liaghat,\n                      Online prophet-inequality matching with applications to ad allocation\n                      , in Proceedings of the 13th ACM Conference on Electronic Commerce, 2012, pp. 18-35.","DOI":"10.1145\/2229012.2229018"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"S. Alaei, M. Hajiaghayi, and V. Liaghat,\n                      The online stochastic generalized assignment problem\n                      , in Proceedings of the 16th\/17th APPROX-RANDOM Workshop, 2013, pp. 11-25.","DOI":"10.1007\/978-3-642-40328-6_2"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"S. Alaei, J. D. Hartline, R. Niazadeh, E. Pountourakis, and Y. Yuan,\n                      Optimal auctions vs. anonymous pricing\n                      , in Proceedings of the 56th IEEE Symposium on Foundations of Computer Science, 2015, pp. 1446-1463.","DOI":"10.1109\/FOCS.2015.92"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"P. D. Azar, R. Kleinberg, and S. M. Weinberg,\n                      Prophet inequalities with limited information\n                      , in Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms, 2014, pp. 1358-1377.","DOI":"10.1137\/1.9781611973402.100"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"M. Balcan, A. Blum, and Y. Mansour,\n                      Item pricing for revenue maximization\n                      , in Proceedings of the 9th ACM Conference on Electronic Commerce, 2008, pp. 50-59.","DOI":"10.1145\/1386790.1386802"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"K. Bhawalkar and T. Roughgarden,\n                      Welfare guarantees for combinatorial auctions with item bidding\n                      , in Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms, 2011, pp. 700-709.","DOI":"10.1137\/1.9781611973082.55"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"Y. Cai and M. Zhao,\n                      Simple mechanisms for subadditive buyers via duality\n                      , in Proceedings of the 49th ACM Symposium on Theory of Computing, 2017, pp. 170-183.","DOI":"10.1145\/3055399.3055465"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"T. Chakraborty, Z. Huang, and S. Khanna,\n                      Dynamic and non-uniform pricing strategies for revenue maximization\n                      , in Proceedings of the 50th IEEE Symposium on Foundations of Computer Science, 2009, pp. 495-504.","DOI":"10.1109\/FOCS.2009.43"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"S. Chawla, J. D. Hartline, and R. D. Kleinberg,\n                      Algorithmic pricing via virtual valuations\n                      , in Proceedings of the 8th ACM Conference on Electronic Commerce, 2007, pp. 243-251.","DOI":"10.1145\/1250910.1250946"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"S. Chawla, J. D. Hartline, D. L. Malec, and B. Sivan,\n                      Multi-parameter mechanism design and sequential posted pricing\n                      , in Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010, pp. 311-320.","DOI":"10.1145\/1806689.1806733"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1145\/2835172"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"I. R. Cohen, A. Eden, A. Fiat, and L. Jez,\n                      Pricing online decisions: Beyond auctions\n                      , in Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms, 2015, pp. 73-91.","DOI":"10.1137\/1.9781611973730.7"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"V. Cohen-Addad, A. Eden, M. Feldman, and A. Fiat,\n                      The invisible hand of dynamic market pricing\n                      , in Proceedings of the 17th ACM Conference on Economics and Computation, 2016, pp. 383-400.","DOI":"10.1145\/2940716.2940730"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"C. Daskalakis and V. Syrgkanis,\n                      Learning in auctions: Regret is hard, envy is easy\n                      , in Proceedings of the 57th IEEE Symposium on Foundations of Computer Science, 2016, pp. 219-228.","DOI":"10.1109\/FOCS.2016.31"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"S. Dobzinski,\n                      Two randomized mechanisms for combinatorial auctions\n                      , in Proceedings of the 10th\/11th APPROX-RANDOM Workshop, 2007, pp. 89-103.","DOI":"10.1007\/978-3-540-74208-1_7"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"S. Dobzinski, N. Nisan, and M. Schapira,\n                      Truthful randomized mechanisms for combinatorial auctions\n                      , in Proceedings of the 38th ACM Symposium on Theory of Computing, 2006, pp. 644-652.","DOI":"10.1145\/1132516.1132607"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"P. D\u00fctting and T. Kesselheim,\n                      Algorithms against anarchy: Understanding non-truthful mechanisms\n                      , in Proceedings of the 16th ACM Conference on Economics and Computation, 2015, pp. 239-255.","DOI":"10.1145\/2764468.2764507"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"P. D\u00fctting and R. Kleinberg,\n                      Polymatroid prophet inequalities\n                      , in Proceedings of the 23rd European Symposium on Algorithms, 2015, pp. 437-449.","DOI":"10.1007\/978-3-662-48350-3_37"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"U. Feige, M. Feldman, N. Immorlica, R. Izsak, B. Lucier, and V. Syrgkanis,\n                      A unifying hierarchy of valuations with complements and substitutes\n                      , in Proceedings of the 29th AAAI Conference on Artificial Intelligence, 2015, pp. 872-878.","DOI":"10.1609\/aaai.v29i1.9314"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"M. Feldman, A. Fiat, and A. Roytman,\n                      Makespan minimization via posted prices\n                      , in Proceedings of the 18th ACM Conference on Economics and Computation, 2017, pp. 405-422.","DOI":"10.1145\/3033274.3085129"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"M. Feldman, H. Fu, N. Gravin, and B. Lucier,\n                      Simultaneous auctions are (almost) efficient\n                      , in Proceedings of the 45th ACM Symposium on Theory of Computing, 2013, pp. 201-210.","DOI":"10.1145\/2488608.2488634"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"M. Feldman, N. Gravin, and B. Lucier,\n                      Combinatorial auctions via posted prices\n                      , in Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms, 2015, pp. 123-135.","DOI":"10.1137\/1.9781611973730.10"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"M. Feldman, N. Immorlica, B. Lucier, T. Roughgarden, and V. Syrgkanis,\n                      The price of anarchy in large games\n                      , in Proceedings of the 48th ACM Symposium on Theory of Computing, 2016, pp. 963-976.","DOI":"10.1145\/2897518.2897580"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"M. Feldman, O. Svensson, and R. Zenklusen,\n                      A simple o(log log(rank))-competitive algorithm for the matroid secretary problem\n                      , in Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms, 2015, pp. 1189-1201.","DOI":"10.1137\/1.9781611973730.79"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"M. Feldman, O. Svensson, and R. Zenklusen,\n                      Online contention resolution schemes\n                      , in Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms, 2016, pp. 1014-1033.","DOI":"10.1137\/1.9781611974331.ch72"},{"key":"atypb29","unstructured":"M. Hajiaghayi, R. Kleinberg, and T. W. Sandholm,\n                      Automated mechanism design and prophet inequalities\n                      , in Proceedings of the 22nd AAAI Conference on Artificial Intelligence, 2007, pp. 58-65."},{"key":"atypb30","unstructured":"M. Hardt, B. Recht, and Y. Singer,\n                      Train faster, generalize better: Stability of stochastic gradient descent\n                      , in Proceedings of the 33rd International Conference on Machine Learning, 2016, pp. 1225-1234."},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"J. D. Hartline, D. Hoy, and S. Taggart,\n                      Price of anarchy for auction revenue\n                      , in Proceedings of the 15th ACM Conference on Economics and Computation, 2014, pp. 693-710.","DOI":"10.1145\/2600057.2602878"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321909"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"R. Kleinberg and S. M. Weinberg,\n                      Matroid prophet inequalities\n                      , in Proceedings of the 44th ACM Symposium on Theory of Computing, 2012, pp. 123-136.","DOI":"10.1145\/2213977.2213991"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"atypb35","first-page":"197","volume":"4","author":"Krengel U.","year":"1978","journal-title":"Adv. Probab. Relat. Topics"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0463"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"B. Lucier and A. Borodin,\n                      Price of anarchy for greedy auctions\n                      , in Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms, 2010, pp. 537-553.","DOI":"10.1137\/1.9781611973075.46"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"B. Lucier and V. Syrgkanis,\n                      Greedy algorithms make efficient mechanisms\n                      , in Proceedings of the 16th ACM Conference on Economics and Computation, 2015, pp. 221-238.","DOI":"10.1145\/2764468.2764506"},{"key":"atypb40","doi-asserted-by":"crossref","unstructured":"T. Lykouris, V. Syrgkanis, and \u00c9. Tardos,\n                      Learning and efficiency in games with dynamic population\n                      , in Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms, 2016, pp. 120-129.","DOI":"10.1137\/1.9781611974331.ch9"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1145\/2806883"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"A. Rubinstein,\n                      Beyond matroids: Secretary problem and prophet inequality with general constraints\n                      , in Proceedings of the 48th ACM Symposium on Theory of Computing, 2016. 324-332.","DOI":"10.1145\/2897518.2897540"},{"key":"atypb43","doi-asserted-by":"crossref","unstructured":"A. Rubinstein and S. Singla,\n                      Combinatorial prophet inequalities\n                      , in Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 1671-1687.","DOI":"10.1137\/1.9781611974782.110"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993150"},{"key":"atypb45","doi-asserted-by":"crossref","unstructured":"V. Syrgkanis and \u00c9. Tardos,\n                      Composable and efficient mechanisms\n                      , in Proceedings of the 45th ACM Symposium on Theory of Computing, 2013, pp. 211-220.","DOI":"10.1145\/2488608.2488635"},{"key":"atypb46","doi-asserted-by":"crossref","unstructured":"L. Trevisan,\n                      Non-approximability results for optimization problems on bounded degree instances\n                      , in Proceedings of the 33rd ACM Symposium on Theory of Computing, 2001, pp. 453-461.","DOI":"10.1145\/380752.380839"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1323850","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:40:46Z","timestamp":1787337646000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1323850"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":46,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/20M1323850"],"URL":"https:\/\/doi.org\/10.1137\/20m1323850","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}