Worst-case versus average-case design for estimation from partial pairwise comparisons
From MaRDI portal
Publication:2196209
Abstract: Pairwise comparison data arises in many domains, including tournament rankings, web search, and preference elicitation. Given noisy comparisons of a fixed subset of pairs of items, we study the problem of estimating the underlying comparison probabilities under the assumption of strong stochastic transitivity (SST). We also consider the noisy sorting subclass of the SST model. We show that when the assignment of items to the topology is arbitrary, these permutation-based models, unlike their parametric counterparts, do not admit consistent estimation for most comparison topologies used in practice. We then demonstrate that consistent estimation is possible when the assignment of items to the topology is randomized, thus establishing a dichotomy between worst-case and average-case designs. We propose two estimators in the average-case setting and analyze their risk, showing that it depends on the comparison topology only through the degree sequence of the topology. The rates achieved by these estimators are shown to be optimal for a large class of graphs. Our results are corroborated by simulations on multiple comparison topologies.
The authors study the problem of estimating the comparison probabilities from noisy pairwise comparisons under average-case and worst-case design assumptions. They also exhibite a dichotomy between both designs for permutation-based models, and they conjecture that a similar distinction may exist even for their parametric counterparts. Other relevant results about the problem of estimating the comparison probabilities from noisy pairwise comparisons are presented in the paper. In addition, the article ends with a discussion of open problems in this area of research.
Recommendations
- scientific article; zbMATH DE number 2172872
- Approximate and exact optimal designs for paired comparisons of partial profiles when there are two groups of factors
- On the choice of optimality criteria in comparing statistical designs
- Asymptotic relative efficiency of designs for factorial paired comparison experiments
- Comparing search and estimation performances of designs based on a compound criterion
- OPTIMAL DESIGNS FOR 2kPAIRED COMPARISON EXPERIMENTS
- Optimal designs for asymmetric linear paired comparisons with a profile strength constraint
- Optimal paired comparison designs for factorial and quadratic models
Cites work
- A remark on the existence of finite graphs
- Aggregation and Social Choice: A Mean Voter Theorem
- Binary choice probabilities: on the varieties of stochastic transitivity
- Competitive analysis of the top-K ranking problem
- Data-driven rank breaking for efficient rank aggregation
- Emergence of Scaling in Random Networks
- Estimation from pairwise comparisons: sharp minimax bounds with topology dependence
- Estimation in Tournaments and Graphs Under Monotonicity Constraints
- Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons
- High-dimensional statistics. A non-asymptotic viewpoint
- scientific article; zbMATH DE number 3152611 (Why is no real title available?)
- scientific article; zbMATH DE number 3584785 (Why is no real title available?)
- scientific article; zbMATH DE number 3253520 (Why is no real title available?)
- scientific article; zbMATH DE number 3049708 (Why is no real title available?)
- scientific article; zbMATH DE number 3073477 (Why is no real title available?)
- Learning from comparisons and choices
- Matrix estimation by universal singular value thresholding
- Minimax rates and efficient algorithms for noisy sorting
- Models for paired comparison data: a review with emphasis on dependent data
- Noisy sorting without resampling
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- Optimal rates of statistical seriation
- Probability models and statistical analyses for ranking data. Papers presented at the AMS-IMS-SIAM conference, Amherst, MA, USA, June 1990
- Rank Centrality: Ranking from Pairwise Comparisons
- Simple, Robust and Optimal Ranking from Pairwise Comparisons
- Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues
- The algebraic combinatorial approach for low-rank matrix completion
- Uncoupled isotonic regression via minimum Wasserstein deconvolution
Cited in
(10)- Towards optimal estimation of bivariate isotonic matrices with unknown permutations
- On the estimation of latent distances using graph distances
- Isotonic regression with unknown permutations: statistics, computation and adaptation
- Optimal full ranking from pairwise comparisons
- Estimation of Monge matrices
- Spectral method and regularized MLE are both optimal for top-\(K\) ranking
- Minimax rates and efficient algorithms for noisy sorting
- Optimal permutation estimation in crowdsourcing problems
- Optimal level set estimation for non-parametric tournament and crowdsourcing problems
- List's worst-average-case or WAC ratio
This page was built for publication: Worst-case versus average-case design for estimation from partial pairwise comparisons
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196209)
