nucleation

LIT-1439: Statistical ranking and combinatorial Hodge theory

2 min read

Properties5
StatusActive — read 2026-10-23 (NOTE-1099): in full, from arXiv 0811.1067v2 (42 pp.). HodgeRank. Pairwise comparisons, aggregated into a weighted edge flow on the graph of alternatives, decompose orthogonally into a gradient flow, the l2-best global ranking found by weighted least squares, and a divergence-free residual. The residual splits into curl (local, triangular inconsistency) and harmonic (global inconsistency) parts. Binary win/loss data enter as averaged signs, and on complete balanced binary data the ranking is Borda's. The decomposition is cardinal: curl-freeness is stronger than transitivity. It is the tool for reading the record's conflict record.
Tagsmathematical-statistics, mathematics, network-science, anthology-candidate
Cited as “grounds” byCLAIM-538 — On a finite graph of contexts whose overlaps carry preferred real offsets a and tolerances δ_e ≥ 0, an assignment within every tolerance, |Dx − a| ≤ δ, exists exactly when no cycle's holonomy exceeds the sum of its tolerances; with every δ_e > 0 the least uniform enlargement of the tolerances that admits one is the largest ratio, over simple cycles, of holonomy to summed tolerance, so the obstruction is certified by a cycle; the feasible allocations of tolerance depend on the offsets only through their class in H¹, so local adjustment can move a mismatch among the overlaps of a cycle and never remove it; and an evaluation that omits one overlap of every witnessing cycle reports a compatibility that does not hold
Cited as “paper” byNOTE-1099 — Statistical ranking and combinatorial Hodge theory
Cited as “source” byTHEORY-894 — A flow of pairwise comparisons on a graph splits orthogonally and uniquely into a gradient part, the l2-best global ranking, and a cyclic part, which splits into curl (local) and harmonic (global) inconsistency; a finite game's flow of unilateral payoff differences has no curl part, so every finite game is uniquely a potential game plus a harmonic game plus a nonstrategic remainder, and potential games are exactly those with no harmonic part; the decomposition is cardinal

Graph View

Xiaoye Jiang, Lek-Heng Lim, Yuan Yao and Yinyu Ye (2011), Mathematical Programming 127(1):203–244 — DOI-10.1007/s10107-010-0419-x, ARXIV-0811.1067

Key takeaways

  • Comparisons as a flow. Voters’ pairwise comparisons are aggregated into a skew-symmetric Ȳ on the graph whose edges are the compared pairs, weighted by w_ij, the number of comparisons (eqs. 4–8). Four aggregations are offered (§2.2.1). One of them is binary: Ȳ_ij is the share preferring j minus the share preferring i, which “is invariant up to a monotone transformation” (p. 10).
  • HodgeRank (eq. 7, Theorem 5.1, pp. 21–22). The global ranking is the weighted least-squares projection of Ȳ onto gradient flows, s* = −∆₀† div Ȳ. The residual is divergence-free. It splits into a curl part, which is “a local cyclic ranking accounting for local inconsistencies”, and a harmonic part, which is “a harmonic ranking accounting for global inconsistencies” (p. 22).
  • Local implies global when there are no holes (Theorem 5.2, p. 24). If the comparison graph’s 3-clique complex has β₁ = 0, “every locally consistent pairwise ranking is also globally consistent”. The harmonic part is always zero on a complete comparison graph.
  • Cardinal, not ordinal. Curl measures triangular inconsistency. It “extends the consistency index of Kendall and Smith [26], which counts the number of circular triads, from ordinal settings to cardinal settings” (p. 12). The impossibility theorems of social choice “are about intransitivity”, while their approach deals with inconsistency, “which is a cardinal condition” (p. 30).
  • Social choice. For complete, balanced, binary data the HodgeRank ranking is the Borda count (p. 31). Kemeny optimization is the ordinal counterpart, an l1 projection onto the transitive region, and it is NP-hard (Theorem 7.1, pp. 31–32).
  • Certificate. “the data may be ‘explained’ by a global ranking only when the cyclic component is small” (p. 30). The cyclicity ratio C_p = ‖R*‖²/‖Ȳ‖² measures it (p. 35).

Standing in the record

Filed on 2026-10-23 at the owner’s request. It is the measure the renamed term needs: QUESTION-268’s conflict record is a set of pairwise decisions, and this paper decomposes such a set. Read in NOTE-1099, whose bearing section sets out what the measure assumes. The decomposition theorem is THEORY-894, with Candogan et al. (LIT-1442).

Backlinks