Minimizing Time-to-Rank: A Learning and Recommendation Approach

1 Introduction

Eliciting preferences in the form of rankings over a set of alternatives is a common task in social choice, crowdsourcing, and in daily life. For example, the organizer of a meeting might ask the participants to rank a set of time-slots based on their individual schedules. Likewise, in an election, voters might be required to rank a set of candidates in order of preference.

Over the years, computerized systems have been increasingly used in carrying out preference elicitation tasks such as the ones mentioned above. Indeed, recently there has been a proliferation of online voting platforms such as CIVS, OPRA, Pnyx, RoboVote, and Whale4 . 1 In many of these platforms,

∗Contact Author

1 CIVS (https://civs.cs.cornell.edu/), OPRA (opra.io), Pnyx (https://pnyx.dss.in.tum.de/), RoboVote (http://robovote.org/), Whale4 (https://whale.imag.fr/).

a user is presented with an arbitrarily ordered list of alternatives, and is asked to shuffle them around in-place using drag-and-drop operations until her desired preference ordering is achieved. Figure 1 illustrates the use of drag-and-drop operations to sort a list of numbers in descending order.

Our focus in this work is on time-to-rank, i.e., the time it takes for a user to arrive at her desired ranking, starting from a ranking suggested by the platform and using only drag-anddrop operations. We study this problem from the perspective of the voting platform that wants to recommend an optimal initial ranking to the user (i.e., one that minimizes time-to-rank). Time to accomplish a designated task is widely considered as a key consideration in the usability of automated systems [Bevan et al., 2015; Albert and Tullis, 2013], and serves as a proxy for user effort. Indeed, 'time on task' was identified as a key factor in the usability and efficiency of computerized voting systems in a 2004 report by NIST to the U.S. Congress for the Help America Vote Act (HAVA) [Laskowski et al., 2004].

Note that the initial ranking suggested by the platform can have a significant impact on the time spent by the user on the ranking task. Indeed, if the user's preferences are known beforehand, then the platform can simply recommended it to her and she will only need to verify that the ordering is correct. In practice, however, users' preferences are often unknown. Furthermore, users employ a wide variety of ranking strategies, and based on their proficiency with the interface, users can have very different drag-and-drop times. All these factors make the task of predicting the time-to-rank and finding an optimal recommendation challenging and non-trivial.

We emphasize the subtle difference between our problem and that of preference elicitation. The latter involves repeatedly asking questions to the users (e.g., pairwise comparisons between alternatives) to gather enough information about their preferences. By contrast, our problem involves a one-shot recommendation followed by a series of drag-and-drop operations until the desired ranking is achieved. There is an extensive literature on preference elicitation [Conitzer and Sandholm, 2002; Blum et al., 2004; Boutilier, 2013; Busa-Fekete et al., 2014; Soufiani et al., 2013; Zhao et al., 2018]. Yet, somewhat surprisingly, the problem of recommending a ranking that minimizes users' time has received little attention. Our work aims to address this gap.

Our Contributions

We make contributions on three fronts:

• On the conceptual side, we propose the problem of minimizing time-to-rank and outline a framework for addressing it (Figure 2).
• On the theoretical side, we formulate the optimization problem of finding a recommendation to minimize timeto-rank (Section 4). We show that this problem is NPhard, even under highly restricted settings (Theorem 3). We complement the intractability results by providing a number of exact (Theorem 2) and approximation algorithms (Theorems 4 to 6) for special cases of the problem.
• We use experimental analysis to motivate our modeling assumptions as well as to justify the effectiveness of our approach (Section 5). Our experiments on MTurk reveal two insights about user behavior (Section 5.1): (1) The ranking strategies of real-world users closely resemble insertion/selection sort, and (2) the drag-and-drop time of an alternative varies linearly with the distance moved. We find that a simple adaptive strategy (based on Borda count voting rule) can reduce time-to-rank by up to 50% compared to a random strategy (Section 5.2), validating the usefulness of the proposed framework.

1.1 Overview of Our Framework

Figure 2 illustrates the proposed framework which consists of three key steps. In Step 1, we learn user preferences from historical data by developing a statistical ranking model, typically in the form of a distribution D over the space of all rankings (refer to Section 2 for examples of ranking models). In Step 2, which runs in parallel to Step 1, we learn user behavior; in particular, we identify their sorting strategies (Section 3.1) as well as their drag-and-drop times (Section 3.2). Together, these two components define the time function which models the time taken by a user in transforming a given initial ranking σ into a target ranking τ , denoted by time(σ, τ). The ranking model D from Step 1 and the time function from Step 2 together define the recommendation problem in Step 3, called (D,w)-RECOMMENDATION (the parameter w is closely related to the time function; we elaborate on this below). This is the optimization problem of computing a ranking σ that minimizes the expected time-to-rank of the user, i.e., minimizes Eτ∼D[time(σ, τ)]. The user is then recommended σ, and her preference history is updated.

The literature on learning statistical ranking models is already well-developed [Guiver and Snelson, 2009; Awasthi et al., 2014; Lu and Boutilier, 2014; Zhao et al., 2016; Xia, 2019]. Thus, while this is a key ingredient of our framework (Step 1), our work only focuses on Steps 2 and 3 concerning user behavior and the recommendation problem.

Recall that the time function defines the time taken by a user in transforming a given ranking σ into a target ranking τ . For a user who follows a fixed sorting algorithm (e.g., insertion or selection sort), the time function can be broken down into (1) the number of drag-and-drop operations suggested by the sorting algorithm, and, (2) the (average) time taken for each drag-and-drop operation by the user. As we will show in Lemma 1 in Section 3.1, point (1) above is independent of the choice of the sorting algorithm. Therefore, the time function can be equivalently defined in terms of the weight function w, which describes the time taken by a user, denoted by w(ℓ), in moving an alternative by ℓ positions via a drag-and-drop operation. For this reason, we use w in the formulation of (D, w)-RECOMMENDATION.

Applicability. Our framework is best suited for users who have already formed their preferences, so that the recommended ranking does not bias their preferences. This is a natural assumption in some applications, such as in the meeting organization example in Section 1. In general, however, it is possible that a user, who is undecided between options A and B, might prefer A over B if presented in that order by the recommended ranking. Investigating such biases (a.k.a. "framing effect") is an interesting direction for future work.

Additional related work. Our work is related to the literature on inferring a ground truth ordering from noisy information [Braverman and Mossel, 2008], and aggregating preferences by minimizing some notion of distance to the observed rankings such as the total Kendall's Tau distance [Procaccia and Shah, 2016]. Previous work on preference learning and learning to rank can also be integrated in our framework [Liu, 2011; Lu and Boutilier, 2014; Khetan and Oh, 2016; Agarwal, 2016; Negahban et al., 2017; Zhao and Xia, 2018].

2 Preliminaries

Let A = {a1, . . . , am} denote a set of m alternatives, and let L(A) be the set of all linear orders over A. For any σ ∈ L(A), ai ≻σ aj denotes that ai is preferred over aj under σ, and let σ(k) denote the kth most preferred alternative in σ. A set of n linear orders {σ(1) , . . . , σ(n) } is called a preference profile.

Definition 1 (Kendall's Tau distance; [Kendall, 1938]). Given two linear orders σ, σ′ ∈ L(A), the Kendall's Tau distance dkt(σ, σ′ ) is the number of pairwise disagreements between σ and σ′ . That is, dkt(σ, σ′ ) := ∑ai,aj∈A 1[aj ≻σ′ ai and ai ≻σ aj], where 1 is the indicator function.

Definition 2 (Plackett-Luce model; [Plackett, 1975; Luce, 1959]). Let θ := (θ1, . . . , θm) be such that θi ∈ (0, 1) for each i ∈ [m] and ∑i∈[m] θi = 1. Let Θ denote the corresponding parameter space. The Plackett-Luce (PL) model parameterized by θ ∈ Θ defines a distribution over the set of linear orders L(A) as follows: The probability of generating σ := (ai1 ≻ ai2 ≻ . . . ≻ aim ) is given by

More generally, a k-mixture Plackett-Luce model (k-PL) is parameterized by {γ (ℓ) , θ(ℓ) }kℓ=1 , where ∑kℓ=1 γ (ℓ) = 1, γ (ℓ) ≥ 0 for all ℓ ∈ [k], and θ(ℓ) ∈ Θ for all ℓ ∈ [k]. The probability of generating σ ∈ L(A) is given by Pr(σ|{γ (ℓ) , θ(ℓ) }kℓ=1 ) = ∑kℓ=1 γ (ℓ) Pr(σ|θ(ℓ) ).

Definition 3 (Mallows model; [Mallows, 1957]). The Mallows model (MM) is specified by a reference ranking σ∗ ∈

L(A) and a dispersion parameter φ ∈ (0, 1]. The probability of generating a ranking σ is given by Pr(σ|σ∗ , φ) = φdkt (σ,σ∗ ) Z , where Z = ∑σ′∈L(A) φdkt(σ′ ,σ∗ ) .

More generally, a k-mixture Mallows model (k-MM) is parameterized by {γ (ℓ) , σ∗ (ℓ) , φ(ℓ)}kℓ=1 , where ∑kℓ=1 γ (ℓ) = 1, γ (ℓ) ≥ 0 for all ℓ ∈ [k], and σ∗ (ℓ) ∈ L(A), φ(ℓ) ∈ (0, 1] for all ℓ ∈ [k]. The probability of generating σ ∈ L(A) is given by Pr(σ|{γ (ℓ) , σ∗ (ℓ) , φ(ℓ)}kℓ=1 ) = ∑kℓ=1 γ (ℓ) Pr(σ|σ∗ (ℓ) , φ(ℓ)).

Definition 4 (Uniform distribution). Under the uniform distribution (Unif) supported on a preference profile {σ(i) }ni=1 , the probability of generating σ ∈ L(A) is 1n if σ ∈ {σ(i) }ni=1 and 0 otherwise.

3 Modeling User Behavior

In this section, we will model the time spent by the user in transforming the recommended ranking σ into the target ranking τ . Our formulation involves the sorting strategy of the user (Section 3.1) as well as her drag-and-drop time (Section 3.2).

3.1 Sorting Algorithms

A sorting algorithm takes as input a ranking σ ∈ L(A) and performs a sequence of drag-and-drop operations until the target ranking is achieved. At each step, an alternative is moved from its current position to another (possibly different) position and the current ranking is updated accordingly. Below we will describe two well-known examples of sorting algorithms: selection sort and insertion sort. Let σ(k) denote the current list at time step k ∈ {1, 2, . . . } (i.e., before the sorting operation at time step k takes place). Thus, σ(1) = σ. For any σ ∈ L(A), define the k-prefix set of σ as Pk(σ) := {σ(1), σ(2), . . . , σ(k)} (where P0(σ) := ∅) and corresponding suffix set as Sk(σ) := A \ Pk(σ).

Selection sort. Let ai denote the most preferred alternative according to τ in the set Sk-1(σ(k) ). At step k of selection sort, the alternative ai is promoted to a position such that the top k alternatives in the new list are ordered according to τ. Note that this step is well-defined only under the sorted-prefix property, i.e., at the beginning of step k of the algorithm, the alternatives in Pk-1(σ(k) ) are sorted according to τ. This property is maintained by selection sort.

Insertion sort. Let ai denote the most preferred alternative in Sk-1(σ(k) ) according to σ(k) . At step k of insertion sort, the alternative ai is promoted to a position such that the top k alternatives in the new list are ordered according to τ . Note that this step is well-defined only under the sorted-prefix property, which is maintained by insertion sort.

Sorting algorithms. In this work, we will be concerned with sorting algorithms that involve a combination of insertion and selection sort. Specifically, we will use the term sorting algorithm to refer to a sequence of steps s1, s2, . . . such that each step sk corresponds to either selection or insertion sort, i.e., sk ∈ {SEL,INS} for every k. If sk = SEL, then the algorithm promotes the most preferred alternative in Sk-1(σ(k) ) (according to τ) to a position such that the top k alternatives in the new list are ordered according to τ. If sk = INS, then the algorithm promotes the most preferred alternative in Sk-1(σ(k) ) (according to σ(k) ) to a position such that the top k alternatives in the new list are ordered according to τ . For example, in Figure 1, starting from the recommended list at the extreme left, the user performs a selection sort operation (promoting 19 to the top of the current list) followed by an insertion sort operation (promoting 30 to its correct position in the sorted prefix {19, 22, 40}) followed by either selection or insertion sort operation (promoting 23 to its correct position). We will denote a generic sorting algorithm by A and the class of all sorting algorithms by A.

Count function. Given a sorting algorithmA, a source ranking σ ∈ L(A) and a target ranking τ ∈ L(A), the count function f σ→τ A : [m-1] →Z+∪{0} keeps track of the number of drag-and-drop operations (and the number of positions by which some alternative is moved in each such operation) during the execution of A. Formally, f σ→τ A (ℓ) is the number of times some alternative is 'moved up by ℓ positions' during the execution of algorithm A when the source and target rankings are σ and τ respectively. 2 For example, let A be insertion sort, σ = (d, c, a, b), and τ = (a, b, c, d). In step 1, the user considers the alternative d and no move-up operation is required. In step 2, the user promotes c by one position (since c ≻τ d) to obtain the new list (c, d, a, b). In step 3, the user promotes a by two positions to obtain (a, c, d, b). Finally, the user promotes b by two positions to obtain the target list (a, b, c, d). Overall, the user performs one 'move up by one position' operation and two 'move up by two positions' operations. Hence, f σ→τ A (1) = 1, f σ→τ A (2) = 2, and f σ→τ A (3) = 0. We will write #moves to denote the total number of drag-and-drop operations performed during the execution of A, i.e., #moves = ∑m-1 ℓ=1 f σ→τ A (ℓ).

Remark 1. Notice the difference between the number of dragand-drop operations (#moves) and the total distance covered (i.e., the number of positions by which alternatives are moved). Indeed, the above example involves three drag-anddrop operations (#moves = 3), but the total distance moved is

2 Notice that we do not keep track of which alternative is moved by ℓ positions. We believe it is reasonable to assume that moving a1 up by ℓ positions takes the same time as it does for a2. Also, we do not need to define the count function for move down operations as neither selection sort nor insertion sort will ever make such a move.

0 + 1 + 2 + 2 = 5. The latter quantity is equal to dkt(σ, τ ).

Lemma 1. For any two sorting algorithms A,A′ ∈ A, any σ, τ ∈ L(A), and any ℓ ∈ [m- 1], f σ→τ A (ℓ) = f σ→τ A′ (ℓ).

In light of Lemma 1, we will hereafter drop the subscript A and simply write f σ→τ instead of f σ→τ A . All missing proofs can be found in the full version [Li et al., 2019].

3.2 Drag-and-Drop Time

Weight function. The weight function w : [m-1] →R≥0 models the time taken for each drag-and-drop operation; specifically, w(ℓ) denotes the time taken by the user in moving an alternative up by ℓ positions. 3 Of particular interest to us will be the linear weight function wlin(ℓ) = ℓ for each ℓ ∈ [m - 1] and the affine weight function waff(ℓ) = cℓ + d for each ℓ ∈ [m - 1] and fixed constants c, d ∈ N.

Time function. Given the count function f σ→τ and the weight function w, the time function is defined as their inner product, i.e., timew(σ, τ) = 〈f σ→τ ,w〉 = ∑m-1 ℓ=1 f σ→τ (ℓ) · w(ℓ).

Theorem 1 shows that for the linear weight function wlin, time is equal to the Kendall's Tau distance, and for the affine weight function, time is equal to a weighted combination of Kendall's Tau distance and the total number of moves.

Theorem 1. For any σ, τ ∈ L(A), timewlin (σ, τ) = dkt(σ, τ) and timewaff (σ, τ) = c · dkt(σ, τ) + d · #moves.

4 Formulation of the Recommendation Problem and Theoretical Results

We model the recommendation problem as the following computational problem: Given the preference distribution D of the user and her time function (which, in turn, is determined by the weight function w), find a ranking that minimizes the expected time taken by the user to transform the recommended ranking σ into her preference τ .

Definition 5 ((D, w)-RECOMMENDATION). Given a distribution D over L(A), a weight function w, and a number δ ∈ Q, does there exist σ ∈ L(A) so that Eτ∼D[timew(σ, τ)] ≤ δ?

We will focus on settings where D is Plackett-Luce, Mallows, or Uniform, and w ∈ {Linear, Affine, General}. Note that if the quantity Eτ∼D[timew(σ, τ)] can be computed in polynomial time for a given distribution D and weight function w, then (D,w)-RECOMMENDATION is in NP.

Our computational results for (D,w)-RECOMMENDATION are summarized in Table 1. We show that this problem is NP-hard, even when the weight function is linear (Theorem 3). On the algorithmic side, we provide a polynomial-time approximation scheme (PTAS) and a 5-approximation algorithm for the linear weight function (Theorems 4 and 5), and an approximation scheme for non-linear weights (Theorem 6).

Theorem2 (Exact Algorithms). (D,w)-RECOMMENDATION is solvable in polynomial time when w is linear and D is either (a) k-mixture Plackett-Luce (k-PL) with k = 1, (b) kmixture Mallows model (k-MM) with k = 1, or (c) a uniform distribution with support size n ≤ 2.

3 Here, 'time taken' includes the time spent in thinking about which alternative to move as well as actually carrying out the move.

Theorem 3 (Hardness results). (D,w)-RECOMMENDATION is NP-complete even when w is linear and D is either (a) kmixture Plackett-Luce model (k-PL) for k = 4, (b) k-mixture Mallows model (k-MM) for k = 4, or (c) a uniform distribution over n = 4 linear orders.

Theorem 4 (PTAS). (D,w)-RECOMMENDATION admits a polynomial time approximation scheme (PTAS) when w is linear and D is either (a) k-mixture Plackett-Luce model (k-PL) for k ∈ N, (b) k-mixture Mallows model (k-MM) for k ∈ N, or (c) a uniform distribution (Unif).

The PTAS in Theorem 4 is quite complicated and is primarily of theoretical interest (indeed, for any fixed ε > 0, the running time of the algorithm is m2 ˜O(1/ε) , making it difficult to be applied in experiments). A simpler and more practical algorithm (although with a worse approximation) is based on the well-known Borda count voting rule (Theorem 5).

Theorem 5 (5-approximation). (D,w)-RECOMMENDATION admits a polynomial time 5-approximation algorithm when w is linear and D is either (a) k-mixture Plackett-Luce model (k-PL) for k ∈ N, (b) k-mixture Mallows model (k-MM) for k ∈ N, or (c) a uniform distribution (Unif).

Our next result (Theorem 6) provides an approximation guarantee for (D,w)-RECOMMENDATION that applies to nonlinear weight functions, as long as they are "close" to the linear weight function in the following sense:

Definition 6 (Closeness-of-weights). A weight function w is said to be (α, β)-close to another weight function w′ if there exist α, β ≥ 1 such that for every ℓ ∈ [m- 1], we have

For any (possibly non-linear) weight function w that is (α, β) close to the linear weight function wlin, Theorem 6 provides an αβ-approximation scheme for (D,w)- RECOMMENDATION.

Theorem 6 (Approximation for general weights). Given any ε > 0 and any weight function w that is (α, β)-close to the linear weight function wlin, there exists an algorithm that runs in time m2 ˜O(1/ε) and returns a linear order σ such that

Remark 2. Notice that the PTAS of Theorem 4 is applicable for any affine weight function waff = c ·wlin +d for some fixed constants c, d ∈ N. As a result, the approximation guarantee of Theorem 6 also extends to any weight function that is (α, β)- close to some affine weight function.

5 Experimental Results

We perform two sets of experiments on Amazon Mechanical Turk (MTurk). The first set of experiments (Section 5.1) is aimed at identifying the sorting strategies of the users as well as a model of their drag-and-drop behavior. The observations from these experiments directly motivate the formulation of our theoretical model, which we have already presented in Section 4. The second set of experiments (Section 5.2) is aimed at evaluating the practical usefulness of our approach.

In both sets of experiments, the crowdworkers were asked to sort in increasing order randomly generated lists of numbers between 0 and 100. Sections 5.1 and 5.2 provide details about the length of the lists and how they are generated.

In each experiment, the task length was advertised as 10 minutes, and the payment offered was $0.25 per task. The crowdworkers were provided a user interface (see Figure 1) that allows for drag-and-drop operations. To ensure data quality, we removed those workers from the data who failed to successfully order the integers more than 80% of the time, or did not complete all the polls. We also removed the workers with high variance in their sorting time; in particular, those with coefficient of variation above the 80th percentile. The reported results are for the workers whose data was retained.

5.1 Identifying User Behavior

To identify user behavior, we performed two experiments: (a) RANK10, where each crowdworker participated in 20 polls, each consisting of a list of 10 integers (between 0 and 100) generated uniformly at random, and (b) RANK5, which is a similar task with 30 polls and lists of length 5. In each poll, we recorded the time taken by a crowdworker to move an alternative (via drag-and-drop operation) and the number of positions by which the alternative was moved. After the initial pruning (as described above), we retained 9840 polls submitted by 492 workers in the RANK10 experiment, and 10320 polls submitted by 344 workers retained in the RANK5 experiment. Table 2 summarizes the aggregate statistics. Our observations are discussed below.

Sorting behavior. Our hypothesis regarding the ranking behavior of human crowdworkers was that they use (some combination of) natural sorting algorithms such as selection sort or insertion sort (Section 3.1). To test our hypothesis, we examined the fraction of the drag-and-drop operations that coincided with an iteration of selection/insertion sort. (Given a ranking σ, a drag-and-drop operation on σ coincides with selection/insertion sort if the order of alternatives resulting from the drag-and-drop operation exactly matches the order of alternatives when one iteration of either selection or insertion sort is applied on σ.) We found that, on average, 2.21 2.91 = 76% of all drag-and-drop operations in RANK5 (and 5.09 7.69 = 66.2% in the RANK10) coincided with selection/insertion sort.

Drag-and-drop behavior. To identify the drag-and-drop behavior of the users, we plot the time-to-rank as a function of the total number of positions by which the alternatives are moved in each poll (Figure 3). Recall from Remark 1 that for an ideal user who uses only insertion/selection sort, the latter quantity is equal to dkt(σ, τ). Our hypothesis was that the sorting time varies linearly with the total number of dragand-drop operations (#moves) and the Kendall's Tau distance (dkt(σ, τ)). To verify this, we used linear regression with timeto-rank (or sorting time) as the target variable and measured the mean squared error (MSE) using 5-fold cross-validation Dataset Avg. MSE √Avg. MSE Avg. Sorting Time Number of users based on their best-fit model for three different choices of independent variables: (1) Only dkt, (2) only #moves, and (3) both dkt and #moves. For each user, we picked the model with the smallest MSE (see Table 3 for the resulting distribution of the number of users). We found that the predicted drag-and-drop times (using the best-fit model for each user) are, on average, within 6.56 24.41 = 26.8% of the observed times for RANK10 and within 2.78 7.75 = 35.8% for RANK5.

5.2 Evaluating the Proposed Framework

To evaluate the usefulness of our framework, we compared a random recommendation strategy with one that forms an increasingly accurate estimate of users' preferences with time. Specifically, we first fix the ground truth ranking of 10 alternatives consisting of randomly generated integers between 0 and 100. Each crowdworker then participates in two sets of 10 polls each. In one set of polls, the crowdworkers are provided with initial rankings generated by adding independent Gaussian noise to the ground truth (to simulate a random recommendation strategy), and their sorting times are recorded.

In the second set of polls, the recommended set of alternatives is the same as under the random strategy but ordered order to a Borda ranking. Specifically, the ordering in the kth iteration is determined by the Borda ranking aggregated from the previous k - 1 iterations.

Figure 4 shows the average sorting time of the crowdworkers as a function of the index of the polls under two different noise settings: std. dev. = 10 and std. dev. = 20.

Figure 4: Relationship between sorting time and the number of polls completed by the users for std dev=10 (left) and std dev=20 (right).

We observe that Borda recommendation strategy (in green) provides a significant reduction in the sorting time of the users compared to the random strategy (in blue). Indeed, the sorting time of the users is reduced by up to 50%, thus validating the practical usefulness of our framework. Note that the reduction in sorting time is not due to increasing familiarity with the interface. This is because the average sorting time for the random strategy remains almost constant throughout the duration of the poll.

6 FutureWork

Our work opens up a number of directions for future research. First, it would be interesting to analyze the complexity of the recommendation problem for other distance measures, e.g., Ulam distance. Second, it would be interesting to analyze the effect of cognitive biases such as the framing effect [Tversky and Kahneman, 1981] and list position bias [Lerman and Hogg, 2014] on the recommendation problem. Progress in this direction can, in turn, have implications on the fairness of recommendation algorithms.

Acknowledgments

We are grateful to IJCAI-19 reviewers for their helpful comments. This work is supported by NSF #1453542 and ONR #N00014-17-1-2621.