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

CardsList
  1. Can LLMs Rank? A Tale of Triads and Triage

    Jun 29, 2026Gaurab Pokharel, Shafkat Farabi, Patrick J. Fowler +1Pairwise ComparisonSocial Choice Theory

  2. Learning Preference from Observed Rankings

    Feb 18, 2026Yu-Chang Chen, Chen Chian Fuh, Shang En TsaiPreference ModelingUser Preference Modeling