Crowdsourcing Pareto-Optimal Object Finding by Pairwise Comparisons
This addresses the problem of efficient group decision-making in applications like public opinion collection, though it is incremental as it builds on prior crowdsourcing query studies.
The paper tackled the problem of finding all Pareto-optimal objects via crowdsourced pairwise comparisons, aiming to minimize the number of questions asked; it achieved orders of magnitude reductions in questions compared to brute-force methods, with the most efficient algorithm showing close-to-optimal performance.
This is the first study on crowdsourcing Pareto-optimal object finding, which has applications in public opinion collection, group decision making, and information exploration. Departing from prior studies on crowdsourcing skyline and ranking queries, it considers the case where objects do not have explicit attributes and preference relations on objects are strict partial orders. The partial orders are derived by aggregating crowdsourcers' responses to pairwise comparison questions. The goal is to find all Pareto-optimal objects by the fewest possible questions. It employs an iterative question-selection framework. Guided by the principle of eagerly identifying non-Pareto optimal objects, the framework only chooses candidate questions which must satisfy three conditions. This design is both sufficient and efficient, as it is proven to find a short terminal question sequence. The framework is further steered by two ideas---macro-ordering and micro-ordering. By different micro-ordering heuristics, the framework is instantiated into several algorithms with varying power in pruning questions. Experiment results using both real crowdsourcing marketplace and simulations exhibited not only orders of magnitude reductions in questions when compared with a brute-force approach, but also close-to-optimal performance from the most efficient instantiation.