Lagrangian Inference for Ranking Problems

Yue Liu (), Ethan X. Fang () and Junwei Lu ()
Additional contact information
Yue Liu: Department of Statistics, Harvard University, Boston, Massachusetts 02138
Ethan X. Fang: Department of Biostatistics & Bioinformatics, Duke University, Durham, North Carolina 27705
Junwei Lu: Department of Biostatistics, Harvard T.H. Chan School of Public Health, Boston, Massachusetts 02130

Operations Research, 2023, vol. 71, issue 1, 202-223

Abstract: We propose a novel combinatorial inference framework to conduct general uncertainty quantification in ranking problems. We consider the widely adopted Bradley-Terry-Luce (BTL) model, where each item is assigned a positive preference score that determines the Bernoulli distributions of pairwise comparisons’ outcomes. Our proposed method aims to infer general ranking properties of the BTL model. The general ranking properties include the “local” properties such as if an item is preferred over another and the “global” properties such as if an item is among the top K -ranked items. We further generalize our inferential framework to multiple testing problems where we control the false discovery rate (FDR) and apply the method to infer the top- K ranked items. We also derive the information-theoretic lower bound to justify the minimax optimality of the proposed method. We conduct extensive numerical studies using both synthetic and real data sets to back up our theory.

Keywords: Machine Learning and Data Science; combinatorial inference; ranking; pairwise comparisons; Bradley-Terry-Luce model; minimax lower bound (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2313 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:71:y:2023:i:1:p:202-223

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().