Learning and Aggregating Incomplete Preference Rankings

231 concepts161 papers1 proposal

When we think of ranking data, we often imagine a complete list: a voter ordering every candidate on a ballot, or a user sorting every movie in a catalog from best to worst. Mathematically, this corresponds to a full permutation—a single point in the symmetric group $S_n$.

However, real-world preference data rarely looks like this. Voters experience cognitive fatigue and leave ballots top-truncated, ranking only their top few choices, as discussed by Nina Narodytska et al. in The Computational Impact of Partial Votes on Strategic Voting. Consumers frequently select only their single favorite item from a small subset of options, a scenario studied by Zhipeng Lou et al. in Ranking Inferences Based on the Top Choice of Multiway Comparisons.

Forcing these partial observations into classical ranking frameworks creates severe issues. If we treat unranked items as tied for last, we misrepresent users who simply did not know those items existed, a distinction highlighted by Philip L. H. Yu in Weighted Distance-Based Models for Ranking Data Using the R Package rankdist. Conversely, if we try to marginalize over all possible full permutations that could complete a partial ranking, the computational complexity explodes exponentially.

To solve this, modern preference modeling treats incompleteness not as "missing data to be guessed," but as structured geometric, algebraic, and decision-theoretic constraints.

The Geometry of Incompleteness: Cosets and Lattices

How do we represent a partial ranking mathematically without losing information or inventing preferences?

An elegant solution is to model partial rankings as cosets within a ranking lattice. As shown by Guy Lebanon et al. in Non-parametric Modeling of Partially Ranked Data, instead of viewing an incomplete ranking as a fragmented vector, we can treat it as the set of all full permutations that satisfy the observed constraints.

For example, if a user states they prefer item $A$ over item $B$, this partial ranking corresponds to a coset containing every full permutation where $A$ precedes $B$. By mapping these cosets onto a permutation graph, we can apply non-parametric estimators (such as Parzen windows). This allows us to aggregate highly diverse types of partial data—such as top-$k$ lists mixed with arbitrary pairwise comparisons—into a single, unified probability distribution without relying on restrictive parametric assumptions.

Breaking and Decomposing Sparse Rankings

Even with a solid geometric representation, computing parameters for global ranking models can be computationally daunting when data is sparse. Two primary mechanisms make this tractable: rank-breaking and topological graph decomposition.

Rank-Breaking

Instead of computing a complex likelihood over a massive combinatorial space of permutations, rank-breaking decomposes an incomplete ranking into a collection of independent pairwise comparisons. As explored by David C. Parkes et al. in Computing Parametric Ranking Models via Rank-Breaking, breaking full or partial rankings into pairs allows researchers to apply the Generalized Method of Moments (GMM). This achieves massive computational speedups while maintaining statistical consistency, bypassing the need to evaluate full permutations.

Topological Decomposition

When preference data is sparse and imbalanced, we can view comparisons as a directed graph where nodes represent items and edges represent observed preferences. In Statistical ranking and combinatorial Hodge theory, Xiaoye Jiang et al. demonstrated that combinatorial Hodge theory (HodgeRank) can decompose this preference flow into two orthogonal components:

  1. A global gradient flow, which yields a clean, linear consensus ranking.
  2. A cyclic curl flow, which captures inconsistent loops (e.g., $A \succ B \succ C \succ A$).

This projection transforms an NP-hard rank aggregation problem into an efficient linear least-squares problem, providing a built-in "certificate of reliability" based on how much of the data falls into the gradient versus the loops. For massive item universes where observations are highly fragmented, Eric Sibony et al. in MRA-based Statistical Learning from Incomplete Rankings extended this philosophy using Multi-Resolution Analysis (MRA), using wavelet-like components to smoothly infer global preferences from local, sparse subsets.

[Partial Rankings] ───> [Pairwise Graph Flow] ───> Hodge Decomposition ───> ┌─ Gradient Flow ──> Global Order
                                                                           └─ Curl Flow ─────> Cyclic Noise

Decision-Making Under Uncertainty: Possible vs. Necessary Winners

In collective decision-making and social choice, incomplete data introduces a fundamental ambiguity: if voters only provide partial orders, who actually wins the election?

To resolve this without forcing arbitrary completions, Lirong Xia et al. in Determining Possible and Necessary Winners under Common Voting Rules Given Partial Orders formalized a crucial distinction:

  • Possible Winner: A candidate who wins under at least one valid full completion of the partial orders.
  • Necessary Winner: A candidate who wins under all possible valid completions.

The authors mapped out the computational complexity of these problems, revealing a sharp dichotomy. Verifying a Necessary Winner is often computationally easy (polynomial time) because it reduces to checking worst-case bounds. However, identifying a Possible Winner is frequently NP-complete for common voting rules, as it requires searching the combinatorial space of potential ballot completions. This framework allows multiagent systems to determine exactly when a winner is guaranteed, or when more preference elicitation is required.

When votes are entirely absent or truncated, tracking these boundaries becomes vital. For instance, Qishen Han et al. in Determining Winners in Elections with Absent Votes proved that while tracking winners under top-truncated rankings is generally hard for rules like Single Transferable Vote (STV), the problem becomes tractable when the number of missing votes or candidates remains small.

Rather than forcing a definitive but fragile total order from incomplete data, some frameworks embrace this ambiguity directly. In Selective Preference Aggregation, Shreyas Kadekodi et al. proposed a framework that produces tiered rankings. By only comparing items when a significant majority of partial preferences agree, the system "agrees to disagree" on sparse or highly contested items, ensuring that the final collective choice remains stable and transparent.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 165 papers
  2. Version 1 · 2026-10-04 · 120 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_partial_preference_modeling_5d2805a8,
  title = {partial preference modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/partial-preference-modeling/rdr_5d2805a8a0bb41c38177f01b8d0fbc06},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_partial_preference_modeling_5d2805a8_v2,
  title = {partial preference modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/partial-preference-modeling/rdr_5d2805a8a0bb41c38177f01b8d0fbc06/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake