Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors discuss distance-based ranking model for identifying population's preferences and their ranked choice behavior. This is useful for many applications such as new product introduction, crowdsourcing, etc. They introduce to a new type of distance based (Mallows-type) ranking model, which uses Reverse Major Index (RMJ) as the underlying distance function. They discuss several theoretical properties of this model and show that RMJ based ranking distribution aggregates into (ranked) choice probabilities with simple closed-form expression. In particular, for k > 1, the characterization of choice probabilities, efficient sampling of a top-k list,  and learning of parameters are novel aspects of the paper.
strengths_and_weaknesses: Strengths:

Introduction of a novel ranking model with certain desired properties
Theoretical and empirical justification of the desired properties
While the presentation may have some issues, but I liked the paper described its results intuitively

Weaknesses:
Presentation: A lot of things are imprecise and not clear in the paper, including introduction
Rigorousness:  Certain mathematical statements are not quantified properly
questions: Overall, the paper has novel aspects. I specially liked Lemma 1 and Lemma 3. However, there a few questions I would like authors to comment on:

Presentation:
1. A lot of things in the introduction are not clear. For example, it is difficult to make sense of the first paragraph on page 2, unless the mallow-type models are not described. 
2. Line 28 — what do the authors mean by the most representative distance?
3. What is PTAS in line 77 (it is mentioned in line 227)? Also in line 311, what is MNL? The authors should judicially use acronyms.
4. Use of Mallows-type ranking models and Mallows model for Mallows model with KD distance function is confusing. 
5. Line 151 - I do not understand how the authors came to the conclusion that “Therefore, both can be used as “kernels" to smooth out the distribution over rankings.”
6. Theorem 1: Is there a way you can specify that it corresponds to RMJ model. The current form doesn’t tell us that this is for RMJ. 

Mathematical Rigorousness:
1. Theorem 2 is not precise. It would be better to add sample complexity numbers. Specifically, quantifying what one means by consistent and infinite samples. I am further confused by the use of the word consistent in Theorem 3. Are the solutions from Mallows smoothing not equivalent? If they are, then the heuristic may not allow to converge to a single entity, but the heuristic may still be consistent when it is converging to equally good set of entities. It would be better to precisely mention (in quantifiable terms) the meaning of these words. 

Others:
1. I see that RMJ has some links with measures like NDCG. Also, there can be other variants of RMJ which look at specific portions, or precisely, specific pairwise comparisons of the ranking. For example, pAUC [Narasimhan et al.], pap@k [Hiranandani et al.]. Would authors like to comment on that? 
2. Line 147 — Can the authors also mention the use of major index in combinatorics for completeness?

Narasimhan, Harikrishna, and Shivani Agarwal. "A structural SVM based approach for optimizing partial AUC." In International Conference on Machine Learning, pp. 516-524. PMLR, 2013.
Hiranandani, Gaurush, Warut Vijitbenjaronk, Sanmi Koyejo, and Prateek Jain. "Optimization and Analysis of the pAp@ k Metric for Recommender Systems." In International Conference on Machine Learning, pp. 4260-4270. PMLR, 2020.
limitations: yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposed a Mallows-type (probabilistic) model for ranking data. Based on the new model, several theorems/lemmas are proved to  show different properties of the new model. Using the properties, the authors proposed a learning algorithm for the new model, and experimentally showed that the new model has better accuracy than the widely-used Plackett-Luce model and Mallows model. 
strengths_and_weaknesses: Strengths:

1. The presentation is very clear! It's easy for me to find the main contribution of this highly theoretical paper

2. The theorems look sound to me

3. The idea is simple. It looks similar to the intuition behind DCG (or NDCG).

Weakness:

1.  I think the model is not novel because it can be seen as a weighted version of Mallow's model with Cayley distance (Irurozki, Ekhine, Borja Calvo, and Jose A. Lozano. "Sampling and learning Mallows and Generalized Mallows models under the Cayley distance." Methodology and Computing in Applied Probability 20.1 (2018): 1-35.). If my understanding is correct, the baseline should also be changed to the Mallow's with Cayley distance. Please correct me if the proposed measure is totally different from Cayley distance. PS: My current (overall) evaluation is based on the assumption that the proposed measure is similar to Cayley distance. 

