Efficient Dynamic Barter Exchange
Efficient Dynamic Barter Exchange
复制标题
DOI：
10.1287/opre.2017.1644
复制
发表时间：
2017-09
期刊：
影响因子：
--
通讯作者：
Ross Anderson;I. Ashlagi;D. Gamarnik;Yashodhan Kanoria
中科院分区：
文献类型：
--
作者：
Ross Anderson;I. Ashlagi;D. Gamarnik;Yashodhan Kanoria
我们研究动态匹配政策，在一个随机的市场易货，随着时间的推移到达代理。每个代理被赋予一个项目，并有兴趣在一个项目拥有的另一个代理均匀的概率p，独立的所有对代理。三种设置被认为是相对于允许的交换类型：（a）只有双向循环，其中两个代理交换项目，（B）双向或三向循环，（c）（无界）链发起的代理谁提供一个项目，但不期望任何回报。我们认为平均等待时间作为衡量效率的一个指标，并发现等待的成本超过了等待市场的收益。特别地，在上述每种设置中，以贪婪方式进行交换的策略接近最优。此外，对于小p，我们发现，允许三路循环大大减少了等待时间，只有双向循环，并通过链进行交换进一步减少了等待时间显着。因此，一个中心…
We study dynamic matching policies in a stochastic marketplace for barter, with agents arriving over time. Each agent is endowed with an item and is interested in an item possessed by another agent homogeneously with probability p, independently for all pairs of agents. Three settings are considered with respect to the types of allowed exchanges: (a) only two-way cycles, in which two agents swap items, (b) two-way or three-way cycles, (c) (unbounded) chains initiated by an agent who provides an item but expects nothing in return. We consider the average waiting time as a measure of efficiency and find that the cost outweighs the benefit from waiting to thicken the market. In particular, in each of the above settings, a policy that conducts exchanges in a greedy fashion is near optimal. Further, for small p, we find that allowing three-way cycles greatly reduces the waiting time over just two-way cycles, and conducting exchanges through a chain further reduces the waiting time significantly. Thus, a centra...