Generalized Top-k Mallows Model for Ranked Choices
Authors: Shahrzad Haddadan
Sara Ahmadian
Venue: NeurIPS 2025 spotlight ()
Keywords: Mallows Model
choice modeling
top-k sampling
Primary area: theory
TL;DR: We propose a choice model based on top-k Mallows model and design algorithms for it

Abstract: The classic Mallows model is a foundational tool for modeling user preferences. However, it has limitations in capturing real-world scenarios, where users often focus only on a limited set of preferred items and are indifferent to the rest. To address this, extensions such as the top-$k$ Mallows model have been proposed, aligning better with practical applications.
In this paper, we address several challenges related to the generalized top-$k$ Mallows model, with a focus on analyzing buyer choices. Our key contributions are: (1) a novel sampling scheme tailored to generalized top-$k$ Mallows models, (2) an efficient algorithm for computing choice probabilities under this model, and (3) an active learning algorithm for estimating the model parameters from observed choice data. These contributions provide new tools for analysis and prediction in critical decision-making scenarios.
We present a rigorous mathematical analysis for the performance of our algorithms. Furthermore, through extensive experiments on synthetic data and real-world data, we demonstrate the scalability and accuracy of our proposed methods, and we compare the predictive power of Mallows model for top-$k$ lists compared to the simpler Multinomial Logit model.

Generalized Top-k Mallows Model for Ranked Choices
Shahrzad Haddadan Rutgers Business School Piscataway, NJ shaddadanCCuusinesss.uu rutgooseeeeeeeee.eeeeeeee
Sara Ahmadian Google research Seattle, WA sahmadian gmail.com
Abstract
The classic Mallows model is foundational tool for modeling user preferences. However, has limitations capturing real-world scenarios, where users often focus only on limited of preferred items and indifferent the rest. To address this, extensions such as the top-k Mallows model have been proposed, aligning better with practical applications. In this paper, address several chal- lenges related to the generalized top-k Mallows model, with a focus on analyzing buyer choices. Our key contributions are: (I) novel sampling scheme tailored generalized top-k Mallows models, (2) an efficient algorithm for computing choice probabilities under this model. and (3) an active learning algorithm for estimating the model parameters from observed choice data. These contributions provide new tools for analysis and prediction in critical present a rigorous mathematical analysis for the performance of our algorithms. Furthermore, through extensive experiments on synthetic data and real-world data, we demonstrate the scalability and accuracy of our proposed methods, and we compare the predictive power of Mallows model for top-k lists compared to the simpler Multinomial Logit model.
scenarios. We
Introduction
User preferences over a set of alternative items play crucial role in various decision-making scenarios. A key concept in this context is the choices customers make when presented with a subset of alternatives, referred to an assortment, drawn from larger pool of items. The mathematical modeling of preferences and choices is both essential and challenging. enables researchers and business leaders to analyze and predict customer behavior, thereby informing more effective decision- making. Probabilistic models over rankings, such as the Plackett-Luuce (PI.) and Mallows models, are widely used to represent user preferences. Based on the Plackett-Lucc (PL. model, the Multinomial Logit (MNL) model has been suggested for modeling choice, and has been extensively applied in choice modeling due to its simplicity and interpretability.
The Mallows model (Mallows 1957 is a distance-based probability distribution defined over per- mutations and is reminiscent of the Gaussian distribution for scalar variables. It has been used successfully model preferences, particularly where ranking data available. Recent work has demonstrated the high predictive power of the Mallows model in modeling choices (Désir et al. 2023 (02T), sparking follow-up research into revenue management and assortment optimization in this framework Désir et al. (2021) 2023); ; |Feng & Tang (2022); RReger & Segev (2023). One key challenge applying the Mallows model more broadly is that its classic definition restricted to full permutations.
In many real-world scenarios, however, user preferences are often observed as top-k lists rather than full rankings. For example, many platforms display only subset of items to customers and ask them rank fixed number of preferred items. In recommender systems, advertising platforms, search engines, news aggregators, and social media friend suggestions, users are typically shown only the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

k most relevant items, rather than an exhaustive list. Likewise, users often express preferences for limited number of favorite items and show indifference toward the remainder.
This recurring structure in many applications has motivated the extension of the Mallows model to handle top-k lists. The design of algorithm for this variant is significantly more complex than in the traditional permutation-ben based setting, leading to growing body of research focused on learning, inference, and aggregation under the top-k Mallows model (Lu & Boutilier 2011 Chierichetti et al.
2018a; Collas & Irurozki| 2021] Vitelli et al. 2018: Fotakis et al. [002]] Boehmer et al.) 2023; Goibert
et al. 2023 Awadelkarim & Ugander 2024 Qian & Philip 2019 Akbani & Escobedo 2022)
In this paper, we propose employing a generalized Mallows model for top-k lists for choice modeling, and we develop efficient algorithms related to generating samples from it, learning its parameters and finding choice probabilities. Our approach addresses more realistic preference structures, where users are unlikely to hold complete rankings over a large set of items, assumption that is often impractical in real-world applications.
1.1 Related Work
In this section we present relevant related work on choice modeling and Mallows model.
Choice modeling Various probabilistic models have been developed to capture choice behavior, with the Multinomial Logit (MNL) (Bradley & Terry] 1952) model being the most widely used due to its simplicity and interpretability. In the MNL. model each product is assigned a positive score or weight, and the probability of selecting product from an assortment is proportional to its score. Importantly, the MNL model satisfies Luce's Choice Axiom, also known as the Independence of Irrelevant Alternatives (IIA). While this property makes the MNL model analytically convenient, it also limits its expressiveness in capturing more complex choice behaviors.
To overcome the limitations of MNL, the mixture MNL model (also known as mixed logit) was introduced and popularized by [cFaddeen & Train (2000). Learning the parameters of mixed MNL model from observed choices- -where each observation is an assortment and a chosen item is key challenge. Early approaches used heuristics based on maximum likelihood estimation (Dempster et al. 1977), and more recent work has provided statistically rigorous methods with provable sample complexity guarantees (Chierichetti al. 2018b Oh & Shah 2014 Ma al. 2022).
Beyond MNL-based models, other frameworks such as the Mallows- choice model DDssir et al., 202I) and Markov chain-based models (Blanchet et al., (016) have been proposed. These models offer greater flexibility but come with added complexity: tasks that are straightforward in MNL, such as computing choice probabilities or generating samples become substantially more challenging.
Mallows model The Mallows model (MM), originally introduced by Mallows (1977). defines distance-based distribution over full rankings, where the probability of permutation decays exponentially with its distance from a central (ground-truth) ranking. This property has made MM a useful foundation for preference modeling in machine lcarning. To better accommodate real-world data-where users often provide partial rather than full rankings -everra extensions have been proposed. Early work by Fligner & Verducci (198)) and Lebanon & Mao (2008) adapted MM to top-k rankings. Later Chierichetti et al. (2018 Sa) proposed a new distance measure on top-k lists and defined parametrized Mallows model for top-k lists based it (TopKMM))
One of the strengths of the standard Mallows model on permutations is the closed-form expression of its normalization constant which enables the design of several algorithms. For instance, the Repeated Insertion Method (RIM) (Doignon et al., 2004) allows efficient sampling from the full-ranking Mallows model. However, this tractability does not extend to TopKMM: computing probabilities or generating samples becomes non-trin non-trivial due to the lack of a closed-for -orm normalizing constant. While Chierichetti al. (2018a) proposed a dynamic programming approach to generate samples, they highlighted the absence of an RIM-like sampling method for top-k lists as an open problem.
Désir et al. (202T) proposed leveraging the Mallows model to capture choice behavior, demonstrating improved predictive accuracy over traditional models like the Multinomial Logit (MNL). However, a key challenge in applying the Mallows model to choice modeling lies in computing choice proba- bilities-i.e., the likelihood that a given item is selected from an assortment. Unlike MNL, where such probabilities have closed-form solutions the Mallows model does not admit such tractable computation general. To address this, some works have introduced Mallows-like models designed to simplify choice probabilities calculations (Feng & Tang 2022). In contrast, Désir et al. (2023)
2

---

tackle the original model directly and develop dynamic programming approach for computing choice probabilities by leveraging key ideas form the Repeated Insertion Method (RIM).
Learning the parameters of the Mallows model or its mixtures from full permutation, or top-k list
samples has been extensively studied in prior work (Liu & Moitra 2018a| [Braverman & Mossel
2008; Awasthi et al., 2014, Seshadri et al. 2020; Tangl 2019 Collas & Irurozki [021]] Akbari &
Escobedo 2022 Liu & Moitra 2018b; Chierichetti al. 2015). Some studies focus on learning
these parameters from historical data, while others consider an active learning setting, where upon each consumer's arrival, the platform adaptively selects the assortment of items offer based on past observations Susan et al. (2022). In contrast, learning model parameters from partial observations presents greater challenge. Several works address this problem by studying learning from pairwise comparisons Lu & Boutilier (2014); Vitelli et al. (2018); Tang (219)) A less explored problem is estimating the model parameters when only the users' choices from offered assortments of arbitrary sizes are observed. Existing methods in this setting often lack finite-sample complexity guarantees, limiting their theoretical robustness.
1.2 Summary of Contributions
In this paper, we focus on Mallows model on top-k lists, and we make several algorithmic con- tributions for the usage of this model. In order to obtain our results in full generality, we extend Chicrichetti et al. (2018a)'s model on Mallows model for top-k list generalized version by associating a weight to each product. Our algorithmic contribution are listed as follows:
1. Sampling: PROFILE BASED REPEATED INSERTION METHOD (PRIM): The Repeated Insertion Method (RIM) is a common method for sampling permutations in the classic Mallows model. However, extending this method to the top- Mallows model remains an open problem. Our proposed algorithm, PRIM, offers similar functionality to RIM and improves upon the prior dynamic programming approach by Chierichetti et al. (201 Sa). reducing the runtime from O(24* + 122 log n) to Ol:2* k.2 logn).
2. Choice Probabilities: DYNAMIC PROGRAMMING FOR CHOICE PROBABILITIES (DYPCHIP): DYPCHIP is an algorithm to calculate the choice probabilities when they are inferred from a Mallows model on top-k lists. This result extends the work of Désir et al. (2021) who consider the classic Mallows model for permutations.
3. Learning the Center: BUILD CENTER FROM CHOICES (BUCCHOI): BUCCHOI is an active learning algorithm designed to learn the center of top-k Mallows model distribution. It operates by presenting assortments of a specified size r to customers and, based on their observed choices, infers both the ranking of the center and the size of the center k.
The accuracy and complexity of these algorithms are demonstrated through rigorous mathematical analysis as well as experiments on real-world and synthetic data.
Furthermore, we apply these algorithms and fit a top-k Mallows model to a weal-world publicly available dataset including users' preferences over 100 sushi types, represented as top-10 lists (Kamishima et al. (005). This model helps us predict choice probabilities with high accuracy, and our results demonstrate that the top-k Mallows model achieves significantly higher predictive accuracy than the Multinomial Logit model on this dataset
2 Preliminaries and Definitions
Let N [m] = 21, ... _ represent a universe of n elements. A top-k list is a partial order on N structured as i > i2 while the remaining n - l elements are incomparable to each other. The collection of all top- lists over N is represented by Tk.N, where T,,N = SN corresponds to the symmetric group on N.
> in > (i++1, ,in where the top-k elements are strictly ordered,
For a top-k list 7 and a position 1 E [kt), (?) refers to the element ranked at position 1, while F denotes the set of elements ranked below the top-k. For simplicity, we sometimes use represent the top-k elements (2), rlk)). Thus E 7 indicates that i ranked among the top-k elements of T, and set operations like C and O are applied accordingly. For i, j N, i > j means is ranked
We remark that some prior work considers scenarios where users select multiple items or a list of l items referred to as a top-k choice. In contrast, our focus is solely on the selection of single item, and we use the term top-k only as parameter of the Mallows model.
3

---

