  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.

Artificial Intelligence;Databases