Representing and Reasoning with Qualitative Preferences for Compositional Systems

Ganesh Ram Santhanam, Samik Basu, Vasant G. Honavar

Introduction

In many artificial intelligence applications, the goal is not to select a single optimal object but to find a composition of objects—a "bundle"—that collectively satisfies a functional objective. Examples include assembling a graduate program of study, configuring a web service pipeline, or planning a complex travel itinerary. This paper presents a formal framework for reasoning with qualitative user preferences to identify the most preferred compositions without requiring the user to provide precise numeric scores.

The Composition Problem

Traditional decision theory often relies on quantitative utility functions. However, humans find it difficult to assign exact numeric values (e.g., "I like this instructor with a score of 0.8"). Instead, qualitative preferences—such as "I prefer Professor Smith over Professor Jones"—are more natural and easier to elicit.

The challenge lies in aggregating these individual preferences across a collection of items. A bundle might be judged by its "weakest link"; for instance, a student might reject an otherwise perfect course schedule if it contains one highly disliked class.

Table of available courses with their respective areas, instructors, and credit values, illustrating the components of a composition problem.

Methodology: Dominance and Algorithms

The authors propose a multi-layered approach to determine the "best" compositions:

  1. Aggregation Functions: These functions define how to evaluate a composition's value. While "Summation" is used for additive attributes like credits, the authors introduce the "Worst Frontier" function to identify the set of least-preferred elements within a bundle, effectively characterizing a bundle by its weakest components.
  2. The Dominance Relation ($\succ_d$): This mathematical relation determines if one composition dominates another. It relies on the concept of a "witness" attribute: bundle A dominates bundle B if there exists an attribute where A is strictly better, and for all attributes of equal or greater importance, A is at least as good as B.
  3. Preference Modeling: Individual preferences are modeled as partial orders, allowing for incomparable items and hierarchical structures.
Qualitative preference hierarchies for research areas (a) and instructors (b), represented as partial orders.

The framework includes several algorithms to find optimal solutions. While A1 (ComposeAndFilter) is an exhaustive approach, the more sophisticated A4 (InterleaveCompose) prunes the search space during bundle construction. By "interleaving" preference reasoning with composition, it avoids building partial bundles that are already guaranteed to be dominated.

Theoretical Insights and Results

A key theoretical finding is the necessity of interval orders. For the dominance relation to remain transitive (ensuring that if A > B and B > C, then A > C), the user's relative importance of attributes must follow an interval order structure. Random partial orders can lead to preference "loops," making it impossible to identify a clear winner.

The framework was evaluated using simulated problem instances based on Uniform Recursive Trees, modeling search spaces with up to 200 components. The results demonstrated that the interleaving approach (A4) significantly outperforms exhaustive search, particularly when preferences are strict. The authors also provided mathematical proofs for the soundness and completeness of their algorithms.

Conclusion and Future Work

This research provides a robust foundation for automated reasoning in compositional systems using qualitative feedback. While the current model handles static preferences well, future work aims to incorporate conditional preferences (e.g., "I prefer X only if Y is present") and dynamic aggregation functions where component interactions might change the overall value of the bundle.

Summary updated

Abstract

Many applications, e.g., Web service composition, complex system design, team formation, etc., rely on methods for identifying collections of objects or entities satisfying some functional requirement. Among the collections that satisfy the functional requirement, it is often necessary to identify one or more collections that are optimal with respect to user preferences over a set of attributes that describe the non-functional properties of the collection. We develop a formalism that lets users express the relative importance among attributes and qualitative preferences over the valuations of each attribute. We define a dominance relation that allows us to compare collections of objects in terms of preferences over attributes of the objects that make up the collection. We establish some key properties of the dominance relation. In particular, we show that the dominance relation is a strict partial order when the intra-attribute preference relations are strict partial orders and the relative importance preference relation is an interval order. We provide algorithms that use this dominance relation to identify the set of most preferred collections. We show that under certain conditions, the algorithms are guaranteed to return only (sound), all (complete), or at least one (weakly complete) of the most preferred collections. We present results of simulation experiments comparing the proposed algorithms with respect to (a) the quality of solutions (number of most preferred solutions) produced by the algorithms, and (b) their performance and efficiency. We also explore some interesting conjectures suggested by the results of our experiments that relate the properties of the user preferences, the dominance relation, and the algorithms.
BibTeX
@misc{santhanam2011representing,
  author = {Ganesh Ram Santhanam and Samik Basu and Vasant G. Honavar},
  title = {{Representing and Reasoning with Qualitative Preferences for Compositional Systems}},
  year = {2011},
  eprint = {1401.3899},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1401.3899},
}
Figure