{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T23:10:22Z","timestamp":1769814622640,"version":"3.49.0"},"reference-count":53,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["788893"],"award-info":[{"award-number":["788893"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2026,2,28]]},"DOI":"10.1137\/22m1518918","type":"journal-article","created":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T12:15:03Z","timestamp":1769775303000},"page":"65-92","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Two-Sided Markets with Limited Information"],"prefix":"10.1137","volume":"55","author":[{"given":"Paul","family":"D\u00fctting","sequence":"first","affiliation":[{"name":"Google Research, Z\u00fcrich, Switzerland."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6250-945X","authenticated-orcid":true,"given":"Federico","family":"Fusco","sequence":"additional","affiliation":[{"name":"Department of Computer, Control, and Management Engineering, Sapienza University of Rome, Rome, Italy."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philip","family":"Lazos","sequence":"additional","affiliation":[{"name":"Independent Researcher, London, UK."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Leonardi","sequence":"additional","affiliation":[{"name":"Department of Computer, Control, and Management Engineering, Sapienza University of Rome, Rome, Italy."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rebecca","family":"Reiffenh\u00e4user","sequence":"additional","affiliation":[{"name":"University of Amsterdam, Amsterdam, The Netherlands."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"351","published-online":{"date-parts":[[2026,1,30]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"S. Assadi, T. Kesselheim, and S. Singla, Improved truthful mechanisms for subadditive combinatorial auctions: Breaking the logarithmic barrier, in Proceeding 32nd ACM-SIAM SODA, 2021, pp. 653\u2013661, https:\/\/doi.org\/10.1137\/1.9781611976465.40.","DOI":"10.1137\/1.9781611976465.40"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"S. Assadi and S. Singla, Improved truthful mechanisms for combinatorial auctions with submodular bidders, in Proceeding 60th IEEE FOCS, 2019, pp. 233\u2013248, https:\/\/doi.org\/10.1109\/FOCS.2019.00024.","DOI":"10.1109\/FOCS.2019.00024"},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"P. D. Azar, R. Kleinberg, and S. M. Weinberg, Prophet inequalities with limited information, in Proceeding 25th ACM-SIAM SODA, 2014, pp. 1358\u20131377, https:\/\/doi.org\/10.1137\/1.9781611973402.100.","DOI":"10.1137\/1.9781611973402.100"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2024.104231"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"M. Babaioff, Y. Cai, Y. A. Gonczarowski, and M. Zhao, The best of both worlds: Asymptotically efficient mechanisms with a guarantee on the expected gains-from-trade, in Proceeding 19th ACM EC, 2018, 373, https:\/\/doi.org\/10.1145\/3219166.3219203.","DOI":"10.1145\/3219166.3219203"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1316"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.dss.2004.08.008"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"S. R. Balseiro, V. S. Mirrokni, R. Paes Leme, and S. Zuo, Dynamic double auctions: Towards first best, in Proceeding 30th ACM-SIAM SODA, 2019, pp. 157\u2013172, https:\/\/doi.org\/10.1137\/1.9781611975482.11.","DOI":"10.1137\/1.9781611975482.11"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"L. Blumrosen and S. Dobzinski, Reallocation mechanisms, in Proceeding 15th ACM EC, 2014, 617, https:\/\/doi.org\/10.1145\/2600057.2602843.","DOI":"10.1145\/2600057.2602843"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2021.08.011"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"L. Blumrosen and Y. Mizrahi, Approximating gains-from-trade in bilateral trading, in Proceeding 12th WINE, 2016, pp. 400\u2013413, https:\/\/doi.org\/10.1007\/978-3-662-54110-4_28.","DOI":"10.1007\/978-3-662-54110-4_28"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"A. Braun and T. Kesselheim, Truthful mechanisms for two-sided markets via prophet inequalities, in Proceeding 21st ACM EC, 2021, pp. 202\u2013203, https:\/\/doi.org\/10.1145\/3465456.3467632.","DOI":"10.1145\/3465456.3467632"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"J. Brustle, Y. Cai, F. Wu, and M. Zhao, Approximating gains from trade in two-sided markets via simple mechanisms, in Proceeding 20th ACM EC, 2017, pp. 589\u2013590, https:\/\/doi.org\/10.1145\/3033274.3085148.","DOI":"10.1145\/3033274.3085148"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"Y. Cai and J. Wu, On the optimal fixed-price mechanism in bilateral trade, in Proceeding 55th STOC, 2023, pp. 737\u2013750, https:\/\/doi.org\/10.1145\/3564246.3585171.","DOI":"10.1145\/3564246.3585171"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"C. Caramanis, P. D\u00fctting, M. Faw, F. Fusco, P. Lazos, S. Leonardi, O. Papadigenopoulos, E. Pountourakis, and R. Reiffenh\u00e4user, Single-sample prophet inequalities via greedy-ordered selection, in Proceeding 33rd ACM-SIAM SODA, 2022, pp. 1298\u20131325, https:\/\/doi.org\/10.1137\/1.9781611977073.54.","DOI":"10.1137\/1.9781611977073.54"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2023.1351"},{"key":"ref17","first-page":"234:","volume":"25","author":"Cesa-Bianchi N.","year":"2024","journal-title":"J. Mach. Learn. Res."},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01726210"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"R. Cole and T. Roughgarden, The sample complexity of revenue maximization, in Proceeding 46th ACM-SIGACT STOC, 2014, pp. 243\u2013252, https:\/\/doi.org\/10.1145\/2591796.2591867.","DOI":"10.1145\/2591796.2591867"},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"R. Colini-Baldeschi, B. de Keijzer, S. Leonardi, and S. Turchetta, Approximately efficient double auctions with strong budget balance, in Proceeding 27th ACM-SIAM SODA, 2016, pp. 1424\u20131443, https:\/\/doi.org\/10.1137\/1.9781611974331.ch98.","DOI":"10.1137\/1.9781611974331.ch98"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"R. Colini-Baldeschi, P. W. Goldberg, B. de Keijzer, S. Leonardi, T. Roughgarden, and S. Turchetta, Approximately efficient two-sided combinatorial auctions, in Proceeding 18th ACM EC, 2017, pp. 591\u2013608, https:\/\/doi.org\/10.1145\/3033274.3085128.","DOI":"10.1145\/3033274.3085128"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"R. Colini-Baldeschi, P. W. Goldberg, B. de Keijzer, S. Leonardi, and S. Turchetta, Fixed price approximability of the optimal gain from trade, in Proceeding 13th WINE, 2017, pp. 146\u2013160, https:\/\/doi.org\/10.1007\/978-3-319-71924-5_11.","DOI":"10.1007\/978-3-319-71924-5_11"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"J. R. Correa, A. Cristi, B. Epstein, and J. A. Soto, The two-sided game of googol and sample-based prophet inequalities, in Proceeding 14th ACM-SIAM SODA, 2020, pp. 2066\u20132081, https:\/\/doi.org\/10.1137\/1.9781611975994.127.","DOI":"10.1137\/1.9781611975994.127"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"J. R. Correa, P. D\u00fctting, F. A. Fischer, and K. Schewior, Prophet inequalities for I.I.D. random variables from an unknown distribution, in Proceeding 20th ACM EC, 2019, pp. 3\u201317, https:\/\/doi.org\/10.1145\/3328526.3329627.","DOI":"10.1145\/3328526.3329627"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"Y. Deng, J. Mao, B. Sivan, and K. Wang, Approximately efficient bilateral trade, in Proceeding 54th ACM-SIGACT STOC, 2022, pp. 718\u2013721, https:\/\/doi.org\/10.1145\/3519935.3520054.","DOI":"10.1145\/3519935.3520054"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.03.011"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"S. Dobzinski, Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders, in Proceeding 48th STOC, ACM, 2016, pp. 940\u2013948, https:\/\/doi.org\/10.1145\/2897518.2897569.","DOI":"10.1145\/2897518.2897569"},{"key":"ref28","doi-asserted-by":"crossref","unstructured":"P. D\u00fctting, F. Fusco, P. Lazos, S. Leonardi, and R. Reiffenh\u00e4user, Efficient two-sided markets with limited information, in Proceeding 53rd ACM-SIGACT STOC, 2021, pp. 1452\u20131465, https:\/\/doi.org\/10.1145\/3406325.3451076.","DOI":"10.1145\/3406325.3451076"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2017.06.008"},{"key":"ref30","unstructured":"Y. Giannakopoulos, E. Koutsoupias, and P. Lazos, Online market intermediation, in Proceeding 44th ICALP, 2017, pp. 47:1\u201347:14, https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.47."},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"K. Goldner, M. Babaioff, and Y. A. Gonczarowski, Bulow-Klemperer-style results for welfare maximization in two-sided markets, in Proceeding 31st ACM-SIAM SODA, 2020, pp. 2452\u20132471, https:\/\/doi.org\/10.1137\/1.9781611975994.150.","DOI":"10.1137\/1.9781611975994.150"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"R. Gomes and V. S. Mirrokni, Optimal revenue-sharing double auctions with applications to ad exchanges, in Proceeding 23rd WWW, 2014, pp. 19\u201328, https:\/\/doi.org\/10.1145\/2566486.2568029.","DOI":"10.1145\/2566486.2568029"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"ref34","doi-asserted-by":"crossref","unstructured":"Z. Y. Kang, F. Pernice, and J. Vondr\u00e1k, Fixed-price approximations in bilateral trade, in Proceeding 33rd ACM-SIAM SODA, 2022, pp. 2964\u20132985, https:\/\/doi.org\/10.1137\/1.9781611977073.115.","DOI":"10.1137\/1.9781611977073.115"},{"key":"ref35","doi-asserted-by":"crossref","unstructured":"H. Kaplan, D. Naori, and D. Raz, Online weighted matching with a sample, in Proceeding 33rd ACM-SIAM SODA, 2022, pp. 1247\u20131272, https:\/\/doi.org\/10.1137\/1.9781611977073.52.","DOI":"10.1137\/1.9781611977073.52"},{"key":"ref36","unstructured":"R. D. Kleinberg, A multiple-choice secretary algorithm with applications to online auctions, in Proceeding 16th ACM-SIAM SODA, 2005, pp. 630\u2013631."},{"key":"ref37","doi-asserted-by":"crossref","unstructured":"E. Koutsoupias and P. Lazos, Online trading as a secretary problem, in Proceeding 11th SAGT, 2018, pp. 201\u2013212, https:\/\/doi.org\/10.1007\/978-3-319-99660-8_18.","DOI":"10.1007\/978-3-319-99660-8_18"},{"key":"ref38","doi-asserted-by":"crossref","unstructured":"Z. Liu, Z. Ren, and Z. Wang, Improved approximation ratios of fixed-price mechanisms in bilateral trades, in Proceeding 55th STOC, ACM, 2023, pp. 751\u2013760, https:\/\/doi.org\/10.1145\/3564246.3585160.","DOI":"10.1145\/3564246.3585160"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(92)90091-U"},{"key":"ref40","first-page":"1","volume":"1","author":"McAfee R. P.","year":"2008","journal-title":"Appl. Econ. Res. Bull."},{"key":"ref41","unstructured":"J. Morgenstern and T. Roughgarden, On the pseudo-dimension of nearly optimal auctions, in Proceeding NIPS, 2015, pp. 136\u2013144."},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2007.12.009"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(83)90048-0"},{"key":"ref44","doi-asserted-by":"crossref","unstructured":"R. Niazadeh, Y. Yuan, and R. D. Kleinberg, Simple and near-optimal mechanisms for market intermediation, in Proceeding 10th WINE, 2014, pp. 386\u2013399, https:\/\/doi.org\/10.1007\/978-3-319-13129-0_31.","DOI":"10.1007\/978-3-319-13129-0_31"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2004.10.007"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2017.10.016"},{"key":"ref47","doi-asserted-by":"crossref","unstructured":"R. Reiffenh\u00e4user, An optimal truthful mechanism for the online weighted bipartite matching problem, in Proceeding 30th ACM-SIAM SODA, 2019, pp. 1982\u20131993, https:\/\/doi.org\/10.1137\/1.9781611975482.120.","DOI":"10.1137\/1.9781611975482.120"},{"key":"ref48","doi-asserted-by":"crossref","unstructured":"A. Rubinstein, J. Z. Wang, and S. M. Weinberg, Optimal single-choice prophet inequalities from samples, in Proceeding 11th ITCS, 2020, pp. 60:1- 60:10, https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2020.60.","DOI":"10.1093\/af\/vfz046"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.2307\/2951506"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.2307\/2297496"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00355"},{"key":"ref52","doi-asserted-by":"crossref","unstructured":"E. Segal-Halevi, A. Hassidim, and Y. Aumann, SBBA: A strongly-budget-balanced double-auction mechanism, in Proceeding 9th SAGT, 9928 (2016), pp. 260\u2013272, https:\/\/doi.org\/10.1007\/978-3-662-53354-3_21.","DOI":"10.1007\/978-3-662-53354-3_21"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T12:15:06Z","timestamp":1769775306000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1518918"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,30]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2,28]]}},"alternative-id":["10.1137\/22M1518918"],"URL":"https:\/\/doi.org\/10.1137\/22m1518918","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,30]]}}}