The Segmentation-Thickness Tradeoff in Online Marketplaces
The Segmentation-Thickness Tradeoff in Online Marketplaces
复制标题
在线市场的细分与厚度权衡
DOI：
10.1145/3311089
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Munagala, Kamesh
中科院分区：
文献类型：
--
作者：
Alijani, Reza;Banerjee, Siddhartha;Gollapudi, Sreenivas;Kollias, Kostas;Munagala, Kamesh
在线市场运营的核心张力在于细分（平台可以通过将市场细分为更小的子市场来增加收入）和厚度（子市场的规模影响代理商体验到的效用）之间。一个重要的例子是在动态的在线市场中，买家和卖家除了对不同匹配的偏好之外，对匹配的耐心（或截止日期）也是有限的。我们通过一个新的优化问题来形式化这种权衡，我们称之为“双边设施位置”：我们考虑一个市场，其中代理到达嵌入底层度量空间的节点，其中买方和卖方之间的距离捕获相应匹配的质量。该平台在节点上公布价格和工资，并开设一组虚拟清算所，代理在其中进行匹配。为了确保高匹配质量，平台在代理商与其清算所之间施加了距离限制；为了确保厚度，平台要求任何清算所的流量至少达到预先指定的下限。受到这些限制，平台的目标是在弱预算平衡的情况下最大化社会盈余，即利润非负。我们的工作通过提供硬度结果以及针对该设置的算法来表征该问题的复杂性；特别是，我们提出了一种算法，对于任何常数 ε > 0 都会产生贸易收益的 (1 + ε ) 近似值，同时通过常数因子放宽匹配质量（即任何匹配的最大距离）。
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 ε > 0 yields a (1 + ε ) approximation for the gains from trade, while relaxing the match quality (i.e., maximum distance of any match) by a constant factor.
登录
查看更多内容
DOI：
--
发表时间：
2017
期刊：
ACM Conference on Economics and Computation
影响因子：
--
作者：
J. Brustle;Yang Cai;Fa Wu;Mingfei Zhao
通讯作者：
Mingfei Zhao
DOI：
10.1145/2600057.2602887
发表时间：
2014-02
期刊：
Proceedings of the fifteenth ACM conference on Economics and computation
影响因子：
--
作者：
M. Akbarpour;Shengwu Li;S. Gharan
通讯作者：
M. Akbarpour;Shengwu Li;S. Gharan
DOI：
10.1145/380752.380756
发表时间：
2001
期刊：
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
A. Meyerson
通讯作者：
A. Meyerson
网上排班的真相与遗憾
DOI：
10.1145/3033274.3085119
发表时间：
2017
期刊：
Proceedings of the 2017 ACM Conference on Economics and Computation
影响因子：
--
作者：
Shuchi Chawla;Nikhil R. Devanur;Janardhan Kulkarni;Rad Niazadeh
通讯作者：
Rad Niazadeh
影响因子：
1.2
作者：
Colini-Baldeschi, Riccardo;Goldberg, Paul W.;Keijzer, Bart de;Leonardi, Stefano;Roughgarden, Tim;Turchetta, Stefano
通讯作者：
Turchetta, Stefano