# Selecting Workers Wisely for Crowdsourcing When Copiers and Domain Experts Co-exist
## 4 Task Assignment
### Fine-Grained Worker Credibility Calculation  
In reality, tasks may contain multiple domains, and workers may be good at different domains. In order to assign tasks to appropriate workers, we need to calculate the credibility of workers for each task. We define it as the worker fine-grained credibility, e.g., \(q_{i}^{j}\). For single-domain tasks, we can regard worker's domain quality in that domain as the fine-grained credibility for these tasks. However, it is unreasonable to consider only one domain of the task for multi-domain tasks. We should consider all the domains covered by the task. For multi-domain tasks, we take the average value of the worker's domain quality in all the domains involved in the task as the fine-grained credibility of the worker. Here, fine-grained credibility is the worker's credibility for this specific task. The calculation of worker fine-grained credibility is shown in Formula (1). \[q_{i}^{j}=\frac{1}{\left|D_{t_{j}}\right|}\sum_{d\in D_{t_{j}}}v_{i}^{d} \tag{1}\]  
After obtaining the fine-grained  
upper limit (\(M\)) on the number of tasks that can be completed. For example, we assign \(M\) tasks to worker \(w_{1}\). In the following tasks, \(w_{1}\) is still the best worker. Which K tasks will the worker \(w_{1}\) be assigned? We need to take this situation into account. We use set \(\{m_{w_{i}}\}\) to record the number of tasks that worker \(w_{i}\) has been assigned. For the set of tasks, Step 2 finds an optimal assignment scheme \(S\) to maximize the summation of the overall worker fine-grained credibility of all tasks in the scheme, i.e.,  
\[S=argmax\sum_{t_{j}\in T}\left(\sum_{w_{j}\in\hat{W}_{t_{j}}}q_{i}^{j}\right) \tag{2}\]  
subject to:  
\[max(m_{w_{i}})\leqslant M \tag{3}\]  
where \(\sum_{w_{j}\in\hat{W}_{t_{j}}}q_{i}^{j}\) is the overall credibility of workers that globally complete \(t_{j}\). Summing such overall credibility of each task, \(\sum_{t_{j}\in T}\left(\sum_{w_{i}\in\hat{W}_{t_{j}}}q_{i}^{j}\right)\) can measure the credibility of all globally completed tasks. Next, we prove that the optimal problem of worker selection is NP-hard. Proof. : Given a set of workers \(W\), each of which corresponds to their credibility, then the system has a set of tasks \(T\), each of which needs \(K\) workers to complete. In order to meet scheme \(S\), we may need to detect \((C_{|W|}^{K})^{|T|}\) possible cases to find the optimal solution. There is no doubt that this has an exponential time complexity, which cannot be obtained in polynomial time. Therefore, the optimal problem of worker selection is a typical NP-hard problem. **A Greedy approximation algorithm:**  
As the optimal problem of worker selection is NP-hard, we developed a greedy-based approximation algorithm to efficiently solve it. The algorithm takes task \(t_{j}\), candidate worker set \(\hat{W}_{t_{j}}\), number of workers needed K, and number of tasks completed by workers \(\{m_{w_{i}}\}\) as the input. The algorithm obtains an allocation set \(\hat{W}_{t_{j}}\) for each task \(t_{j}\). For each task \(t_{j}\), it selects the worker with the highest credibility from the candidate worker set \(\hat{W}_{t_{j}}\) to assign the task. When \(t_{j}\) selects worker \(w_{i}\), if \(m_{w_{i}}\) has reached the upper limit, it skips the worker and removes \(w_{i}\) from \(\hat{W}_{t_{j}}\). Otherwise, \(t_{j}\) increases \(m_{w_{i}}\) by one, inserts \(w_{i}\) into \(\hat{W}_{t_{j}}\), and removes \(w_{i}\) from \(\hat{W}_{t_{j}}\). Perform this operation K times until the number of workers required for the task is reached, and output \(\hat{W}_{t_{j}}\). The algorithm pseudo code of the worker selection part is shown in Algorithm 2. The time complexity for all tasks to complete worker selection is O(K\(\,\)I\(\,\)T\(\,\)).