Three-dimensional stable matching problem for spatial crowdsourcing platforms

The popularity of mobile Internet techniques and Online-To-Offline (O2O) business models has led to the emergence of various spatial crowdsourcing (SC) platforms in our daily life. A core issue of SC platforms is to assign tasks to suitable crowd workers. Existing approaches usually focus on the matching of two types of objects, tasks and workers, and let workers to travel to the location of users to provide services, which is a 2D matching problem. However, recent services provided by some new platforms, such as personalized haircut service¹ and station ride-sharing², need users and workers travel together to a third workplace to complete the service, which is indeed a 3D matching problem. Approaches in the existing studies either cannot solve such 3D matching problem, or lack a assignment plan satisfying both users' and workers' preference in real applications. Thus, in this paper, we propose a 3-Dimensional Stable Spatial Matching (3D-SSM) for the 3D matching problem in new SC services. We prove that the 3D-SSM problem is NP-hard, and propose two baseline algorithms and two efficient approximate algorithms with bounded approximate ratios to solve it. Finally, we conduct extensive experiment studies which verify the efficiency and effectiveness of the proposed algorithms on real and synthetic datasets.