Matching Service Providers and Customers in Two-Sided Dynamic Markets

Abstract This paper presents matching algorithms for two-sided dynamic service markets where service providers and customers form two disjoint sets and an agent from one side of the market can be matched only with an agent from the other side. We address the challenges derived from dynamic changes of the market. The algorithms are designed based on re-matching and repair-based matching models. The re-matching algorithm is straightforward and easy to implement. However, it does not have a mechanism to maintain matching consistency with the previous matching solution. Instead of computing a completely new matching solution, the repair-based matching algorithm maintain good matching consistency by repairing only the part of matching affected by the dynamic changes. In addition to better matching consistency, we show that the matching solutions generated by the repair-based matching algorithm are also stable.