Multi-Agent Based Optimization For Crowdsourcing System Considering Worker Characteristics

In recent years,crowdsourcing,as an emerging model that utilizes human-intelligence to accomplish tasks in an open call,has attracted much attentions.The openness of crowdsourcing can attract a large number of freelance workers.However,when crowd workers select and perform tasks,they often exhibit some individual characteristics that are detrimental to the efficient completion of tasks.1)Choice bias of workers: workers usually choose the task with the highest net revenue,which can lead to the imbalance of task selection.2)Variability of workers' abilities: workers' abilities can change dynamically due to the boredom,attention or other factors,which can lead to the uncertain quality of completed tasks.3)Untruthfulness of workers: workers may misreport work costs to maximize their own benefits,which can lead to the harmful competition within workers and overspending on task budgets.Therefore,this thesis conducts the researches to optimize crowdsourcing system from the above three perspectives,and proposes the corresponding solutions and algorithms.For the choice bias of workers,traditional methods usually adopt subsidy or reward to mitigate the imbalance of task selections,but it requires an extra budget.Thus,this thesis proposes a price mediation mechanism without a budget,which works by allowing the crowdsourcing platform to adjust the task prices,thereby eliciting workers to balance their choices and maximizing the social welfare.To solve the optimal price adjustment strategy,an branch-and-bound algorithm based on bound function and pruning strategies is proposed for small-scale instances.For adapting larger scale situations,we also design a heuristic method based on the thought of price transfers.Experimental results show that our method can improve the social welfare more effectively under different problem scales.For the variability of workers' abilities,traditional solutions usually adopt static or periodic test methods,but it cannot actively adapt to the dynamic changes of workers' abilities.Thus,this thesis proposes an adaptive worker ability test mechanism,which dynamically inserts test tasks(with true answer)to detect a worker's performance in real time,while ensuring that the normal task(with unknown true answer)is assigned when this worker is currently deemed reliable via testing,to guarantee the quality of the completed tasks.To decide when to assign a test task,test mechanism adopts Partially Observable Markov Decision Process(POMDP)model.In addition,the rejection strategies are designed for malicious workers and unreliable answers.Experimental results show that our mechanism has a better performance in the accuracy of task answers,comparing with benchmarks.For the untruthfulness of workers,previous works mainly focus on the scenario of simple tasks,while this thesis considers how to overcome the influence of workers' untruthful behaviors for complex tasks(that requires team work),and form a skill robust team to ensure that the absence of some workers does not affect the satisfaction of the task's skill requirements.This thesis designs a greedy based robust team formation mechanism with incentive compatibility.The mechanism greedily selects the worker according to the marginal skill contribution per cost(i.e.the worker's skill incremental contribution under the unit of costs)and then gives each team member to the greatest reward that they can obtain.The theoretical analysis proves that the mechanism can incentivize a worker to report the true cost.The experimental results show that,comparing with the classical VCG mechanism,our mechanism is superior in running time,and has an approximate performance in the total costs of the team,total payments to workers,and total utilities of workers.