{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:30:06Z","timestamp":1750221006261,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,3,26]],"date-time":"2019-03-26T00:00:00Z","timestamp":1553558400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006754","name":"Army Research Laboratory","doi-asserted-by":"publisher","award":["W911NF-17-1-0094"],"award-info":[{"award-number":["W911NF-17-1-0094"]}],"id":[{"id":"10.13039\/100006754","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1839346, CCF-1408784, CCF-1637397, IIS-1447554"],"award-info":[{"award-number":["DMS-1839346, CCF-1408784, CCF-1637397, IIS-1447554"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2019,3,26]]},"abstract":"<jats:p>A core tension in the operations of online marketplaces is between segmentation (wherein platforms can increase revenue by segmenting the market into ever smaller sub-markets) and thickness (wherein the size of the sub-market affects the utility experienced by an agent). An important example of this is in dynamic online marketplaces, where buyers and sellers, in addition to preferences for different matches, also have finite patience (or deadlines) for being matched. We formalize this trade-off via a novel optimization problem that we term as 'Two-sided Facility Location': we consider a market wherein agents arrive at nodes embedded in an underlying metric space, where the distance between a buyer and seller captures the quality of the corresponding match. The platform posts prices and wages at the nodes, and opens a set of virtual clearinghouses where agents are routed for matching. To ensure high match-quality, the platform imposes a distance constraint between an agent and its clearinghouse; to ensure thickness, the platform requires the flow to any clearinghouse be at least a pre-specified lower bound. Subject to these constraints, the goal of the platform is to maximize the social surplus subject to weak budget balance, i.e., profit being non-negative. Our work characterizes the complexity of this problem by providing both hardness results as well as algorithms for this setting; in particular, we present an algorithm that for any constant \u03b5 &gt; 0 yields a (1 + \u03b5 ) approximation for the gains from trade, while relaxing the match quality (i.e., maximum distance of any match) by a constant factor.<\/jats:p>","DOI":"10.1145\/3322205.3311089","type":"journal-article","created":{"date-parts":[[2020,3,26]],"date-time":"2020-03-26T13:12:37Z","timestamp":1585228357000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["The Segmentation-Thickness Tradeoff in Online Marketplaces"],"prefix":"10.1145","volume":"3","author":[{"given":"Reza","family":"Alijani","sequence":"first","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siddhartha","family":"Banerjee","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sreenivas","family":"Gollapudi","sequence":"additional","affiliation":[{"name":"Google Research, San Francisco Bay Area , CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kostas","family":"Kollias","sequence":"additional","affiliation":[{"name":"Google research, San Francisco Bay Area , CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kamesh","family":"Munagala","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,3,26]]},"reference":[{"key":"e_1_2_1_1_1","article-title":"is experimenting with letting riders wait longer in exchange for cheaper fares","author":"Uber","year":"2018","journal-title":"Quartz Magazine"},{"volume-title":"Reversibility and further properties of fcfs infinite bipartite matching. arXiv preprint arXiv:1507.05939","year":"2015","author":"Adan Ivo","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1110.1027"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602887"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01277956"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1756-2171.2006.tb00037.x"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039753"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052578"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764527"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54110-4_28"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2909990.2910000"},{"volume-title":"Approximating gains from trade in two-sided markets via simple mechanisms. CoRR, abs\/1706.04637","year":"2017","author":"Brustle Johannes","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1239\/aap\/1253281061"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055455"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085119"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884533"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085128"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0330"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897557"},{"volume-title":"15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016","year":"2016","author":"Friggstad Zachary","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796579"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/13-SSY097"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064009.1064027"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0205-6"},{"volume-title":"41st Annual Symposium on Foundations of Computer Science, FOCS 2000","year":"2000","author":"David","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1214\/10-AAP681"},{"issue":"1","key":"e_1_2_1_28_1","first-page":"1","article-title":"The gains from trade under fixed price mechanisms","volume":"1","author":"McAfee R Preston","year":"2008","journal-title":"Applied Economics Research Bulletin"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380756"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(83)90048-0"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1162\/154247603322493212"},{"key":"e_1_2_1_32_1","first-page":"1154","volume-title":"Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008","author":"Svitkina Zoya","year":"2008"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021804515162"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.100.4.1642"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511921735","volume-title":"The design of approximation algorithms","author":"Williamson David P","year":"2011"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322205.3311089","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3322205.3311089","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3322205.3311089","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:55Z","timestamp":1750206355000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322205.3311089"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,26]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,3,26]]}},"alternative-id":["10.1145\/3322205.3311089"],"URL":"https:\/\/doi.org\/10.1145\/3322205.3311089","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2019,3,26]]},"assertion":[{"value":"2019-03-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}