Complex task allocation for crowdsourcing in social network context

• Main Author: Jiang, Jiuchuan
• Other Authors: Bo An
• Format: Theses and Dissertations
• Language: English
• Published: 2019
• Subjects: DRNTU::Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/98686; http://hdl.handle.net/10220/48546
• Institution: Nanyang Technological University

Allocation of complex tasks has attracted significant attention in crowdsourcing area recently, which can be categorized into decomposition and monolithic allocations. Decomposition allocation means that each complex task will first be decomposed into a flow of simple subtasks and then the subtasks will be allocated to individual workers; monolithic allocation means that each complex task will be allocated as a whole, which includes individual-oriented and team formation-based approaches. However, those existing approaches have some problems for real crowdsourcing markets. On the other hand, workers are often connected through social networks, which can significantly facilitate crowdsourcing of complex tasks. Therefore, this thesis investigates crowdsourcing in social network context and presents models to address the typical problems in complex task allocation. The main contributions of this thesis are shown as follows. First, traditional decomposition allocation for complex tasks has the following typical problems: 1) decomposing complex tasks into a set of subtasks requires the decomposition capability of the requesters; and 2) reliability may not be ensured when there are many malicious workers in the crowd. To this end, this thesis investigates the context-aware reliable crowdsourcing in social networks. In our approach, when a requester wishes to outsource a task, a worker candidate’s self-situation and contextual-situation in the social network are considered. Complex tasks can be performed through autonomous coordination between the assigned worker and his contextual workers in the social network; thus, requesters can be exempt from decomposing complex tasks into subtasks. Moreover, the reliability of a worker is determined not only by the reputation of the worker himself but also by the reputations of the contextual workers, which can effectively address the unreliability of transient or malicious workers. Second, traditional individual-oriented monolithic allocation for complex tasks often allocate tasks independently, which has the following typical problems: 1) the execution of one task seldom utilize the results of other tasks and the requester must pay in full for the task; and 2) many workers only undertake a very small number of tasks contemporaneously, thus the workers’ skills and time may not be fully utilized. To this end, this thesis investigates the batch allocation for tasks with overlapping skill requirements. Then, two approaches are designed: layered batch allocation and core-based batch allocation. The former approach utilizes the hierarchy pattern to form all possible batches, which can achieve better performance but may require higher computational cost; the latter approach selects core tasks to form batches, which can achieve suboptimal performance with significantly reducing computational cost. If the assigned worker cannot complete a batch of tasks alone, he/she will cooperate with the contextual workers in the social network. Through the batch allocation, requesters’ real payment can be discounted because the real execution cost of tasks can be reduced, and each worker’s real earnings may increase because he/she can undertake more tasks contemporaneously. Third, traditional team formation-based monolithic allocation for complex tasks has the following typical problems: 1) each team is created for only one task, which may be costly and cannot accommodate crowdsourcing markets with a large number of tasks; and 2) most existing studies form teams in a centralized manner, which may place a heavy burden on requesters. To this end, this thesis investigates the distributed team formation for a batch of tasks, in which similar tasks can be addressed in a batch to reduce computational costs and workers can self-organize through their social networks to form teams. In the presented team formation model, the requester only needs to select the first initiator worker and other team members are selected in a distributed manner, which avoids imposing all team formation computation loads on the requester. Then, two heuristic approaches are designed: one is to form a fixed team for all tasks in the batch, which has lower computational complexity; the other is to form a basic team that can be dynamically adjusted for each task in the batch, which performs better in reducing the total payments by requesters. Forth, current workers are often naturally organized into groups through social networks. To address such common problem, this thesis investigates a new group-oriented crowdsourcing paradigm in which the task allocation targets are naturally existing worker groups but not individual workers or artificially-formed teams as before. An assigned group often needs to coordinate with other groups in the social network contexts for performing a complex task since such natural group might not possess all of the required skills to complete the task. Therefore, a concept of contextual crowdsourcing value is presented to measure a group’s capacity to complete a task by coordinating with its contextual groups, which determines the probability that the group is assigned the task; then the task allocation algorithms, including the allocations of groups and the workers actually participating in executing the task, are designed. In summary, this thesis develops new models to cover the shortages of previous complex task allocation works and designs efficient algorithms to solve the corresponding problems by considering the social network contexts. Experimental results conducted on real-world datasets collected from some representative crowdsourcing platforms show that the presented approaches outperform existing benchmark approaches in previous studies.