Learning and Decision Making with Partial Preferences

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2120 papers142 conceptsfrozen 2026-10-04

Most classical models of social choice and machine learning assume that agents can provide a total order of alternatives—a complete, transitive ranking where every item is compared to every other item. However, in real-world scenarios ranging from large-scale elections to recommendation engines, this assumption collapses. Voters may only know their top three candidates, consumers may only choose one product out of a subset, and some outcomes may be fundamentally incomparable.

Research in this area focuses on bridging the gap between the mathematical convenience of total orders and the sparse, "messy" reality of partial preferences.

The Computational Challenge of Uncertainty

When preferences are incomplete, we can no longer ask "Who won the election?" Instead, we must ask two different questions: Who could win, and who must win?

Lirong Xia and Vincent Conitzer established a foundational framework for this in Determining Possible and Necessary Winners under Common Voting Rules Given Partial Orders. They defined the Possible Winner (a candidate who wins under at least one completion of the partial orders) and the Necessary Winner (a candidate who wins under all possible completions).

The intuition here is that partial information creates a "version space" of possible elections. While determining these winners is often NP-hard, Nadja Betzler and colleagues showed in A Multivariate Complexity Analysis of Determining Possible Winners Given Incomplete Votes that the problem becomes tractable if the number of candidates is small or the amount of "missingness" is limited.

Statistical Inference from Sparse Rankings

If we treat a partial ranking as a noisy observation of an underlying "true" total order, how do we recover that truth? Traditional models like Plackett-Luce or Mallows are difficult to scale because the space of permutations grows factorially ($n!$).

To solve this, Jonathan Huang and Carlos Guestrin introduced the concept of riffled independence in Riffled Independence for Efficient Inference with Partial Rankings. They observed that many partial rankings (like top-$k$ lists) allow the ranking space to be factorized into independent "shuffles," turning an exponential inference problem into a linear one.

Another powerful mechanism is rank-breaking. In Computing Parametric Ranking Models via Rank-Breaking, David C. Parkes and Lirong Xia demonstrated that a full or partial ranking can be decomposed into a set of pairwise comparisons. By applying the Generalized Method of Moments to these "broken" pairs, researchers can estimate complex model parameters with massive computational speedups without losing statistical consistency.

Structural Constraints and Fairness

In resource allocation, partial preferences can break standard fairness guarantees. Haibin Wang and Lirong Xia explored this in Multi-Type Resource Allocation with Partial Preferences. They found that while a "perfect" mechanism for arbitrary partial orders is impossible, we can restore fairness and efficiency by assuming preferences follow a structure like CP-nets (Conditional Preference networks).

Similarly, in voting theory, the concept of single-peakedness—the idea that candidates can be arranged along a single axis (like left-to-right politics)—is a powerful tool for avoiding paradoxes. Martin Lackner showed in Incomplete Preferences in Single-Peaked Electorates that even when ballots are incomplete, we can still efficiently detect this structure, provided we prevent "u-valleys" where a voter prefers two extremes over a middle option.

Incompleteness vs. Incomparability

A critical conceptual distinction in this field is between missing information and inherent incomparability.

As Maria Silvia Pini and Francesca Rossi 0001 argue in Incompleteness and Incomparability in Preference Aggregation, treating these the same leads to a loss of nuance.

  • Incompleteness is a state of ignorance: the agent has a preference, but we don't know it yet.
  • Incomparability is a state of the world: two items (like "health" and "wealth") may simply not be rankable against each other on a single scale.

Recognizing this distinction allows for more robust decision-making. For instance, in Nash Equilibrium in Games on Graphs with Incomplete Preferences, Abhishek N. Kulkarni and colleagues use this to characterize equilibria in games where players encounter outcomes that are fundamentally non-ranked, leading to new solution concepts like "non-dominated almost-sure winning."

Papers in this version

Showing 60 of 120 papers.

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 1, frozen text):

@misc{lacuna_learning_and_decision_making_with_partia_5d2805a8_v1,
  title = {Learning and Decision Making with Partial Preferences},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/learning-and-decision-making-with-partial-preferences/rdr_5d2805a8a0bb41c38177f01b8d0fbc06/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}