*Result*: Towards stable task assignment with preference lists and ties in spatial crowdsourcing.
*Further Information*
*• One-sided online stable task assignment with incomplete preference lists and ties. • Relaxed linear programming with stable constraint. • Combination solutions with two suggested matching technology. • Improving total utility of matched pairs and decreasing the blocking pair ratio. 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. [ABSTRACT FROM AUTHOR]
Copyright of Information Sciences is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)*