{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:58Z","timestamp":1781077738596,"version":"3.54.1"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,2,29]],"date-time":"2020-02-29T00:00:00Z","timestamp":1582934400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"MIUR PRIN project ALGADIMAR \u201cAlgorithms, Games, and Digital Markets\u201d"},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1524062"],"award-info":[{"award-number":["CCF-1524062"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ERC","award":["788893"],"award-info":[{"award-number":["788893"]}]},{"name":"Google Focused Award on \u201cAlgorithms for Large-scale Data Analysis\u201d"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2020,2,29]]},"abstract":"<jats:p>We develop and extend a line of recent work on the design of mechanisms for two-sided markets. The markets we consider consist of buyers and sellers of a number of items, and the aim of a mechanism is to improve the social welfare by arranging purchases and sales of the items. A mechanism is given prior distributions on the agents\u2019 valuations of the items, but not the actual valuations; thus, the aim is to maximise the expected social welfare over these distributions. As in previous work, we are interested in the worst-case ratio between the social welfare achieved by a truthful mechanism and the best social welfare possible.<\/jats:p>\n          <jats:p>\n            Our main result is an incentive compatible and budget balanced constant-factor approximation mechanism in a setting where buyers have XOS valuations and sellers\u2019 valuations are additive. This is the first such approximation mechanism for a two-sided market setting where the agents have combinatorial valuation functions. To achieve this result, we introduce a more general kind of demand query that seems to be needed in this situation. In the simpler case that sellers have unit supply (each having just one item to sell), we give a new mechanism whose welfare guarantee improves on a recent one in the literature. We also introduce a more demanding version of the\n            <jats:italic>strong budget balance<\/jats:italic>\n            (SBB) criterion, aimed at ruling out certain \u201cunnatural\u201d transactions satisfied by SBB. We show that the stronger version is satisfied by our mechanisms.\n          <\/jats:p>","DOI":"10.1145\/3381523","type":"journal-article","created":{"date-parts":[[2020,3,11]],"date-time":"2020-03-11T08:34:33Z","timestamp":1583915673000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Approximately Efficient Two-Sided Combinatorial Auctions"],"prefix":"10.1145","volume":"8","author":[{"given":"Riccardo","family":"Colini-Baldeschi","sequence":"first","affiliation":[{"name":"Facebook Core Data Science, London, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul W.","family":"Goldberg","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bart de","family":"Keijzer","sequence":"additional","affiliation":[{"name":"University of Essex, Amsterdam, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefano","family":"Leonardi","sequence":"additional","affiliation":[{"name":"Sapienza, University of Rome, Roma, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tim","family":"Roughgarden","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefano","family":"Turchetta","sequence":"additional","affiliation":[{"name":"NTT Data and University of Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,3,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219203"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219203"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.07.005"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602843"},{"key":"e_1_2_1_5_1","unstructured":"Liad Blumrosen and Shahar Dobzinski. 2016. (Almost) efficient mechanisms for bilateral trading. ArXiv\/CoRR abs\/1604.04876 (2016).  Liad Blumrosen and Shahar Dobzinski. 2016. (Almost) efficient mechanisms for bilateral trading. ArXiv\/CoRR abs\/1604.04876 (2016)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386801"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54110-4_28"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085148"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC\u201910)","author":"Chawla Shuchi","year":"2010","unstructured":"Shuchi Chawla , Jason D. Hartline , David L. Malec , and Balasubramanian Sivan . 2010 . Multi-parameter mechanism design and sequential posted pricing . In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC\u201910) . ACM, 311--320. Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. 2010. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC\u201910). ACM, 311--320."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01726210"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-71924-5_11"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch98"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.04.013"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 10th Annual European Symposium on Algorithms (ESA\u201902)","author":"Deshmukh Kaustubh","unstructured":"Kaustubh Deshmukh , Andrew V. Goldberg , Jason D. Hartline , and Anna R. Karlin . 2002. Truthful and competitive double auctions . In Proceedings of the 10th Annual European Symposium on Algorithms (ESA\u201902) . Springer, 361--373. Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline, and Anna R. Karlin. 2002. Truthful and competitive double auctions. In Proceedings of the 10th Annual European Symposium on Algorithms (ESA\u201902). Springer, 361--373."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0436"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_37"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602854"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_40"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722139"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(89)90128-2"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC). ACM, 123--136","author":"Kleinberg Robert","unstructured":"Robert Kleinberg and Seth M. Weinberg . 2012. Matroid prophet inequalities . In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC). ACM, 123--136 . Robert Kleinberg and Seth M. Weinberg. 2012. Matroid prophet inequalities. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC). ACM, 123--136."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622698.1622700"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(92)90091-U"},{"key":"e_1_2_1_25_1","first-page":"1","article-title":"The gains from trade under fixed price mechanisms","volume":"1","author":"McAfee R. Preston","year":"2008","unstructured":"R. Preston McAfee . 2008 . The gains from trade under fixed price mechanisms . Appl. Econ. Res. Bull. 1 , 1 (2008), 1 -- 10 . R. Preston McAfee. 2008. The gains from trade under fixed price mechanisms. Appl. Econ. Res. Bull. 1, 1 (2008), 1--10.","journal-title":"Appl. Econ. Res. Bull."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(83)90048-0"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.2307\/2951506"},{"key":"e_1_2_1_29_1","volume-title":"Sequences of Take-It-or-Leave-It Offers: Near-Optimal Auctions Without Full Valuation Revelation","author":"Sandholm Tuomas","unstructured":"Tuomas Sandholm and Andrew Gilpin . 2004. Sequences of Take-It-or-Leave-It Offers: Near-Optimal Auctions Without Full Valuation Revelation . Springer , 73--91. Tuomas Sandholm and Andrew Gilpin. 2004. Sequences of Take-It-or-Leave-It Offers: Near-Optimal Auctions Without Full Valuation Revelation. Springer, 73--91."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.2307\/2297496"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00355"},{"key":"e_1_2_1_32_1","volume-title":"A random-sampling double-auction mechanism. CoRR abs\/1604.06210","author":"Segal-Halevi Erel","year":"2016","unstructured":"Erel Segal-Halevi , Avinatan Hassidim , and Yonatan Aumann . 2016. A random-sampling double-auction mechanism. CoRR abs\/1604.06210 ( 2016 ). Erel Segal-Halevi, Avinatan Hassidim, and Yonatan Aumann. 2016. A random-sampling double-auction mechanism. CoRR abs\/1604.06210 (2016)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53354-3_21"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381523","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3381523","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3381523","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:07Z","timestamp":1750199587000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381523"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,29]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,2,29]]}},"alternative-id":["10.1145\/3381523"],"URL":"https:\/\/doi.org\/10.1145\/3381523","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,29]]},"assertion":[{"value":"2017-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-03-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}