Traditional decision theory, machine learning, and economics share a convenient assumption: all outcomes can be mapped to a single, linear scale of real numbers. If you are choosing between two options, $A$ and $B$, you either prefer $A$, prefer $B$, or are perfectly indifferent between them ($A = B$). This is a total order.
While mathematically elegant, total orders fail to capture how humans actually evaluate the world. Consider choosing between a fuel-efficient compact car and a spacious SUV. One excels at economy; the other excels at cargo capacity. They are not equal, yet neither is universally better. They are incomparable.
Forcing incomparable options onto a single numerical scale introduces artificial distinctions and decision deadlocks. To solve this, a growing body of research replaces total orders with partially ordered sets (posets) and distributive lattices. By allowing options to be explicitly incomparable, these frameworks build more realistic models for AI planning, game theory, matching markets, and reinforcement learning.
Incomparability is Not Indifference
The core mathematical shift from a total order to a partial order hinges on how we define a lack of preference. In a standard utility model, if you do not prefer $A$ over $B$ and do not prefer $B$ over $A$, you must be indifferent to them. Indifference is transitive: if you like $A$ and $B$ equally, and you like $B$ and $C$ equally, you must like $A$ and $C$ equally.
In contrast, a partial order introduces a fourth state: incomparability. Two options are incomparable when they excel in entirely different, non-overlapping dimensions. As Sheila A. McIlraith et al. note in the context of preference-based planning, qualitative preferences naturally produce partial orders because humans resist making arbitrary trade-offs between complex, multi-criteria outcomes.
To formalize this mathematically, Adriana Zapico established axiomatic foundations for qualitative decision-making by mapping preferences and uncertainties to distributive lattices rather than linear numerical scales. This lattice structure provides a rigorous way to aggregate qualitative information without forcing artificial total rankings.
In logical reasoning, this flexibility is vital for handling conflicts and messy data. For example, Gerhard Brewka reimagined default reasoning by organizing logical premises into a partial order based on reliability, allowing AI systems to resolve contradictions locally without needing a global hierarchy. Similarly, Guido Boella et al. designed a non-monotonic logic that leverages partial pre-orders to represent genuine conflicts or missing information as incomparable states, ensuring that a reasoning system remains functional even when it lacks definitive preference data.
Learning Choice Functions via Pareto Frontiers
If outcomes cannot be ranked on a single line, how can a machine learning model learn to choose between them? Instead of predicting a single "best" item, algorithms must learn choice functions—models that output a subset of preferred, non-dominated items.
A powerful way to visualize this is through multi-dimensional geometric embeddings. Eyke Hüllermeier et al. introduced Pareto-Embeddings, a method that maps objects into a multi-dimensional latent space. Instead of looking for the highest score, the model identifies the Pareto frontier: the set of points that are not strictly outperformed by any other point across all dimensions. This allows the system to naturally select diverse subsets of items that excel in different latent criteria without relying on arbitrary numerical thresholds.
Utility Score (Total Order) Pareto Frontier (Partial Order)
A B C D Dimension 2 ▲
◄─────┼───┼───┼───┼─────► │ A B
0.2 0.5 0.7 0.9 │ \ /
│ C
│ D
└───────────────► Dimension 1
(Forces a single winner) (A and B are incomparable but dominate C)
To handle uncertainty in these multi-criteria spaces, Alessio Benavoli et al. developed ChoiceGP, a Bayesian framework that uses Gaussian Processes to model multiple latent utility functions simultaneously. By combining Gaussian Processes with Pareto optimality, the authors provide a robust mechanism for predicting preferred subsets when options are fundamentally incomparable.
Overhauling Search and Matching Algorithms
Most classical computer science algorithms are built on the assumption of a total order. When preferences are partially ordered, these algorithms break down and must be fundamentally redesigned.
1. Adversarial Search
Standard alpha-beta pruning works because game states have strict numerical values (e.g., $+10$ is always better than $+5$). If a branch yields a value worse than what a player is already guaranteed, that branch can be safely pruned.
When game states have partially ordered values—such as in games with hidden information or multi-criteria goals—standard pruning logic fails because a state might be incomparable to the current guaranteed value. Junkang Li et al. solved this by generalizing alpha-beta search to work over distributive lattices, rewriting the pruning conditions so that branches are only discarded when they are definitively dominated, preserving correctness while maintaining efficiency.
2. Matching Markets
In economic matching markets (like the classic Shapley-Scarf housing market), agents trade items based on their preferences. Standard models assume strict linear rankings, but real-world agents often encounter items they cannot compare.
Lydia Mirabel Mendoza-Cadena extended housing market theory to partial orders, providing the first structural characterization of the "strong core"—the set of allocations where no group of agents has an incentive to break away and trade among themselves. The author introduced a polynomial-time algorithm to find these allocations, proving that market stability can be maintained even when the transitivity of indifference is lost.
While incorporating partial orders increases mathematical complexity, it uncovers deeper structural truths. Ildikó Schlotter et al. demonstrated that although finding specific allocations in the market's core becomes NP-complete under partial orders, the core still fundamentally "respects improvement" (i.e., upgrading your initial item guarantees an outcome at least as good as before). To bypass the computational hardness of these non-linear structures, Telikepalli Kavitha et al. utilized linear programming duality to find stable and popular allocations without forcing agents to construct artificial linear lists.
Sequential Decisions and Reinforcement Learning
The shift toward partial orders is also transforming how autonomous agents learn to act in complex environments.
In Reinforcement Learning from Human Feedback (RLHF), systems typically force human evaluators to choose between two agent trajectories. However, if the trajectories are completely different, forcing a choice introduces noise into the reward function. Simone Drago et al. formalized human feedback as a partial preorder to explicitly accommodate incomparable trajectory pairs. The authors proved that while finding a minimal utility representation for these partial preferences is NP-hard, policy optimality can still be defined directly from the partial order and efficiently approximated with standard rewards.
Forced Choice (Total Order) Partial Preorder
Trajectory 1 vs Trajectory 2 Trajectory 1 ─── Incomparable ─── Trajectory 2
│ │ │
▼ ▼ ▼
[Must pick one, [Acknowledge distinct [Learn robust
introduces noise] strengths/weaknesses] policy directly]
For multi-agent systems, Alessandro Zanardi et al. introduced Posetal Games. Instead of collapsing a robot's competing objectives into a single scalar cost function (e.g., balancing safety, speed, and passenger comfort via arbitrary weights), agents prioritize objectives using posets. This framework guarantees the existence of stable, interpretable Nash Equilibria, allowing autonomous vehicles to navigate trade-offs using pure Pareto logic.
Finally, when an agent faces an adversarial environment with incomplete human preferences, traditional optimization fails. Abhishek N. Kulkarni et al. addressed this by introducing a solution concept called non-dominated almost-sure winning (ND-ASWin). By using a novel rank metric over incomplete preferences, their framework allows control strategies to be synthesized so that the agent's behavior is guaranteed to be non-dominated by any other achievable outcome, ensuring robust alignment with human intent.
Key Foundational Work
Axiomatic Foundations for Qualitative/Ordinal Decisions with Partial Preferences (1999) — contributed 2 concept elements to this direction.
Axiomatic Foundations for Qualitative/Ordinal Decisions with Partial Preferences (1999) — contributed 1 concept elements to this direction.
Preferred Subtheories: An Extended Logical Framework for Default Reasoning (1989) — contributed 1 concept elements to this direction.