Towards stable task assignment with preference lists and ties in spatial crowdsourcing

摘要

Task assignment is a fundamental problem in spatial crowdsourcing. Since workers and tasks accept each other within a limited range, there are incomplete and tied preference lists for any vertex on two sides (workers and tasks). Many studies ignore that workers' preferences may conflict with tasks' preferences, which results in unstable matching. In this paper, we investigate the preferences-oriented online stable task assignment (POSTA) in which tasks arrive online and obey independent identical distribution (i.i.d.). First, we construct a weighted partite graph G and formulate the POSTA problem based on G. Then, prove it to be NP-complete. To measure the weight of edges, we design a utility estimation method. Second, we formulate the linear programming model of POSTA and obtain the solution. Next, we solve the maximum weighted matching of G. Based on these two solutions, we design the algorithm utilizing two suggested matching (TSM) technology to obtain the combination solution, which guides the algorithm for matching. Then, we analyze the competitive ratio. Finally, we examine the performance of the proposed method through extensive experiments. The experiment results show that our strategy outperforms other methods in total utility, competitive ratio and blocking pair ratio.

关键词