skip to main content

This content will become publicly available on February 28, 2023

Title: Topic-aware Incentive Mechanism for Task Diffusion in Mobile Crowdsourcing through Social Network
Crowdsourcing has become an efficient paradigm to utilize human intelligence to perform tasks that are challenging for machines. Many incentive mechanisms for crowdsourcing systems have been proposed. However, most of existing incentive mechanisms assume that there are sufficient participants to perform crowdsourcing tasks. In large-scale crowdsourcing scenarios, this assumption may be not applicable. To address this issue, we diffuse the crowdsourcing tasks in social network to increase the number of participants. To make the task diffusion more applicable to crowdsourcing system, we enhance the classic Independent Cascade model so the influence is strongly connected with both the types and topics of tasks. Based on the tailored task diffusion model, we formulate the Budget Feasible Task Diffusion ( BFTD ) problem for maximizing the value function of platform with constrained budget. We design a parameter estimation algorithm based on Expectation Maximization algorithm to estimate the parameters in proposed task diffusion model. Benefitting from the submodular property of the objective function, we apply the budget-feasible incentive mechanism, which satisfies desirable properties of computational efficiency, individual rationality, budget-feasible, truthfulness, and guaranteed approximation, to stimulate the task diffusers. The simulation results based on two real-world datasets show that our incentive mechanism can improve the more » number of active users and the task completion rate by 9.8% and 11%, on average. « less
Authors:
; ; ; ; ;
Award ID(s):
1717315
Publication Date:
NSF-PAR ID:
10313954
Journal Name:
ACM Transactions on Internet Technology
Volume:
22
Issue:
1
ISSN:
1533-5399
Sponsoring Org:
National Science Foundation
More Like this
  1. While prior studies have designed incentive mechanisms to attract the public to share their collected data, they tend to ignore information asymmetry between data requesters and collectors. In reality, the sensing costs information (time cost, battery drainage, bandwidth occupation of mobile devices, and so on) is the private information of collectors, which is unknown by the data requester. In this article, we model the strategic interactions between health-data requester and collectors using a bilevel optimization model. Considering that the crowdsensing market is open and the participants are equal, we propose a Walrasian equilibrium-based pricing mechanism to coordinate the interest conflicts between health-data requesters and collectors. Specifically, based on the exchange economic theory, we transform the bilevel optimization problem into a social welfare maximization problem with the constraint condition that the balance between supply and demand, and dual decomposition is then employed to divide the social welfare maximization problem into a set of subproblems that can be solved by health-data requesters and collectors. We prove that the optimal task price is equal to the marginal utility generated by the collector's health data. To avoid obtaining the collector's private information, a distributed iterative algorithm is then designed to obtain the optimal taskmore »pricing strategy. Furthermore, we conduct computational experiments to evaluate the performance of the proposed pricing mechanism and analyze the effects of intrinsic rewards, sensing costs on optimal task prices, and collectors' health-data supplies.« less
  2. Smart City is a key component in Internet of Things (IoTs), so it has attracted much attention. The emergence of Mobile Crowd Sensing (MCS) systems enables many smart city applications. In an MCS system, sensing tasks are allocated to a number of mobile users. As a result, the sensing related context of each mobile user plays a significant role on service quality. However, some important sensing context is ignored in the literature. This motivates us to propose a Context-aware Multi-Armed Bandit (C-MAB) incentive mechanism to facilitate quality-based worker selection in an MCS system. We evaluate a worker’s service quality by its context (i.e., extrinsic ability and intrinsic ability) and cost. Based on our proposed C-MAB incentive mechanism and quality evaluation design, we develop a Modified Thompson Sampling Worker Selection (MTS-WS) algorithm to select workers in a reinforcement learning manner. MTS-WS is able to choose effective workers because it can maintain accurate worker quality information by updating evaluation parameters according to the status of task accomplishment. We theoretically prove that our C-MAB incentive mechanism is selection efficient, computationally efficient, individually rational, and truthful. Finally, we evaluate our MTS-WS algorithm on simulated and real-world datasets in comparison with some other classic algorithms.more »Our evaluation results demonstrate that MTS-WS achieves the highest cumulative utility of the requester and social welfare.« less
  3. Efficient allocation of tasks to workers is a central problem in crowdsourcing. In this paper, we consider a special setting inspired by spatial crowdsourcing platforms where both workers and tasks arrive dynamically. Additionally, we assume all tasks are heterogeneous and each worker-task assignment brings a known reward. The natural challenge lies in how to incorporate the uncertainty in the arrivals from both workers and tasks into our online allocation policy such that the total expected reward is maximized. To formulate this, we assume the arrival patterns of worker “types” and task “types” can be predicted from historical data. Specifically, we consider a finite time horizon T and assume that in each time-step, a single worker and task are sampled (i.e., “arrive”) from two respective distributions independently, and that this sampling process repeats identically and independently for the entire T online time-steps. Our model, called Online Task Assignment with Two-Sided Arrival (OTA-TSA), is a significant generalization of the classical online task assignment where the set of tasks is assumed to be available offline. For the general version of OTA-TSA, we present an optimal non-adaptive algorithm which achieves an online competitive ratio of 0.295. For the special case of OTA-TSA where themore »reward is a function of just the worker type, we present an improved algorithm (which is adaptive) and achieves a competitive ratio of at least 0.343. On the hardness side, along with showing that the ratio obtained by our non-adaptive algorithm is the best possible among all non-adaptive algorithms, we further show that no (adaptive) algorithm can achieve a ratio better than 0.581 (unconditionally), even for the special case of OTA-TSA with homogenous tasks (i.e., all rewards are the same). At the heart of our analysis lies a new technical tool (which is a refined notion of the birth-death process), called the two-stage birth-death process, which may be of independent interest. Finally, we perform numerical experiments on two real-world datasets obtained from crowdsourcing platforms to complement our theoretical results.« less
  4. Online crowdsourcing platforms have proliferated over the last few years and cover a number of important domains, these platforms include worker-task platforms such as Amazon Mechanical Turk, worker-for hire platforms such as TaskRabbit to specialized platforms with specific tasks such as ridesharing like Uber, Lyft, Ola, etc. An increasing proportion of the human workforce will be employed by these platforms in the near future. The crowdsourcing community has done yeoman’s work in designing effective algorithms for various key components, such as incentive design, task assignment, and quality control. Given the increasing importance of these crowdsourcing platforms, it is now time to design mechanisms so that it is easier to evaluate the effectiveness of these platforms. Specifically, we advocate developing benchmarks for crowdsourcing research. Benchmarks often identify important issues for the community to focus on and improve upon. This has played a key role in the development of research domains as diverse as databases and deep learning. We believe that developing appropriate benchmarks for crowdsourcing will ignite further innovations. However, crowdsourcing – and future of work, in general – is a very diverse field that makes developing benchmarks much more challenging. Substantial effort is needed that spans across developing benchmarks formore »datasets, metrics, algorithms, platforms, and so on. In this article, we initiate some discussion into this important problem and issue a call-to-arms for the community to work on this important initiative.« less
  5. Matching markets with historical data are abundant in many applications, e.g., matching candidates to jobs in hiring, workers to tasks in crowdsourcing markets, and jobs to servers in cloud services. In all these applications, a match consumes one or more shared and limited resources and the goal is to best utilize these to maximize a global objective. Additionally, one often has historical data and hence some statistics (usually first-order moments) of the arriving agents (e.g., candidates, workers, and jobs) can be learnt. To model these scenarios, we propose a unifying framework, called Multi- Budgeted Online Assignment with Known Adversarial Distributions. In this model,we have a set of offline servers with different deadlines and a set of online job types. At each time, a job of type j arrives. Assigning this job to a server i yields a profit w(i, j) while consuming a(i,j) -- a vector lying in [0, 1]^K -- quantities of distinct resources. The goal is to design an (online) assignment policy that maximizes the total expected profit without violating the (hard) budget constraint. We propose and theoretically analyze two linear programming (LP) based algorithms which are almost optimal among all LP-based approaches. We also propose several heuristicsmore »adapted from our algorithms and compare them to other LP-agnostic algorithms using both synthetic as well as real-time cloud scheduling and public safety datasets. Experimental results show that our proposed algorithms are effective and significantly out-perform the baselines. Moreover, we show empirically the trade-off between fairness and efficiency of our algorithms which does well even on fairness metrics without explicitly optimizing for it.« less