Enhancing Crowdsourcing with the Zero-Determinant Game Theory Public
Contenu téléchargeableTélécharger le fichier PDF
Crowdsourcing is a promising technology to accomplish a complex task via eliciting services from a large group of contributors. As a new paradigm, crowdsourcing has provided more opportunities to accomplish the labor-intensive and large-scale jobs that are difficult for one entity alone. However, due to the heterogeneous nature of the workers, it is challenging to guarantee the performance of crowdsourcing system.In this dissertation, we target to effectively enhance the performance of crowdsourcing based on the zero-determinant (ZD) strategy which appears to be an innovative and powerful technique in game theory. To be specific, we study this problem from the following three aspects.First, recent observations indicate that the success of crowdsourcing has been threatened by the malicious behaviors of the contributors. So we first analyze the malicious attack problem using a two-player simultaneous game, i.e., an iterated prisoner’s dilemma (IPD), where the action of the requestor is the payment level to the worker while that of the worker is completing task with attack or not. In light of this model, we propose a reward-penalty expected payoff algorithm based on the ZD strategy to reward a worker’s cooperation or penalize its defection in order to entice the final cooperation. Both theoretical analysis and simulation studies are performed, and the results indicate that the proposed algorithm has the following two attractive characteristics: 1) the requestor can incentivize the worker to become cooperative without any long-term extra payment; and 2) the proposed algorithm is fair so that the requestor cannot arbitrarily penalize an innocent worker to increase its payoff even though it can dominate the game. To the best of our knowledge, we are the first to adopt the ZD strategies to stimulate both players to cooperate in an IPD. Moreover, our proposed algorithm is not restricted to solve only the crowdsourcing dilemma - it can be employed to tackle any problem that can be formulated into an IPD.Second, the heterogeneity of workers leads to the diverse submission quality of the completed tasks, pressing an urgent need for quality control in crowdsourcing. Considering that in many cases the requestor presents the price for each crowdsourced task at first and then the worker performs the claimed job with an adjustable effort level resulting in different completion quality of the job, we model this sort of interactions between the requestor and any worker as a two-player sequential game. In order to achieve the goal of controlling the quality of worker’s submissions, different from the costly state-of-the-art solutions with additional operations or procedures, we propose a systematic idea that takes advantage of the market power to embed the quality control into the crowdsourcing process. Specifically, we employ two sequential games to model the interactions between the requestor and the workers, with one considering binary strategies while the other taking continuous strategies. Accordingly, two incentive algorithms for improving the job quality are proposed to tackle the sequential crowdsourcing dilemmas. Both algorithms are based on the sequential zero-determinant (SZD) strategy modified from the classical ZD strategy. Such a revision not only provides a theoretical basis for designing our incentive algorithms, but also enlarges the application scope of the ZD strategy. Our incentive algorithms have the following desired features: 1) they leverage economics theory to train the workers to behave nicely for better job quality instead of filtering out the unprofessional ones; 2) no extra costs are incurred in the long run; and 3) fairness is guaranteed as even the requestor with the SZD strategy dominates the game, its utility cannot be increased by arbitrarily penalizing the innocent worker.Third, as a typical crowdsourcing application, mobile crowdsensing exerts the poten- tial of widespread sensors embedded in mobile devices, attracting more attention in recent. With the spatial diversity and the temporal dynamics leading to heterogeneous worker sup- plies in mobile crowdsensing, it is difficult for the requestor to utilize a homogeneous pricing strategy to achieve a cost-efficient deal from a systematic viewpoint. Therefore, a cost-efficient deal calls for a cost-efficient pricing strategy, boosting the whole sensing quality with less operation cost. However, the state-of-the-art studies ignore the dual cost- efficient demands of large-scale sensing tasks. Hence, we propose a combinatorial pinning zero-determinant (CPZD) strategy, which empowers the requestor to utilize a single strategy within its feasible range to minimize the total expected utilities of the workers throughout all sensing regions for each time interval, without being affected by the strategies of the workers. Through turning the worker-customized strategy to an interval-customized one, the proposed CPZD strategy reduces the number of pricing strategies required by the requestor from O(n3) to O(n). Besides, it extends the application scenarios of the classical ZD strategy from two-player simultaneous-move games to multiple-heterogeneous-player sequential-move ones, where a leader can solely determine the linear relationship of their expected utilities. Such an extension enriches the theoretical hierarchy of ZD strategies, broadening their application scope. Extensive simulations based on real-world data verify the effectiveness and efficiency of the proposed scheme.
|La vignette||Titre||Date de téléchargement||Visibilité||actes|