On A Mallows-type Model For (Ranked) Choices
Authors: Yifan Feng
Yuxuan Tang
Venue: NeurIPS 2022 Accept (2022)
Keywords: probabilistic ranking models
Mallows model
preference learning
choice modeling
top-$k$ list

Abstract: We consider a preference learning setting where every participant chooses an ordered list of $k$ most preferred items among a displayed set of candidates. (The set can be different for every participant.) We identify a distance-based ranking model for the population's preferences and their (ranked) choice behavior. The ranking model resembles the Mallows model but uses a new distance function called Reverse Major Index (RMJ). We find that despite the need to sum over all permutations, the RMJ-based ranking distribution aggregates into (ranked) choice probabilities with simple closed-form expression. We develop effective methods to estimate the model parameters and showcase their generalization power using real data, especially when there is a limited variety of display sets.

On A Mallows-type Model For (Ranked) Choices
Yifan Feng
Yuxuan Tang
Department Analytics and Operations NUS Business School
Institute Operations Research and Analytics National University of Singapore yuxuan tang@u. aus.edu
yifan fenggnus. edu.
Abstract
We consider a preference learning setting where every participant chooses an ordered list of k most preferred items among a displayed set of candidates. (The set can be different for every participant.) We identify a cestance-basee ranking model for the population's 's preferences and their (ranked) choice behavior. The ranking model resembles the Mallows model but uses a new distance function called Reverse Major Index (RM.).. We find that despite the need to sum over all permutations, the RMJ-based ranking distribution aggregates into (ranked) choice probabilities with simple closed- form expression. We develop effective methods estimate the model parameters and showcase their generalization power using real data, especially when there limited variety of display sets.
Introduction
How to aggregate the population's preferences from their (ranked) choices out of different choice sets? This question is interest to many communities, such as economics, business, and computer science. A concrete setting is platform that wishes to learn customer preferences over a universe of n product prototypes. The platform is able to display different subsets of versions to different customers, who then provide feedback in the form of a top-k ranked list of their most preferred items within the subset they see (hereafter referred to as "ranked choices")."
The population's is (ranked) choice behavior could be summarized as a (ranked) choice model Pr(Tu|S). which specifies the probability that randomly drawn participant choosing a top-k list Jy. from the display set S. An cconomically rationalizable and yet very general way to model (ranked) choices to use probabilistic ranking models. That is, given a probability distribution À over preference rankings, PT(лх) (8) equals the probability that a randomly drawn participant would place as the top-k positions among the items in
popular family of ranking models is distance-based which is the conceptual analog of Gaussian distribution for scalars; see [1]. A distance-based ranking model is specified by modal (central) ranking x= and a dispersion parameter E (0, 1). Given a ranking ग, its probability of being sampled proportional to gd(a" ,s))_ Here d(=1, T2) is a distance function that describes the discrepancy of ranking गi from æ2. and different distance functions lead to different models. The most popular distance-based ranking model is the Mallows model ([2]), which uses the Kendall-Tau distance as its distance function. It has been studied extensively the literature regarding topics such as sampling, estimation from sampled (partial) rankings, and learning in a Mallows mixture setting: see [3] and references therein. Due to its popularity and the fact that every distance-brug based ranking model only differs from the Mallows by distance function, we will also refer to distance-basee ranking model as Mallows-type model interchangeably in the sequel.
If 1 1, each participant is asked to choose the most preferred candidate. That effectively reduces to (single) choice, which is a feedback structure extensively studied in the choice modeling literature.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Maylows-type models could be used as "kernels" to "smooth out" the distribution over rankings. As such, they could help mitigate the overfitting issues of generic (i.e., nonparametric) ranking models, which are typically overparameterized. Yet, Mallows models can be highly expressive in mixture setting: mixture of Mallows-type models can approximate any probability distribution over rankings by an arbitrary precision (as q tends to zero and the number of clusters tends to infinity). Therefore, the Mallows-tyr model family is a helpful tool to balance capturing (complex) preference heterogeneity across individuals and regularizing the ranking distribution for better out-of-sample predictions. representative work is by Antoine et al. [4], who use the Mallows model to aggregate customer preferences from their choices (i.e., k 1).
Despite the theoretical elegance, the main challenge in applying Male ranking models to (ranked) choice modeling is analytical and computational tractability. More specifically, Pr(Tx|() calculated from summation over all rankings subject to nontrivial conditions. Therefore, even if Mallows-type ranking model has a simple structure for X, the resulting choice probabilities (Pr(*e[S)) can be difficult to obtain even when k 1. The state-of-art results are obtained by Antoine et al. [4], who develop polynomial-inne numerical algorithms to compute [Pr(T*[[)) for = under the Mallows model. The estimation problem even more difficult, which involves finding the central ranking x² and dispersion parameters g that best explain the (ranked) choice data. To the best of our knowledge, no effective methods to estimate any Mallows-type ranking model from (ranked) choice data are known. (Perhaps the best method to date is again by Antoine et al. [4]. who use a "Mallows smoothing" heuristic to conduct the estimation when k = 1, which we will discuss later.)
Summary of results and contributions. This paper identifies and studies a new distance-based (i.e., Mallows-type) ranking model. It is the same as the Mallows model except that it builds on new distance function (i.c., smoothing kernel), which we call reverse major index (RMJ). Unlike the Mallows model's Kendall-Tau distance (which weighs all pairwise disagreements equally), RMJ puts more weight on top-position deviations.
The R.MJ- ranking model is small conceptual deviation from the Mallows model (and, in particular, enjoys the desired properties mentioned above, such as rationalizability, smoothing, and expressive power); see Section 2. However, this twist brings sigmificant ad advantage in both analytical and computational simplicity. Specifically, we solve list of problems under the RMJ-based ranking distribution. That includes:
Characterizing (ranked) choice probabilities: Given & 2 1, calculating (Pr(*x(S)):
Sampling: Given A: 2 1, efficiently sampling a top-k list m&:
Parameter learning: Estimating the central ranking π² and dispersion parameter q from the (ranked) choice data through maximum likelihood estimator (MLE) formulation;
Learning in a mixture setting: Assuming that there are multiple clusters of participant preferences, learning the central ranking and dispersion parameter for each cluster from choice data.
The solutions to the problems above can be implemented relatively casily. First, we are able to obtain (Pr(**[S)} in simple and closed-form expressions for all 1: 2 1; see Theorems 1 and This is in contrast to, say, its counterpart for the Mallows model ([4]), and we view it as our main theoretical achievement. Second, the sampling can be done in Onkk) time directly; see Lemma Third, the estimation problem can be reduced to well-studied monking-agrregation-yyy see (5) and Theorem 5. Many off-the-shelf tools are available. For example, it admits a polynomial- time approximation scheme (PTAS) and can be practically solved via linear integer programming formulation. The estimation is guaranteed to recover the model parameters asymptotically under mild conditions on the coverage of display sets; see Theorem 2. This stands in contrast to Mallows Smoothing by [4], which cannot recover the Mallows central ranking even under sufficient coverage; see Theorem 3. Finally, the learning problem in mixture setting can be solved using the standard Expectation SoppetationnMMaximzziinn Maxxmizaaiinnn (EM) algorithm.
formulation;
We demonstrate the practical effectiveness of our methodology on two data sets on customer prefer- ence over different types of sushi. When k: 1, we compare it with two representative ranking-based choice models: one based on the Mallows and the other on Plackett-Luce (which leads to the Multi- nomial Logit choice model). Our tools display superb generalization power, especially when there is a limited variety of display sets in the choice data. When & > 1, we demonstrate the robustness

---

of the methodology. (It is difficult to find direct comparisons for prediction power.) Specifically, as long as the underlying population keeps the same, different top-k lists aggregate into the same central rankings. We also show that our methodology can handle relatively large number of items (n = 100) by achieving high precision solutions (< 2% optimality gap) in a reasonable time (< minute solving time).
Related literature. Our paper is most closely related to the (extensive) literature on Mallows-type ranking models and their applications to preference and choice modeling (e.g., [1, 6, 7, 9, 4, 10] to name a few.) Besides the new distance function and tractability results explained above, the most notable difference of this paper is the feedback structure. In our paper, every participant chooses from an arbitrary display set (as opposed to pairwise or the full display set only), and their feedback is in the form of top-k ranked list (as opposed to single choices, e.g., [11, 12], or full rankings). To the best of our knowledge, the combination of both generalities makes the setting the first of its kind, 2 is also worth mentioning that the analytical and computational simplicity of our model makes it convenient building block for subsequent optimization problems (e.g., new product introduction). is an advantage that many common methods (e.g., Monte- Corto algorithms) do not have.
Also related is the literature on learning to rank (e.g.. [14, 15]). We wish to stress that we do not merely fit a ranking from the data but also the uncertainty quantification of the estimate (and the whole choice model a choice model, called the "ordinal attraction model" (OAM), that emerges from an active learning problem of consumer preferences. We rationalize the (surprisingly simple) OAM by showing that is equivalent to the aggregated choice probabilities (Pr(*x(5)) from the RMJ-based ranking model We view as nontrivial observation in its own right.
Finally, our paper is also closely related that of [13]. They study
when k
2 A Ranking Model Based on Reverse Major Index
Preliminary. We consider a universe of n candidates (hereafter referred as "items"), represented by [n] = (1.2,...,, ,... We assume that every participant has a strict preference over these items, represented by ranking (permutation). We use a bijection π [r]] - [ni] to represent ranking where π (i) is the ith most preferred item. We sometimes find the notation o == x helpful, where (x) is the position of item x in the ranking o. We also use >~x y if item x is preferred to item y under π., i.c., π (x) < π (yy) For example, π = (3, 1, 2) means 3 >5 1 >~ 2 and it corresponds "o" notation of a (2, 3, 1). Finally, we use e to represent the identity ranking, > for the set of
all rankings over n items, T& (k 2 1) for top-k list, and Σg for the set of all top-k rankings.
Mallows-type ranking models. Given the distance function d(.,-), the probability mass function of the ranking for a Mallows-type model can be written as
X(T)
Σa guis
where is the central ranking, q is the dispersion parameter, and Σ= q dd(""" is the normalization constant. Intuitively, the Mallows-type model defines a population of participants whose preferences are "similar" they are centered around common ranking, where the probability for deviations thereof decreases exponentially.
Different distance functions correspond to different models. A common requirement for a valid distance function is that it is invariant to "relabeling." " Formally, that means dl.:.) is left-invariant under the ranking composition, i.e., d (T1, (T1,T2) = d (IT,1 RT2) for every π, T1, T2. This invariance property enables to make the following conventions without loss of generality: First, we assume that the items have been properly relabeled so that the central ranking 'T" (unless otherwise specified). Second, we may use d(Tr) ) as shorthand notation for die, T),, which fully represents a distance function with the knowledge that d(m1, T2) = d(e, क. 1
"This setting is also practically relevant. For example, the platform may have capacity constraints on displaying how many items. The platform may also have an incentive to judiciously select the display sets to make feedback collection more efficient; see [13].
"Equivalently, one could use the "o" notation and write the distance function as d(01, 02) == d(T2, T1) and d will be right-invariant under ranking composition.
3

---

The Mallows (Kendall's Tau distance based) ranking model. Commonly studied distance functions include the Spearman's 's rank correlation, Spearman's 's Footrule, and the Kendall's Tau distance ([I]). Among those three, Kendall's s Tau corresponds to the Mallows model and is defined as
dx(x) = " ابرر (((()) T())-
(1)
measures a ranking's total number of pairwise disagreements (with the identity ranking e). For example, consider the ranking π = (4. 2. 1.3). There are four pairwise disagreements: {(4, 2), (4, 1), 3), (2, 1)}. Therefore, dx ((4, 2, 1,3) 4.
As an appealing property, Kendall's tau distance leads to a tractable expression for A. Other common distances do not have this since the normalization constant involves summing over n! rankings. The constant under the Mallows model can be expressed as (see [16]):
Σ gd (dا(m)) (m) (n, g) = II. ==
1-0' = III
...... (1)-
(2)
The RMJ-based ranking model. In this paper, we identify a new distance function, which we call reverse major index (RMJ). is defined as
(R(T)= == Reverse Major Index(T) = >T 1=
n- [(x(1) +(++ 1)} (n i)
(3)
Compared to Kendall's Tau in (1), RMJ focuses on adjacent disagreements and puts more weight on top-position disagreements. For example, consider the ranking (4, 2, 1,3) again. The only adjacent disagreements are {(4, 2). (2, 1)}. Therefore, after including the weights in (3), we have d<<(4, 2, 1, = 3+2 = 5. The name of RMJ is inspired by the major index from the combinatories literature ([17)), which is defined as d (TT
Σ [(x(i)= aii + 1)] i.
Discussion: Kendall's Tau vs. RMJ. Both metrics are conceptually similar: they measure ranking's deviation from the identity. They coincide in many intuitive cases. For example, in the most extreme ones we have dg (e) de(e) both can be used as "kernels" " to smooth out the distribution over rankings. However, they emphasize the deviation in subtly different way. Therefore, we can also find subtle rankings where their values are different. For example, dx ((4, 2, 1, 3)) = 4 but dz 1, = 5.
and d& (1z,,.... 1)) dR (n,, ...,,.... 1)) n(n 1)/2. Therefore,
We believe that both Kendall's Tau and RMJ reasonable measures of ranking discrepancy, and we find it difficult to tell which kernel is necessarily "better" from a theoretical/axiomaal approach. For example, [1] specifies a of properties that reasonable distance function should satisfy:
1. The distance d(TT #) 2 0, and the equality holds if and only if π and से are the same ranking;
2. The distance function d(-,-) )) is invariant to relabeling. (See earlier discussion in this section, especially footnote 3.)
In this sense, both Kendall's Tau and RMJ satisfy the basic axioms for ranking distances. Meanwhile, [18] specifies larger set of axioms so that Kendall's Tau the unique distance function satisfying all axioms. (For example, it can be verified that Kendall's Tau is a symmetric measure while RMJ is not.) However, it could also be argued that when comes to human beings' preferences, top-position deviations matters more than bottom- bottom-position ones. If one makes that into a axiom, it will be satisfied by RMJ but not Kendall's Tau. In this regard, there is not a measure that satisfies "all possible" axioms.
Despite the aforementioned diffieulties, we will show later that the RMJ produces a more tangible ranking model for ranked choices. For example, the estimatable (ranked) choice probabilities without compromising the desirable properties of Mallows, such as rationalizability and flexibility for a mixture setting. Moreover, regarding its ability to describe preference distributions that may occur in practice, we will demonstrate its descriptive and predictive power in a case study with real preference data. Therefore, we believe that RMJ produces promising tool that more tailed to the application of learning population preferences from (ranked) choice data.
ranking model leads to simple and

---

3 Analysis of the (Ranked) Choice Model (Pr(Tx[5))
In this section, we will characterize the (ranked) choice model {Pr(Tx]S)) aggregated from the RMJ-based ranking model, formally defined as
Pr(mx[S)= E (TR) S,
where [(TT T,, S) means the top-k list тy compatible with the ranking f in the set S. That is. mi()) E S and (i) > for all position i {l...., k} and item I S (mx(1).... Tx (i)}. Note that the summation is over rankings with nontrivial conditions. Therefore it unclear in priori whether any distance-based ranking model can aggregate into tractable Pr(m=|S) (even for k 1). We will also discuss how to estimate the ranked choice model parameters from data. In the sequel, we will write d()) d-) since RMJ is the distance function of interest.
3.1 The 1: 1 case
When A = 1, a top-k list model reduces to a choice model, which connects to richer literature (e.g.. [4]). Therefore, it is worth a separate discussion, which also helps build intuition for the k >> 1 case.
Choice probabilities. Our main result for k = summarized below, which characterizes the choice probabilities under the RMJ-based ranking model.
Theorem Let display set S = {I1, [21,22.... 22. ................................ ?MM] be such that œ1 < 22 <... < 2M- Under the RMJ-bused ranking model
d
Pr({z;[S}) = 1 1+ M-T
(4)
In other words, for every display set, all the items within the display set are re-ranked so that their choice probabilities decay exponentially fast according to their relative runking within the display set. Noticeably, the choice probabilities in (4) are (much) simpler than that induced by the Mallows model, which even needs Fast Fourier Transform evaluate in O(n² logn) time ([4]). Also, (4) rediscovers the "Ordinal Attraction Model" (OAM) in [13], which could also be viewed as a "multiwise" generalization of pairwise noisy comparison models (e.g., [19, 20]). OAM gets its name because the "attractiveness" (i.e., choice probability) of an item within a display set only depends on its relative position in S and therefore is only function of the "ordinal" information. While OAM emerges from an active learning problem of consumer preferences, we "rationalize" it by showing that it can be aggregated from the RMJ--ased ranking model, which believe is nontrivial observation in its own right. In the sequel, we will follow its convention and refer to the choice model defined in Theorem OAM.
Proof outline and key intermediate results for Theorem Let us introduce few notations for top-k (sub-) rankings. Given top-k ranking Th Σg. we could define RMJ for тR by truncating the index at position k, i.e., d(Tx) = -k (i) > az 1)} (n i). In addition, let
R(TT)= := { (i) ==l,.... 1,..., k} be the set of top-k items and (T&)) : [m]] \ R((ss) its complement. Finally, let L (TT) == {z R²(
x < [k)} be the number of items that are (i) not included
in कHy and (ii) having smaller indices than (i.e., preferred under π = e) item (k). For example, suppose 7 and I (7,4. 4, 6, 2). Then d(T.) 6 4 10, R(T,) {2, 4, 6, 7), (TA)) (1,3,5), (4) = 2, and T. (m1) 1(1]=
Given two subrankings compatible, i.e., (i) = (i) for all 1....,k, k. Our first result concerns extending the domain of À to top-k rankings, formally defined as A(TA) Ex {( #).
E Σg and
E Eg with k < K, we write C T& if they are
Lemma (Probability distribution of top-k rankings) X ( = L(m))) ((n-kg))
((n.0)
The significance of the result above is that we could think of a ranking as stochastic process "tree" with depth n and nz leaves. While (X(T) : क E Σ} describe the probability distribution over the leaves, for every k, (A(TR): Tak E }g} describe the probability distribution over the nodes at level k.
5

---

As consequence of Lemma 1, we can write out how to randomly sample ranking т under the ranking model from the top the bottom position. Given a top-k ranking TT and an item we write Tkk ( as the concatenation of gy and item z. For example, suppose æ3 = (5, 2, 4), then T3 ( 2,33).
Lemma (Random ranking generation) Given a top-k ranking Th such that TT(k) = 2, the conditional probability for the (k: + -oposiitone item is
Pr(Te+1 Thk + y|TTx)
A(Ta A(Ha)
git
1tg 1+gh"+gr=tt-
E 1fz < n- ExER((A)) Ty <
ify> ify
where h(ylz))
Finally, Lemmas and lead the following result based on an induction argument.
Lemma Let a display set (x1 v2,-. ... . JMM be such that Xı < i22 <... < EMM and a top-k ranking me be such that Th = - @ and R(Tk-1) n = 0.. Then conditional on participant' s top-k preference list Th, the probability that (s)he will choose item xa out of display set is
if > x; and = $ S
Σ= A(#) I( R, S) IT C
(((1))
Pr((o:[SHaL)
if r; and S
A(Tx))
if = Ii.
0
if E S {zi}.
where p(z|s):= Ene =}
Note that Lemma 3 could be viewed as generalization of Theorem 1 by setting T (which corresponds to 2 = 0).
Parameter learning from choice data. In the parameter learning problem, we are endowed with choice data H7 (S1, ......, Sr, IT), where S, is the display set shown to the 7th participant and J, is his/her choice. Following [13], the maximum likelihood estimator (MLE) for the central ranking x² can be obtained from the following choice aggregation problem
# E argmin
E'E EES,
T
Σ
1x > Iz}.
It has a further linear integer programming formulation. Let wa == ΣT [it C St and x, = be the number of times that item and item j are displayed together and item chosen. Intuitively, a positive Wij- - Wy is an indication that item i should be preferred to item j. Invoking Proposition in [13], the integer programming could be written follows:
E argmin,
Σ Ensyes WijTej
Pij + Izt =1
Visijsnit
(5)
s.t.
Tij + Jjr + Fri 2
MSiijrsnniij
Tij E (0,1)
visi,j
In the formulation above, the solution & is such that f.j 1 if > j under the MLE f. Com- putationally, this integer programming is an instance of the well-studied feedback are set problem on tournaments. Therefore, it admits polynomial-ting more practical side, the central ranking x" can be effectively obtained using off-the-shelf integer programming solvers and with many speeding-up heuristics; see [13] for more discussion. The MI.E for dispersion parameter q can be subsequently obtained from an one-dimensional (convex) optimization problem & E argmin, {a ΣT= Eves, 14x > xx) + +I log D)5 e-jaa that â - Ing. q. It is also worth noting that the MLE framework can be easily extended to learning in
approximation scheme (PTAS). From

---

mixture setting using the standard EM algorithm, which we refer to the supplementary materials for more details.
Let us conclude this section by providing some theoretical understanding of whether we could recover the ground truth values of x² and q at least asymptotically. Intuitively, this should depend on the "coverage" of display sets: if only pair {x, y is repeatedly, there is no hope of recovering the full ranking x*. It turns out that the parameters can be recovered as long as every pair is "covered" by some display set.
Theorem 2 Consider a sequence of display sets {St]. Suppose every puir of items {i,j} S [n]] displayed infinitely often. That is, Et [[iij St}) + 30 as + c0. (ft, ④) = (+t (Hr), ((H)) is an consistent estimator. That is, (ft.4) + (q)) almost surely as + cc. Conversely, if there exists a pair of items {i.j} that is only displayed finitely often, then there exists tie-breaking rule for MLE so that के i H² with positive probability.
00. Then the MLE
We would like to mention that the coverage condition is fairly mild. For example, as long as the full display set is displayed sufficiently many times, the RMJ-implied central ranking can eventually be recovered. This stands in contrast to its counterpart in the Mallows model. Since the Mallows model does not produce simple choice probabilities, the MLE from choice data is rather difficult to obtain. Perhaps the best method date is by [4], who uses a "Mallows smoothing" heuristic. The following result reveals that the heuristic can be unstable or fail to recover the underlying Mallows parameters even under sufficient coverage of display sets.
Theorem Even if all display sets with sizes larger than two are displayed infinite times, the estimator from the Mallows Smoothing heuristic is not consistent.
The intuition behind the result above is that Mallows Smoothing needs a "choice ranking" step. That is, needs to first find a distribution over rankings, denoted by Å E A(E), that aggregates into choice probabilities to match the empirical choice probabilities {Pr(x:) [1: [Pr( Formally, it corresponds to solving the system of linear equations
Σg ((F)I(Z, R,) Pr(x|S)
(6)
for all display set S in the data and x E S. Since there are vastly more variables than equations, the solutions in general form a polytope rather than a singleton. More importantly, we find that there can be solutions d and d2 that aggregate to different Mallows models in the "ranking aggregation" step of the heuristic. Therefore, in general, this heuristic can produce non-unique results and thus be inconsistent.
3.2 The general (k: 2 1) case
In the general (A: 2 1) case, the ranked choice probabilities and the corresponding estimation remain parsimonious. Roughly speaking, the ranked choice model behaves like a generalized OAM where Pr(TT: (S) depends on the relative rankings of the items in T. among the set S. The tractability comes from the sole dependence as the "full display set" for a subuniverse of items, then re-rank all the items within the display set S, and finally just apply Lemma 1.
the relative ranking. That is, to obtain Pr(m (S), one could first treat S
Choice probabilities. Given a display set S, let ds(.), I.(()) be the originally defined d(.) and L(-) functions, but treating the display set S as the universe. Formally, (T&) : Σ [( (i) > Tuli + 1)} (IS) i) and Ls (TT) := {I ( i S
< TA (k)) J. For example, suppose again that n = and T = (7, 4. 6, 2). and let S = {2, 3, 4, 5, 6, 7}. Recall that d(TT) = + + 10 and L (IT) K1) 1. In comparison, (T( 5 + 3 8 and Ls (TT) [0] = 0.
Theorem Given a display set S and a top-k ranking Ty such that R(Tx)) S S, we have
Pr(T+[S)= = dlsst)) $[S k.g)
(1S),
7

---

Note that Theorem 4 generalizes both Theorem and Lemma 1 (but in different ways). It reduces to
Theorem 1 by setting & 1: Given मं = (2) where & E S, we have d = 0, Ls (T) = [r E
S' {z) : I < zH| the relative ranking of a in display set S, and 1([8[2) the appropriate normalizing constant where k = 1. In addition, Theorem 4 reduces to Lemma by setting S = [r]. as can be easily verified.
-[S)-kk)) 1 + +.....++.. 1
Parameter learning from ranked choice data. In the parameter learning problem, we are endowed with choice data Hr (S1, T................. ................................ Sr, mT. where St is the display set shown to the tth participant and _ ( x are his/her top-k choices ranked from the most preferred to the kth preferred.
It turns out that (somewhat surprisingly) in the h: 2 case, the central ranking x can be estimated from the same integer programming (5) but just with generalized re-definition of the weight parameters {way}.
Theorem The MLE for the central ranking n¹, 4, can be obtained from the integer program (5) with Zig = 1 iff >a j and a generalized definition of {wey} below
T Why Σ Maa = ((05) S S.f.f....,,.lll + E(s 1-51-Mi h) --). i, i, 53 h=1
Intuitively, a positive Wij wys is still an indication that item i should be preferred to item j. but now taking into consideration that every participant's response is actually a ranked list rather than a single choice. Practically speaking, the {way} } can be maintained in a relatively simple manner. Suppose display set S and ranked choice TT are given. Then (x)(t).<. will be added by |S] - l for all f = 1, ..... k- - 1. (This captures the ranking information for items included in n&.) In addition, (k). will be added by for all E {R*( n SS.. (This captures the ranking information between TA. (k) and all items that are not included in TT.)) For example, suppose n = and k = 3. The ranked choice data is such that S 21 2, 3, 4, 5) and T = (3, 1,2). Then we have W = 4, W1,2 = 3, W2.4 = W2,5 = and all the other wij = 0.
model limitation. A few more words on the ranked choice model (Pr(Tg[S) The specific form gives it great simplicity, but as with any other parametric model, it may be vulnerable to model missspecification issues in practice. In particular, since the model is calculated from a unimodal ranking distribution, this model (in its "vanilla" form) is best suited when there is an approximate "consensus" ranking in the population. In our numerical studies, we will demonstrate how we can effectively mitigate those issues by considering learning the model parameters in mixture setting to better capture the preference heterogeneity in the population.
Discussion:
4 Numerical Experiments
We investigate the performance of our methodology on two anonymous survey data sets regarding sushi preferences ([21]): The first one consists of 5,000 full preference rankings over 10 kinds of sushi, while the second one consists of 5,000 top-10 10 rankings over 100 kinds.* Throughout the numerical experiments, we use workstation with dual Intel Xeon Gold 6244 CPU (3.6 GHz and 32 cores in total), no GPUs, and 754 GB of memory.
Experiment 1: Top-1 choice. When = 1, a top-k list corresponds to a choice model, which connects a richer literature (e.g.. [22, 4, 13]). We compare our prediction power with two representative ranking models: Mallows and Plackett-Luce. (The previous is distance-based. The latter is not but leads to the famous multinomial logit model (MNL) choice model.) We use the Mallows Smoothing (MS) heuristic to estimate a Mallows model and MLE to estimate a Plackett- Luce. For all three rankings models (Mallows, PL, and ours), we also use an EM algorithm to perform parameter learning in mixture setting.
Since the estimation and generalization performances can depend on the display sets, let define an instance of the comparison by {Strain Stest, C}. Here Strain (resp. Stest) is collection of display
'In the supplementary material, we also conducted a numerical experiment on an e e-commerce dataset, and the result is consistent with experiment I on sushi data.
8

---

sets in the training (resp. test) data, and C is the number of clusters. In every instance, we split the data into 4000 participants in training and 1000 in testing. We generate empirical training (resp. testing) choice data by first enumerating all display sets in Strain (resp. Stest) and then record every participant's is favorite type of sushi for every display set in the training (resp. testing) data. Finally, we use the log-likeling oogliikelihodd as performance metric. We will use term explanation power (resp. prediction power) to refer the performance metric evaluated on the training (resp. lesting) data.
We use two configurations for Strain and Stest. respectively. For Strain. we take it to be ei- ther the full set or a collection of three randomly generated sets, which are realized be {[1,3, 3, 4, 7, 7,8, 10}. (2, 4, 5, 6, 8, 9). [10]]. For Steat, we take it to be either the collection of all pairwise sets or all display sets with sizes least two. Note that Strain has low variability and many elements in Stest do not appear in Strain, making the experiment emphasizing more on the generalization power. We take C (1, 21,2,4 4, 6, 15).
We summarize our results in Figure 1. We find that our method has favorable performance compared to MS and MNL across the settings. Intuitively, MS and MNL underperform in different ways. MS is vulnerable to the identifiability issue in the "choice-to-rankingg step, for which we provide theoretical understanding in Theorem 3. Our numerical experiments confirm the theoretical insight: We randomize over the extreme points of the polytope of solutions to (6), each of which leads to a valid output of the MS heuristic. Every box plot in Figure contains a summary of the performances of those outputs. It is clear that the performances (both in training and testing) span wide ranges, In the meantime, MNL is vulnerable to both the model risk from its specific parametric form (reflected in the limited increase of explanation power when considering more clusters) and the sample risk of overfitting (reflected in the difference performance training vs. testing, especially when trained on the full display set only); see more details in the supplementary materials.
Figure 1: Comparison of Explanation and Prediction Power for Top- 1 choice
Explaination Pewer
Prediction Power on Sets
Prediction Power on Pairwise Sets
8000
30000
32000
-34000
30000
9550
33000
(rmined full display sot only)
Explaination Power
166
Prediction on
Prediction on Pairwise
-20000
20000
-21000
]
22000
-1.6
23200
36000
-24000
33000
15
15
15
@rained (hree randiom display selg)
In each panel, the x-axis represents the number of clusters, and the y-axis represents the log. likelihood metric.
Experiment 2: Top-k choice. In this experiment, we perform robustness check based the criterion that a good model should return similar central rankings under different feedback structures, i.., different k. Specifically, we conduct estimation top-1, top-2 and top-3 ranked choices constructed from the first 10-sushi data set. The collection of display sets is taken to be all display sets with sizes least k. We find that all three experiment instances produce the same estimated RMJ-implied central ranking म = (8, 5, 6, 3,2, 1, 1, 9, 7, 10). Such robustness stands in contrast with other more naive methods, such as various versions of Borda count; see more details in the supplementary materials. We believe it presents evidence that our methodology is learning sensible information from the data.
Experiment 100 sushi types. In this experiment, we wish to show how effective our method is for relatively large number of items. In the data, each of the 5000 individuals indicates their top-10 choices out of 100 types of sushi. We use the LP-Rand-Pivot speed-up heuristic by [13] based on LP relaxation to train single-cluster RMJ-based model. We bootstrap 10 times (cach time drawing

---

10000 samples) and record the running times and optimality gaps in the Table 1. We find that we can obtain 2% optimality gap within 5 minutes (excl. model building time).
Table 1: Computational Time and Optimality Gap on the 100-sushi data
Model Building Time (min) Model Solving Time (min)
Optimality Gap
Average Max
21.10
4.20
1.47%
21.19
4.50
1.79%
5
Conclusions
We identify a novel distance-based (Mallows-type) ranking model. It aggregates into simple proba- bility distributions for top-k subrankings among an arbitrary display set S. In addition, it facilitates effective parameter learning through the MLE formulation. This is the first distance-based ranking model with such properties (even for 1) the best of our knowledge.
This ranking model can be used to model population preferences and provide a rationalizable way to model their ranked choices from given display sets. We demonstrate its practical value using real preference data. For example, under a mixture setting with only a few clusters, shows promising prediction power, especially when there limited variety in the display sets.
For future steps, we believe our work can serve as the "infrastructure" for a range of business-related decision problems, such as product introduction, crowdsourcing, and marketing research, among others.
Acknowledgments and Disclosure of Funding
This work is supported by the Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier [WBS Number: R-314-000-121-1155 The authors would like to thank René Caldentey and Christopher Thomas Ryan for earlier discussions Xiaobo Li for their feedback. The authors are also very grateful to the Area Chair and reviewers for their careful reading of the paper and for the many helpful and constructive comments.
this problem, well as Long Zhao and
10

---

References
[1] Michael A Fligner and Joseph S Verducci. Distance based ranking models. Journal of the Royal Statistical Society: Series B (Methodological), 48(3):359-369, 1986.
[2] Colin L. Mallows. Non-null ranking models. i. Biometrika, 44(1/2): 1957.
[3] Flavio Chierichetti, Anirban Dasgupta, Shahrzad Haddadan, Ravi Kumar, and Silvio Lattanzi. Mallows models for top-k lists. Advances in Neural Information Processing Systems, 31, 2018.
[4] Desir Antoine, Goyal Vineet, Jagabathula Srikanth, and Segev Danny. Mallows-smoothed distribution over rankings approach for modeling choice. Operations Research, 2021.
[5] Tyler Lu and Craig Boutilier. Effective sampling and learning for mallows models with pairwise- preference data. J. Mach. Learn. Res., 15()):378333829, 2014.
[6] Valeria Vitelli, Øystein Sørensen, Marta Crispino, Arnoldo Frigessi Di Rattalma, and Elja Arjas. Probabilistic preference learning with the mallows rank model. Journal of Machine Learning Research, 18(158): 1-9,,, 2018.
[7] Jagabathula and Rusmevichientong. The limit rationality in choice modeling: formulation, computation, and implications. Management Science, 2018.
[8] Wenpin Tang. Mallows ranking models: maximum likelihood estimate and regeneration. In International Conference on Machine Learning, pages 6125-6134. PMIR, 2019.
[9] Qinghua Liu, Marta Crispino, Ida Scheel, Valeria Vitelli, and Arnoldo Frigessi. Model-based learning from preference data. Annual review of statistics and its application, 6:329-354, 2019,
[10] Fabien Collas and Ekhine Irurozki. Concentric mixtures of mallows models for top-k rankings: sampling and identifiability. International Conference on Machine Learning, pages 2079- 2088. PMLR, 2021.
[11) Austin R Benson, Ravi Kumar, and Andrew Tomkins. A discrete choice model for subset selection. In Proceedings of the eleventh ACM international conference on web search and data mining, pages 37-45, 2018.
[12] Karlson Pfannschmidr, Pritha Gupta, Bjöm Haddenhorst, and Eyke Hüllermeier. Learning context-dependent choice functions. International Journal of Approximate Reasoning, 140:116- 155, 2022.
[13] Yifan Feng, Rene Caldentey, and Christopher Thomas Ryan. Robust learning of consumer preferences. Operations Research, 2021.
[14] Zhe Cao, Tao Qin, Tie- Yan Liu, Ming-Feng Tsai, and Hang Li. Learning to rank: from pairwise approach to listwise approach. In Proceedings of the 24th international conference on Machine learning, pages 129-136, 2007.
[15] Tie- Yan Liu et al. Learning to rank for information retrieval. Foundations and Trends@ in Information Retrieval, 3(3):225-331. 2009.
[16] John I Marden. Analyzing and modeling rank data. CRC Press, 1996.
[17] Thotsaporn Thanatipanonda. Inversions and major index for permutations. Mathematics Magazine, 77(2):136-1444 2004.
[18] John Kemeny. Mathematics without numbers. Daedalus, 88(4))577-591 1959.
[19] Mark Braverman and Elchanan Mossel. Noisy sorting without resampling. In 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 268-276 2008
[20] Mark Braverman and Elchanan Mossel. Sorting from noisy information. arXiv preprint arXiv:0910.1 191,, 2009.
[21] Kamishima, H Kazawa, and Akaho. Supervised ordering-an empirical survey. Proc. 5th IEEE Internat. Conf. Data Mining, 2005.

---

[22] R Duncan Luce. Individual choice behavior, 1959.
[23] David Ben-Shimon, Alexander Tsikinovsky, Michael Friedmann, Bracha Shapira, Lior Rokach, and Johannes Hoerle. Recsys challenge 2015 and the yoochoose dataset. Proceedings of the 9th ACM Conference on Recommender Systems, pages 357-358, 2015.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We have double checked every claim and they are backed by the theorems/lemmas formally stated in the paper.
(b) Did you describe the limitations of your work? [Yes] See end of Section 2 named "Discussion: Kendall's Tau vs. RMJ." " and Section 3 named "Discussion: model limitation."
(c) Did you discuss any potential negative societal impacts of your work? [Yes] The main negative societal impact that we can think of is that the RMJ-based ranking model (in its vallina form) tends to aggregate into a social "consensus ranking, which under estimates preference heterogeneity. This should be mitigated by acknowledging multiple preference clusters using mixture setting. For details, please see the end of Section named "Discussion: model limitation."
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We have carefully read the ethics guidelines and ensured that we follow the guidelines.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 2.
(b) Did you include complete proofs of all theoretical results? [Yes] Proofs of our theoreti- cal results can be found in the supplemental material.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] They are included in the supplemental material. However, we wish to clarify that our code has dependencies (i.c., Gurobi, which paid-for mathematical programming solver) going beyond the algorithm itself.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4.
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes] Yes to applicable ones, i.e., the performances for MS; see Section 4.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We included the computation time in Experiment 3, which was specifically designed to demonstrate the speed of the methods on the 100-sushi data set. For other experiments (especially Experiment 1), a large amount of compute is devoted to finding the extreme points of the solution polytope to (6). This is more about understanding the statistical property of MS and hence the speed is a less relevant issue. For computational resources, please see the beginning of Section 4.
4. If you are using existing assets (e.g., code, data, models) or curating/releasnng new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We use a publicly available sushi dataset and cite the creators [21].
(b) Did you mention the license of the assets? [Yes] The data we use is public.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
We didn't include any new assets.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] This is a public available dataset.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] Please see Section 4.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
13

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "ytYUljXnwj", "reviewer": "Reviewer_Gwow", "summary": "This paper discusses a new ranking model called Reverse Major Index, which is a friend of the classical Mallows ranking model. Various properties of the model including the MLE are discussed, and connection to integer programming is discussed.", "questions": "The paper is well written and I don’t have question.", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and scientifically correct. The model discussed in the paper are novel up to my knowledge.\nHowever, the model seems to me close to the Mallows, and the analysis seems to be similar. The authors should emphasize more on why the benefit of this ranking model.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "q-LXnrGZAYu", "reviewer": "Reviewer_L5sw", "summary": "The authors study Mallows-type models in the context of top-$k$ ranking.\nThey propose a new distance function called the reverse major index known from combinatorics,\nwith which the computation of choice probabilities and the sampling of rankings can be done efficiently.\nParameter inference reduces to the feedback arc set problem, which is hard but admits a polynomial-time approximation scheme.\nThe authors show that their maximum likelihood estimator is consistent, while this does not hold for the Mallows smoothing heuristic from the literature.\nThey derive closed-form equations for the computation of the choice probabilities of their model.\n\nTo validate the model, experiments on the Sushi datasets are performed. In the case of top-1 choice, the approach shows favorable\nperformance when compared to Mallows smoothing and the multinomial logit model.", "questions": "- In line 330f. you write that your method has \"supreme performance compared to MS and MNL across the settings\".\n  Looking at Figure 1, the prediction power of OAM and MNL on all sets are actually close, with MNL beating OAM for a few cluster configurations.\n  Since there are no error bars/confidence intervals, it is unclear as to how significant this outperformance really is.\n  Can you clarify\n      (1) why it would not be possible to repeatedly shuffle the data and repeat the splitting to obtain multiple performance values, such that error bars can be computed?\n      (2) why \"MNL is vulnerable to [...] overfitting\" is not applicable to OAM as well, since the prediction power of OAM appears to decrease similarly for more clusters.\n- Could you elaborate a bit what the goal of Experiment 2 was? What ranking do other top-k ranking approaches produce on this task? Which ranking do you get if you simply count the occurences of each sushi in the top-k list?\n- Similarly, the goal of Experiment 3 was also not explained. One can deduce that you are trying to gauge how well the method can scale to large choice sets. Are there other approaches you can compare to which will help contextualize your obtained running times?", "limitations": "The authors write about the potential limitations of their model at the end of Section 3. What I am missing, are the limitations of their numerical experiments. The authors could for example write about the choice of dataset(s), baselines, number of repetitions etc., which in addition to more motivation would help the reader contextualize the results.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Originality\nThe authors propose a novel combination of the Mallows model with a new distance function, the *reverse major index*.\nThe distance function only considers neighboring ranks and the absolute position in the ranking, which makes it easier to handle than Kendall’s distance function. \nSubsequently, this allows the authors to simplify computation of several downstream tasks like sampling and inference, and allows them to show consistency of their model.\n\nImmediate related work is adequately cited, and the authors are referencing some of the choice modeling literature.\nSince the setting considered in the paper is dealing with a feedback model where users are ranking a given set of items, I would also recommend specifically citing the recent work done in the setting of subset choice:\n\n- Benson, Austin R., Ravi Kumar, and Andrew Tomkins. “A Discrete Choice Model for Subset Selection.” In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, 37–45. WSDM ’18. New York, NY, USA: Association for Computing Machinery, 2018. https://doi.org/10.1145/3159652.3159702.\n- Pfannschmidt, Karlson, Pritha Gupta, Björn Haddenhorst, and Eyke Hüllermeier. “Learning Context-Dependent Choice Functions.” International Journal of Approximate Reasoning 140 (January 1, 2022): 116–55. https://doi.org/10/gn9kh3.\n\n# Quality\n\n## Theoretical analysis\nThe authors prove several theoretical results related to the computation of probabilities, sampling and inference.\nIn addition, they show that the maximum likelihood estimator of their RMJ model is consistent, while Mallows smoothing fails in this respect.\nNotation is clearly introduced and used consistently. The proofs of the claims are provided in the supplemental material. The proofs themselves are written clearly, such that they were straightforward to follow.\n\nIn the proof of Lemma 4, the proof of the identifiability is very short and could benefit from slightly more intermediate steps.\nIn line 560, you refer to a source [20], but in the paper the references only go up to [19]. It is therefore not clear where these conditions come from.\n\n## Empirical analysis\nWhile the theoretical analysis is sound and thorough, the numerical experiments are more limited in scope.\nThe authors only consider the Sushi dataset, which is unique in that it is one of the rare datasets where users provide rankings for the chosen items. Since the authors then consider top-$1$ choice, it would be possible to consider more real-world data (see below), and more baselines of the choice modelling literature. As is, it is difficult to relate the results to the results of the existing literature.\nThe most interesting experiments (2 and 3) could be expanded by comparing the results to simple baselines (see Questions section) or adapting existing ranking/choice approaches to this setting.\n\nExamples for real-world datasets:\n\n- The YOUCHOOSE dataset of the RECSYS 2015 challenge: https://web.archive.org/web/20210120062757/https://2015.recsyschallenge.com/challenge.html\n- The Expedia hotel recommendation dataset: https://www.kaggle.com/competitions/expedia-hotel-recommendations/data\n- The LETOR datasets: https://www.microsoft.com/en-us/research/project/letor-learning-rank-information-retrieval/\n\n# Clarity\nThe paper is written in a clear language and structured logically. Titles and paragraphs are used in such a way that it is easy to follow the key ideas. The source code and data of the experiments is provided with a small readme file, which improves the reproducibility of the results (disclaimer: I did not execute the attached code).\n\nIn the experimental section, since the generation of some of the datasets has been randomized, I am missing a description of whether random seeds were fixed beforehand and to which value. Looking at the attached code, this appears not to be the case, but it should be mentioned.\n# Significance\nThe model proposed in the paper improves on the standard Mallows model, by making it more efficient to learn and use. The authors also demonstrate that the approach scales to moderately sized data (i.e., choices from sets of 100).\nWhether others will use the approach will depend on the predictive performance achieved on real-world data, when compared to other approaches.\nI think that the idea is interesting as is and could lead to other advances in the subsequent literature.\n\n# Minor remarks\n\n- Line 1: Preference learning is a much more general field in machine learning and not only encompasses top-k choice/ranking.\n- L. 42: \"A representative work is by [4]\" -> \"A representative work is by Antoine et al. [4]\"\n- L. 320: \"traing\" -> \"training\"\n- L. 599: \"we will show that even [when] all display sets\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "iXLH6coOg7R", "reviewer": "Reviewer_m77F", "summary": "The authors discuss distance-based ranking model for identifying population's preferences and their ranked choice behavior. This is useful for many applications such as new product introduction, crowdsourcing, etc. They introduce to a new type of distance based (Mallows-type) ranking model, which uses Reverse Major Index (RMJ) as the underlying distance function. They discuss several theoretical properties of this model and show that RMJ based ranking distribution aggregates into (ranked) choice probabilities with simple closed-form expression. In particular, for k > 1, the characterization of choice probabilities, efficient sampling of a top-k list,  and learning of parameters are novel aspects of the paper.", "questions": "Overall, the paper has novel aspects. I specially liked Lemma 1 and Lemma 3. However, there a few questions I would like authors to comment on:\n\nPresentation:\n1. A lot of things in the introduction are not clear. For example, it is difficult to make sense of the first paragraph on page 2, unless the mallow-type models are not described. \n2. Line 28 — what do the authors mean by the most representative distance?\n3. What is PTAS in line 77 (it is mentioned in line 227)? Also in line 311, what is MNL? The authors should judicially use acronyms.\n4. Use of Mallows-type ranking models and Mallows model for Mallows model with KD distance function is confusing. \n5. Line 151 - I do not understand how the authors came to the conclusion that “Therefore, both can be used as “kernels\" to smooth out the distribution over rankings.”\n6. Theorem 1: Is there a way you can specify that it corresponds to RMJ model. The current form doesn’t tell us that this is for RMJ. \n\nMathematical Rigorousness:\n1. Theorem 2 is not precise. It would be better to add sample complexity numbers. Specifically, quantifying what one means by consistent and infinite samples. I am further confused by the use of the word consistent in Theorem 3. Are the solutions from Mallows smoothing not equivalent? If they are, then the heuristic may not allow to converge to a single entity, but the heuristic may still be consistent when it is converging to equally good set of entities. It would be better to precisely mention (in quantifiable terms) the meaning of these words. \n\nOthers:\n1. I see that RMJ has some links with measures like NDCG. Also, there can be other variants of RMJ which look at specific portions, or precisely, specific pairwise comparisons of the ranking. For example, pAUC [Narasimhan et al.], pap@k [Hiranandani et al.]. Would authors like to comment on that? \n2. Line 147 — Can the authors also mention the use of major index in combinatorics for completeness?\n\nNarasimhan, Harikrishna, and Shivani Agarwal. \"A structural SVM based approach for optimizing partial AUC.\" In International Conference on Machine Learning, pp. 516-524. PMLR, 2013.\nHiranandani, Gaurush, Warut Vijitbenjaronk, Sanmi Koyejo, and Prateek Jain. \"Optimization and Analysis of the pAp@ k Metric for Recommender Systems.\" In International Conference on Machine Learning, pp. 4260-4270. PMLR, 2020.", "limitations": "yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nIntroduction of a novel ranking model with certain desired properties\nTheoretical and empirical justification of the desired properties\nWhile the presentation may have some issues, but I liked the paper described its results intuitively\n\nWeaknesses:\nPresentation: A lot of things are imprecise and not clear in the paper, including introduction\nRigorousness:  Certain mathematical statements are not quantified properly", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dswq5dUgbpk", "reviewer": "Reviewer_nVtJ", "summary": "This paper proposed a Mallows-type (probabilistic) model for ranking data. Based on the new model, several theorems/lemmas are proved to  show different properties of the new model. Using the properties, the authors proposed a learning algorithm for the new model, and experimentally showed that the new model has better accuracy than the widely-used Plackett-Luce model and Mallows model. ", "questions": "As mentioned in the weakness part, can the authors provides more discussions about the time-complexity?\n\nAlso, Please correct me if my understanding of the distance measure is incorrect.\n\nWhy is linear weight used in the distance measure? Why not use other weights like log-based weighting in DCG?", "limitations": "I haven't found any negative social impact in this paper", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The presentation is very clear! It's easy for me to find the main contribution of this highly theoretical paper\n\n2. The theorems look sound to me\n\n3. The idea is simple. It looks similar to the intuition behind DCG (or NDCG).\n\nWeakness:\n\n1.  I think the model is not novel because it can be seen as a weighted version of Mallow's model with Cayley distance (Irurozki, Ekhine, Borja Calvo, and Jose A. Lozano. \"Sampling and learning Mallows and Generalized Mallows models under the Cayley distance.\" Methodology and Computing in Applied Probability 20.1 (2018): 1-35.). If my understanding is correct, the baseline should also be changed to the Mallow's with Cayley distance. Please correct me if the proposed measure is totally different from Cayley distance. PS: My current (overall) evaluation is based on the assumption that the proposed measure is similar to Cayley distance. \n\n2. I would  like to see more discussions about the time complexity of the new algorithm. I think it would be a big improvement if the authors can provide the analysis about the overall time-complexity of this algorithm in Section 3.1. Or, alternatively, it would also be great if the authors can show a comparison of Mallows and OAM in terms of the running time.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept