Abstract
Consider the following problem faced by an online
voting platform: A user is provided with a list of alternatives, and is asked to rank them in order of preference using only drag-and-drop operations. The
platform’s goal is to recommend an initial ranking
that minimizes the time spent by the user in arriving
at her desired ranking. We develop the first optimization framework to address this problem, and
make theoretical as well as practical contributions.
On the practical side, our experiments on Amazon
Mechanical Turk provide two interesting insights
about user behavior: First, that users’ ranking strategies closely resemble selection or insertion sort, and
second, that the time taken for a drag-and-drop operation depends linearly on the number of positions
moved. These insights directly motivate our theoretical model of the optimization problem. We
show that computing an optimal recommendation
is NP-hard, and provide exact and approximation
algorithms for a variety of special cases of the problem. Experimental evaluation on MTurk shows that,
compared to a random recommendation strategy, the
proposed approach reduces the average time-to-rank
by up to 50%