{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:34Z","timestamp":1787337574808,"version":"build-2736575974"},"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]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>A celebrated impossibility result by Myerson and Satterthwaite (1983) shows that any truthful mechanism for two-sided markets that maximizes social welfare must run a deficit, resulting in a necessity to relax welfare efficiency and the use of approximation mechanisms. Such mechanisms, in general, make extensive use of the Bayesian priors. In this work, we investigate a question of increasing theoretical and practical importance: how much prior information is required to design mechanisms with near-optimal approximations? Our first contribution is a more general impossibility result stating that no meaningful approximation is possible without any prior information, expanding the famous impossibility result of Myerson and Satterthwaite. Our second contribution is that one single sample (one number per item), arguably a minimum-possible amount of prior information, from each seller distribution is sufficient for a large class of two-sided markets. We prove matching upper and lower bounds on the best approximation that can be obtained with one single sample for subadditive buyers and additive sellers regardless of computational considerations. Our third contribution is the design of computationally efficient black box reductions that turn any one-sided mechanism into a two-sided mechanism with a small loss in the approximation, while using only one single sample from each seller. On the way, our black box-type mechanisms deliver several interesting positive results in their own right, often beating even the state of the art that uses full prior information.<\/jats:p>","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":1,"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":[{"vocabulary":"crossref","role":"author"}]},{"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":[{"vocabulary":"crossref","role":"author"}]},{"given":"Philip","family":"Lazos","sequence":"additional","affiliation":[{"name":"Independent Researcher, London, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefano","family":"Leonardi","sequence":"additional","affiliation":[{"name":"Department of Computer, Control, and Management Engineering, Sapienza University of Rome, Rome, Italy."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rebecca","family":"Reiffenh\u00e4user","sequence":"additional","affiliation":[{"name":"University of Amsterdam, Amsterdam, The Netherlands."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"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","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1518918","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:18:27Z","timestamp":1787336307000},"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]]}}}