2. I would  like to see more discussions about the time complexity of the new algorithm. I think it would be a big improvement if the authors can provide the analysis about the overall time-complexity of this algorithm in Section 3.1. Or, alternatively, it would also be great if the authors can show a comparison of Mallows and OAM in terms of the running time.  
questions: As mentioned in the weakness part, can the authors provides more discussions about the time-complexity?

Also, Please correct me if my understanding of the distance measure is incorrect.

Why is linear weight used in the distance measure? Why not use other weights like log-based weighting in DCG?
limitations: I haven't found any negative social impact in this paper
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors study Mallows-type models in the context of top-$k$ ranking.
They propose a new distance function called the reverse major index known from combinatorics,
with which the computation of choice probabilities and the sampling of rankings can be done efficiently.
Parameter inference reduces to the feedback arc set problem, which is hard but admits a polynomial-time approximation scheme.
The authors show that their maximum likelihood estimator is consistent, while this does not hold for the Mallows smoothing heuristic from the literature.
They derive closed-form equations for the computation of the choice probabilities of their model.

To validate the model, experiments on the Sushi datasets are performed. In the case of top-1 choice, the approach shows favorable
performance when compared to Mallows smoothing and the multinomial logit model.
strengths_and_weaknesses: # Originality
The authors propose a novel combination of the Mallows model with a new distance function, the *reverse major index*.
The distance function only considers neighboring ranks and the absolute position in the ranking, which makes it easier to handle than Kendall’s distance function. 
Subsequently, this allows the authors to simplify computation of several downstream tasks like sampling and inference, and allows them to show consistency of their model.

Immediate related work is adequately cited, and the authors are referencing some of the choice modeling literature.
Since the setting considered in the paper is dealing with a feedback model where users are ranking a given set of items, I would also recommend specifically citing the recent work done in the setting of subset choice:

- Benson, Austin R., Ravi Kumar, and Andrew Tomkins. “A Discrete Choice Model for Subset Selection.” In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, 37–45. WSDM ’18. New York, NY, USA: Association for Computing Machinery, 2018. https://doi.org/10.1145/3159652.3159702.
- Pfannschmidt, Karlson, Pritha Gupta, Björn Haddenhorst, and Eyke Hüllermeier. “Learning Context-Dependent Choice Functions.” International Journal of Approximate Reasoning 140 (January 1, 2022): 116–55. https://doi.org/10/gn9kh3.

# Quality

## Theoretical analysis
The authors prove several theoretical results related to the computation of probabilities, sampling and inference.
In addition, they show that the maximum likelihood estimator of their RMJ model is consistent, while Mallows smoothing fails in this respect.
Notation is clearly introduced and used consistently. The proofs of the claims are provided in the supplemental material. The proofs themselves are written clearly, such that they were straightforward to follow.

In the proof of Lemma 4, the proof of the identifiability is very short and could benefit from slightly more intermediate steps.
In line 560, you refer to a source [20], but in the paper the references only go up to [19]. It is therefore not clear where these conditions come from.

## Empirical analysis
While the theoretical analysis is sound and thorough, the numerical experiments are more limited in scope.
The authors only consider the Sushi dataset, which is unique in that it is one of the rare datasets where users provide rankings for the chosen items. Since the authors then consider top-$1$ choice, it would be possible to consider more real-world data (see below), and more baselines of the choice modelling literature. As is, it is difficult to relate the results to the results of the existing literature.
The most interesting experiments (2 and 3) could be expanded by comparing the results to simple baselines (see Questions section) or adapting existing ranking/choice approaches to this setting.

Examples for real-world datasets:

- The YOUCHOOSE dataset of the RECSYS 2015 challenge: https://web.archive.org/web/20210120062757/https://2015.recsyschallenge.com/challenge.html
- The Expedia hotel recommendation dataset: https://www.kaggle.com/competitions/expedia-hotel-recommendations/data
- The LETOR datasets: https://www.microsoft.com/en-us/research/project/letor-learning-rank-information-retrieval/

# Clarity
The paper is written in a clear language and structured logically. Titles and paragraphs are used in such a way that it is easy to follow the key ideas. The source code and data of the experiments is provided with a small readme file, which improves the reproducibility of the results (disclaimer: I did not execute the attached code).

