Crowdsourcing: Uncertainties and Optimizations

Abstract:

Current crowdsourcing platforms are facing challenges of providing better services. In this thesis, we focus on the challenges in recommendation tasks on collaborative crowdsourcing platforms. The collection and exploitation of ratings from the crowds are commonly leveraged for the recommendation task. However, the independent collection of information, the multiplicity, and diversity of the collected information result in uncertainty. The uncertainty gives rise to the questions of how to rank the items according to the ratings from the heterogeneous users and how many ratings are supposed to be sufficient. Beyond the ratings made by the crowds, the recommendation can also be based on other features. Items, such as hotels, restaurants and vacation rentals, have uncertain scores for their various features such as the prices of the rentals and the waiting time of the restaurants. In this context, ranking the items based on the uncertain scores of the features becomes a challenging issue.

In this thesis, we devise an effective and efficient algorithm that computes the best-rated items in a ranking constructed from crowdsourced ratings. We propose an approach that learns from the available data how many ratings are enough to estimate the score of an item. We model the uncertain scores of the various features of the items with probability distributions, and we explore the design space of Markov chain Monte Carlo algorithms for answering the uncertain top-k queries. We are able to devise several algorithms that yield better performance than the state of the art algorithm.

Spatial crowdsourcing applications are helpful in alleviating uncertainty and providing more accurate and personalized recommendations. Spatial tasks are outsourced to a community of online, yet on-ground and mobile, workers to gather information such as ratings of the items. A spatial task is characterized by the requirement that workers need to move from their current location to a specified location to accomplish the task, which incurs non-negligible commuting cost. The design of an efficient and effective task assignment strategy is in need to minimize the commuting cost. Beyond the tasks that can be completed by a single worker, we also consider the assignment of complex tasks that require a variety of skills. A team of workers with certified skills needs to be selected to complete such a complex task and the payment to each selected worker needs to be determined.

We devise two distribution-aware algorithms that utilize the distribution information of the tasks for the assignment of the spatial tasks. Experimental results show that the proposed algorithms outperform the baseline algorithms. We design four incentive mechanisms for selecting workers to form a valid team that can complete a complex task and for determining each individual worker's payment. One of the proposed mechanisms is superior to the others due to its computational efficiency and truthfulness.

Overall, our work provides insights in dealing with crowdsourced uncertain information. It also shows how to exploit crowdsourcing platforms to gather information or to complete tasks in an optimal way.