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
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) has rank two, including when the induced preferences contain cycles. Writing Wij=det(hi,hj) and adding the closing vector h0=−∑ihi turns the objective into twice the signed area of a closed polygon. This geometry yields CloseSort, which polar-sorts the n+1 edge vectors, cuts after h0, and returns a global maximum-likelihood order in O(nlogn) 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+E, the CloseSort order of W0 has regret at most ∑i<j∣Eij∣ on W 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
Method
Cycles
Exact MLE
Complexity
BT sort
×
✓
O(nlogn)
Rank-two MFAST
✓
×
O(n2)
CloseSort
✓
✓
O(nlogn)
General Kemeny (unrestricted)
✓
✓
NP-hard
Table 1. Comparison of exact-ranking methods for pairwise preferences under rank-two structure, alongside unrestricted general Kemeny. BT sort and CloseSort start from scores or factors; rank-two MFAST starts from tournament signs.
Figure 1. The augmented edge vectors sum to zero. (a) An arbitrary order traces a self-intersecting polygon with small signed area. (b) Angular sorting produces a weakly convex, maximum-area polygon; removing the closing edge h0 (dashed) yields the item ranking. The objective equals twice the signed area. Two-dimensional comparison factors are closed into a polygon and arranged by polar angle to maximize its signed area.
n
4
6
8
10
16
32
Suboptimal (%)
14.7
22.9
28.6
35.5
46.0
63.6
Table 2. Frequency with which the sign-optimal order is suboptimal for the weighted objective, over 2,000 random rank-two instances per size.
Figure 2. Fraction of trials in which the rank-two CloseSort order remains globally optimal under random or targeted residuals. The targeted construction attains the theorem’s threshold. Recovery curves for CloseSort under random perturbations and a targeted worst-case perturbation for several problem sizes.
Mean population regret
m
E2 (%)
CloseSort
Plug-in
Borda
Copeland
Win vs. plug-in (%)
4
47.6
11.509
13.993
20.812
21.003
68.6
16
68.1
3.021
5.847
17.506
18.467
84.7
64
87.7
.748
1.891
15.121
16.476
85.7
Table 3. Finite-sample study over 5,120 latent determinant-logit profiles ( n=14 ) with m observations per pair. E2 : log-odds energy captured by rank two. Plug-in: exact optimum of the empirical log-odds. Win vs. plug-in is the percentage of profiles on which CloseSort has lower population regret.
Baseline
All
Empirical W
Cyclic
Acyclic
Full-data baselines; evaluated on W
Bradley–Terry
.01959
.03307
.01243
Borda
.02803
.04328
.01993
Copeland
−.00102
.01567
−.00989
Rank Centrality
.02310
.03660
.01593
Table 4. Mean per-profile normalized objective gain of CloseSort over each baseline. CloseSort uses the factors of W2 throughout; block headings specify the baseline input and evaluation objective. Cycle status is determined by the directed majority graph of the empirical matrix W (1,249 cyclic and 2,351 acyclic of 3,600 profiles). Positive values favor CloseSort .
Figure 3. Single-thread ranking-stage runtime from supplied two-dimensional factors. Each point is the median over 25 exact Gaussian rank-two instances after taking the median of five repeats within each instance. Log-scale ranking-stage runtime curves for exact dynamic programming and CloseSort, aggregated over repeated measurements.
Table 5. Ability-ordered JuStRank cohorts. Ranks are determined on the construction split. Each cohort contributes 400 evaluation profiles from 40 question blocks and ten judges; the final column is the fraction that are empirically cyclic.
Rank aggregation combines ranked lists or pairwise preferences into a consensus ordering for tasks such as search, recommendation, and model evaluation.
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.
Gaurab Pokharel, Shafkat Farabi, Patrick J. Fowler +1
Virginia Tech Alexandria, VA · Washington University in St. Louis St. Louis, MO
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) 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/Δ)) 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) 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.
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.