Efficient Crowdsourced Pareto-Optimal Queries Over Partial Orders With Quality Guarantee
Bo Yin, Xuetao Wei · IEEE Transactions on Emerging Topics in Computing · 2020
The development of crowdsourcing marketplaces has leveraged the power of human intelligence into tackling computationally challenging problems. Pareto-optimal queries become more and more popular in subtle and comprehensive decision support due to the increasingly complex comparison criteria, e.g., partial orders. However, none of previous work focused on efficient crowdsourced Pareto-optimal queries over partial orders with minimum monetary cost and quality guarantee with a confidence level. In this article, we propose a cost-efficient framework to find Pareto-optimal objects with minimum monetary cost and quality guarantee with a confidence level. We first propose a dynamic-status judgment model based on Student’s$t$-distribution, which gives a confidence interval of the judgment to ensure the quality of pairwise comparisons while minimizing the number of crowdsourcers required for each pairwise comparison. We then propose a filtering-verification scheme that takes full advantage of transitivity to avoid unnecessary crowdsourcing comparisons, which significantly reduces the number of crowdsourcing pairwise comparisons. The results of our extensive experiments demonstrate that the dynamic-status judgment model requires a small number of crowdsourcers for a pairwise comparison while maintaining the accuracy, and the filtering-verification scheme can reduce the number of pairwise comparisons by 40 percent in average.