Modeling Cyclic Preferences

25 concepts20 papers1 proposal

When we think about preferences, we naturally tend to think in hierarchies. If you are buying a car, you might decide on the manufacturer first, which then dictates your choice of model, which finally determines the color. In artificial intelligence, this hierarchical structure is elegantly captured by Conditional Preference Networks (CP-nets). CP-nets assume that our preferences form a Directed Acyclic Graph (DAG), allowing algorithms to sweep through the network from top to bottom to find an optimal outcome.

But human preferences are rarely so well-behaved. Consider a couple planning a dinner: the first person prefers steak if they drink red wine, but the second person only wants red wine if they are having pasta. This creates a circular dependency: Food $\rightarrow$ Wine $\rightarrow$ Food.

When preferences loop back on themselves, traditional acyclic frameworks break down. For years, cyclic dependencies were treated as logical inconsistencies or errors to be engineered away. However, a growing body of research recognizes that cycles are a natural, inevitable feature of complex decision-making. Modeling cyclic preferences requires shifting away from rigid hierarchical graphs toward flexible, constraint-driven optimization.

The Complexity Barrier of Loops

Why did early preference frameworks ban cycles in the first place? The answer lies in how algorithms determine whether one outcome is better than another—a task known as dominance testing.

In an acyclic CP-net, proving that outcome $A$ dominates outcome $B$ is straightforward. Because there is a clear top-down order of importance, you can compare the attributes sequentially. But when a network contains cycles, this sequential chain vanishes. You can easily find yourself trapped in an infinite regression where outcome $A$ is preferred to $B$, $B$ is preferred to $C$, and $C$ is preferred back to $A$.

Because of these interdependent loops, reasoning about cyclic networks becomes computationally daunting. As demonstrated by Goldsmith et al. (2005), determining dominance and consistency in a cyclic CP-net is PSPACE-complete, placing it in the same complexity class as robot motion planning or playing a perfect game of chess.

Despite this complexity, forcing acyclicity comes at a steep price. As noted by Xia et al. (2008), acyclic structures can only represent an exponentially small fraction of all possible preference orderings. By restricting models to DAGs, AI systems suffer from a severe expressivity gap, failing to capture realistic human behaviors and multi-agent dynamics (Gimenez et al. (2024); Allen (2014)).

From Graph Traversal to Constraint Satisfaction

To handle cycles without falling into infinite loops, researchers had to change how preference networks are evaluated. The key insight is to stop treating a preference network as a graph to be traversed, and instead treat it as a set of constraints to be satisfied.

1. Relaxing the Semantics

Traditional semantics are unforgiving: if a cycle causes a contradiction, the entire model is deemed invalid. To circumvent this, Brafman et al. (2003) introduced "weak" semantics for cyclic networks. Instead of demanding a flawless, strict ordering across the entire loop, weak semantics look for stable assignments where no single variable wants to change given the state of its neighbors. By mapping these conditions to logic programming and SAT solvers, the authors showed that systems can compute optimal outcomes even within cyclic structures without requiring the user to rewrite their preferences.

2. Global Optimality Constraints

If we cannot rely on a step-by-step hierarchical search to find the best outcome, how do we locate it? The solution is to convert local preference rules into global "optimality constraints."

Prestwich et al. (2005) demonstrated this by encoding CP-nets directly into Constraint Satisfaction Problems (CSPs). Instead of performing expensive pairwise dominance tests across a cyclic graph, the framework translates the preference rules into hard constraints that define what an undominated outcome looks like. A standard constraint solver can then search the entire space globally to find Pareto-optimal solutions. This approach completely bypasses the need for an acyclic graph, allowing cyclic networks to be optimized just as efficiently as their acyclic counterparts.

Acyclic Approach (Sequential):
[Attribute 1] ---> [Attribute 2] ---> [Attribute 3] ---> Optimal Outcome

Cyclic Approach (Constraint-Based):
  [Attribute 1] <---> [Attribute 2]
         ^                 ^
         |                 |
         v                 v
  [Attribute 3] <---> [Global Constraints] ---> Solver ---> Optimal Outcome

Aggregating Cyclic Preferences in Groups

The challenge of cyclic preferences multiplies when moving from a single user to a group. Even if every individual agent has a perfectly acyclic, hierarchical preference structure, the collective group preference often becomes cyclic when aggregated—a phenomenon closely related to Condorcet's Voting Paradox.

If a group is voting on multiple related issues (such as funding a new park and raising property taxes), sequential voting methods fail if the voters disagree on which issue should be decided first (Xia et al. (2009)). The order of the votes can be easily manipulated, leading to highly inefficient outcomes.

To resolve this, the authors of Xia et al. (2008) developed a framework called H-composition. Instead of forcing a sequential voting order or ignoring the dependencies between attributes, H-composition allows the group to vote on complex, multi-attribute domains with cyclic dependencies. It works by decomposing the cyclic preference structure into strongly connected components, optimizing within those components, and then composing the pieces back together. This allows voting mechanisms to remain computationally manageable while respecting the interdependent loops inherent in collective choice.

Key Foundational Work

A New Look at the Semantics and Optimization Methods of CP-Networks (2003) — contributed 1 concept elements to this direction.
Answer Set Optimization (2003) — contributed 1 concept elements to this direction.
Reasoning about soft constraints and conditional preferences: complexity results and approximation techniques (2003) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

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

This exact version (version 2, frozen text):

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

These directions overlap with this one through shared papers.

See something wrong? Report a mistake