cs.DSNov 7, 2026

Close and Sort: Exact Maximum-Likelihood Aggregation of Cyclic Rank-Two Preferences

Authors: Kehan Liu, Zhaoyun Chen, Xianquan Yan

Organizations: Department of Physics, National University of Singapore, Singapore · Department of Computer Science, National University of Singapore, Singapore

Abstract

Pairwise probabilities arise in rank aggregation, recommendation, and human or LLM evaluation, yet converting them into a maximum-likelihood list is a weighted Kemeny problem and is NP-hard in general. Known exact algorithms for rank-two tournaments use only comparison signs and do not optimize this likelihood. We show that the weighted problem is exactly solvable when the skew-symmetric log-odds matrix Wij=log⁡(pij/pji)W_{ij}=\log(p_{ij}/p_{ji}) has rank two, including when the induced preferences contain cycles. Writing Wij=det⁡(hi,hj)W_{ij}=\det(h_i,h_j) and adding the closing vector h0=−∑ihih_0=-\sum_i h_i turns the objective into twice the signed area of a closed polygon. This geometry yields CloseSort, which polar-sorts the n+1n+1 edge vectors, cuts after h0h_0, and returns a global maximum-likelihood order in O(nlog⁡n)O(n\log n) time from the factors. The same geometry identifies the runner-up and gives a stability certificate beyond exact rank two. When the smallest determinant δδ of two consecutive edges in the closed angular cycle is positive, it is exactly the best-to-runner-up log-likelihood gap. For W=W0+EW=W_0+E, the CloseSort order of W0W_0 has regret at most ∑i<j∣Eij∣\sum_{i<j}|E_{ij}| on WW and remains optimal whenever this sum is below δδ, a worst-case tight threshold. In 5,120 determinant-logit simulations, increasing the observations per pair from 4 to 64 raises the fraction on which rank-two projection outperforms the empirical plug-in optimum from 68.6% to 85.7%. On 3,600 Arena-Hard LLM-judge profiles drawn from 63 systems and ten judges, the leading rank-two component captures 89.2% of the log-odds energy. On profiles containing a directed majority triangle, CloseSort reduces normalized regret by 44% relative to Borda and improves the mean normalized objective over each of eight baselines. With factors supplied, it is 8,407 times faster than exact dynamic programming on 18-item rankings.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Jun 29, 2026

Can LLMs Rank? A Tale of Triads and Triage

From housing allocation for households experiencing homelessness to triage in emergency departments, LLMs are increasingly being considered as judges of consequential decisions that require ranking people for scarce resources. Ranking large groups simultaneously is cognitively demanding and error-prone. A natural solution, drawing on decades of social choice theory, elicits pairwise comparisons and aggregates them into a total order. However, a fundamental question remains when LLMs serve as the pairwise judge: how can a practitioner tell, before committing to a ranking, whether the LLM's judgments are sufficiently consistent to trust the result? We discuss two different ways of identifying consistency. A classical diagnostic, the coefficient of consistency ζζ, originally developed to measure judge reliability by counting circular triads in tournament graphs, provides a cheap, model-free measure of intra-run consistency. Various standard measures of distance between rankings, for example Kendall's ττ, can measure inter-run variability. We show, in both theory and practice, that these measures are independently valuable, and advocate for using both to assess reliability of rankings. We demonstrate the practical importance of our results across two high-stakes prioritization tasks: homelessness service allocation and emergency department triage. Three different leading LLMs have considerably different performance profiles across these two axes of consistency. We provide guidelines for how practitioners could think about measuring and assessing consistency before committing to a model for ranking or prioritization.
Oct 7, 2026

How Many Repeated Pairwise Comparisons Are Needed for Ranking under Heterogeneity?

We study ranking models by population-average utility from pairwise comparisons when preferences vary across users and tasks. Prior work shows that a single comparison per user can be insufficient to identify the alternative with the highest average utility, even with arbitrarily many users (Golz et al., 2025). We investigate how many repeated comparisons within each user-task context are necessary and sufficient for ranking recovery. Under a heterogeneous Bradley-Terry model with fixed inverse temperature, we start with a naive MLE-based algorithm that requires Ω(1/Δ2)Ω(1/Δ^2) repeated comparisons per context to ensure ranking recovery. We then present two MLE-based variants and a randomized Russian Roulette-style algorithm that recover the ranking using O(log⁡(1/Δ))O(\log(1/Δ)) repeated comparisons per context, and we prove that this logarithmic dependence is optimal. Despite this worst-case requirement, our Russian Roulette algorithm uses only O(1)O(1) comparisons per context in expectation. Synthetic experiments and semi-synthetic experiments based on Arena data compare the four algorithms in settings with varying levels of preference heterogeneity and under varying context distributions.
Feb 18, 2026

Learning Preference from Observed Rankings

Estimating consumer preferences is central to many problems in economics and marketing. This paper develops a flexible framework for learning individual preferences from partial ranking information by interpreting observed rankings as collections of pairwise comparisons with logistic choice probabilities. We model latent utility as the sum of interpretable product attributes, item fixed effects, and a low-rank user-item factor structure, enabling both interpretability and information sharing across consumers and items. We further correct for selection in which comparisons are observed: a comparison is recorded only if both items enter the consumer's consideration set, inducing exposure bias toward frequently encountered items. We model pair observability as the product of item-level observability propensities and estimate these propensities with a logistic model for the marginal probability that an item is observable. Preference parameters are then estimated by maximizing an inverse-probability-weighted (IPW), ridge-regularized log-likelihood that reweights observed comparisons toward a target comparison population. To scale computation, we propose a stochastic gradient descent (SGD) algorithm based on inverse-probability resampling, which draws comparisons in proportion to their IPW weights. In an application to transaction data from an online wine retailer, the method improves out-of-sample recommendation performance relative to a popularity-based benchmark, with particularly strong gains in predicting purchases of previously unconsumed products.