Balancing Cooperation and Competition: Selfish Worker Coalition Formation in Spatial Crowdsourcing

Spatial Crowdsourcing (SC), which outsources location-dependent tasks to workers for physical completion, is gaining popularity. Recently, more complex tasks have emerged that require a group of workers collaborating in a coalition. Several pioneering studies have examined this issue using the server assigned tasks mode from an overall perspective, such as maximizing the total benefits of all workers. Unfortunately, maximizing the overall benefit does not necessarily align with maximizing individual benefits. In practice, crowd workers are often self-interested and autonomous, making decisions based on their personal perspectives. In this article, under the worker selected tasks mode, we investigate an important problem: Selfish Workers Coalition Formation (SWCF) problem in SC. Here, selfish workers autonomously form coalitions to accomplish tasks to maximize their individual benefits. Achieving a stable coalition formation for SWCF problem requires balancing cooperation and competition. First, we transform the SWCF problem into a hedonic coalition formation game using a devised exploited skills-based reward distribution model. Subsequently, we propose a distributed algorithm HCFTA and prove its Nash stability and performance bounds. Additionally, to enhance coalition formation efficiency, we propose a Markov blanket coloring parallel optimization algorithm MCPHCF. Extensive experiments demonstrate the superiority of the proposed methods on both synthetic and real-world datasets.