Joint Dependency and Conflicting Task Allocation in Collaboration-Aware Spatial Crowdsourcing

Spatial crowdsourcing (SC) is a new form of crowdsourcing that utilizes users (i.e., workers) equipped with smart devices to complete tasks at specific locations. Previous studies usually focus on single task relationships (e.g., dependencies or conflicts) without considering task allocation under multiple relationships. To address this limitation, we jointly consider task dependency and conflict while also considering collaboration among workers for task allocation. In this paper, we define and formulate a new problem, called Joint Dependency and Conflicting Task Allocation in Collaboration-aware Spatial Crowdsourcing (JDCTA), which is proved to be NP-hard. To tackle the JDCTA problem, we first design an approximation algorithm, JDCTA-Greedy, which constructs a set of associated task groups based on task relationships and then greedily allocates these groups, in which we can obtain results with a theoretical bound on the approximate ratio. We then propose JDCTA-Game, a both dependency and conflict aware game approach. JDCTA -Game reduces the strategy space by defining dependency and conflict trees, combined with a dynamic payoff function based on the multiple relationships between tasks, to achieve high-quality solutions. Theoretical analysis demonstrates that this method guarantees the existence of at least one Nash equilibrium, and the solution quality is bounded. Experimental results on both synthetic and real datasets show that our proposed approach outperforms the representative approaches in terms of overall utility.