Dynamic Bipartite Matching Market with Arrivals and Departures
Dynamic Bipartite Matching Market with Arrivals and Departures
复制标题
DOI：
--
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Naonori Kakimura;Donghao Zhu
中科院分区：
文献类型：
--
作者：
Naonori Kakimura;Donghao Zhu
本文研究了二部网络上的一个匹配市场模型，其中每一方的代理人都是按泊松过程随机到达和离开的。对于这样一个动态模型，我们设计了一个机制，不仅决定哪些代理匹配，而且何时匹配他们，以尽量减少不匹配的代理的预期数量。本文的主要贡献是实现不同的定时属性的本地机制的性能的理论界。我们证明了一个等待市场的算法，称为$\textit{Patient}$算法，比$\textit{Greedy}$算法要好，即，一种匹配特工的算法这意味着等待在最大化二分网络上的匹配方面有很大的好处。我们注意到，病人的算法需要规划者确定代理人谁是即将离开市场，并在要求下，病人的算法被证明是一个最优的算法。我们还表明，没有要求，贪婪算法几乎是最优的。此外，我们考虑$\textit{1-sided算法}$，其中只有一侧的代理可以尝试匹配。这模拟了一个实际的匹配市场，如运费交换市场和劳动力市场，只有一方的代理人可以做出决定。对于这种设置，我们证明了贪婪和耐心算法承认相同的性能，即等待市场是没有价值的。这一结论与双方代理人都能做出决定的情况和[Akbarpour et al.，$~\]的非双方情况相反《政治经济学杂志》，2020年。
In this paper, we study a matching market model on a bipartite network where agents on each side arrive and depart stochastically by a Poisson process. For such a dynamic model, we design a mechanism that decides not only which agents to match, but also when to match them, to minimize the expected number of unmatched agents. The main contribution of this paper is to achieve theoretical bounds on the performance of local mechanisms with different timing properties. We show that an algorithm that waits to thicken the market, called the $\textit{Patient}$ algorithm, is exponentially better than the $\textit{Greedy}$ algorithm, i.e., an algorithm that matches agents greedily. This means that waiting has substantial benefits on maximizing a matching over a bipartite network. We remark that the Patient algorithm requires the planner to identify agents who are about to leave the market, and, under the requirement, the Patient algorithm is shown to be an optimal algorithm. We also show that, without the requirement, the Greedy algorithm is almost optimal. In addition, we consider the $\textit{1-sided algorithms}$ where only an agent on one side can attempt to match. This models a practical matching market such as a freight exchange market and a labor market where only agents on one side can make a decision. For this setting, we prove that the Greedy and Patient algorithms admit the same performance, that is, waiting to thicken the market is not valuable. This conclusion is in contrast to the case where agents on both sides can make a decision and the non-bipartite case by [Akbarpour et al.,$~\textit{Journal of Political Economy}$, 2020].