Research map / Learning theory and algorithms / Prediction and decision losses
Generalized Top-k Mallows Model for Ranked Choices
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Generalizes the top-k Mallows model with per-item weights (TopKGMM) and provides a profile-based sampler (PRIM), a dynamic program for choice probabilities (DyPChiP), and an active learner for the center from choice data (BuCChoi), with experiments on the Sushi dataset versus MNL.
Problem
Top-k Mallows models lack RIM-style sampling and tractable choice probabilities, and learning their center from partial choice data has lacked finite-sample guarantees; choice modeling needs a model where users rank only a few preferred items.
Approach
Extends the top-k Mallows model (Chierichetti et al.) with per-item weights and conditions on a "profile" (the set of center-top-k items appearing in the sampled list) so that sampling reduces to a RIM-like insertion procedure, and choice probabilities are computed by dynamic programming over profiles.
Key results
- PRIM reduces sampling runtime from O(k^2 4^k + k^2 log n) to O(k 2^k + k^2 log n) relative to prior DP sampler.
- DyPChiP computes choice probabilities in O(2^gamma k^3 |A|^2 + 2^gamma k^2 |A| n) time, gamma = min{k, n-k}.
- On the Sushi dataset, the top-k Mallows model achieves significantly higher out-of-sample choice-prediction accuracy than MNL.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PRIM instead of the prior dynamic programming sampling approach | TopKGMM sampling · Top-$k$ sampling | runtime: O(k^24^k+k^2\log n) -> O(k2^k+k^2\log n) | Helped |
| Use TopKGMM rather than MNL for choice-probability prediction | Sushi Preference Data Set · Sushi Preference Data Set (test set) | predictive accuracy | Helped |
Limitations
- Choice probability and sampling complexity remain exponential in min(k, n-k).
- Learning guarantees require beta >= log(3)/w_min and assume the no-purchase option is not in the center top-k.
- Experiments run on a single laptop with a single real dataset.
Experimental setup
Datasets: Sushi Preference Data Set
Benchmarks: Sushi Preference Data Set
Metrics: choice probability prediction error on test set empirical vs predicted choice frequency runtime
Baselines: Multinomial Logit (MNL)
Builds on: Mallows model TopKMM (Chierichetti et al.) Repeated Insertion Method Generalized Mallows Model Multinomial Logit
Closest papers by meaning
- On A Mallows-type Model For (Ranked) Choices (NeurIPS 2022 · similarity 0.89)
- Properties of the Mallows Model Depending on the Number of Alternatives: A Warning for an Experimentalist (ICML 2023 · similarity 0.88)
- Optimal Sample Complexity of M-wise Data for Top-K Ranking (NeurIPS 2017 · similarity 0.87)
- Gaussian Process Bandits for Top-k Recommendations (NeurIPS 2024 · similarity 0.85)
- Online Learning of Delayed Choices (NeurIPS 2024 · similarity 0.84)
- Logic-Logit: A Logic-Based Approach to Choice Modeling (ICLR 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.