above in i..., i E r and either j E or j E T but ranked below i. Additionally, || j indicates i and are incomparable (both are in f), while i 1 means they are comparable - or j >- i).
In this paper, we utilize the widely recognized Kendall's Tau distance, a commonly used metric that quantifies the number of pairwise disagreements between two permutations (Fagin al. [003) Critchlow 2012). This concept has been extended to top-k lists, where it no longer forms true metric but retains useful mathematical properties. Given parameter p 0, the p-parametrized distance between T E Tk,N is defined as
1
if j & > i) or vice-versa if j & i || j) or vice-versa
(T, = Σ
Ky (T,(T, where K (T,()
SJETUrlacj
0
otherwise.
Using this distance measure, Chierichetti al. (2018a) define the Mallows model for the top-k lists. Given a center 7' and a decay parameter 3. the probability distribution D over top-k lists Tg,N is defined as:
PD [T E TR,N) x exp (-3 10" (T,
(TopKMM)
To simplify our notation, we assume, without loss of generality, that the center T" is always the identity list 1 > k > {k + 1...... .n). Therefore, we denote (T r") as (C"(T). For full rankings, where all elements are comparable, we simply use IC(T).
natural extension of this model arises when the elements have associated weights. Generalized Mallows Model (GMM))lligner & Verducci] (1986) considers this case for full rankings: Given a decay parameter and non-negative weights W/ R20 for each i N, the probability distribution D over rankings is defined as:
PD [T E Tn, To,N] exp -B Σ (:KKssTT)
(GMM)
where (T) is i disagrees with r* i... 7 ranks j before for j i and otherwise, as defined in (]). In this model, each disagreement contributes the weight of the item ranked higher in T" This formulation can be simplified by the use of inversion vectors follows:
PD (r E NI xx exp -8 Σ w. ((T
where 4(7)= = - 10
(E(A)
$33$
where 1 is an indicator function that takes the value when true and 0 otherwise.
The generalized mallows model has traditionally been defined only for full rankings, and we extend to Generulized Mallows Model for Top-k lists. In this setting, each element j E T* is assigned non-negative weight, i.e., Wi Rzo for i [k], along with an additional weight w Rgo for any element in F* We use E _ to represent this collection of weights, which uses the following extension for inversion vectors:
Definition 2.1 (Inversion Vectors of a Top-k list). Given a top-k list T E Tk,N, there are three components for inversion vectors: vectors I(T), P(T) E R where for i E [k]]
[(()) E1( E1 (1.je77
jusi
and Q(T) = (K=9)) where E = |
Note that this definition is an alternative way to count the disagreement between and 7" where the disagreement is always assigned to the higher-ranked element by -" When neither element is ranked higher (i.j $ 7*), disagreements are assigned to Q. For example, for (2, 1, 5) E Ta,18,
have I(T) [1. 0, 2, 2]. P(T) [o. 0, 1, 0). Q(T) 1. [T( since element 2 is ranked higher since elements and 6 are ranked higher than and the same argument applies to [T(). PT(T) since elements and 4 are not comparable by (but they are ranked by r²) and this disagreement assigned to element 3 as it is ranked higher than element by r" Q counts disagreements for elements not ranked by r", i.c., elements 5 and 6.
than 1 by T. [T(7)

---

Generalized Mallows Model for Top-k lists Given the center T" E Tk.N and parameters B 2 0, E 1800" and 0, the probability distribution D over TN,N is defined as:
PD [T E Tk,Nl exp (-3 KM (T,
(TopKGMM)
where
= :op + Σ
wi (L((T) +P((T))
M [
Note that setting w 1, we obtain Equation (TopKMM). and k n, recovers Equation (GM))
3
Sampling from TopKGMM
We begin by investigating the challenge of efficiently sampling from TopKGMM. Although Chierichetti et al.] (2018a)'s sampling algorithms for TopKMM can easily be extended to incor- porate weights as in TopKGMM, here our concentration is to develop sampling algorithm with similar functionality to the repeated insertion model, which was left open (Chierichetti et al. (018a). The theory develop here not only helps in the design of the sampling algorithm PRIM but also plays a crucial role in the development DYPCHIP, our proposed algorithm for choice probabilities.
Theorem 3.1 (Sampling from TopK GMM). For given instance 'D of Top there exists algorüthm that efficiently samples a top-k list according 'D in time complexity O 2 k log and space complexity O )" where min(k; n k).
Similar to the RIM method for permutations (Dognno et al. 2004), the core idea of our approach involves iteratively adding elements to a partially ordered sequence until exactly A: elements are sampled. While this strategy results in a correct sampling scheme in the context of permutations, for top-k lists it is essential to partition the sample space based on several features before iterative insertions begin. Our careful definition of inversion vectors in Equation (T) plays crucial role here, as it allows us to focus on the behavior of elements in [k] and specifically those sampled by т. This insights leads us introduce profiles which represent the shared top-k elements T and 7²
3.1 Profile-hased TopKGMM Distribution
Let profile S S [k] represent the subset of sample top-k elements for given top-k list r. Formally, Definition 3.2 (top-k Profile). Given a center T' E Tk.N with corresponding TopKGMM distribution D, we call set S r"a profile and we define T,. (S) and its probability with respect D as:
(S) n
P [S]
Σ PD
(ST
When the center is clear from the context, we may simply use T(S).
For any r E T(S), since Q(T) = (*~ only depends on S, we simply write Q(S). The inversion vector P counts the number of lower-priority elements that previously ranked strictly lower but are now incomparable. An element j has a positive (T) only if it is not ranked by т, in which case its value is given by (T) now ranked by r. Since P strictly depends on S, we can use P(S) instead of P(T).
(k as exactly
l elements from {k + 1,..,,,............ ,n)
The inversion vector I is defined for elements in [k). and for each element, is the number of lower- priority elements (w.r.t. the center) that are now ranked higher in т. For any element j not ranked by i.e., j e [k] 8, (T) = Kj + 1, 3 n S). Thus part of vector I, is entirely determined by S and independent of r. Since Q(S), P(S). and [j(())(S(r)) are independent of rankings among r's elements and depend only S, compute the probability of S given this information.
Lemma 3.3. Given a TopKGMM distribution D with parameters 3, and w. any profile S $2........ St} C [k] (s1 < 82 < s1) has probability PD [S] proportional to exp (-Bf(S) where:
f(S) = (S) Σ Ws((((9)+PP3(S)) and Z(S) = (n 1n-k- k)
( k-
(k: L)
II
e
.w.yr
JEINNS
1=1
'Here O(k2") is the complexity of a prepprocessing step, after that each sample can be generate at cost Okk log n).
5

---

and it can be sampled in k)2 where min(k, n k}.
3.2 Sampling Algorithm
Building on the results from the previous section and leveraging the concept of profile, we now propose a method for sampling from the TopKGMM distribution (Algorithm{3) B) We first sample profile S with probability PD [S] (according Lemma (.3), and then we sample E T(S) by inserting the elements j E based on their contribution inversion vectors Equation (ToPKGMMJ).
The later step can be viewed as generalizing the Repeated Insertion Method (RIM). We reter to our method as PROFILE BASED--S-----EE -EEEEREEEEEEDD--E REPEATEEDINSERRIIN INSERTION-METHOD (PRIM).
In PRIM, we generate top-k list proportional to its sampling probability in D conditioned on the fact that the common elements with the center top-k ranking is S. Specifically, let l = [S]. We begin with an empty array A and then sample k- - l elements from [n]] [K] uniformly at random. Then we sequentially, insert the elements in S in increasing order of their priority. When processing element s, we insert in the current array A at position j E {0, 1,. |4|] with probability proportional to Priinerting 8 at position j) x exp (-Buc,
as j is the number of inversion associated with element s when it is inserted at position j. Note that higher priority elements do not contribute to inversion of so when their position when they are inserted later is not important for 8. See Appendix for pseudocodes and proofs.
Choice modeling and probabilities
In this section, we focus on the problems related to choice. In particular we focus the analysis of problems which help us predict the (top) choice of a customer from a set of alternatives, a.k.a an assortment using TopK After presenting definitions we design an algorithm which efficiently calculates choice probabilities having the distributions parameters. Section 5 we study the opposite problem in this context, which is learning the center of TopKGMM distribution by observing its choice data.
Given a set of products [n]. an assortment is any subset A of [n]. When A is offered to customer, she may choose any of its elements or the "no purchase" option denoted by Ø. We use N = [2] to denote all purchase options and correspondingly. we define TR.N to denote all top-k lists over N. We assume that the preferences of customers are derived from TopKGMM, and if we have multiple customer types, we use mixture of several TopKGMM's where each may have different parameters.
Given a top-k list T E Tk.N, we define the choice function C, : 2(r) + N as follows: for any assortment A C [m]. C, (AA) = i, iff is the highest ranked element in A {Ø) with respect to r. If all elements of AU } are incomparable w.r.t. т, then is taken uniformly from AU (2).
We focus on applying the TopKGMM model to represent customer preferences. Specifically, we assume that 7 is sampled from a distribution D, where D is TopKGMM distribution characterizing single customer type. More generally, DD can represent several customer types and we may use mixture distribution. Since choice probabilities of mixture distribution can simply be obtained as a linear combination of its singleton components, here we focus on singleton distributions.
4.1 Calculation of Choice Probabilities: DYPCHIP
Let D be TopKGMM distribution on Tk.N- We let Cp be function mapping any assortment A S [n]] and an option E A U {Ø} to the probability that C, (A) = i where 7 is sampled from D. Formally, Cp N x 2 + [o, 1] is defined as follows:
Co(
Σ
=
TETE.N
We now introduce DYPCHIP which calculates choice probabilities as defined in Equation 4 and its correctness and runtime complexity stated in the following theorem:
Theorem 4.1 (Calculation of choice probabilities). Given an assortment A S [m] and a TopKGMM instance D, DYPCHIP calculates CD (j. A) for all E AU in (2minthaa-t) 2
The main idea of this algorithm is to find these probabilities by conditioning on a given profile. Our dynamic programming tables are defined based on the order in which items are considered in PRIM.

---

Overview of DYPCHIP Consider profile S Ii] with é = |S|. Let A
{u For a top-k list 5 E [S), item a from picked if (i) r does not include any item from A and is picked randomly from A C F or (ii) a is top-ranked in A w.r.f We handle the two cases separately:
1. Let (s(a) denote the probability associated to case (i). Note that 7 n A implies that т is from a profile S with S nA 0. Thus for any a E A
k- (11+1)
(s( = P (Tn 0) A = (49 ns= 0)
[A +1
2. Let A = A n.. The elements in A who have a non-zero probability of being top ranked at some iteration of DP table are only i U S. We calculate these probabilities by conditioning on two other parameters: (1) where in PRIM algorithm they have chance of being sampled, and (2) the position in which they are positioned in the top-k list when they the winner, i.e, ranked highest among A We use three dimensional dynamic programming table Ts as follows: Let {a1, 02...... ay Sg, 8t-1..... 81 be an ordering of the elements in A U S where the first segment is arbitrary ordering of A and the second is the ordering of S used in PRIM.
J, q) be the probability that any element a, E {ai, 02,..... ar) is For q 0, we let ( ranked jth and higher than all other elements of A (see Equation (6)) Then, by iterating over q = 1......C l, we consider the gth iteration of the for loop in PRIM, and for any position 1 S. j < q. we define ( j. q) be the probability that after completion of the gth iteration of the for loop in PRIM, a is the highest element in A (the winner) which has so far been sampled, and a; is so far ranked j-th.
We update these probabilities by conditioning whether the newly inserted element, i.e., S1+1-g is added before the prior winner, or after it. Note that, since we the profile S is fixed, the probability of inserting a new element in particular location may be obtained from Equation (3), For details of the recursive definition of ( J. q) please see Appendix A.2 After the dynamic programming table is filled, we may calculate the choice probability of each a; A conditioned on profile S with |S| l by:
(a.))) = Σ Ts (.) 1=1
In each cell of the table, we need look at O(k) other cells which involves at most O (4) operations so each table entry can be calculated in O(k (Al) time. Finally, we may calculate the
Va E A, CD(a,
Σ SCIA]
PD [S] (TS(a) + +s(())
(5)
Runtime of DYPCHIP The size of the dynamic programming table is |A| k2 and calculation of each element needs & [A] +n operations. In Equation ( we have a sum over all profiles; which bounded by ((2 (R.. Thus, in total all choice probabilities may be calculated in time (2 |A 2 + 27 [A[n): = min(k, kj.
5 Learning the center from choice data
In this section, we focus on the problem of learning the center of a TopKGMM distribution from choice data. This task is more challenging than learning from complete top-k samples, as each data point provides limited information and the choice data depends on the specific assortments presented.
Consider a TopKGMM distribution D on Tk,N, the goal is to construct the center of D, namely T' by observing choice data. The choice data consists of pairs (At, where A, represents the assortment offered at round t, and o is the item selected by the customer from A₁. Formally, we let (cr, Ar):: where for t 2, T we have C C, (At), T D. While in traditional learning algorithms D is given as input. Here, we focus active learning and collect choice data by presenting assortments to the customers and recording observed choices.
D ((c1. A1), Az)
Our active learning algorithm for the estimation the center is BUCCHOI. takes as input the set of products N and assortment size & and offers sequence of assortments A1, .2.... to the
7

---

Algorithm FINDTOP
Algorithm 2 BUCCHOI
1: Input: Assortment A, a sequence
1: Input: N: set of products, r: assortment size, m: num- ber of samples, choice oracle Cy; TopKGMM D.
(C1, O2...., Cm. where C2 (A)
for 7 sampled from D.
2: Output: size center, T" center of
2: Output: C.. (A) if 0 # V.
3: T = 0, B 0, U = N
3: + 0A*xA=
4: repeat
4: for = 1: do
5: A assortment of size from UP
5: for E 1 {oi do
6:
S 0 collect choice data 9 by showing A repeatedly
6:
Xça= X a
7: for 1 do
7:
Xac: = Xan:
8:
S (A))
8:
end for
9:
end for
9: end for
10:
FINDTOP(AA (A
Y < -X/m
11:
if' + None then
11: if 3a Yau 24lAlaa' E Ao {a}
12:
T = TU (a), U U U. {a}
then
13:
else
12: Return
14:
B = BU U
else
15: end if
14: Return None
16: until U 0
end if
17: = |
18: T² SORTTCTT r., # (Algorithm
19: Return K,
"If [0| < use some elements from B
customers, recoding corresponding choices e, for 1.,..... A Pseudocode of BUCCHOI is presented in Algorithm 2 Assume TopKGMM distribution 'D with center r", and parameters B, प. Let Winin = minges W;, and n = -N]. The following theorem shows the sample complexity of BUCCHOT:
Theorem 5.1. Assume that 3 2 log 3/ w/imin and Ø & T". By only receiving N and as input and being able to collect choice samples by selecting assortments, with probability at least o(1), we are able to learn r" and k from D using only ( logn) choice samples.
The main building block of BUCCHOI is a procedure FINDTOP which given an assortment and a set of choice samples D, outputs _ such that i has the highest rank w.rt. r" among elements of A If all elements of _ are incomparable in r FINDTOP returns None. We note that FIND in not an active learning algorithm and receives D as input. We also assume that the choice data were collected by presenting a single arbitrary assortment A.
pseudocode for FINDTOP presented in Algorithm | The main idea is to maintain for each i E A variable Xıj. For any choice sample o, increment Xaj if is chosen over ie., = & and j A {cr), and we decrement it otherwise. Taking Yış = Xig/m m for all i,j A it is not diffficult to see that:
FINDTOP
E = -
TND
Based on this observation and by calculating lower bound on C, (i, CC(AA when i is ' top element w.r.t. 7" and j E a \ {i} we are able to show that the top element will be found by FINDTOP if the discrepancy parameter 3 is large enough and we have enough samples. Formally we show the following lemma whose proof presented full details Appendix
Lemma 5.2. Assume that 3 2 log(3)/ (og(3)/minn Wmin and let r = |A] and 2 1 arbitrary constant. If A appears at least O(C(r 1 1 log n.) times among the displayed assortments, with probubility at least
1 - (5n we have: if _ n * 0, FINDTOP will return i E A such that >,- j for any j E A {i}, otherwise, returns None, and we can conclude that A n==" =
BUCCHoT BUCCHOT first identifies all elements in N which are ranked above Ø and are in r".
To this end, we maintain three sets: T C 7" and B C 7", unknown whether they are in 7* or Assortments of size selected repeatedly and after calling FINDTOP either find the top

---

element in the assortment which has to be in T" or we find out that none of the elements in the assortment are in r" Note that the number of times that Repeat loop iterates is bounded by k + n/r. Finally we call Algorithm to find the rank of items in r". Theorem 5. will be concluded from L.2 and using a union bound on all FINDTOP calls. We remark that if e r", BUCCHOI will be able to return the top prefix of r" constituting of the elements ranked above Ø (see Appendix A.3)
6 Experiments
In this section, we present our experimental analysis, designed to achieve two main objectives: (1) to compare the predictive power of the top-k Mallows model (TopKGMM) with that of the multinomial logit model (MNL), and (2) to evaluate the accuracy and computational complexity of our methods, namely PRIM sampling algorithm, the DYPCHIP choice probability computation, and the two learning algorithms, FINDTOP and BUCCHOI. The code and log files are available publicly Results are generated by running the code on a MacBook Pro MI Max, 32GM RAM.
Predictive power of top-k MM compared to MNL: experiments real-world data We used "Sushi Preference Data Set" Set" (Kamishima et al. (005) which contains preference of customers over a set of 100 different sushi types The data-set includes 5K preferences in the form of top-10 lists.
Set-Up. We begin by randomly splitting the 5K top-10 preference data into a training set (80%) and test set (20%). We apply BUCCHOI using assortments of size training set using various values of and / to learn the center of the distribution. With the learned parameters, we use DYPCHIP to compute the corresponding choice probabilities.
two (Algorithm 7 to the
For evaluation, we use empirical choice probabilities on the test set by repeatedly sampling random assortments and recording corresponding choices. These empirical estimates are then compared to the predictions from DYPCHIP to assess out-of-sample accuracy; the errors are reported Table Based on these results, we identify the values of p and that yield the lowest test error. Figure shows the prediction error of the TopKGMM compared to MNL after tuning.
Considering multiple customer types, cluster the training data (into 2-5 groups) using the Kendall's s Tau distance K", varying p. Clusters with positive silhouette scores are retained, and choice probabilities computed within each cluster using both ToPKGMM and MNL. Final predictions are weighted averages based on cluster sizes. Figure shows the results for the two-clusters.
test errer MKL VS OMM
Test error of KN. top &t MN mocel
0.20
VML
0175
0323
8375
0.00
0.033
0.03
0.50
8803
0:05
(a) No clustering
(b) Training-set set partitioned into two clusters
Figure 1: Test error of the top-k Mallows model compared to MNL. Parameter 3 and have been selected to derive highest accuracy. Tables T and 2 show the test error for all choices of p and B.
Experimental Findings. Our findings show high accuracy of out-of-sample choice probability prediction of TopKGMM compared to the accuracy obtained from MNI. These results are consistent with findings of Désir et al. (20T)) who observe the same for classic Mallows model on permutations.
Accuracy and complexity of algorithms: experiments on synthetic Data We use synthetic data to evaluate the accuracy and complexity of our algorithms, as provides access to ground-truth choice probabilities and distribution centers- cnnters-iiformatiionn unavailable in real-world datasets. This enables controlled analysis of sample complexity trade-offs with respect to key parameters: n (number of products), & (size of top-k)), (assortment size), 3 (decay parameter) and p (Kendall's s Tau parameter).
P1 LLink to the code
"Link to of Sushi Preference Data Set http://wwwwww.otsssaaaeeeeete///

---

Accuracy and time complexity of PRIM and DYPCHIP. We evaluate algorithm accuracy by gener- ating samples from TopKGMM using PRIM and comparing empirical choice frequencies over random assortments to the probabilities predicted by DYPCHIP. This is repeated across 20 as- sortments, with the mean and standard deviation of results shown in Figure 2a The run-times of DYPCHIP and PRIM are reported in Appendix B.2
Accuracy and sample complexity of learning algorithms of BUCCHOI and FINDTOP. We evaluate our two learning algorithms by generating m samples from TMPKGMM distribution using PRIM and running FIND TOP and BUCCHOI to learn the top element or distribution center. We assess the convergence of these methods by comparing the learned and true values. When learning the center in BUCCHOI, we use the Kendall's 's Tau distance K" of learned and true center. In FINDTOP we check whether the learned top element is the same as the true top element and directly calculate accuracy based on the frequency of matching values. Each experiments repeated 10 times across a range of model parameters and average and standard deviation are obtained; see Figure 2 and Appendix B.3
Dihae acjecin TyPCCPPPCaaaaao calcomes angrital
30-
sccurecy of Reetoo
co-
04-
100
1000
number samples
Accuracy DyPCHIP for 200, 6, r
(b) Sample complexity of FINDTOP, 900,
4. p 0.5, 2I.
10,
p, w
21.
dittrccs tue and lesmeed conter
120
distancce
179
325
120
275
200
205
samples
nattore Sarr
(c) Sample complexity of BUCCHot for 10.p 0.5, 2T.
(d) Sample complexity BUCCHOI
500, &
300, & 8.p m 2, w 32222111.
Figure performance algorithms DYPCHIP, FINDTOP and BUCCHOI on synthetic data.
Experimental Findings. Our experiments in this section support the theoretical results on the accuracy and complexity of our algorithms. Notably, we observe that our methods achieve high accuracy with a relatively small number of samples-ofte logarithmic in the number of items n. For DYPCHIP, we find that time complexity increases rapidly with k., as expected due its exponen- tial dependence on this parameter (See Figure In contrast, the runtime shows minimal sensitivity the number of products n. For PRIM, the exponential dependence on le is less restrictive since primarily affects the preprocessing step; once this step is completed, generating a large number of samples remains efficient with low amortized cost (See Table 3)
In the learning algorithms BUCCHOT and FINDTTPP, we observe that the sample complexity increases as 3 decreases. This is expected, as smaller values cause the distribution to approach uniformity, reducing the concentration of samples around the center and making learning more challenging.
7 Conclusion
In conclusion, the generalized Mallows model for top-k lists provides more realistic framework for understanding user preferences, particularly when users care only about limited set of options. Our work centers on applying TopKGMM to choice modeling and developing several key algorithms. An important open direction is learning the model parameters for mixture versions of these models.
10

---

8 Acknowledgment
We are thankful to Anonymous NeurlPS reviewers for helping us strengthen the presentation of our paper. Shahrzad Haddadan is supported by Rutgers Business School's Dean's Research Seed Fund.
References
Akhari, S. and Escobedo, A. R. Top-k list aggregation: Mathematical formulations and polyhedral comparisons. In International Symposium on Combinatorial Optimization, pp. 51-63, Springer, 2022.
Awadelkarim, A. and Ugander, J. Statistical models of top-k partial orders. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. KDD '24, pp. 39-48, New York, NY. USA, 2024. Association for Computing Machinery. ISBN 9798400704901. doi: 1145/3637522.....
00.1145/363752836672111 URL https:///oo...rr///00 /ttp://00...rrr1011.1444411688 36720144
Awasthi, P., Blum, A., Sheffet, O., and Vijayaraghvaa,, A. Learning mixtures of ranking models.
In Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 2, NIPS' 14, pp. 2609-2617, 17, Cambridge, MA, USA, 2014. MIT Press.
Blanchet, J., Gallego, G., and Goyal, V. markov chain approximation choice modeling. Operations Research, (4(4):886-900 2016.
Boehmer, N., Celis, L. E., Huang, L., Mehrotra, A., and Vishnoi, N. K. Subset selection based on multiple rankings in the presence of bias: Effectiveness of fairness constraints for multiwinner voting score functions. In Proceedings of the 40th International Conference on Machine Learning. volume 202 of Proceedings of Machine Learning Research, pp. 2641 -6688. PMLR, 23-29 Jul 2023. URL httpsttps:/// ptttps:///rroeedinng. mlr press/ (aless/v202//oeee htee///eeeeeeeeeee 23a. html
Bradley, R. A. and Terry, M. E. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39/4/))3324 345, 1952.
Braverman, M. and Mossel. Noisy sorting without resampling, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '08, pp. 268-276, USA, 2008. Society for Industrial and Applied Mathematics.
Chierichetti, F., Dasgupta, A., Kumar, R., and Lattanzi. S. On learning mixture models for permuta- tions. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS '15. pp. 85-92, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450333337. doi: 15.1145/268877..0 262188887773.818111111 11. URI httth://///si org/ wtt.:o....///............ 1144/2688077 2688111
Chierichetti, F., Dasgupta, A., Haddadan, S., Kumar, R., and Lattanzi, Mallows models for top-k lists. Advances in Neural Information Processing Systems, 31, 2018a.
Chierichetti, F., Kumar, R., and Tomkins, A. Learning mixture of two multinomial logits. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 961-969. PMLR, 10-15 Jul 2018b. URL teattt::/ppooceediiee
mlr. prress/v0// http:/chheiiitttieeee html
Collas, F. and Irurozki, E. Concentric mixtures mallows models for top-k rankings: sampling and identifiability. In International Conference on Machine Learning, pp. 2079-2053 PMLR, 2021.
Critchlow, D. E. Metric methods for analyzing partially ranked data, volume 34. Springer Science & Business Media, 2012.
Dempster, A. P., Laird, N. M., and Rubin, D. B. Maximum likelihood from incomplete data via the em algorithm. Journal of the royal statistical society: series B (methodological), 39(1):1-22, 1977.
Désir, A., Goyal, V., Jagabathula, S., and Segev, D. Mallows-smoothhd distribution over rankings approach for modeling choice. Operations Research, 69(4): 2021.
Désir, A., Goyal, V., Jiang, B., Xie, T., and Zhang, J. Robust assortment optimization under the markov chain choice model. Operations Research, 2023.

---

Doigmon, J.-P., Pekeë, A., and Regenwetter. M. The repeated insertion model for rankings: Missing link between two subset choice models. Psychometrika, 69(1333355 2004.
Fagin, R., Kumar, R., and Sivakumar, D. Comparing top lists. SIAM Journal on discrete mathemat- ics, 17(1):134-60, 2003.
Feng. and Tang, Y. On maye model for (ranked) choices. Advances in Neural Information Processing Systems, 00630226266,,,, 2022.
Fligner, M. A. and Verducci. S. Distance based ranking models. Journal of the Royal Statistical Society, 1986. URL http://www jstor . org/ / stasle/ stable/2345433.
Fotakis, D., Kalavasis, A., and Stavropoulos, Aggregating incomplete and noisy rankings. In International Conference Artificial Intelligence and Statistics, pp. 2278-2286. PMLR, 2021.
Goibert, M., Calauzènes, C., Irurozki, E., and Clémençon, S. Robust consensus in ranking data analysis: Definitions, properties and computational issues. In International Conference on Machine Learning, pp. 1184-115997 PMLR, 2023.
Kamishima, T., Kazawa, H., and Akaho, S. Supervised ordering an empirical survey. In Proceedings of the Fifth IEEE International Conference on Data Mining, ICDM '05, pp. 673-676, USA, 2005. IEEE Computer Society. ISBN 0769522785. doi: 10.1109/CDD.2000 https://doi. org/10 10. 1109/ICDM. 200.://I................
URL
Lebanon, G. and Mao, Y. Non-parametric modeling of partially ranked data. Journal of Machine Learning Research, 9(79):2401 -429,, 2008. URL htt:htt::///mi http://...gg/ppppe///////aaaaaaa
html
Liu, A. and Moitra, A. Efficiently learning mixtures of mallows models. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 627-638, 2018a.
Liu, A. and Moitra, A. Efficiently learning mixtures of mallows models. 20/8 IEEE 59th Annual Symposium Foundations of Computer Science (FOCS), pp. 627-638. IEEE, 2018b.
Lu, T. and Boutilier, C. Learning mallows models with pairwise preferences. In Proceedings of the 28th international conference on machine learning (icml-11), pp. 145-152, 2011.
Lu, T. and Boutilier, C. Effective sampling and learning for mallows models with pairvise-preference data. J. Mach. Learn. Res., 15(1)33783-882, 2014.
Ma, J., Zhang, X., and Mei, Q. Fast learning of mnl model from general partial rankings with application network formation modeling. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, WSDM '22, pp. 715-725, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 978145039) 150031330. doi: 10.1 00.114///485500.4985666
URL htt.hhtts///ooo: org
10. 10.
3498506
Mallows, C. L. Non-null ranking models. i. Biometrika, 44(1/2): (4112)):114-1000 130, 1957.
McFadden, D. and Train, K. Mixed mnl models for discrete response. Journal of applied Economet- rics, 15(5):447 4700 2000.
Oh, and Shah, D. Learning mixed multinomial logit model from ordinal data. In Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N.. and Weinberger, K. (eds.), Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014. URL https: h htttps://proceeednngs meweeeeeeddddeeeeenne.seeeeeeeep neurips. cttppsscccpppp..ppe cumper_ffleet files/ Siaapprrfilesspppp////1////// papppppp///////eee 033356550cC0044446aaaaaaaaabb
pdf
Qian, Z. and Philip. L. Weighted distance-based models for ranking data using the package rankdist, Journal of Statistical Software, 90:1-31, 2019.
Rieger, A. and Segev, D. Quasi-polynomial time approximation schemes for assortment opti- mization under mallows-based rankings. Muth. Progrum., 208(1-2):111-17) December 2023. ISSN 0025-5610. doi: 10.100774110007-022-00033. 210107-0233
URI. https://dois http:///ooo..o/1..1000.000
022-0033---220------- 02033-4
12

---

Seshadri, A., Ragain, S., and Ugander, J. Learning rich rankings. In Larochelle, H., Ranzato, M., Had- sell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, vol- ume 33, pp. 9435-9446. Curran Associates, Inc., 2020. URL http:ttttts::/preeeeediii neurips httppp//....ppo......aaaaaaaaaaa
pdf
Susan, F., Golrezaei, N., Emamjomeh-Zadehh E., and Kempe, D. Active learning for non-parametric choice models. arXiv preprint ar.0v:220..033::30000 2022.
Tang, W. Mallows ranking models: maximum likelihood estimate and regeneration. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6125-6134. PMLR, 09-15 Jun 2019. URL
mlr www.mmr.rreeeee prw..spesssvvv//e https/////tttgggggg tang19a....... html
Vitelli, V., Sprensen, Ø., Crispino, M., Frigessi Di Rattalma, A., and Arjas, E. Probabilistic preference learning with the mallows rank model. Journal of Machine Learning Research, 18(158):1 49, 2018.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All claims in the introduction and abstract are later clearly stated in the main body of the paper as theorems with a clear statement of all theoretical assumptions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The runtime of some algorithms are large and this is explained in the experi- ments sections.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiiatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
The assumptions are clearly stated and all the proofs are presented in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: The details of set-up, evaluation metrics and the data-set are explained detail in the appedix of the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
15

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We have used publicly available datasets and cited them our paper. The code is attached to this submission.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
public/guides/ Soaddd/s///oeeSSmmmsiiiinooooe
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ https/cccppullcgggudeeeeeeeeeeee Coaee///ddeSSbbmmcma ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All hyperparameter settings are explained in detail in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: We have ran all experiments 5 times and average results are reported but we don't have statistical significance analysis. We don't ton't think it is applicable problem.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
16

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
They are reported at the beginning of the experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: It does.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
We are not aware of any negative societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We belive that our work does not have such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: We have only used publicly available datasets which properly cited.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We don't release new datasets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Our paper does not involve human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
20

---

A Missing proofs and details
A.1 Missing details from Section 3.2
To this end, we first establish the correctness of Lemma that proves profile S can be sampled according to PD [S].
In this section, we prove Theorem 3.1
3.3
Lemma (Restatement of Lemma 3.3
Given a TopKGMM distribution D with parameters 3, p and
w, any profile S = {s1, $2....,
se} S [k] (81 < < ... < st) has probability IP [S] proportional
exp (-3((S) (S), where:
f(5) waPQ(S)
+
Σ wy(1,(5)+
jE(R)Vs
nn-k) k) (k: E)! I12
Z(S) =
k -
j=1r=0
and it can be sampled in O22%)
Proof. Let M be the normalizing factor in Equation
TopKGMM M ETETU PD PT]T]. Then
PD [S] =
1
Σ
PDll
(Equation 2
M
TET(S)
1
Σ exp
-((wopQ(T)
+
Σ wj (4(())++)(+
M
TET(S)
jE(M
(Equation (TopKGMM)
Σ
-(wupQ((S)
Σ (E(R)(S
wy (1,())+PP(SS) + Σ
wj 12(T))
exp
M
TET(S)
jES
Σ
exp
B(wopQ(S)
Σ
wy (1, + (P2
exp
- -B> wy 1T(
M
TET(S)
kE(k](s
jeS
Σ W 1T(T)
exp
M
(ET(S)
JES
The remaining sum relates to the inversions of elements in S. Based on Definition 2.1 an element 8y E [k] makes an inversion with another element iff s, >-, and >- 8j. Note that since T E (S). the possibilities for such s are {sj+1,-.. }22 and the elements of [m] [K] which are now in r. i.e., T {k + 1,... n). Note that T n {k: + +1..... .n]
k Thus, the inversion of j (k f) which is any number from 0 to A: j. Furthermore,
can be any number between 0 to (E ((-5) for any valid selection of these values for elements j of these elements in are uniquely determined. This can be achieved by starting with sequence of k - stars which would correspond to any selection of elements from {k + 1.... ,n). and then inserting element E (st, $ , -1)) iteratively based on their value of L.. This shows the 1:1 correspondence between values of l,s and how elements of are positioned in r. Since there are (x=1) (I !)! possible cases for the arrangement of the remaining elements, we get that
w.r.t. defined ranges, then the position
Σ exp -B Σ W (T) = (n. TET(S)
n --k) -1 (
1)!
Σ choice I, for all +E.S
exp(-8 Σ w I1) Z(S). JES
JES
where the last equality follows from the fact that depending on the value of L.y, any of the terms in the summation + =",,, +.... + (k-j))m,, appears once. Taking product over the terms selected from these sums would exactly correspond to a valid selection of 1, for all S. Since M
21

---

ΣreTa,N Po [r] and each Pp [r] contributes to the PD [S], the defined values form probability distribution over different subsets of [k] where PD [S] proportional exp (-3f(S)) (SS).
remains to show that this value can computed in O(27 k);; - min n - kj. We argue that for each S, (() and S(S) can be calculated in (k), the total number of profiles is bounded by 27, hence all the computation can be done in (). For 2(S), the coefficient before sum has at most 2k terms and there are at most & terms in the sum where each term corresponds to a geometric series, so (S) can easily be calculated (kk). f(S) can be calculated in ((k) using the following algorithm which clearly has (lk) runtime.
Algorithm 3 TOPK
(TOPKGMM)
Input: TopKGMM (33, w).
Output:
Sampled Top-k ordering T proportional to D PROFILE PROBABILITY
((S)
Sample S proportional to PD [S] = S(S) Z(S).
Return [RIM(B, S).
Algorithm 4 PROFILE-BASHE RIM(PRIM)
Input: [opKGMM w). S 82, 88 C [ki where < 82 < ... < 8t. Output: Top-k list E (S). A + ordered random k 6- elements from [n] [k]
for 5é, st-1 S1 do
Insert s at position j in w.p.
exp(- Σ Zzz exp(- -Banaa)
end for Return A
Algorithm PROFILE PROBABILITY
Input: Profile $ = {si, 82, .2.....,8 se} S [k].
Output:f(S)
Q(S) (K-).
2, + 0,0
for j E (k, 1.... 1] do
1, + k: 1 a
P, < n 2k + y
j E S then
2 I
else
y <- y +
end if
end for
Return f(S) :- w>p(((S)) (
Using Lemma 3.3 and analyzing Algorithm we can prove Theorem 3.1
Proof of Theorem 3.1 Any T E TR,N with S 5 [kt], according to Algorithm is sampled with
probability
ESEs exp( (xxpp) Ejes exp(-3w,,)
(I: 1)! E/= Since each S, is sampled by
Z(S)
E Esc expl (f()))((8) we get that T is sampled with
exp( (op((ff(S))Z()
cxp(-Bf(5))Z(55
exp(E,es -Bw;Tz) exp(-8(f(S) Ejes -
Σ ScN Excneep(( (
Z(S)
Esc (xc=Bex((((((5)
22

---

where the denominator as previously discussed in proof of Lemma 3.3 is equal to normalizing factor M =EErr,, Po [r]. Since numerator just restating Equation (lopKGMM) each F is sampled
w.r.t Equation TopKGMM
Time complexity An upperbound on the number of profiles is 27:7- min(k, n kj. Therefore ((5) and [(S) can be computed in k(2>k) by Lemma and we can sample S in O(27 Next, fixing S, we need to execute A Algorithm 4 where we first need to sample k - elements which an be done in Ok log n). And then inserting elements of S with respect to probabilities that can be calculated in (kk for each element of S, so requiring O(k²) time for the recursive insertion loop. Hence overall the algorithm runs in ( + llog n k²); y = min(k, k}.
A.2 Missing details from Section 4.1
In this section, we provide the details in design of DYPCHIP. The main remaining part is the calculation of ( j. q) for given A, i I....,.,r......
.....r L, 2. r + q, k; where r = |A| and |S]. We remind the reader that in < (i.j.)):
f. and j = r + 1,
indicated the index of an item a whose choice probability being calculated. We use L to ranking of the elements in A U S where 01, 022, ar is an arbitrary ranking of A and 88, 8c-1, ......... 81 is the ranking of S used in PRIM. Thus, when we say a, we mean the ith element in L.
, refer to the ordered set (01, 02....., Ary $t, 81-1, ...11 81
j indicates the position of a; if it is the winner until the gth iteration of the for loop in PRIM.
When j = h mean that the winner is in 7.
q denote that so far we are considering only elements that have been sampled until the gth iteration of the for loop in PRIM.
Since (t, j. q) can only take non-zero value when is sampled in the top-k list, we either have a, E F or a, E S. We analyze each of these two possible cases separately. We first initialize the DP table for q 0 by considering i = 2, ... Then we consider items that are in S in the reverse order their priority (consistent with the Algorithm
1. Let A = A n.. Before start of the loop in PRIM, only elements of A have been sampled and have nonzero probability of being selected. These elements are the first r elements in our list. Thus, for i 1,2,.... .., r, we store these probabilities in the DP table as:
i-1 II
mi.j,0)
for S
n n n-k-j+1
72
j
the probability that is sampled position
the probability that element of A is sampled in positions
(" (o-)) (2=3)
[1,, k,
the case that A C 7
r+1
2. For q = 1,2,,..., f, consider the for loop in PRIM and let oeur be the element that is inserted in the top-k list at iteration of this loop. Therefore, 88+1-9- and in our list r + q. We distinguish between the two cases where
it is ranked (r t)th thus, Oeur A or not.
Case 1. aeur & A since dear is not a choice option, we have that Ts (s(cur, jj. g) = 0 for all j S q. For any cur, if Oear is inserted higher than the previous winner, the winner position will increment. If acur is inserted lower than the previous winner, the winner position will not change. Therefore Vi cur,
Ts(i. q) = (i.j.....11) PRIMPOSS > j. 9) tss 1.) j--1,9)
where PRIMPOS(S, j. 4) is the probability that at iteration q of PRIM we insert an element in a position after (lower than) j. and PRIMPOS(S, < j. is inserted before (higher than) j. Note that PRIMPOS(S, S j.g) 1 PRIMPOS(S,> j.g), and the probability PRIMPOS(S. < j.q) can be directly calculated using Equation (3) by summing over all insertion probabilities for j' 1, 2.........
23

---

Case 2. acur E : In this case, if dcur is positioned higher than the previous winner, it will become the new winner. Otherwise, the position the previous winner will increment. Thus,
vi cur, Ts(i, = 1) PRIMPOS(S, > 1.9)
Furthermore,
ss(eur, j.q) PRIMPOS(S.j.c)
Ts(i, ( ΣΣ i<eur j'=j
where PRIMPOS(S, j. q) is the probability that at the 9th iteration of PRIM we insert element in location j which again can be directly calculated from Equation
Proof of Theorem 4.1
The above analysis forms a proof for the correctness of DYPCHIP.
A.3 Missing proofs and details from Section S
In this section we provide the missing proof for correctness and sample complexity of BUCCHOI and FINDTOP and present the missing details.
Let us first present the pseudocode of SORTCNTR which is called in BUCCHOL
Algorithm SORTCNTR
Input:
choice oracle Cy; D where D is toPKGMM with center r*
U containing elements of T" as an (unsorted) set, assortment size
m sample size
B set of elements out of center
Output: 7* sorted
[0' for i = k do
# find the top element in U and delete it
T -U
repeat
# 'I' maintains potential top elements of U
Divide 7' non-intersceting assortments of size r: Ai A2. .2....
Ayi7 ..yb......... [i/r] elements
of B for A, if needed do
for ς
T = /
# collect choice samples by showing A,, customers and find the top element of A,
S = 0
for j == 1 m S SCC+(A
end for (FINDTOP(A,, S)}
end for until [T = U T end for Return 7"
SORTCNTR When BUCCHOI finds all the elements that are in the center, we call SORTCNTR to find the ranking of these items as a list. the for loop the item which positioned the ith will be found and deleted from U. In other words, we first find the top element of U this is the element ranked first, after deleting it, we find the top element in the remainder which is ranked second and so
24

---

In order to find the top element we use a Repeat- Untill loop. In this loop U is divided to assortments of size and using FINDTOP we find the winner in each assortment and continue by having tournament between the winners until the winner of all (which is the top element) is found.
Note that the repeat-until loop iterates at most log, (k) times. We call FINDTOP each iteration [k/r]] times, and since we have for loop the total number of times that FINDTOP is called is bounded by ((k² (k)).
We now present the proof lemmas and theorems. As before, without loss of generality we assume that T" 1>> > > ...k {1e + L........ ,n].
Lemma A.1. Leti < Au, and assume I (i1, de) Ae is such that < ig < for all 2 E I. We have:
(B(w)) Σ whe,) k=1
CD(L,A)) AD(i.A)) exp
Bluy +
Consider now fixed A and let ar, 1....,,,,11111 Ao be such that, for each a, there are elements in A which are ranked under by T", i.., Ha E A > a.} = i. As consequence this definition we have: |A]
and A n (a, a. 1..... a1j. and Ao F. We denote any
arbitrary element of Au by au-
Lemma A.2. For any ii = 1,r 2,... 2....1,0, 1,0, we have:
1 exexp( Bwa.)
Clar, A) - C(an, 2
1 perpeeexBuus
Proof. From Lemma A. C(ur,A) exp(-Bwa.) C(ax;A). A).
we can immediately conclude that: for any K = r 1,r - 2,...1,0,
Let us now rearrange this incquality:
C(ar; A)
2 C(ax; A)
C(a,,A) exp(-BBa..) A(a,,A) 2 C(a,: A) C(a,, C(a,, A) [1- -
& C(ar, A) - A)
On the other hand we have that: E Clax, A) + EageA, Clao, A) 1. Thus.
S C(ar, A) + rC(ar, A) exp(-Bwwa,) C(ar, A) 2 1/(1 + rexp( Bexp(-BBux (-Bwa..)
We now substitute this lower bound in Equation and obtain the premise.
Consider now for any for any í, E A for / 1,2, ... T. assume we keep displaying assortment A and consider the following random variable:
+1 if is chosen
X
if is chosen
otherwise
We denote Yú, = ET / /T, we have that:
E [Y =
In the following lemma we let Wiinn be the minium weight assigned to the elements in r", i.e.
Wmin = mingek
25

---

Lemma A.3 (Restatement of Lemma 5.2). Assume that Wmin log(3)/5 and r |A] and Ç 1 arbitrary constant. appears at least ((((r 1)a log n) times among the displayed assortments, with probability least o(n we have: if A n + 0 we are able to identify E A such that i < for any j E A {i}, otherwise, we can conclude that A 7 =0.
Proof. Note that if A Or* * there is at least one element with rank r in A For this element we may apply Lemma A.2 Note that this element is unique. If A Tr" 0, then the choice probability
of all the elements in A are equal 1/(r 1).
Assuming Wmin 2 log 3/8, may bound the right-hand side of Lemma A.2 follows:
Since ay E T
1 exp(-BWa,) 2 1 exp(-
2 - exp 3)
2 2/3.
Therefore,
exp(pxxx. + r cexp(3wa.
exp(-Buupp (Bwa r r1 cxp( -3wa,) )) +
We substitute exp(p (.,,). note 1 2 x: 2 2/3.
1
1 - 1E
Note that we have:
Itz 1+2r
S 2/3 for r 2 1.
Thus,
1 - x01 +r) 2 14r-11 FE
1+r F
x 2 1 1+r-12 Tx
x(1 2 1 +r
x2(1+r) + 2r) * r 2 2/3.
We now consider random variables Yi, for any i,j 1,2..... n as defined before.
We have:
i = a, =0 if i.jer E
2 1/(r+11
(8)
Using Hoeffding bound, we have:
P(Y EYy1 2 1/2(1 + +r)) < 2exp
(-32(1+ r)²
Which for T 2 64c(r 1)a log(n n + +r) is bounded by:
64c(r + 1)a log(n +r)
2 2exp
= 2exp (-2( log(n (n + +r)
32(1 + r)2
2n 26 r r- 22
26

---

In order to find we estimate Y, for all @(r²) pairs of ij in A Using the above bound, and applying a union bound over all pairs we have:
With probability 1 2n- 22::
Vi.j W.JEAP [y - B|y,, & 1/2(1 +))(1+))
Using Equation (). this means that:
With probability 1 2n 25;
VjEA, Ya.j >1/2(1 + r), and Vi,j ET Yu 1 +r)
We the above rule find a,: first we find all Yıss, and output the for which we have:
E \ (0) Y13 > 1/2(1++)
Note that if a, exists, there will be one unique A Equation 9 holds. Therefore, we take a, i. Alternatvelly, if there is no element with rank r we have vi,j E , E T thus, Yig 1/2(1 rr)
Theorem A.4 (Restatement of Theorem 5.1.. Assume that 3 2 log 3/Win and Ø $ T². By only receiving N and as input and being able to collect choice samples D adaptively, with probability at least 1 - (1). BUCCHOI is able to learn 5 and lo from D using only O log n) choice samples.
Proof. Note that BUCCHOI calls FINDTOP most O(k + n/r + h2 log, k) = O(n/r + k2 log, k) times. We take Ç = 3, and using Lemma 5.2 we have that by θ (3(r + 1)2 log n) choice samples which are obtained from presentation of A with probability 1 o(n-3) we will be able to identity the top element of A. Since the total number of pairs i, is (n/rr + log k)) = (n² log n), we need to take union bound over n² log variables thus, in total the probability of failure is bounded by o(n2n o11) from which we conclude the premise.
B Experimental setup and extra tables and figures
B.1 Details of learning choice probabilities on the Sushi data-set.
As explained in the main body, we have divided the data set into two con-intersecting parts for training (80%) and test sets (20%). We use the training set to learn choice probabilities. First we employ BUCCHOI-II (Algorithm BUCCHOI-II uses the top-10 sushi types as samples generated from an unknown distribution and collects choice data from it by actively selecting assortments. Since the result of BUCCHOI-II may produce partial orders, we break the ties, by using a score function based the random variables Xiş that are used in FINDTOP. In particular, since Xij shows the number times item beats j we use ΣjEN X1j as tie breaking score for item
This is needed because we need feed the learned center from BUCCHOI-II to DYPCHIP to learn choice probabilities and DYPCHIP receives as input a top-k list. Note that is unknown to the algorithm and we let BUCCHOI learn it. If is too large (>15) we truncate the learned center to reduce time complexity.
We tune parameters 3 and p by performing grid search over range of values in Table | From this table we conclude that 0.5 and 3 = 0.05 have the best test error. Thus, we select them as the model parameters. The mean and std of test error of the best parameters reported in Figure la
We handle learning mixture models by clustering the data into several clusters. First we use KP as a distance metric taking p E [0.01, 0.25, 0.05, 0.75. 0.1, 0.25, 0.5, 1.5, 2.2.5. 5) and then we divide data set to 2.3 or 5 clusters. Most of the clusters we obtain have a negative silhouette coefficient, and the only positive ones are:
27

---

Algorithm 7 BUCCHOI-II
Input, N: set of products, m: number of samples, choice oracle Cr; ~ D where D is topKGMM.
Output center of DD
T= 0
for i N do
S = 0
A {i}
for 1 m do
: = (A)
$ fuft
end for T T FUFIDTOOP(AA
end for for i T do
A == {i.}}
for j = 1: 1 do
C (A)
S SU {cp}
end for
if
FINDTOP(A, then [i]
else
<<]]
end if end for
Return
p= 0.1 num clusters 2: silhouette score 0.0062873993358866688
p= 1.25 num clusters = 2: silhouette score = 0.007796245381136666
p= 2.5 num clusters
silhouette score 0..004198089502999903
p= num clusters= 2: silhouette score 0.0110022017881645542
p= num clusters 3: silhouette score 0.002322231133397816
As we can see, even when the silhouette scores are positive they are pretty low, which suggests that one cluster is the best choice. This is consistent with the test error obtained, the model trained without clustering has a lower test error compared to the model trained on two clusters or more; see Figure 1b
9
0.05
0.1
0.25
0.5
0.75
1.25
1.5
1.75
2
p
0.01
0.1162
0.1047
0.0888
0.0879
0.0925
0.0979
0.1030
0.1087
0.1145
0.1202
0.025
0.1133
0.1007
0.0858
0.0872
0.0922
0.09768
0.1028
0.1085
0.1144
0.1201
0.05
0.1083
0.0938
0.0817
0.0852
0.0907
0.0964
0.1017
0.1075
0.1135
0.1193
0.075
0.1032
0.0868
0.0797
0.0841
0.0898
0.0956
0.1011
0.1070
0.1130
0.1188
0.1
0.0980
0.0798
0.0768
0.0819
0,0880
0.0941
0.0997
0.1058
0.1119
0.1178
0.25
0.0709
0.0598
0.0658
0.0732
0.0808
0.0879
0.09433
0.1009
0.1075
0.1139
0.5
0.0445
0.0555
0.0629
0.07098
0.0789
0.0863
0.0929
0.0997
0.1064
0.1128
1
0.0504
0.0619
0.0677
0.0748
0.0821
0.0890
0.0953
0.1018
0.1083
0.1146
1.5
0.0696
0.07479
0.0773
0.0825
0.0885
0.09454
0.1001
0.1061
0.1122
0.1181
2 0.0791
0.08115
0.0821
0.0863
0.0917
0.0972
0.1025
0.1082
0.1141
0.1198
2.5
0.0825
0.0834
0.0838
0.08769
0.0928
0.09824
0.1033
0.1090
0.1148
0.1204
5
0.0851
0.0851
0.0851
0.0887
0.0937
0.0989
0.1099
0.1095
0.1153
0.1209
Table 1: Average performed, average test error we obtain for MNI. 0.168.
for several choices of and B used for parameter tuning. No clustering has been
28

---

0.05
0.1
0.25
0.5
0.75
1.25
MNL
p =
0.0997
0.0771
0.0732
0.0748
0.0785
0.083
0.0876
0.1877
1.25
0.0788
0.09273
0.1022
0.1116
0.1224
0.1324
0,1409
0,1883
Table 2: average test error of learning choice probabilities, comparison of Mallows model with different Is and
MNL; 2 clusters are generated based on distance function X? for given The best values are highlighted.
B.2
Runtime PRIM and DYPCHIP
k pre-processing time
amortized time per sample
k:
12
14
8
== 10
12
k 14
16
200
0.007
0.035
0.19
1.06
8.64
5.67c-05
9.59c-05
0.00022
0.00074
0.0032
500
0.008
0.044
0.23
1.24
7.83
7.89e-05
0.00012
0.00025
0.00076
0.0028
1000
0.012
0.079
0.29
1,46
8.39
0.00011
0.00022
0.00031
0.00082
0.0030
Table 3: average (among 10 runs) runtime of sampling algorithm PRIM in seconds, B = 0.2
m-100
B-30V
n=100C
290
nc 12
D02000
rantie Oy
100
100
Figure 3: Runtime of DYPCHIP (in seconds) for various choices of k. Here 3 = 0.6, = 0.5 and
w = 21, size of assortment r = 2.
B.3 Additional tables and figures for the analysis of sample complexity of BUCCHOI and FINDTOP on synthetic data
10
k= 10
71 1000
6.95 + 5.06
0.4 0.48
2 = 1000
0.1 0.3
0.0
5000
228.5 + 53.3
228.6 64.56
5000
0.35 0.50
1.92 0.92
л 10000
934.05 209.35
870.1 259.64
a 10000
2.95 2.228
3.1
n 20000
3505.05 + 409.87
3282.55 708.9
n = 20000
5.1
3.5
9.0 13.2
Table 4: Kendall's Tau distance of true and learned center BUCCHOI with 100 (left table) or 200 (right table)
samples 1000, 5000, 10000, 20000 and 6, 10. We let / 0.6. distance reported mean these numhers are taken from 10 runs of algorithm.
3 = 0.4
8 = 0.6
8 0.8
8 = 1.2
50 samples
12.75
8.25
7.05 1 5.64
4.35
1
1.65
100 samples
0.67
0.35 + 0.549
0.0
0.0
+
0.0
0.0 0.0
Table Kendall's Tau distance of true and learned center by BUCCHOI with and 100 samples various
89, 1000, & 12, p = 0.5 reported as mean mean and standard deviation taken for 10 runs the algorithm for each set of paramcters.
29

---

18.
arcuneyy of Findlop
2.4-
beand.3
beand.3
beant
389
226
389
samples
(a) 1000,
21.
(b) 1000.
0.5, 2I.
33-
arcuaac Ffedlinn
866
bea-04
bean04
beand.3
bean0.3
22-
300
126
256
300
120
350
rumber of samples
rumber of semples
(c)
500, 12, 10, O.G, 10
27.
(d) n 500, 14, 12, O.G,
eccurecy of Findoo
eccurccy of FindTop
c.
becand 8.6
betan3
beran 2
berain 2
382
200
200
312
200
200
flumbeer
samples
samples
(e) p
322T.
32222211.
Figure 4: Sample complexity of FINDTOP for wide range of parameters.
30

---

+20
100
10%
190
maless
samples
(a) 1000, 10, 0.5, 2I.
(b) 1000, 14, 0.5, 2T.
distance true and learned ceneer
distance troe and learned ceneer
lecambb
-8-
numbber of camples
number of samples
(c)
300, & 8.p 1.5, 322T.
(d) n 300, A 8, 2, 32222113 11.
Figure 5: Sample complexity of BUCCHOI for wide range of parameters. y axis shows the Kendall's Tau distance between true and learned center while axis shows sample complexity
31


Reviews:
[{"review_id": "DdtmWmi8Tt", "reviewer": "Reviewer_W9Hi", "summary": "The authors propose a generalized Mallows model for top-k lists and develop efficient algorithms\nrelated to generating samples from it, learning its parameters and finding choice probabilities.\n\nIn particular, they propose a sampling scheme with running time exponential in k (the length of the top-k list) and polynomial in n, improving upon the previously best sampling scheme, and adapted to the generalized top k Mallows model. They give a dynamic programming algorithm to compute the choice probabilities\nAnd finally provide a method to learn the center of the top-k generalized Mallows model.\n\nExperimentally, they check the runtime of their algorithms and also show that that the test error on the Sushi data set is lower as compared to the Multinomial Logit Model.", "questions": "Why is Generalized Mallows sensible? Why would you only have weights attributed to the higher element?\nIs this well motivated or does it simply make the math easier?\n\nWhat is the sample complexity of doing the same things as you do in the paper for the Plackett-Luce model? In particular, the Plackett Luce model seems mode amenable to top-k rankings, since its sampling algorithm exactly sampled in order of ranking.What is the main different between Plackett Luce and Mallows, especially if in Plackett Luce once uses exponential weights?\n\n\nMinor Questions:\n\nWhy do you say that two items in tau bar are incomparable as opposed to assuming they are a tie (mathematically)?\nLine 29: \"High predictive Power of the Mallows model...\": What do you mean by this?\n\n\n\nLine 33: Can you reference concrete examples where platforms show user specific top k relevant items and the k\nIs the same across all users?\n\nWhat is \\tau^* in Equation 1? Do you mean \\tau'?", "limitations": "The algorithms are exponential in the parameter k, thus not practicable for larger k. It is not clear why the generalized version for top-k Mallows is needed.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I don't feel particularly convinced by several parts of the paper and I feel that I struggle to understand its relevance -  please see my questions for several things I am unclear about. The authors could much improve the motivation in the paper by offering concrete examples in which their particular model is more useful/ important/ relevant than other ranked choice models.\n\nThe experiments are down for the top-k mallows model not its generalized version and thus do not support the version introduced by the authors in this paper . This begs the question where one would use the weighted version.\nAlso the TopKGMM mixture models are computed by using the Kendall-Tau distance K^p, and then used to compare TOPKGMM with MNL, and I worry that this inherently is advantageous towards TOPKGMM. At the very least the authors should discuss this choice. Figure 1 and the meaning of the test error is further not clear to me.\n\nI am not convinced that this paper solves an open question regarding a new RIM for top-k Mallows. My impression would be that RIM is a very nice and simple method, and something is RIM-like in so far as it is still simple, not because it uses insertions in some way.\n\nLine 164:\nI would be useful to explain in words to the reader what I, P and Q mean.\nFor P_3(tau): are not 4,7,8 all greater than 3 and all of 3,4,7,8 satisfy that they ar in \\bar(\\tau)? Thus, shouldn't \nP_3(\\tau)=3? Similarly P_4(\\tau) seems wrong?\nLine 45: \"efficient\" - how is exponential in k an efficient algorithm?\nLine 159: Should the index in the summation include \\tau^*? What is \">\"? Is it the same as the curly version?\n\nMinor comments:\n\nLine 158: It would be helpful for the reader if you introduced the general inversion vectors before you introduce the special case, to understand what they are.\nLine 115: Chioces -> Choices\nLine 124: full stop missing\nLine 163: \"For example,..\" This is not a full sentence\nLine 167L \",\" should be on the previous line\nLine 210: later -> latter\n\nLine \"219\": One cannot evaluate the computational complexity of an algorithm through experiments..", "was_revised": true, "final_justification": "The authors resolved several concerns I raised and promised to improve the clarity of the paper.", "rebuttal": "Thank you for your time and careful reading of our paper. We try our best to answer your questions and looking forward to constructive conversation. We will fix the typos and apply the suggestions for clarifying the paper. \n\n**[Q1-a] Why is Generalized Mallows sensible?**\n\nGeneralized Mallows (for permuations) is introduced by Fligner & Verducci and it is a sensible extension because it more realistically captures user preferences by acknowledging that not all items are equally important. We develop this same extension to Chierichetti et al work on top-k lists .\n\n**[Q1-b] Why would you only have weights attributed to the higher element? Is this well motivated or does it simply make the math easier?** \n\nThe weights are associated with the “rank” of items. The higher elements in the top-k have rank $1,2,\\dots k$ and the lower elements all have rank $k+1$. This is consistent with the applications in which platforms have top-k rankings and the users are not exposed to the lower items. \n\n\n**[Q2] What is the sample complexity of doing the same things as you do in the paper for the Plackett-Luce model? In particular, the Plackett Luce model seems more amenable to top-k rankings, since its sampling algorithm exactly sampled in order of ranking. What is the main difference between Plackett Luce and Mallows, especially if in Plackett Luce once uses exponential weights?** \n\nModels based on Plackett-Luce, such as the Multinomial Logit (MNL) model are inherently different from Mallows models. The mallows model introduces a distribution based on the distance of a permutation (or a  top-k list) from the center distribution (or center top-k list); this distance is defined in terms of the number of transpositions (swaps) to go from one permutation to another one. Plackett-Luce Model does not use a central ranking or a distance metric. Instead, it assigns an intrinsic positive score or utility to each item. The probability of a ranking is determined by a sequential choice process: the probability of picking an item first is its score divided by the sum of scores of all available items. The process repeats for the remaining items. Using exponential weights (e.g., as in the MNL formulation) does not change this underlying score-based mechanism.\n\nAnother main difference of  PL/MNL model and Mallows models is in satisfying Independence of Irrelevant Alternatives (IIA) axiom which means the relative probability of choosing item $i$ over item $j$ is unaffected by the presence of a third item $\\ell$. The Mallows model violates the IIA axiom while MNL satisfies this axiom. In Mallows model, the probability of preferring $i$ over $j$ depends on the entire central ranking $\\tau$. This allows the Mallows model to capture more complex and realistic substitution effects among items, which is a key reason for its high predictive power.\n\n\nWe now respond to minor questions (MQ): \n\n**[MQ1] Why do you say that two items in a tau bar are incomparable as opposed to assuming they are a tie (mathematically)?** \n \nCould you please clarify this question? When saying i and j are incomparable we mean that the user has no preference of one over the other. As in previous work, e.g., Chierichetti et al, this is the terminology that is used. This shows a scenario in which users have no preference over less relevant items and they are ranked lowest for them. \n\n\n**[MQ2] Line 29: \"High predictive Power of the Mallows model...\": What do you mean by this?**\nWe mean that Mallows model when compared to MNL offers higher prediction accuracy (i.e., achieves lower test error) on several publicly available datasets. This is demonstrated by the work of Desir et al for the classic Mallows model and we show it here for top-k MM on Sushi data set. \n\n\n**[MQ3] Can you reference concrete examples where platforms show user specific top k relevant items and the k Is the same across all users?**\nIn many real-world applications, platforms have a fixed and limited space to display items. This is particularly true in online settings where, for example, a dedicated area on a website or an advertising box, e.g., on Google or Facebook, can only fit a predetermined number of choices. It also happens in the physical world, for example display areas of stores that display the latest arrivals however it has a fixed setup that would fit a predetermined number of items, e.g., stands in the store with a fixed number of shelves. Because of these spatial limitations, users are typically shown only the top-k most relevant items rather than an exhaustive list. This approach aligns well with user behavior, as people often express clear preferences for a limited number of favorite items and are indifferent toward the rest. Consequently, the preference data that can be collected from these platforms naturally takes the form of top-k lists instead of full rankings.\n\n**[MQ4] What is $\\tau^\\*$ in Equation 1? Do you mean $\\tau'$?**\n\nThanks for flagging this. There is a typo in the equation. We use $\\\\tau^\\*$ to refer to the central ranking, and we changed Eq (1) to make it a general definition and not just with respect to $\\tau^\\*$. However, we seem to have forgotten to completely update it. $\\\\tau^\\*$ should be updated to $\\\\tau’$ in the formula. We have updated our manuscript to reflect this.\n\nWe now responds to points made in Weaknesses: \n\n**[W0] What is the main different between Plackett Luce and Mallows, especially if in Plackett Luce once uses exponential weights?**\n\nModels based on Plackett-Luce, such as the Multinomial Logit (MNL) model are inherently different from Mallows models. The mallows model introduces a distribution based on the distance of a permutation (or a  top-k list) from the center distribution (or center top-k list); this distance is defined in terms of the number of transpositions (swaps) to go from one permutation to another one. Plackett-Luce Model does not use a central ranking or a distance metric. Instead, it assigns an intrinsic positive score or utility to each item. The probability of a ranking is determined by a sequential choice process: the probability of picking an item first is its score divided by the sum of scores of all available items. The process repeats for the remaining items. Using exponential weights (e.g., as in the MNL formulation) does not change this underlying score-based mechanism.\n\n\nAnother main difference of  PL/MNL model and mallows models is in satisfying Independence of Irrelevant Alternatives (IIA) axiom which means the relative probability of choosing item $i$ over item $j$ is unaffected by the presence of a third item $\\ell$. The Mallows model violates the IIA axiom while MNL satisfies this axiom. In Mallows model, the probability of preferring $i$ over $j$ depends on the entire central ranking $\\tau$. This allows the Mallows model to capture more complex and realistic substitution effects among items, which is a key reason for its high predictive power.\n\n\n**[W1] The experiments are down for the top-k mallows model not its generalized version and thus do not support the version introduced by the authors in this paper. This begs the question where one would use the weighted version**\n \nWe extended the topKMM model to topKGMM model since our sampling and dynamic programming algorithms are applicable in the general setting. \nOur learning algorithm is also applicable to arbitrary weights as long as the condition of $\\beta>\\log 3/w_{\\min}$ is satisfied (see theorem 5.1). The learning algorithm learns the center as well as the parameter $k$ and does not learn the weight vector $\\vec{w}$; learning weights is a difficult problem and is left as a future direction.\nVarious weight vectors (combination of 3s 2s and 1s) are chosen in synthetic experiments. For the experiments on sushi data we only used the topkMM model since we have no algorithm for learning the weights. \n\n**[W2] Figure 1 and the meaning of the test error is further not clear to me.**\n\nWe have run the algorithms 10 times and the figure shows the mean and std of the test error. \n\n**[W3] I am not convinced that this paper solves an open question regarding a new RIM for top-k Mallows. My impression would be that RIM is a very nice and simple method, and something is RIM-like in so far as it is still simple, not because it uses insertions in some way**\n\nA key property of RIM is that it inserts the elements iteratively in the permutation (top-k list) by explicitly calculating the probabilities of insertion. This property is fundamental to the design of the dynamic programming algorithm for calculating choice probabilities. \nOur algorithm PRIM has a similar property: after sampling a profile inserts the element iteratively in the top-k by explicitly calculating the probabilities of insertion. This property is used in the design of DyPHIP.\n\n**[W4] Clarification request**\nThanks for flagging the areas that need clarification. We will make sure to address these in the final version."}, {"review_id": "kkzg3kfFC4", "reviewer": "Reviewer_CcCu", "summary": "This paper proposes a novel sampling strategy, an efficient algorithm, and a parameter learning method for generalized top-k Mallows models. Specifically, traditional Mallows models only fit the full permutation circumstances, while practical scenarios require Mallows models for top-k assortments, which are called generalized Mallows models. The proposed method extends the generalized Mallows models from three perspectives: RIM for generalized Mallows models, choice probabilities calculation for top-k list, and the choice centers construction. The authors provide the theoretical guarantee and empirical validation to support the effectiveness.", "questions": "1. How to use the proposed method for practical problems? In other words, can the authors provide a usage example/algorithm (or maybe it is one of the presented algorithms in the Appendix)? \n\n2. How do centers of choices help to enhance the framework?", "limitations": "Yes.", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "I am totally unfamiliar with the topic and could only provide some reviews on formatting and illustration. My understanding of technical details might be wrong, and the authors are welcome to figure out mistakes within my review. \n\n# Strength\n\n1. Clarity. The authors clearly state their motivation, method, and experimental results. The background and notations for the studied problem, as well as the practical usage scenarios, are sufficiently illustrated to understand the problem and setting of the work. \n\n2. The authors provide theoretical guarantees for the proposed method. \n\n3. Extensive experimental results are provided to support effectiveness. \n\n\n\n# Weakness \n\n1. The text in several figures is too small to read. \n\n2. The grammar in some places might be problematic; please check. For example, around Line 23, the authors wrote, \"Based on Plackett-Luce (PL) model the Multinomial Logit (MNL) model has been suggested\", where there should be a comma between \"model\" and \"the\". \n\n3. A holistic comparison with current methods may help to signify the importance of the proposed method. The authors illustrated their contributions by iterating the components, where there is a lack of an overview of the systematic advancement of current methods. The authors may illustrate how they achieve more usable/suitable generalized Mallow models by proposing three novel components.", "was_revised": true, "final_justification": "Due to the limited relevance to my area, other reviewers may ignore my ratings.", "rebuttal": "Thank you for the supportive review. We appreciate the careful read and make sure to fix the typos for the final version. Please see below for responses to your questions:\n\n**Q1** \n\nThe proposed methods, centered around the Generalized Top-k Mallows Model (TopKGMM), offer a robust framework for addressing practical problems involving user preferences, especially when those preferences are expressed as top-k lists rather than full rankings. For practical application, the process primarily involves two key algorithms: BUCCHOI and DYPCHIP. BUCCHOI is used first to learn the underlying central ranking ($\\tau^\\*$) and other model parameters from observed customer choices, which are typically recorded as (assortment, chosen_item) pairs. It achieves this by adaptively presenting specific assortments and inferring preferences based on selections. Once the model parameters are established, DYPCHIP efficiently calculates the choice probability for any given item within an assortment. This predictive capability is vital for businesses, enabling them to optimize product assortments, refine recommendation systems, and enhance advertising strategies. \n\n**Q2**\n\nWe are not sure if we understand this question clearly. Please let us know if the following answers your question. \n\nThe main ranking acts as the fundamental \"true\" preference order for a user or a group of users. Rather than modeling preferences as a set of disconnected probabilities, the center provides a single, intuitive ranking that summarizes the core preference structure. This makes the model more interpretable; one can look at the central ranking to understand the typical preference of a customer population."}, {"review_id": "oh5lccwDPV", "reviewer": "Reviewer_wgQk", "summary": "The paper proposes a generalized Mallows model for top-k preference lists over n items that allows item-specific weights and extends the Kendall-tau distance to partial rankings. Three tasks are considered: sampling a top-k list according to the model. It takes  O(k*2^k+klogn) time; computing the choice probabilities, which takes O(2^k*k^3*∣A∣^2) time, where A is the assortment; and an active learning algorithm that learns the central ranking with O(log n) assortments.", "questions": "1 It is claimed that \"once setting w = 1, we obtain Equation (TopKMM).\" But that equation is actually parameterized by w. Is there a typo? \n\n2. Why omit Mixed-MNL or Plackett–Luce mixtures? This is usually included in the literature so explanation of the exclusion would be helpful. \n\n3. It is unclear what the 100-sushi data tries to mimic in practice. If the authors are just trying to mimic a situation where the observer can only see single choices, then the value of \"k\" is only a hyper-parameter to be tuned. If the authors are actually using the fact the the raw data is based on top-10 lists, why not directly train the model based on the top-10 lists?\n\n\nApart from that, I do not have questions beyond the \"weakness\" comments.  That said, in the rebuttal, if the authors can come up compelling advantages of the newly proposed model/method compared to what has been proposed in the literature, I am happy to re-evaluate.", "limitations": "Yes (after various clarifications of the rebuttal process).", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength: \n\n\nThe main contribution of this paper is the introduction of a probabilistic model for top-k lists, which extends the Generalized Mallows Model of Fligner and Verducci (1986). The analysis of the sampling procedure and the derivation of choice probabilities build naturally on prior work, particularly the RIM method and the dynamic programming framework. The derivations can be difficult, given the complex combinatorial structure, and hence the paper has merits in terms of technical contributions. Overall, the paper is clearly written.\n\n\nWeakness:\n\n\n\n1. (Computational complexity) It is unclear how computationally tractable the proposed GMM for top-k lists is in practice. For example, according to Theorem 3.1, even sampling a top-k list can take O(k·2^k) time, which is a very weak guarantee when k is close to n. This contrasts with the RIM method, which remains efficient at least when k = n, and the sampling procedure of Feng and Tang (2021), which is very efficient albeit based on a different variant of the Mallows model. Unsurprisingly, computing choice probabilities also appears challenging when k is large; see Theorem 4.1.\n\n\n2. (Parameter learning from choice data) Given the discussion above, it is only natural to expect that learning (i.e., estimating the model parameters) from choice data would be even more difficult. I therefore read Section 5 with interest, but found the results somewhat underwhelming for several reasons:\n\n\n    - 2a First, the analysis assumes that the algorithm has full control over the assortments. In fact, I believe BUCCHOI only picks assortments of size at most two. From a practical perspective, however, the observer may only be endowed with observed data and then the question is how to infer the model parameters (e.g., the central ranking) in which the assortment history is arbitrary (i.e., not controlled by the observer). Methodologically, this is precisely the challenge that much of the prior literature (e.g., Desir et al. 2022; Feng and Tang, 2021) was trying to address, but this paper effectively sidesteps it. If the assortments are only pairwise, there is already a **very** vast body of work on passive and/or active learning of ranking and/or best-item identification from pairwise comparisons. (So even in the active learning setting, it is unclear how strong the sample complexity guarantee of \\Theta(\\log n) is.)\n\n\n    - 2b Another important question is that the model brings richness by introducing a few new parameters and the paper remains relatively silent about how to determine them. Based on Section 5, the underlying data are choice data (rather than ranked or top-k list data). This makes the value of k essentially a modeling parameter, but it is unclear how to \"learn\" the right k. In addition, one of the key distinctions of this model compared to the original Mallows model is the introduction of the \"weights\" w. However, it remains silent how these w parameters should be calibrated. If making them uniformly one, does the proposed model go back to some more basic version of TopKGMM?", "was_revised": true, "final_justification": "Overall, the Mallows model and its variations remain challenging combinatorial objects to analyze and apply. This paper makes a meaningful contribution by extending the literature to a weighted version of top-k distributions. The authors’ analysis of choice probabilities from arbitrary assortments, along with their demonstration of how the model can be applied to learning from discrete choice data, is particularly commendable. \n\nIn my view, the contributions are sufficient. I am happy to recommend acceptance.", "rebuttal": "We thank the reviewer for their helpful comments; we will use this feedback in preparing the camera ready version. \nHere is our response to some of the questions:\n\n**Re W1 (Computational complexity)**\n\nThe sample complexity of $O(k·2^k)$ is only for a pre-processing step in PRIM (sampling algorithm), and generating samples after this step only takes polynomial time. We assume that $k$ is small, which is a common assumption due to practical setups in online platforms, and cognitive abilities of users for ranking items (see Chierchetti et al for more explanation). A common choice for $k$ is $10$ (with datasets collected as in thetoptens website)  for which the preprocessing time is constant and hence generating samples takes $\\Theta(\\log n)$ (see Theorem 3.1). We also note that our algorithm is more efficient than the sampling algorithm of Chierichetti et al (even considering the pre-processing step).\n\nBoth in the preprocessing step of RIM and DypCHIP the $2^k$ term is an upper bound on the number of ``profiles’’. For $k$ close to $n$ the number of profiles becomes polynomial in $n$ and specifically for $k=n$ the number of profiles is only 1. For $k=n$ PRIM and RIM are the same algorithm since we will only have one profile.  \n\n**Re W2 (Parameter learning from choice data)**\n\n**Re W2a**\n\nWe would like to clarify a few points about our learning algorithm BUCCHOI: (1) whether it is only applicable in active learning scenarios (2) how does the algorithm compare with prior works which use pairwise comparison data. \n\nThe crux of our active learning algorithm BuCCHOI is the FindTOP (Algorithm 4 in the appendix). Given an assortment $A$  which is repeatedly shown to the user and choice data collected,  FindTOP finds: an element in the assortment which has the highest rank among other elements in the assortment w.r.t. $\\tau^\\*$ the center of the distribution. If such an element does not exist, i.e., none of the elements in the assortment are in the center (thus, they are all incomparable w.r.t. $\\tau^*$ ) the algorithm returns none. \nA simple case is if the assortment  $A=\\\\{i,j\\\\}$ has size two. In this case FindTOP outputs  $i$ meaning $i>\\_{\\tau^\\*} j$ or outputs $j$ meaning  $j>\\_{\\tau^\\*} i$ or None meaning  $i\\parallel_{\\tau^\\*} j$. Thus, we obtain full information about the relative order of $i$ and $j$.\n\nIf the assortment $A$ has size $\\\\ell$ we either infer $\\\\ell-1$ pairwise comparisons of the elements; or that all $\\ell$ elements are incomparable and do not belong to the top-k center. For instance, assume given $A$ FindTOP returns $i\\in A$  this means that $i>_{\\tau^\\*} j$ for any $j\\\\in A\\setminus\\\\{i\\\\}$ ($\\\\ell-1$ relations) or it returns None meaning $i,j\\in A\\implies i\\\\parallel\\_{\\\\tau^\\*} j$.\n\nFindTOP can be used either in a passive algorithm where the assortments are not selected by the algorithm or in an active algorithm. Clearly, if the assortments are not selected, we may only obtain some partial knowledge of the top-k center. It is not clear how to then expand this partial information to a top-ranking. We will add this question as future work in our conclusion and we will clarify that our methodology is an active algorithm in the introduction. \n\nThe reviewer is correct that  BuCCHOI is only using pairwise comparison. But this is only for the simplicity of design. We could use FindTOP with various sets of assortments to find the center. For instance assume that the assortments must be all of size $\\ell$. In this case we can use the following algorithm:\n\n* Divide the n elements to non-intersecting assortments of size $\\\\ell$ (assuming that n is divisible by ell for simplicity): \n* Run FindTop on these assortments, let $S = \\\\emptyset$\n * * If FindTOP returns NONE then none of the elements in the assortment are in the center. Add them to set $S$. \n * * If FindTOP returns $i$, $i$ belongs to the center, replace $i$ with an element $j$ in $S$ and run FindTOP on this new assortment. \n* Repeat the above two steps until all elements of [n] are either in $S$ and for those which are not in $S$ all the pairwise orders are determined. \n\nNote that this procedure concludes after $n/\\\\ell+2k$ assortment queries as with $n/\\\\ell+k$ calls we can get the top-k elements and with $k$ calls we can get the ordering of them. \nSimilar to Theorem 5.1 we can prove that the sample complexity will be $O(\\\\ell^2\\\\log n)$. \n\nThe reason that we design BUCCHOi using pairwise comparisons is merely simplicity and many other algorithms similar to the above can be designed to infer the relative orders of all pairs of items. \n\nWe thank the reviewer for mentioning the existence of a broad body of works considering pairwise comparisons. When it comes to learning Mallows model center the most notable prior works are [Lu and Boutilier] and [Vitelli et al]. Both of these works are based on Maximum likelihood estimation and the EM method and only the convergence of algorithms are shown. These works differ from our work in the sense that they do not include any mathematical analysis of finite sample complexity bounds or theoretical guarantees on the error. \n\nIn our work by the use of concentration bounds we have provided a mathematical guarantee on the error of FindTOP and BuCChoi showing their finite sample complexity, \nThis kind of mathematical guarantee does not exist in prior work which considers choice data or pairwise data and only exists when permutations or top-k samples are available or a linear order of some items are available.\nWe thank the reviewer for pointing out this ambiguity and will add the above discussion to our paper.\n - [Lu and Boutilier] Effective Sampling and Learning for Mallows Models with Pairwise-Preference Data, Tyler Lu and Craig Boutilier, JMLR 2014\n-  [Vitelli et al] Probabilistic Preference Learning with the Mallows Rank Model, Valeria Vitelli\nOystein Sorensen, Marta Crispino, Elja Arjas, JMLR 2018\n\n\n**Re W2b** \n\nBuCCHOI is learning both the center and $k$. BuCCHOI (or any other algorithm which uses FindTOP such as the above) finds all pairwise ordering of the elements in [n] without knowing $k$. When these orderings are found, k is also found. Therefore, BuCCHOI also learns k. The reviewer is correct that we do not have an algorithm for learning the weights however we are **not** assuming that $\\\\vec{w}=1$. In order for our algorithm to work (Theorem 5.1), we just need that $\\\\beta> \\\\log 3/w\\_{min}$. Learning weights requires additional analysis and hence we leave it as a future direction. \n\n\n**Re Q1**\n\nWe are not sure what you are referring to here. We don’t have $w$ in line 143. Would you please clarify where you are referring to?\n\n**Re Q2** \n\nWe considered the possibility of mixture models however, our algorithm is not directly applicable to mixture models. To handle a mixture of models, we first cluster the data to 2-5 clusters. Our thought for bypassing MNL mixture models was that we wanted to have an apple to apple comparison with our method which is not a mixture model. \nWe note that, after doing the clustering the silhouette coefficient was always very low and we observed the lowest test error of our algorithm associated with no clustering. Therefore, we did not explore other possibilities for mixture models. \n\n\n**Re Q3**\n\n It is true that the Sushi dataset is top-10 and we can just focus on learning top-$k$ without assuming access to choice data, however the goal of our paper is to use choice models to learn top-$k$. Since this is a prominent dataset used in prior work and that we were not aware of any other dataset suitable for our method, we curated it to generate choices. \nWe assume that the top-10 lists of the sushi data set are samples generated from a TopKMM and we learn its center. We have used these samples and our definition for choice for top-k lists (lines  231-233 of the submitted manuscript) to generate choice data. In particular, for a given (we chose $A$ randomly) assortment $A$ and sample $\\tau$ we take the choice to be the highest element of $A$ with respect to $\\tau$ if $A\\cap \\tau=\\\\emptyset$ we select uniformly at random an element of $A$."}, {"review_id": "8skf8Y9VT3", "reviewer": "Reviewer_7DBg", "summary": "The paper studies top-K Mallows model, a variant of the ground truth-based statistical model, for sampling rankings. The paper builds on a paper by Chierichetti et al. titled “Mallows models for top-k lists”. First, the paper provides the “PROFILE BASED REPEATED INSERTION METHOD”, i.e.,  sampling procedure for the generalized version of the Mallows model. Second, the paper introduces the “DYNAMIC PROGRAMMING FOR CHOICE PROBABILITIES”, i.e., a method for calculating the choice probabilities functions. Third, the paper provides the “BUILD CENTER FROM CHIOCES”, i.e., a learning algorithm for inferring the ground truth of Mallows. Finally, the authors provide experimental analysis, demonstrating the behavior of the top-k Mallows model. They use synthetic data and real-life Sushi model (one of the most frequently used dataset in computational social choice).", "questions": "Q1: In what practical use-case the p parameter would be set to a value larger than 1? (Intuitively I would say that p should fall in [0,1] interval).", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "[Significance]\n\nThe Mallows model is widely used, and the generalization to the top-*k* variant seems like a natural and valuable extension that one would want to have.\n\n[Originality]\n\nThe originality of this paper is somewhat limited, although I don't see that as a major drawback.\n\n[Quality]\n\nThe overall quality of the paper is good, with some minor issues that should be addressed:\n\n- Lines 138/139 “This concept has been extended to top-k lists, where it no longer forms a true metric but retains useful mathematical properties.” This statement is too vague. There are various ways in which a function can fail to be a true metric—for example, becoming a pseudometric, semimetric, or quasimetric. It seems that the function described here is a semi-metric as it fails the triangle inequality. Please clarify explicitly in what way the function deviates from being a true distance.\n- The citations occasionally feel somewhat arbitrary. While the paper includes an extensive list of works related to the Mallows model, several cited papers seem only vaguely relevant. It would be helpful if the authors reviewed the bibliography more carefully to ensure relevance and accuracy. For example, ”Liu, A. and Moitra,” appears twice. (Side comment: it might be worth taking a look at “Properties of the Mallows Model Depending on the Number of Alternatives: A Warning for an Experimentalist”)\n- “the generalized Mallows model for top-k lists provides a more realistic framework\nfor understanding user preferences”—while this is quite a strong statement, there is little evidence supporting it in the paper.\n- The authors state that “the Multinomial Logit (MNL) (Bradley & Terry, 1952) model being the most widely used due to its simplicity and interpretability.” Please provide justification for that claim. Additionally, clarify the context in which the model is considered “most widely used”. For example, in the context of computational social choice, the “Guide to Numerical Experiments on Elections in Computational Social Choice” suggests that the impartial culture model is the most widely used.\n\n[Clarity]\n\nClarity of the paper could be improved. \n\n- The font size in Figures 1 and 2 is far too small. As a result, the plots are difficult to read and fall short of NeurIPS presentation standards. Please increase the font size and improve the overall readability of the figures.\n- The “Preliminaries and Definitions” section looks like it is almost copy pasted from the “Mallows models for top-k lists” paper.\n- The authors refer to Kendall’s tau distance, by writing: “Kendall”, “Kendall tau, and “Kendall Tau”. Please unify the name throughout the paper.\n- Line 26: “The Mallows model Mallows (1957)” is awkward. Please rephrase this sentence or use a different citation command.\n- Line 167: A misplaced comma should be moved one line above\n- Line 179: “method for permutations Doignon et al” is awkward. Please rephrase this sentence or use a different citation command.\n- Typo in line 115: CHIOCES", "was_revised": true, "final_justification": "Considering the entire discussion, I increase the evaluation from \"borderline accept\" to \"accept\".", "rebuttal": "Thank you for your time and review. We make sure to apply the suggested changes to make the paper more clear. Please see below for responses to your questions. \n\n**Question.  In what practical use-case the p parameter would be set to a value larger than 1?** \n\n$p \\\\geq 0$ is the parameter for controlling the penalty per a pair of elements that are comparable in one top-k ranking but incomparable in the other.\n\nConsider $\\tau$ to be the top-k center. For instance, let $n=100$ and $k=10$, and consider the center $\\tau=1, 2, 3, 4, 5,...10$. By increasing $p$ (e.g., $p>1$), the probability of any top-k ordering $\\sigma$ with a small size of $\\tau \\cap \\sigma$ will decrease. For instance, in $\\sigma=11,12,13,14,...,20$ or $\\sigma=12,13,...21$, or any other top-k with $\\tau \\cap \\sigma=\\emptyset$, there are ${10}\\choose{2}$ elements that are comparable in $\\tau$ and incomparable in $\\sigma$, all of which incur the penalty of $p$. Meanwhile, in $\\sigma=10, 9, 8,...1$, all pairs pay a penalty of $1$. Therefore, by increasing $p$, we decrease the probability of top-k's whose intersection with the top-k center is small.\n\nThe use case where $p > 1$ would correspond to cases where losing information regarding a relative order of two items is much worse than mis-ranking them, i.e., inclusion of an item in the top-k set is more critical than its exact position within that set.\n\nA practical example is a product recommender system on an e-commerce website. Imagine a system that displays the \"top 5 laptops for students.\" For a potential customer, it is crucial that the most relevant and suitable laptops appear on this initial list. If a highly appropriate laptop fails to make the top-5 cut entirely, the user may never discover it, leading to a poor user experience and a potentially lost sale. This large penalty for an item dropping out of the top-k list corresponds to a high value of $p$.\n\nIn contrast, if that same laptop is present in the top-5 list but is ranked at position #4 instead of its \"true\" rank of #2, the outcome is still largely positive. The user sees the item, can click to evaluate its specifications, and might still purchase it. The penalty for this internal mis-ranking (an inversion) is less severe. \n\n**Comment on the importance of the impartial culture model versus MNL:**\n\nIn the  impartial culture IC, the preference of each user is drawn independently and uniformly from the rankings of candidates. The Impartial Anonymous Culture (IAC) complements this model by using a uniform distribution over preference profiles (defined as tuples of rankings). \nBoth of these models are primarily used in analysis of voting behaviors. In many applications, the simplicity of these models (in particular the assumption of uniform samples) is unrealistic therefore, the MNL model is used in a wider range of applications. \nWe note that the IC model (uniform sampling) is a special case of the MNL and Mallows model. In MNL we obtain uniform distribution by setting all utility values equal to one and in Mallows model we obtain it by setting the discrepancy parameter $\\beta$ equal to 0 \n\n\n**The section 2 looks like it is almost copy pasted from the “Mallows models for top-k lists” paper:**\nThere are some similarities, although we state these definitions in a more general form and use inversions tables. In this section, we review the definition of Mallows models for top-k lists. Note that the main contribution of our paper is to use this model for modeling choice and choice probabilities."}, {"review_id": "yuQccqe6ao", "reviewer": "Reviewer_jMHU", "summary": "This paper proposes inference methods for generalized Mallows model using top-K ranking data, in which each item has an associated weight. Inference is built on efficient sampling of rankings by reducing the computation time of the method by Chierichetti et al. (2018a). Two methods are then proposed for estimating choice probabilities given model parameters and estimating model parameters given choice data.", "questions": "N/A", "limitations": "Please see above.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: Extensive theoretical analysis and synthetic data experiments are provided. Real dataset experiment shows improvement against the Multinomial Logit (MNL) model. \n\nWeaknesses:\n\nA notation table would have been very helpful to improve clarity, particularly as the proofs in the Appendix have some inconsistencies (e.g., caligraphic P should be standard P in line 815, Equation 6 numerator should be A^bar). Further, terminology is inconsistent such as items, samples, products meaning the same thing. \n\nWhile it is important to outperform MNL, this observation is somewhat expected with respect to the literature (e.g. Desir et al.). It is more interesting to compare the proposed algorithms in terms of predictive accuracy and computation time to existing efficient top-k Mallows model inference algorithms like Chierichetti et al. or Fotakis et al. \n\nHyperparameters p and beta were tuned on the test set (rather than a separate validation set), which is unfair against the MNL model.", "was_revised": true, "final_justification": "The authors have addressed all of my comments", "rebuttal": "Thank you for your comment on the clarity of our paper. We will fix the typos and include a notation table in the camera-ready version. We would appreciate engagement in the rebuttal so we can address the reviewer's concerns.\n\nWe now respond to raised questions:\n\n\n**Comparison with Chierichetti et al. or Fotakis et al.**\n\nA direct experimental comparison with Chierichetti et al. and Fotakis et al. is not straightforward because our work addresses a fundamentally different problem. Our paper focuses on the choice modeling setting, using our BUCCHOI and DYPCHIP algorithms to learn a preference model from choice data—i.e., observing a single selected item from an assortment. Chierichetti et al. learn the central ranking from a dataset of observed top-k lists, which is a different and more information-rich signal than choice data. Fotakis et al. focus on the problem of aggregating incomplete and noisy rankings to find a consensus ranking; a distinct task from learning a generative model to predict single choices from assortments. Comparing predictive accuracy would require extending these models to handle choice data, a non-trivial task that our work addresses. To make this distinction clearer, we will expand our Related Work section to better contextualize our contributions.\n\n\n**Hyperparameters $p$ and beta were tuned on the test set (rather than a separate validation set), which is unfair against the MNL model**\n\nOur goal was to do a comprehensive study based on different choices of $p$ and $\\beta$. To this end, we performed experiments for these different choices (through a grid search). Our goal was not to do tuning rather a comprehensive study.  We can clarify this better in the final version. We would like to emphasize that even without tuning we get better test errors; the test error of our algorithm is at most 0.11 along all parameter choices while MNL test error is 0.168. Please see table 1 in the appendix."}]

Author rebuttal:

Meta-review: This study examines top-$k$ Mallows models for preference modeling and presents algorithmic contributions related to generating samples, determining choice probabilities, and learning model parameters. It includes a thorough analysis of the runtime complexity of these algorithms, supported by experimental results. Overall, the paper has received five positive reviews, with an average score reflecting a strong likelihood of acceptance. Therefore, I recommend it for acceptance.

Additionally, the authors have effectively addressed concerns about the clarity and significance of the study during the rebuttal phase. I suggest incorporating these improvements into the revised version of the paper.
Decision: Accept (spotlight)