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.
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
- 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?)
- 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
- 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
(9)- Isotonic regression with unknown permutations: statistics, computation and adaptation
- On the estimation of latent distances using graph distances
- Optimal full ranking from pairwise comparisons
- Minimax rates and efficient algorithms for noisy sorting
- Estimation of Monge matrices
- Spectral method and regularized MLE are both optimal for top-\(K\) ranking
- Optimal permutation estimation in crowdsourcing problems
- List's worst-average-case or WAC ratio
- Towards optimal estimation of bivariate isotonic matrices with unknown permutations
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)
