Lagrangian Inference for Ranking Problems

Yue Liu, Ethan X. Fang, Junwei Lu

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)202-223
Number of pages22
JournalOperations Research
Volume71
Issue number1
DOIs
StatePublished - Jan 1 2023

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Lagrangian Inference for Ranking Problems'. Together they form a unique fingerprint.

Cite this