In the experimental section, since the generation of some of the datasets has been randomized, I am missing a description of whether random seeds were fixed beforehand and to which value. Looking at the attached code, this appears not to be the case, but it should be mentioned.
# Significance
The model proposed in the paper improves on the standard Mallows model, by making it more efficient to learn and use. The authors also demonstrate that the approach scales to moderately sized data (i.e., choices from sets of 100).
Whether others will use the approach will depend on the predictive performance achieved on real-world data, when compared to other approaches.
I think that the idea is interesting as is and could lead to other advances in the subsequent literature.

# Minor remarks

- Line 1: Preference learning is a much more general field in machine learning and not only encompasses top-k choice/ranking.
- L. 42: "A representative work is by [4]" -> "A representative work is by Antoine et al. [4]"
- L. 320: "traing" -> "training"
- L. 599: "we will show that even [when] all display sets"
questions: - In line 330f. you write that your method has "supreme performance compared to MS and MNL across the settings".
  Looking at Figure 1, the prediction power of OAM and MNL on all sets are actually close, with MNL beating OAM for a few cluster configurations.
  Since there are no error bars/confidence intervals, it is unclear as to how significant this outperformance really is.
  Can you clarify
      (1) why it would not be possible to repeatedly shuffle the data and repeat the splitting to obtain multiple performance values, such that error bars can be computed?
      (2) why "MNL is vulnerable to [...] overfitting" is not applicable to OAM as well, since the prediction power of OAM appears to decrease similarly for more clusters.
- Could you elaborate a bit what the goal of Experiment 2 was? What ranking do other top-k ranking approaches produce on this task? Which ranking do you get if you simply count the occurences of each sushi in the top-k list?
- Similarly, the goal of Experiment 3 was also not explained. One can deduce that you are trying to gauge how well the method can scale to large choice sets. Are there other approaches you can compare to which will help contextualize your obtained running times?
limitations: The authors write about the potential limitations of their model at the end of Section 3. What I am missing, are the limitations of their numerical experiments. The authors could for example write about the choice of dataset(s), baselines, number of repetitions etc., which in addition to more motivation would help the reader contextualize the results.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper discusses a new ranking model called Reverse Major Index, which is a friend of the classical Mallows ranking model. Various properties of the model including the MLE are discussed, and connection to integer programming is discussed.
strengths_and_weaknesses: The paper is well written and scientifically correct. The model discussed in the paper are novel up to my knowledge.
However, the model seems to me close to the Mallows, and the analysis seems to be similar. The authors should emphasize more on why the benefit of this ranking model.
questions: The paper is well written and I don’t have question.
limitations: NA
review_title: null

Meta-review: metareview: This paper makes a contribution to probabilistic models for ranking data.  The authors propose a new distribution similar to the  Mallows model but with the so-called reverse major index instead of Kendall as distance function. They address the problem of ML estimation for ranking and choice and show formal consistency properties of the estimate. Simulation studies are also included. The paper has been well-received by all authors. Although a few critical comments have been raised in the original reviews, these could be dispelled in the rebuttal phase. 

That said, a critical discussion came up in the final phase of decision making (regrettably too late to enquire the authors on this point).  Here, it was noticed that the new distance function proposed by the authors seems to have rather doubtful properties. In particular, neither symmetry nor the triangle inequality hold. For example The distance between (1,2,...,n-1,n) and (2,3,,...,n,1) is 1, but the distance between  (2,3,...,n,1) and (1,2,...,n) is n-1. Somewhat counterintuitive behaviour of the distance can also be observed in other cases. For example, swapping the last two items has the same effect as moving the top-item to the bottom: d (1, 2, ..., n, n-1) = d( 2, 3, ..., n, 1) = 1. Or, swapping the second and third item leads to a much higher distance than moving the top-item to the bottom: d(2, 3, ..., n, 1) = 1 < d(1, 3, 2, 4, ..., n) = n-2. Maybe such properties could be explained or defended, but they should at least be addressed in the paper. Comparing Kendall and the new distance, the authors write: "It is difficult to tell which kernel is “better" from an axiomatic approach as both distance functions satisfy the basic axioms for ranking distances". This is at least highly misleading, to put it mildly. Note that the axiomatic approach to ranking distances goes back to Kemeny, who required quite a number of properties and showed that the Kendall distance is the UNIQUE distance satisfying all properties. So comparing Kendall with a distance that violates almost all of these properties, it should be easy to say which one is better from an axiomatic perspective ...
confidence: Certain
Decision: Accept