Minimal Contraction of Preference Relations

Denis Mindolin, Jan ChomickiAAAI 2008

Introduction

In preference-based systems—such as a car-buying application where a user might prefer "newer" or "cheaper" vehicles—preferences are typically modeled as Strict Partial Orders (SPOs). These relations must be transitive (if $A \succ B$ and $B \succ C$, then $A \succ C$) and irreflexive (no item is preferred over itself). While significant research has focused on the incremental addition of preferences, this paper addresses the inverse problem: preference contraction. When a user decides to retract a specific preference, the system must ensure the remaining set of preferences remains a "rational" SPO, which often necessitates the removal of additional, implicitly related preferences.

The Challenge of Preference Contraction

The primary difficulty in contracting a preference relation lies in maintaining transitivity. If a user removes a preference that served as a "bridge" in a transitive chain, the remaining edges might still imply the existence of that preference, or conversely, the removal might leave "orphaned" transitive edges that violate the desired minimal change principle. To keep the system rational, one must often discard more information than the user explicitly requested.

A preference graph illustrating the transitivity constraints between nodes u, x, y, and v.

As shown in the figure above, the relationships between nodes $u, x, y,$ and $v$ are interconnected. Removing a single edge in such a structure requires a principled approach to determine which other edges must be discarded to satisfy the SPO properties while minimizing information loss. The authors seek to find the minimal set of removals required to satisfy the user's request while preserving the SPO structure.

Algorithmic Framework

The authors introduce two core algorithms to handle different contraction scenarios:

  1. minContr (Minimal Contraction): This algorithm takes a preference relation and a "base contractor" (the set of preferences to be removed). It employs a "layered" approach, partitioning the preference graph into layers based on path lengths. By removing edges in a specific sequence, it guarantees a minimal full contractor that preserves the SPO structure.
  2. minContrProt (Preference-Protecting Contraction): Users often wish to discard some preferences while explicitly protecting others. This algorithm identifies "sacrificial" preferences that must be removed to prevent protected preferences from violating transitivity when other parts of the graph are contracted.
Illustration of the contraction process: (a) the original preference relation, (b) the relation after initial removal of the base contractor, and (c) the final minimally contracted strict partial order.

Key Insights and Theoretical Results

The paper provides several critical insights into the nature of preference contraction:

  • Non-Uniqueness of Minimality: There is often no single "correct" way to contract a relation; multiple valid minimal contractions may exist for a given request. The paper demonstrates that the choice of contraction can significantly impact the resulting set of preferred items.
  • The k-layer Constraint: The proposed algorithms are proven correct for "$k$-layer" relations—graphs where the length of preference chains is bounded. This covers the vast majority of practical database applications, although it highlights a theoretical limit for infinite, complex chains.
  • Computational Complexity: For finite relations, the implementation is efficient, requiring $O(|CON|^2 \cdot |\succ| \cdot \log|\succ|)$ time, where $CON$ is the set of contracted preferences. This makes it computationally feasible for standard database applications.
  • Winnowing Efficiency: The authors demonstrate that the set of "best" items under a contracted preference is a superset of the best items under the original preference. This allows database engines to optimize queries by filtering previous results rather than re-executing the entire winnow operation from scratch.

Conclusion

This work establishes a formal foundation for the retraction of preferences in rational systems. By providing efficient algorithms for minimal and protected contraction, the authors enable more dynamic and responsive preference-based applications. Future work includes extending these principles to other models like Conditional Preference networks (CP-nets) and exploring more complex constraint types, such as dependencies between protected preferences.

Summary updated

BibTeX
@inproceedings{mindolin2008minimal,
  author = {Denis Mindolin and Jan Chomicki},
  title = {{Minimal Contraction of Preference Relations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}

Loading related content...

Figure