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.

Popular ride-hailing products, such as DiDi, Uber and Lyft, provide people with transportation convenience. Pricing, order dispatching and vehicle repositioning are three tasks with tight correlation and complex interactions in ride-hailing platforms, significantly impacting each other’s decisions and demand distribution or supply distribution. However, no past work considered combining the three tasks to improve platform efficiency. In this paper, we exploit to optimize pricing, dispatching and repositioning strategies simultaneously. Such a new multi-stage decision-making problem is quite challenging because it involves complex coordination and lacks a unified problem model. To address this problem, we propose a novelJoint optimization framework ofPricing,Dispatching andRepositioning (JPDR) integrating contextual bandit and multi-agent deep reinforcement learning. JPDR consists of two components, including a Soft Actor-Critic (SAC)-based centralized policy for dispatching and repositioning and a pricing strategy learned by a multi-armed contextual bandit algorithm based on the feedback from the former. The two components learn in a mutually guided way to achieve joint optimization because their updates are highly interdependent. Based on real-world data, we implement a realistic environment simulator. Extensive experiments conducted on it show our method outperforms state-of-the-art baselines in terms of both gross merchandise volume and success rate.

Spatial crowdsourcing as a promising computing paradigm has received significant attention recently. A fundamental issue of spatial crowdsourcing is online task assignment, i.e., the platform must make decisions immediately (assign or reject) for newly arriving objects (tasks or workers). Previous studies mostly focus on the rejection-aware assignment, which rarely considers non-rejection assignment for new arrival objects. To solve this new allocation model, in this paper, we first formulate a novel problem, namely Online Non-rejection aware Task Assignment (ONRTA) in spatial crowdsourcing, where an object cannot be rejected by the platform as long as there is a neighbor that satisfies the matching constraint with it. Then, we develop a non-rejection threshold-based random algorithm ONRTA-RT under the adversarial order model while obtaining a theoretical bound on the competitive ratio. More importantly, we consider a more natural random order model and propose a two-stage-based non-rejection aware task assignment approach, ONRTA-Base, which achieves a competitive ratio of$\frac{1}{4}$. Based on this framework, we further devise two non-rejection assignment approaches, ONRTA-OP and ONRTA-Greedy, which are more effective and run faster with a competitive ratio of$\frac{1}{4}$and$\frac{1}{8}$, respectively. Finally, experiments on synthetic and real datasets demonstrate that our proposed methods outperform the representative methods.

Spatial crowdsourcing platforms have become increasingly popular in people's daily life. A fundamental problem in spatial crowdsourcing is task assignment, which assigns spatial tasks to the workers appropriately in order to satisfy certain objectives. Previous studies usually focus on the real-time micro-task allocation, which does not consider the dependency relationships among tasks. To address this limitation, in this article, we define and formulate a new problem, called Online Dependent Task Assignment (ODTA) in preference aware spatial crowdsourcing. We first prove that ODTA is$\mathcal {NP}$-hard. Then, we design a threshold-based algorithm in the adversarial order model and obtain a near-optimal theoretical bound on the competitive ratio. More importantly, considering the random order arrival model, we further present three algorithms based on a two-stage framework, namely ODTA-Greedy, ODTA-Greedy-OP and ODTA-OPT, which are more effective with a constant competition ratio of$\frac{1}{8}$,$\frac{1}{8}$and$\frac{1}{4}$, respectively. Experimental results on both synthetic and real datasets show that our proposed ODTA-OPT approach outperforms the representative approaches in terms of overall utility.

Recommender systems have been widely deployed on E-commerce websites. The cold start problem of making effective recommendations to new users without any historical data on the website is still challenging. These new users often have some available information, such as search keywords, before visiting the website. It is natural to use the information to predict users' preference, such that an immediate recommendation is possible. In this paper, we propose a new product recommendation approach for new users based on the implicit relationships between search keywords and products. The relationships between keywords and products are represented in a graph and relevance of keywords to products is derived from attributes of the graph. The relevance information will be utilized to predict preferences of new users. A preliminary experiment is conducted and shows that our approach outperforms the traditional approach (Recommending Most Popular Products).