Incentive Mechanism For Crowdsourcing Via Social Networks

Crowdsourcing is a typical case of using group wisdom to solve problems.In the context of the booming development of the Internet,social media,and the sharing economy,crowdsourcing based on social networks is a very promising application scenario.Taking crowdsourcing system as the research object and auction theory as the research method,this thesis mainly studies the crowdsourcing incentive mechanism via social networks.In this thesis,both the crowdsourcing platform and the crowdsourcing workers are abstracted as nodes in a social network,which are connected by edges based on the relationship they know each other.The crowdsourcing workers in the network can spread the crowdsourcing information to their neighbors,thereby allowing their neighbors to enter the crowdsourcing system.In this thesis,the task allocation process of crowdsourcing is modeled by reverse auction,and the following two crowdsourcing models are mainly studied:Firstly,for heterogeneous task crowdsourcing considering task constraints,i.e.a one-to-one model of workers and tasks,this thesis models it as a crowdsourcing propagation problem,and proves the NP-hardness of the problem through the reduction from the knapsack problem.Next,this thesis applies some classical crowdsourcing mechanisms to the network environment and demonstrates its infeasibility.After that,under budget constraints,this thesis proposes a distance-based mechanism SNC and a distance-andgreedy-based mechanism SNC-D.The SNC mechanism satisfies the incentive compatibility,individual rationality,budget feasibility,weakly budget balanced and computational efficiency.It can reduce the decision-making cost of workers in practical applications,and has good application prospects.The SNC-D mechanism also satisfies most of the above-mentioned excellent properties,but can only guarantee the propagation incentive compatibility.In addition,SNC-D also satisfies the weakly allocation efficiency,and ensures that the revenue of platform is at least half of the optimal mechanism.Secondly,for heterogeneous task crowdsourcing without task constraints,i.e.,a manyto-many model of workers and tasks,this thesis models it as a social network-based user selection problem,and proves the NP-hardness by reducing the problem from set cover problem.Next,this thesis analyzes the infeasibility of the classic many-to-many model MSensing in the network environment.Afterwards,this thesis proposes the SNUS mechanism,which includes two steps of winner selection and payment determination.As for theoretical analysis,it is proved that the mechanism satisfies incentive compatibility,individual rationality,weakly budget balanced and computational efficiency.Finally,through experiments based on Facebook's real social networks data set,this thesis verifies the good properties of the above three mechanisms,and consolidates the results of theoretical analysis.