{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T21:43:02Z","timestamp":1771623782972,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":26,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100020884","name":"Agencia Nacional de Investigación y Desarrollo","doi-asserted-by":"publisher","award":["ACT210005,FB210005"],"award-info":[{"award-number":["ACT210005,FB210005"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100019827","name":"Meta","doi-asserted-by":"publisher","award":["PhD Fellowship"],"award-info":[{"award-number":["PhD Fellowship"]}],"id":[{"id":"10.13039\/100019827","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100017637","name":"Simons Institute for the Theory of Computing, University of California Berkeley","doi-asserted-by":"publisher","award":[""],"award-info":[{"award-number":[""]}],"id":[{"id":"10.13039\/100017637","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585151","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"686-697","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["A Constant Factor Prophet Inequality for Online Combinatorial Auctions"],"prefix":"10.1145","author":[{"given":"Jos\u00e9","family":"Correa","sequence":"first","affiliation":[{"name":"University of Chile, Chile"}]},{"given":"Andr\u00e9s","family":"Cristi","sequence":"additional","affiliation":[{"name":"University of Chile, Chile"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.40"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00024"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.100"},{"key":"e_1_3_2_1_4_1","volume-title":"EC 2014.","author":"Babaiof M.","unstructured":"M. Babaiof , B. Lucier , N. Nisan , R. Paes Leme . On the eficiency of the walrasian mechanism . EC 2014. M. Babaiof, B. Lucier, N. Nisan, R. Paes Leme. On the eficiency of the walrasian mechanism. EC 2014."},{"key":"e_1_3_2_1_5_1","volume-title":"\u201cdemand types","author":"Baldwin E.","year":"2019","unstructured":"E. Baldwin , P. Klemperer . Understanding preferences: \u201cdemand types \u201d, and the existence of equilibrium with indivisibilities. Econometrica 87 ( 3 ): 867-932, 2019 . E. Baldwin, P. Klemperer. Understanding preferences:\u201cdemand types\u201d, and the existence of equilibrium with indivisibilities. Econometrica 87 ( 3 ): 867-932, 2019."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055465"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-06901-7_10"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109675"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060681"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897569"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"P. D\u00fctting T. Kesselheim B. Lucier. An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions. SIAM J. on Computing to appear (Preliminary version in FOCS 2020 ). \t\t\t\t  P. D\u00fctting T. Kesselheim B. Lucier. An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions. SIAM J. on Computing to appear (Preliminary version in FOCS 2020 ).","DOI":"10.1109\/FOCS46700.2020.00037"},{"key":"e_1_3_2_1_12_1","series-title":"SIAM J. on Computing, 49 ( 3 ): 540-582","volume-title":"Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs","author":"Dutting P.","year":"2020","unstructured":"P. Dutting , M. Feldman , T. Kesselheim , B. Lucier . Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs . SIAM J. on Computing, 49 ( 3 ): 540-582 , 2020 . P. Dutting, M. Feldman, T. Kesselheim, B. Lucier. Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs. SIAM J. on Computing, 49 ( 3 ): 540-582, 2020."},{"key":"e_1_3_2_1_13_1","volume-title":"SODA","author":"Ehsani S.","year":"2018","unstructured":"S. Ehsani , M. Hajiaghayi , T. Kesselheim , S. Singla Prophet secretary for combinatorial auctions and matroids . SODA 2018 . S. Ehsani, M. Hajiaghayi, T. Kesselheim, S. Singla Prophet secretary for combinatorial auctions and matroids. SODA 2018."},{"key":"e_1_3_2_1_14_1","volume-title":"EC 2020.","author":"Ezra T.","unstructured":"T. Ezra , M. Feldman , N. Gravin , Z. Tang . Online stochastic max-weight matching: prophet inequality for vertex and edge arrival models . EC 2020. T. Ezra, M. Feldman, N. Gravin, Z. Tang. Online stochastic max-weight matching: prophet inequality for vertex and edge arrival models. EC 2020."},{"key":"e_1_3_2_1_15_1","volume-title":"STOC","author":"Feldman M.","year":"2013","unstructured":"M. Feldman , H. Fu , N. Gravin , B. Lucier . Simultaneous Auctions are (almost) Eficient . STOC 2013 . M. Feldman, H. Fu, N. Gravin, B. Lucier. Simultaneous Auctions are (almost) Eficient. STOC 2013."},{"key":"e_1_3_2_1_16_1","series-title":"SIAM J. on Computing, 45 ( 1 ): 29-48","volume-title":"Combinatorial walrasian equilibrium","author":"Feldman M.","year":"2016","unstructured":"M. Feldman , N. Gravin , B. Lucier . Combinatorial walrasian equilibrium . SIAM J. on Computing, 45 ( 1 ): 29-48 , 2016 . M. Feldman, N. Gravin, B. Lucier. Combinatorial walrasian equilibrium. SIAM J. on Computing, 45 ( 1 ): 29-48, 2016."},{"key":"e_1_3_2_1_17_1","volume-title":"SODA","author":"Feldman M.","year":"2014","unstructured":"M. Feldman , N. Gravin , B. Lucier . Combinatorial Auctions via Posted Prices . SODA 2014 . M. Feldman, N. Gravin, B. Lucier. Combinatorial Auctions via Posted Prices. SODA 2014."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132523"},{"key":"e_1_3_2_1_19_1","volume-title":"EC 2019.","author":"Gravin N.","unstructured":"N. Gravin , H. Wang . Prophet inequality for bipartite matching: merits of being simple and non adaptive . EC 2019. N. Gravin, H. Wang. Prophet inequality for bipartite matching: merits of being simple and non adaptive. EC 2019."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213991"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"e_1_3_2_1_22_1","first-page":"197","volume":"4","author":"Krengel U.","year":"1978","unstructured":"U. Krengel , L. Sucheston . On semiamarts, amarts, and processes with finite value. Adv. in Probability 4 : 197 - 266 , 1978 . U. Krengel, L. Sucheston. On semiamarts, amarts, and processes with finite value. Adv. in Probability 4 : 197-266, 1978.","journal-title":"Adv. in Probability"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"R. Paes Leme S. Wong. Computing Walrasian equilibria: Fast algorithms and structural properties. Mathematical Programming 179 ( 1 ): 343-384 2020 \t\t\t\t  R. Paes Leme S. Wong. Computing Walrasian equilibria: Fast algorithms and structural properties. Mathematical Programming 179 ( 1 ): 343-384 2020","DOI":"10.1007\/s10107-018-1334-9"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.110"},{"key":"e_1_3_2_1_25_1","volume-title":"ITCS","author":"Rubinstein A.","year":"2020","unstructured":"A. Rubinstein , J.Z. Wang , S.M. Weinberg . Optimal Single-choice prophet inequalities from samples . ITCS 2020 . A. Rubinstein, J.Z. Wang, S.M. Weinberg. Optimal Single-choice prophet inequalities from samples. ITCS 2020."},{"key":"e_1_3_2_1_26_1","volume-title":"Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents. Journal of Computer and System Sciences 123 : 143-146","author":"Zhang H.","year":"2022","unstructured":"H. Zhang . Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents. Journal of Computer and System Sciences 123 : 143-146 , 2022 (Preliminary version in ESA 2020 ). H. Zhang. Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents. Journal of Computer and System Sciences 123 : 143-146, 2022 (Preliminary version in ESA 2020 )."}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585151","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:27Z","timestamp":1750295847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":26,"alternative-id":["10.1145\/3564246.3585151","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585151","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}